Ordinals & Cardinals

Proof. Since $\alpha$ is transitive and $\beta \in \alpha$, we have $\beta \subseteq \alpha$. So $\in$ restricted to $\beta$ inherits irreflexivity, transitivity as a relation, trichotomy and the least-element property from $\in$ restricted to $\alpha$; a nonempty subset of $\beta$ is a nonempty subset of $\alpha$ and therefore has an $\in$ -least element. Hence $\beta$ is well-ordered by $\in$.

It remains to show $\beta$ is a transitive set. Let $x\in y\in \beta$. Since $\beta \subseteq \alpha$ we get $y\in \alpha$, and since $\alpha$ is transitive, $y\subseteq \alpha$, so $x\in \alpha$. Now $x$, $y$ and $\beta$ all lie in $\alpha$, where $\in$ is a transitive relation, and $x\in y\in \beta$ gives $x\in \beta$. Thus every element of $\beta$ is a subset of $\beta$, and $\beta$ is an ordinal.

Finally, $\beta \subseteq \alpha$ means every element of $\beta$ is an element of $\alpha$ lying below $\beta$, and conversely an element of $\alpha$ lying below $\beta$ is by definition a member of $\beta$. So $\beta$ is precisely the initial segment of $\alpha$ determined by $\beta$.∎

Proof. Since $\beta ⊊\alpha$, the set $\alpha \setminus \beta$ is nonempty, so it has an $\in$ -least element $\gamma$. We claim $\beta =\gamma$.

If $x\in \gamma$ then $x\in \alpha$ by transitivity of $\alpha$, and $x\notin \alpha \setminus \beta$ by minimality of $\gamma$, so $x\in \beta$. Hence $\gamma \subseteq \beta$.

Conversely let $x\in \beta$. Then $x,\gamma \in \alpha$, so trichotomy gives $x\in \gamma$, $x=\gamma$, or $\gamma \in x$. The second is impossible since $\gamma \notin \beta$. If $\gamma \in x$ then, $\beta$ being transitive and $x\in \beta$, we would get $\gamma \in \beta$, again impossible. So $x\in \gamma$, giving $\beta \subseteq \gamma$.

Therefore $\beta =\gamma \in \alpha$.∎

Proof. Suppose the set $S=\{a\in X:f(a)<a\}$ is nonempty and let $a$ be its least element. Then $f(a)<a$, and applying the order-preserving $f$ to this inequality gives $f(f(a))<f(a)$. So $f(a)\in S$ and $f(a)<a$, contradicting the minimality of $a$. Hence $S=\varnothing$ and $f(a)\ge a$ always.

If $g:X\to X_{<b}$ were an isomorphism onto a proper initial segment, then viewing $g$ as an order-preserving injection $X\to X$ gives $g(b)\ge b$, whereas $g(b)\in X_{<b}$ forces $g(b)<b$ — a contradiction.

For uniqueness, if $f,g:X\to Y$ are both isomorphisms then $g^{-1}\circ f:X\to X$ is an order-preserving bijection, so by the first part both it and its inverse move nothing downward, forcing $g^{-1}(f(a))=a$ for all $a$, i.e. $f=g$.∎

Proof. First, $\gamma =\alpha \cap \beta$ is a transitive set: if $x\in y\in \gamma$ then $y$ lies in both $\alpha$ and $\beta$, and transitivity of each gives $x\in \alpha$ and $x\in \beta$. Also $\gamma \subseteq \alpha$, so $\in$ well-orders $\gamma$; hence $\gamma$ is an ordinal.

By Ordinals are closed downward under subsets, either $\gamma =\alpha$ or $\gamma \in \alpha$, and likewise either $\gamma =\beta$ or $\gamma \in \beta$. If $\gamma \in \alpha$ and $\gamma \in \beta$ both held, then $\gamma \in \alpha \cap \beta =\gamma$, contradicting irreflexivity of $\in$ on the ordinal $\gamma \cup \{\gamma \}$ 's members — concretely, $\gamma \in \gamma$ is impossible because $\in$ is irreflexive on any ordinal containing $\gamma$. So at least one of $\gamma =\alpha$, $\gamma =\beta$ holds.

