Definition 4.7.2.1. Let $S$ be a set. We let $|S|$ denote the smallest ordinal $\alpha $ for which there exists a well-ordering of $S$ having order type $\alpha $. We will refer to $|S|$ as the cardinality of the set $S$. A cardinal is an ordinal $\kappa $ which has the form $|S|$, for some set $S$.
$\Newextarrow{\xhookrightarrow}{10,10}{0x21AA}$
4.7.2 Cardinals and Cardinality
Let $S$ and $T$ be sets. We say that $S$ and $T$ have the same cardinality if there exists a bijection $S \xrightarrow {\sim } T$. This is an equivalence relation on the collection of sets, whose equivalence classes are called cardinals. Following a standard convention in set theory, it will be convenient to view a cardinal as a special type of ordinal.
Remark 4.7.2.2. Let $S$ be a set, and let $A$ be the collection of all ordinals which arise as the order types of well-orderings on $S$. The collection $A$ is nonempty (Theorem 4.7.1.34), and therefore contains a smallest element (Corollary 4.7.1.24). It follows that the cardinality $|S|$ is well-defined.
Proposition 4.7.2.3. Let $S$ and $T$ be sets. Then $|S| \leq |T|$ if and only if there exists a monomorphism $f: S \hookrightarrow T$.
Proof. Choose well-orderings $(S, \leq _ S)$ and $(T, \leq _ T)$ having order types $|S|$ and $|T|$, respectively. If $|S| \leq |T|$, then there is an isomorphism of $(S, \leq _{S} )$ with an initial segment of $(T, \leq _{T} )$; this isomorphism in particular gives a monomorphism of sets $S \hookrightarrow T$. For the converse, suppose that there exists a monomorphism $f: S \hookrightarrow T$. Then there is a unique linear ordering $\leq '_{S}$ on the set $S$ for which $f$ defines a strictly increasing function $(S, \leq '_{S} ) \rightarrow (T, \leq _{T} )$. Then $\leq '_{S}$ is a well-ordering (Remark 4.7.1.5); let $\alpha $ denote its order type. We then have $|S| \leq \alpha \leq |T|$, where the second inequality follows from Remark 4.7.1.21. $\square$
Corollary 4.7.2.4. Let $S$ and $T$ be sets. Then $S$ and $T$ have the same cardinality if and only if there exists a bijection $S \xrightarrow {\sim } T$.
Proof. Choose well-orderings $(S, \leq _ S)$ and $(T, \leq _ T)$ having order types $|S|$ and $|T|$, respectively. If $|S| = |T|$, then there is an isomorphism of linearly ordered sets $(S, \leq _ S) \simeq (T, \leq _{T} )$, and therefore a bijection $S \xrightarrow {\sim } T$. The converse follows from Proposition 4.7.2.3. $\square$
Corollary 4.7.2.5. Let $(S, \leq )$ be a well-ordered set of order type $\alpha $. Then the cardinality $\kappa = |S|$ is the largest cardinal which satisfies $\kappa \leq \alpha $.
Proof. The inequality $\kappa \leq \alpha $ follows immediately from the definition of $|S|$. Let $\lambda $ be another cardinal satisfying $\lambda \leq \alpha $. Then $\lambda $ is the order type of an initial segment $S_0 \subseteq S$, so we have $\lambda = | S_0 | \leq | S | = \kappa $. $\square$
Remark 4.7.2.6. Let $\kappa $ be an ordinal. The following conditions are equivalent:
The ordinal $\kappa $ is a cardinal. That is, there exists a set $S$ such that $\kappa = |S|$.
For every well-ordered set $(S, \leq )$ of order type $\kappa $, we have $\kappa = |S|$.
The set of ordinals $\mathrm{Ord}_{< \kappa }$ has cardinality $\kappa $.
See Corollary 4.7.1.23.
Example 4.7.2.7 (Finite Cardinals). Let $n$ be a nonnegative integer. Then a set $S$ has cardinality $n$ (in the sense of Definition 4.7.2.1) if and only if it has exactly $n$ elements: that is, there exists a bijection $S \simeq \{ 0 < 1 < \cdots < n-1 \} $. In particular, $n$ is a cardinal. We will say that a cardinal $\kappa $ is finite if it arises in this way (that is, if it is the cardinality of a finite set); otherwise, we say that $\kappa $ is infinite.
Proposition 4.7.2.8 (Cantor's Diagonal Argument). Let $S$ be a set, and let $P(S)$ denote the collection of all subsets of $S$. Then $|S| < | P(S) |$.
Proof. The construction $s \mapsto \{ s\} $ determines an injection from $S$ to $P(S)$, which shows that $|S| \leq | P(S) |$. To show that the inequality is strict, it suffices to observe that no function $f: S \rightarrow P(S)$ can be surjective, since the set $T = \{ s \in S: s \notin f(s) \} $ is an element of $P(S)$ which does not belong to the image of $f$. $\square$
Remark 4.7.2.9. The collection of cardinals is well-ordered. That is, if $S$ is any nonempty collection of cardinals, then $S$ contains a smallest element (see Corollary 4.7.1.24).
Example 4.7.2.10 (The First Infinite Cardinal). We let $\aleph _0$ denote the smallest infinite cardinal. Alternatively, $\aleph _0$ can be defined as the ordinal $\omega $ of Example 4.7.1.10 (the order type of the linearly ordered set $\{ 0 < 1 < 2 < \cdots \} $). A set $S$ has cardinality $\aleph _0$ if and only if it is countably infinite.
Example 4.7.2.11 (Successor Cardinals). Let $\kappa $ be a cardinal. Proposition 4.7.2.8 implies that there exists another cardinal $\lambda $ such that $\kappa < \lambda $. By virtue of Remark 4.7.2.9, there is a smallest cardinal with this property. We denote this cardinal by $\kappa ^{+}$ and refer to it as the successor of $\kappa $.
Example 4.7.2.12 (The First Uncountable Cardinal). We say that a cardinal $\kappa $ is uncountable if it is strictly larger than $\aleph _0$. By virtue of Remark 4.7.2.9, there is a smallest uncountable cardinal, which we denote by $\aleph _{1}$. In other words, $\aleph _{1}$ is the successor cardinal $\aleph _0^{+}$.
Remark 4.7.2.13 (The Continuum Hypothesis). Let $\mathbf{R}$ be the set of real numbers. Then $| \mathbf{R} |$ is an uncountable cardinal (it is also the cardinality of the power set $P(\operatorname{\mathbf{Z}})$). The continuum hypothesis is the assertion that $| \mathbf{R} |$ coincides with the smallest uncountable cardinal $\aleph _1$. This was a central question in the early days of set theory (and first of Hilbert's celebrated list of problems for the mathematics of the 20th century). It is now known to be neither provable nor disprovable from the axioms of Zermelo-Fraenkel set theory (assuming that they are consistent), thanks to the work of Gödel ([MR0002514]) and Cohen ([MR157890], [MR159745]).
Proposition 4.7.2.14. Let $(T, \leq )$ be a linearly ordered set and let $\kappa = \mathrm{cf}(T)$ be its cofinality (Definition 4.7.1.28). Then $\kappa $ is a cardinal.
Proof. Choose a well-ordered set $(S, \leq )$ of order type $\kappa $ and a cofinal function $f: S \rightarrow T$. If $\kappa $ is not a cardinal, then we can choose another well-ordering $\leq '$ of $S$ having order type $\alpha < \kappa $. Applying Proposition 4.7.1.33, we obtain $\mathrm{cf}( T ) \leq \alpha < \kappa $, which is a contradiction. $\square$