Lesson 1

We have not yet defined when we say that one set has a cardinality greater than or not greater than another (although we have allowed ourselves to say a couple of times that there are more real numbers than integers). Below, we will do this formally. (And in parentheses, we note that we are learning to compare cardinalities, but consciously, until now, we have not defined what cardinality is and have not symbolized it in any way.)

We will say that the cardinality of \(A\) is not greater than the cardinality of \(B\), and write \(|A| \le |B|\), if \(A\) is in bijection with some subset of \(B\) (in other words, if there exists an injection from \(A\) to \(B\)). It turns out that the following two natural properties (for any two sets \(A,B\)) hold true (but are not at all obvious!):

1. Antisymmetry: if \(|A| \le |B|\) and \(|B| \le |A|\), then \(|A| = |B|\). This is Cantor–Schröder–Bernstein theorem, which we will prove below.
2. Linearity: either \(|A| \le |B|\) or \(|B| \le |A|\). This is a consequence of Zermelo's theorem, which asserts that any set can be well-ordered. We will go over the formulation of this theorem later, but we will leave it without proof.