Cardinal (initial ordinal) and cardinality

Write $X\approx Y$, and say $X$ and $Y$ are equinumerous, when there is a bijection $X\to Y$.

An ordinal $\kappa$ (Ordinal (von Neumann)) is a cardinal, equivalently an initial ordinal, when

$\text{no }\alpha \in \kappa \text{ satisfies }\alpha \approx \kappa ,$

that is, $\kappa$ is not equinumerous with any strictly smaller ordinal.

Cardinality, under the Axiom of Choice. Assume the Axiom of Choice (The Axiom of Choice) and let $X$ be a set. Then $X$ carries a well-order (The well-ordering theorem), which has an order type $\alpha$ (Every well-order has a unique order type) and in particular $\alpha \approx X$. Now ${\alpha }^{+}=\alpha \cup \{\alpha \}$ is an ordinal (Basic closure properties of ordinals, claim (c)) whose elements are ordinals (claim (a)) and which contains $\alpha$, so $C=\{\xi \in {\alpha }^{+}:\xi \approx X\}$ is a nonempty set of ordinals and has an $\in$-least element $\kappa$ (Trichotomy and well-ordering of the ordinals). This $\kappa$ is the cardinality of $X$, written $\mathrm{\mid }X\mathrm{\mid }$; it is a cardinal, because $\beta \in \kappa$ with $\beta \approx \kappa \approx X$ would lie in ${\alpha }^{+}$ and contradict the minimality of $\kappa$.

Well-definedness: $\kappa$ does not depend on the well-order or on $\alpha$. The recipe above instantiates a well-order of $X$ and an order type $\alpha$ for it, and $X$ will in general carry many well-orders with many different order types, so the value $\kappa$ has to be shown independent of both. It is, because $\kappa$ is in fact the least ordinal equinumerous with $X$ outright, a description in which neither the well-order nor $\alpha$ appears. Let $\beta$ be any ordinal with $\beta \approx X$. By trichotomy for ordinals (Trichotomy and well-ordering of the ordinals) exactly one of $\beta \in {\alpha }^{+}$, $\beta ={\alpha }^{+}$, ${\alpha }^{+}\in \beta$ holds. In the first case $\beta \in C$, so $\kappa \subseteq \beta$ by minimality of $\kappa$. In the other two cases claim (f) of Basic closure properties of ordinals gives ${\alpha }^{+}\subseteq \beta$, and $\alpha \in {\alpha }^{+}$ because ${\alpha }^{+}=\alpha \cup \{\alpha \}$, so $\alpha \in \beta$ and hence $\alpha \subseteq \beta$ by claim (f) again; and $\alpha \in C$, so $\kappa \subseteq \alpha$ by minimality, whence $\kappa \subseteq \beta$. In every case $\kappa \subseteq \beta$, that is $\kappa \le \beta$. So $\kappa$ is the least element of the collection of all ordinals equinumerous with $X$, and any two runs of the recipe, from any two well-orders of $X$, return the same $\kappa$.

• What the well-definedness argument does and does not need. The obligation is that $\mathrm{\mid }X\mathrm{\mid }$ depend on $X$ alone, and it is discharged in the definition itself, from two lemmas that are genuine prerequisites of this item and therefore sit in deps rather than in justified_by: comparability and trichotomy of ordinals (Trichotomy and well-ordering of the ordinals) and the elementary closure facts (Basic closure properties of ordinals). Neither mentions cardinals, so neither points forward, and no separate discharging lemma is needed. The bound ${\alpha }^{+}$ is a device for turning "the least ordinal equinumerous with $X$" into a Separation instance over a set; the argument above is what shows that the device does not change the answer.

• The definition is choice-free; the cardinality assignment is not. Being a cardinal is a property of an ordinal and needs no axiom beyond ZF. Attaching a cardinality to an arbitrary set is a different matter: a set that carries no well-order is equinumerous with no ordinal at all, so $\mathrm{\mid }X\mathrm{\mid }$ simply does not exist for it. Without the Axiom of Choice there is no ordinal-valued notion of size for arbitrary sets, and what survives is Hartogs: an ordinal that does not inject into a given set: every set $A$ has a smallest ordinal $\mathrm{\aleph }(A)$ that does not inject into it.

• Most ordinals are not cardinals. The successor ${\omega }^{+}=\omega \cup \{\omega \}$ is equinumerous with $\omega \in {\omega }^{+}$, by the explicit bijection sending $\omega$ to $0$ and each natural number $n$ to $\sigma (n)$, which is a bijection because $\sigma$ is injective and its image is exactly the nonzero natural numbers. So ${\omega }^{+}$ is an ordinal and not a cardinal, and the same shift applies to the successor of any ordinal containing $\omega$. Cardinals are sparse among ordinals, which is precisely why the least one equinumerous with a given set is a useful representative.

• Which ordinals up to and including $\omega$ are cardinals. Every natural number is a cardinal, and so is $\omega$. Both facts are counting facts rather than order facts, and both come from the pigeonhole principle (The pigeonhole principle on $\mathbb{N}$), proved on the countability page. Every natural number is an ordinal, and so is $\omega$ ($\omega$ is the least limit ordinal, claim (ii)); and if $\alpha \in n$ with $n$ a natural number then $\alpha$ is itself a natural number, since $\mathbb{N}$ is a transitive set (On $\mathbb{N}$ the order is membership: $m<n⟺m\in n$), with $\alpha <n$ by claim (i) of $\omega$ is the least limit ordinal. So if some $\alpha \in n$ had $\alpha \approx n$, claim 3 of the pigeonhole principle would force $\alpha =n$ and hence $n\in n$, which claim (b) of Basic closure properties of ordinals forbids; therefore $n$ is a cardinal. And if some $\alpha \in \omega$ had $\alpha \approx \omega$, then $\alpha$ would be a natural number equinumerous with $\mathbb{N}=\omega$, which claim 4 of the pigeonhole principle forbids; therefore $\omega$ is a cardinal. Nothing else on this page depends on either fact, and the definition above is stated so that it does not.

• Notation. The infinite cardinals are traditionally written ${\mathrm{\aleph }}_0,{\mathrm{\aleph }}_1,\dots$, with ${\mathrm{\aleph }}_0=\omega$. That last equation can now be stated outright rather than quoted: it says $\omega$ is the least ordinal equinumerous with $\omega$, which is precisely the assertion that $\omega$ is a cardinal, established in the previous remark from claim 4 of The pigeonhole principle on $\mathbb{N}$. Nothing below rests on it. The notation $\mathrm{\aleph }(A)$ for the Hartogs number of $A$ (Hartogs: an ordinal that does not inject into a given set) comes from the same source and is deliberately close: under the Axiom of Choice $\mathrm{\aleph }(A)$ is the successor cardinal of $\mathrm{\mid }A\mathrm{\mid }$.

• Why initial ordinals rather than equivalence classes. For a nonempty set $X$, the class of all sets equinumerous with $X$ is a proper class. Indeed, fix $a\in X$. For each set $y\mathrm{\notin }X$, the set $(X\setminus \{a\})\cup \{y\}$ is equinumerous with $X$, by replacing $a$ with $y$ and fixing the other elements. If the equinumerosity class were a set $E$, its union would therefore contain every set outside $X$ and also every member of $X$, since $X\in E$. Thus $\bigcup E$ would contain every ordinal, contrary to Burali-Forti: there is no set of all ordinals. The empty set is the exception: its equinumerosity class is the set $\{\mathrm{\varnothing }\}$. Choosing the least ordinal in an equinumerosity class is von Neumann's fix, and it works exactly when the class contains an ordinal, which is exactly when the set can be well ordered.