If $\gamma =\alpha =\beta$ we get $\alpha =\beta$. If $\gamma =\alpha \ne \beta$ then $\gamma \in \beta$, i.e. $\alpha \in \beta$. Symmetrically if $\gamma =\beta \ne \alpha$ then $\beta \in \alpha$. That is trichotomy; the three cases exclude one another because $\alpha \in \beta \in \alpha$ would give $\alpha \in \alpha$ by transitivity, again impossible.

For the last claim. If $\alpha \in \beta$ then $\alpha \subseteq \beta$ by transitivity of $\beta$, and $\alpha =\beta$ trivially gives $\alpha \subseteq \beta$. Conversely if $\alpha \subseteq \beta$ and $\alpha \ne \beta$, then Ordinals are closed downward under subsets gives $\alpha \in \beta$.∎

Proof. Pick any $\alpha \in A$. If $\alpha$ is already least we are done. Otherwise $\alpha \cap A$ is a nonempty subset of the ordinal $\alpha$, so it has an $\in$ -least element $\beta$. For any $\delta \in A$, trichotomy gives $\delta \in \beta$, $\delta =\beta$ or $\beta \in \delta$; the first would put $\delta \in \beta \in \alpha$, hence $\delta \in \alpha \cap A$ below $\beta$, contradicting minimality. So $\beta \le \delta$ for all $\delta \in A$, and $\beta$ is least. Linearity comes from Ordinals are linearly ordered by membership, so $<$ is a well-order on $A$.

For the supremum, put $\sigma =\bigcup A$. It is transitive: $x\in y\in \sigma$ means $y\in \alpha$ for some $\alpha \in A$, and transitivity of $\alpha$ gives $x\in \alpha \subseteq \sigma$. Its elements are ordinals by Elements of ordinals are ordinals, and a set of ordinals is linearly ordered and well-ordered by the previous paragraph, so $\sigma$ is an ordinal. Each $\alpha \in A$ satisfies $\alpha \subseteq \sigma$, so $\alpha \le \sigma$; and if $\tau \ge \alpha$ for all $\alpha \in A$ then $\alpha \subseteq \tau$ for all $\alpha$, so $\sigma \subseteq \tau$ and $\sigma \le \tau$.∎

Proof. Suppose toward a contradiction that $\Omega =\{\alpha :\alpha \text{ is an ordinal}\}$ is a set.

$\Omega$ is transitive: if $\beta \in \alpha \in \Omega$ then $\beta$ is an ordinal by Elements of ordinals are ordinals, so $\beta \in \Omega$.

$\Omega$ is well-ordered by $\in$: it is linearly ordered by Ordinals are linearly ordered by membership, and every nonempty subset has a least element by Every set of ordinals is well-ordered.

So $\Omega$ meets both clauses of the definition of an ordinal, and therefore $\Omega$ is itself an ordinal. But every ordinal is a member of $\Omega$, so $\Omega \in \Omega$ — and $\in$ is irreflexive on the ordinal $\Omega$, so $\Omega \notin \Omega$. This is a flat contradiction, and the only assumption made was that $\Omega$ is a set.∎

Proof. Uniqueness is immediate: if $\alpha \cong X\cong \beta$ then $\alpha \cong \beta$, and if $\alpha \ne \beta$ then by trichotomy one is an element, hence a proper initial segment, of the other, which Rigidity of well-orders forbids.

Existence (this half uses the replacement scheme, and nothing else beyond ZF). Call $a\in X$ good if the initial segment $X_{<a}$ is isomorphic to some ordinal; by uniqueness that ordinal is unique, call it $F(a)$. We show every $a$ is good by induction along the well-order: suppose every $b<a$ is good. Then $F$ is defined on $X_{<a}$, and by replacement $\{F(b):b<a\}$ is a set of ordinals; call it $S$. Each $F(b)$ is an initial segment of each $F(b^{\prime })$ for $b<b^{\prime }$, so $S$ is transitive and hence an ordinal $\alpha$, and $b\mapsto F(b)$ is an order-isomorphism $X_{<a}\to \alpha$. So $a$ is good with $F(a)=\alpha$. By transfinite induction on the well-order $X$ — which is legitimate here because it is ordinary induction along a well-order, proved in Transfinite induction on a well-ordered set below and independent of this theorem — every $a\in X$ is good.

Now apply replacement once more to the whole of $X$: $\{F(a):a\in X\}$ is a set of ordinals, transitive by the same argument, hence an ordinal $\alpha$, and $F:X\to \alpha$ is an order-isomorphism.∎

Proof. Transitivity: an element of $\alpha \cup \{\alpha \}$ is either an element of $\alpha$, hence a subset of $\alpha \subseteq \alpha +1$, or is $\alpha$ itself, which is a subset of $\alpha +1$. Well-ordering: $\alpha +1$ is a set of ordinals, so Every set of ordinals is well-ordered applies. Thus $\alpha +1$ is an ordinal, and $\alpha \in \alpha \cup \{\alpha \}$ gives $\alpha <\alpha +1$.

If $\alpha <\gamma <\alpha +1$ then $\gamma \in \alpha \cup \{\alpha \}$, so $\gamma \in \alpha$ or $\gamma =\alpha$; either way $\gamma \le \alpha$, contradicting $\alpha <\gamma$.∎

Proof. The three cases are mutually exclusive by definition, and exhaustive because "limit" is defined as the leftover case. For the criterion, $\bigcup \alpha =\sup \{\beta :\beta <\alpha \}$ by Every set of ordinals is well-ordered.

If $\alpha =\beta +1$ then $\beta <\alpha$ and every $\gamma <\alpha$ satisfies $\gamma \le \beta$, so the supremum is $\beta \ne \alpha$, and $(\bigcup \alpha )+1=\beta +1=\alpha$.

Conversely suppose $\sigma =\bigcup \alpha \ne \alpha$. Every $\gamma <\alpha$ has $\gamma \le \sigma$, and $\sigma \subseteq \alpha$ gives $\sigma \le \alpha$; with $\sigma \ne \alpha$ this forces $\sigma <\alpha$, so $\sigma$ is the largest element of $\alpha$ and $\alpha =\sigma \cup \{\sigma \}=\sigma +1$ is a successor. (If $\alpha =0$ then $\bigcup \alpha =\varnothing =\alpha$, so the criterion correctly excludes $0$.)∎

Proof. Every element of $\omega$ is a finite ordinal $n$, and $n+1$ is again finite, so $\omega$ has no largest element and $\bigcup \omega =\omega$; with $\omega \ne 0$, Classification of ordinals makes $\omega$ a limit. An ordinal $n<\omega$ is a finite ordinal, and each nonzero finite ordinal $n$ contains a largest element $n-1$, so $n=(n-1)+1$ is a successor.∎

Proof. Use the order-type definitions, where all three claims become statements about rearranging brackets in a concatenation.

For addition: both $(\alpha +\beta )+\gamma$ and $\alpha +(\beta +\gamma )$ are the order type of the disjoint union $\alpha \bigsqcup \beta \bigsqcup \gamma$ with the three blocks in that order and each block internally ordered as itself. The identity map between the two bracketings is a bijection, and it preserves order because in both readings a point of an earlier block precedes a point of a later block and points within a block compare as they did originally. By Representation of well-orders the two order types are the same ordinal.

For multiplication: $(\alpha \cdot \beta )\cdot \gamma$ is $\gamma$ copies of ($\beta$ copies of $\alpha$), and $\alpha \cdot (\beta \cdot \gamma )$ is ($\beta \cdot \gamma$ = $\gamma$ copies of $\beta$) copies of $\alpha$. Both are the lexicographic order on $\gamma \times \beta \times \alpha$, the leftmost coordinate most significant; associativity of the cartesian product gives the order-isomorphism.

For distributivity: $\alpha \cdot (\beta +\gamma )$ is $\beta +\gamma$ copies of $\alpha$, i.e. $\beta$ copies followed by $\gamma$ copies, which is exactly $\alpha \cdot \beta$ followed by $\alpha \cdot \gamma$.∎

Proof. $1+\omega =\omega$. The order type $1+\omega$ is one point followed by a copy of $\mathbb{N}$: $\ast ,0,1,2,3,\dots$. Map $\ast \mapsto 0$ and $n\mapsto n+1$. This is a bijection onto $\omega$ and it clearly preserves order, so the order type is $\omega$. Structurally: relabelling a sequence that has a first element and no last element as $0,1,2,\dots$ always yields $\omega$.

$\omega +1\ne \omega$. The order $\omega +1$ is $0,1,2,\dots$ followed by one extra point $\ast$ above all of them. It has a greatest element, and $\omega$ does not; having a greatest element is preserved by order-isomorphism, so the two types differ. By trichotomy and $\omega \in \omega +1$ we get $\omega <\omega +1$.

$2\cdot \omega =\omega$. This is $\omega$ copies of the two-point order: $(0,0),(0,1),(1,0),(1,1),(2,0),(2,1),\dots$ — an increasing sequence with a first element, no last element, and every element having only finitely many predecessors. Mapping the $k$ -th term to $k$ is an order-isomorphism onto $\omega$, so $2\cdot \omega =\omega$.

$\omega \cdot 2\ne \omega$. This is two copies of $\omega$ end to end: $0,1,2,\dots$ then $0^{\prime },1^{\prime },2^{\prime },\dots$. The element $0^{\prime }$ has infinitely many predecessors, whereas in $\omega$ every element has finitely many. "Number of predecessors" is an order-isomorphism invariant, so the types differ, and $\omega \cdot 2=\omega +\omega >\omega$.

Right distributivity. $(1+1)\cdot \omega =2\cdot \omega =\omega$ by the third computation, while $1\cdot \omega +1\cdot \omega =\omega +\omega =\omega \cdot 2>\omega$.∎

Proof. Existence, by induction on $\alpha$ using Every set of ordinals is well-ordered. Let ${\beta }_1$ be the largest ordinal with ${\omega }^{{\beta }_1}\le \alpha$; it exists because ${\omega }^{\gamma }>\alpha$ for $\gamma$ large (e.g. $\gamma =\alpha +1$) and the set of $\gamma$ with ${\omega }^{\gamma }\le \alpha$ is a set of ordinals bounded above, so it has a maximum. Let $c_1$ be the largest finite $c$ with ${\omega }^{{\beta }_1}c\le \alpha$; it is finite, for otherwise ${\omega }^{{\beta }_1}\cdot \omega ={\omega }^{{\beta }_1+1}\le \alpha$, contradicting maximality of ${\beta }_1$. By subtraction on the left there is a unique ${\alpha }^{\prime }$ with $\alpha ={\omega }^{{\beta }_1}{c}_1+{\alpha }^{\prime }$, and ${\alpha }^{\prime }<{\omega }^{{\beta }_1}$ by maximality of $c_1$; in particular ${\alpha }^{\prime }<\alpha$, so the induction hypothesis expands ${\alpha }^{\prime }$, and all its exponents are $<{\beta }_1$.

Uniqueness. If two such expressions were equal, compare leading terms. The value of ${\omega }^{{\beta }_1}{c}_1+{\alpha }^{\prime }$ with ${\alpha }^{\prime }<{\omega }^{{\beta }_1}$ lies in the interval $[{\omega }^{{\beta }_1}{c}_1,{\omega }^{{\beta }_1}(c_1+1))$, and these intervals for distinct pairs $({\beta }_1,c_1)$ are disjoint. So the leading exponent and coefficient are determined by $\alpha$, and then ${\alpha }^{\prime }$ is determined by left cancellation; induction finishes the argument.∎

Proof. The identity map witnesses $A\approx A$. If $f:A\to B$ is a bijection then $f^{-1}:B\to A$ is a bijection. If $f:A\to B$ and $g:B\to C$ are bijections then $g\circ f$ is a bijection, being a composite of injections and of surjections. The same three constructions, read for injections only, give reflexivity and transitivity of $\le$.∎

Proof. Think of $A$ and $B$ as disjoint and of $f$, $g$ as arrows. Every element has at most one arrow into it, so following arrows backwards from any point gives a chain that is uniquely determined: from $a\in A$ go back to the unique $b$ with $g(b)=a$ if one exists, then to the unique $a^{\prime }$ with $f(a^{\prime })=b$ if one exists, and so on. Each chain either runs backward forever, or terminates at a point of $A$ not in the image of $g$, or terminates at a point of $B$ not in the image of $f$.

Partition $A$ accordingly: let $A_A$ be the elements whose backward chain stops in $A$, $A_B$ those whose chain stops in $B$, and $A_{\infty }$ those whose chain is infinite. Partition $B$ into $B_A,B_B,B_{\infty }$ the same way. Since $f$ and $g$ shift a chain by one step without changing where it ultimately stops, $f$ restricts to a bijection $A_A\to B_A$ and to a bijection $A_{\infty }\to B_{\infty }$, while $g$ restricts to a bijection $B_B\to A_B$.

Define $h:A\to B$ by $h(a)=f(a)$ for $a\in A_A\cup A_{\infty }$ and $h(a)=g^{-1}(a)$ for $a\in A_B$. The three pieces are bijections onto the three disjoint pieces $B_A$, $B_{\infty }$, $B_B$ whose union is $B$, so $h$ is a bijection.

No choices were made: each backward step is unique when it exists, because $f$ and $g$ are injective, so the chain of any element is defined outright rather than selected.∎

Proof. Induct on $m$. For $m=0$: any $n>0$ is nonempty and there is no function at all into $\varnothing$. Suppose the claim holds for $m$ and let $f:n\to m+1$ be injective with $n>m+1$. If $m$ is not in the range of $f$, then $f$ maps $n$ injectively into $m$, and $n>m+1>m$ contradicts the hypothesis. Otherwise let $k=f^{-1}(m)$ and swap values so that the top element $n-1$ maps to $m$: define $f^{\prime }$ equal to $f$ except $f^{\prime }(n-1)=m$ and $f^{\prime }(k)=f(n-1)$. Then $f^{\prime }$ is injective and restricts to an injection $n-1\to m$ with $n-1>m$, contradicting the hypothesis again.∎

Proof. $|\mathbb{N}|=|\mathbb{Z}|$. Define $f:\mathbb{N}\to \mathbb{Z}$ by $f(n)=n/2$ for even $n$ and $f(n)=-(n+1)/2$ for odd $n$. This lists $\mathbb{Z}$ as $0,-1,1,-2,2,\dots$. It is injective since evens go to non-negatives and odds to negatives, and within each parity the formula is injective; it is surjective since $k\ge 0$ is hit by $2k$ and $k<0$ by $-2k-1$.

$|\mathbb{N}|=|\mathbb{N}\times \mathbb{N}|$. The Cantor pairing function $\pi (m,n)=\frac{(m+n)(m+n+1)}{2}+n$ enumerates $\mathbb{N}\times \mathbb{N}$ by sweeping the anti-diagonals $m+n=0,1,2,\dots$ in turn, each diagonal being finite; it is a bijection because the diagonals partition the plane and $\frac{d(d+1)}{2}$ is exactly the number of points on earlier diagonals.

$|\mathbb{N}|=|\mathbb{Q}|$. Each rational has a unique representation $p/q$ in lowest terms with $q\ge 1$, giving an injection $\mathbb{Q}\to \mathbb{Z}\times \mathbb{N}\approx \mathbb{N}$. In the other direction $n\mapsto n$ injects $\mathbb{N}$ into $\mathbb{Q}$. By Cantor–Schröder–Bernstein, $|\mathbb{Q}|={\aleph }_0$. Note that this conclusion is not defeated by $\mathbb{Q}$ being dense: density is an order property, and cardinality does not see order.∎

Proof. Each $A_n$ is countable, so the set $E_n$ of surjections $\omega \to A_n$ is nonempty (for $A_n=\varnothing$ discard the index). Countable choice supplies a single function $n\mapsto e_n$ with $e_n\in E_n$ — and this is the step that cannot be avoided: the enumerations exist individually, but nothing in ZF picks one for every $n$ at once.

Given the $e_n$, define $g:\omega \times \omega \to {\bigcup }_n{A}_n$ by $g(n,k)=e_n(k)$. Every element of the union lies in some $A_n$ and so is $e_n(k)$ for some $k$; hence $g$ is surjective. Composing with a bijection $\omega \to \omega \times \omega$ from The integers and rationals are countable gives a surjection $\omega \to {\bigcup }_n{A}_n$, and a surjection from $\omega$ onto a nonempty set $S$ yields an injection $S\to \omega$ by sending $s$ to the least preimage — a definable choice, needing no further axiom. So the union is countable.∎

Proof. The map $a\mapsto \{a\}$ is an injection $A\to \mathcal{P}(A)$, so $|A|\le |\mathcal{P}(A)|$.

Suppose some $f:A\to \mathcal{P}(A)$ were surjective, and set

which is a subset of $A$ and hence, by surjectivity, equals $f(d)$ for some $d\in A$. Ask whether $d\in D$. If $d\in D$ then by the definition of $D$ we have $d\notin f(d)=D$. If $d\notin D=f(d)$ then $d$ satisfies the defining condition, so $d\in D$. Both cases are contradictory, so no surjection $A\to \mathcal{P}(A)$ exists; in particular no bijection does, and $|A|<|\mathcal{P}(A)|$.∎

Proof. Subsets of $\mathbb{N}$ correspond bijectively to their indicator functions $\mathbb{N}\to \{0,1\}$, so $|\mathcal{P}(\mathbb{N})|=2^{{\aleph }_0}$, and Cantor's theorem with $A=\mathbb{N}$ gives $2^{{\aleph }_0}>{\aleph }_0$.

For $|\mathbb{R}|=2^{{\aleph }_0}$: binary expansions give an injection $\{0,1{\}}^{\mathbb{N}}\to \mathbb{R}$ via $s\mapsto {\sum }_{n}2s(n)3^{-n-1}$, whose image lies in the Cantor set and which is injective because ternary digits $0$ and $2$ never produce a carry collision. Conversely each real is determined by the set of rationals below it, giving an injection $\mathbb{R}\to \mathcal{P}(\mathbb{Q})\approx \mathcal{P}(\mathbb{N})$. Cantor–Schröder–Bernstein closes the sandwich.

If the irrationals were countable then $\mathbb{R}=\mathbb{Q}\cup (\mathbb{R}\setminus \mathbb{Q})$ would be a union of two countable sets, hence countable by A countable union of countable sets is countable — and that instance needs no choice, since both enumerations are given. So the irrationals are uncountable.∎

Proof. Each is a canonical bijection. Commutativity of $+$ is $A\cup B=B\cup A$; of $\cdot$, the swap $(a,b)\mapsto (b,a)$. Associativity of $\cdot$ is the regrouping $(a,b,c)$. Distributivity is $A\times (B\bigsqcup C)=(A\times B)\bigsqcup (A\times C)$. For ${\kappa }^{\lambda +\mu }$, a function on $B\bigsqcup C$ is exactly a pair consisting of its restrictions to $B$ and to $C$. For $({\kappa }^{\lambda }{)}^{\mu }$, currying identifies a function $C\to A^B$ with a function $B\times C\to A$. For $(\kappa \lambda {)}^{\mu }$, a function into a product is a pair of functions into the factors. None of these bijections makes a choice.∎

Proof. The engine is $\kappa \cdot \kappa =\kappa$ for every infinite cardinal $\kappa$, proved by transfinite induction on $\kappa$ using the Gödel pairing: well-order $\kappa \times \kappa$ by comparing first $\max (\alpha ,\beta )$, then $\alpha$, then $\beta$. Every proper initial segment of that order sits inside $\gamma \times \gamma$ for some $\gamma <\kappa$, which by induction has size $|\gamma |<\kappa$; so the order type of $\kappa \times \kappa$ is at most $\kappa$, giving $\kappa \cdot \kappa \le \kappa$, and $\ge$ is clear. (AC enters in guaranteeing that every infinite set is such a $\kappa$, i.e. is well-orderable.)

Now let $\mu =\max (\kappa ,\lambda )$, so $\mu \le \kappa +\lambda \le \mu +\mu =2\cdot \mu \le \mu \cdot \mu =\mu$, and Cantor–Schröder–Bernstein gives $\kappa +\lambda =\mu$. Similarly $\mu \le \kappa \cdot \lambda \le \mu \cdot \mu =\mu$, so $\kappa \cdot \lambda =\mu$.∎

Proof. The positive constraints are provable here. $2^{{\aleph }_0}>{\aleph }_0$ is Cantor's theorem. That $\mathrm{cf}(2^{{\aleph }_0})>{\aleph }_0$ is König's theorem: if $2^{{\aleph }_0}$ were the supremum of countably many smaller cardinals ${\mu }_n$, then $2^{{\aleph }_0}=(2^{{\aleph }_0}{)}^{{\aleph }_0}\le {\prod }_n{\mu }_n^{\prime }$ for suitable ${\mu }_n^{\prime }<2^{{\aleph }_0}$, and König's inequality ${\sum }_n{\mu }_n<{\prod }_n{\nu }_n$ whenever ${\mu }_n<{\nu }_n$ yields a contradiction. So $2^{{\aleph }_0}\ne {\aleph }_{\omega }$, whose cofinality is $\omega$.

The negative half — that no further value is excluded — is Cohen's forcing theorem, discussed in History and independence below, and is not proved here. Easton's theorem sharpens it: for regular cardinals, the function $\kappa \mapsto 2^{\kappa }$ may be prescribed almost arbitrarily subject only to monotonicity and the cofinality restriction.∎

Proof. Consider the collection $W$ of all pairs $(S,<)$ where $S\subseteq A$ and $<$ well-orders $S$. Each such pair is an element of $\mathcal{P}(A)\times \mathcal{P}(A\times A)$, so $W$ is a set by separation. By Representation of well-orders and replacement, $H=\{\mathrm{ot}(S,<):(S,<)\in W\}$ is a set of ordinals.

An ordinal $\alpha$ injects into $A$ if and only if $\alpha \in H$: an injection transports the well-order of $\alpha$ onto a subset of $A$, and conversely. $H$ is transitive, since a smaller ordinal injects whenever a larger one does, so $H$ is itself an ordinal, and it is the least ordinal not in $H$ — that is, the least ordinal not injecting into $A$. It is a cardinal because any smaller ordinal injects into $A$ while $H$ does not, so $H$ is not equinumerous with a smaller ordinal. No choice was used: every step was separation, replacement or power set.∎

Proof. Strict increase: ${\aleph }_{\alpha +1}>{\aleph }_{\alpha }$ by Hartogs' theorem, and at limits the supremum of a strictly increasing family of cardinals is a cardinal exceeding each of them — it is a cardinal because an initial ordinal is not equinumerous with anything smaller, and a bijection with some $\gamma <\sup$ would already be a bijection at some stage below.

Exhaustiveness: let $\kappa$ be an infinite well-ordered cardinal. The class $\{\alpha :{\aleph }_{\alpha }\le \kappa \}$ is nonempty ($\alpha =0$) and is bounded, since ${\aleph }_{\alpha }\ge \alpha$ for every $\alpha$ by induction, so ${\aleph }_{\kappa +1}>\kappa$. Take $\beta$ the largest index with ${\aleph }_{\beta }\le \kappa$. If ${\aleph }_{\beta }<\kappa$ then ${\aleph }_{\beta +1}={\aleph }_{\beta }^{+}\le \kappa$, contradicting maximality; so $\kappa ={\aleph }_{\beta }$. Uniqueness follows from strict increase. Under AC every set is well-orderable, so every infinite cardinal is covered.∎

Proof. Suppose $A\subseteq {\kappa }^{+}$ is unbounded with $|A|\le \kappa$. Each $\alpha \in A$ has $|\alpha |\le \kappa$, so ${\kappa }^{+}={\bigcup }_{\alpha \in A}\alpha$ has cardinality at most $\kappa \cdot \kappa =\kappa$ by Absorption for infinite cardinals — a union of at most $\kappa$ sets each of size at most $\kappa$. That contradicts $|{\kappa }^{+}|={\kappa }^{+}>\kappa$. So every unbounded subset has size ${\kappa }^{+}$ and $\mathrm{cf}({\kappa }^{+})={\kappa }^{+}$.