Ordinal and cardinal numbers

This lets us prove a statement for every ordinal — finite, $\omega$, and beyond — by only ever handling "assume it holds for everything smaller", with no separate base case and no separate limit case needed in the statement of the principle itself.

Suppose, for contradiction, that $C$ does not contain every ordinal. Then the class $D$ of ordinals not in $C$ is nonempty. The ordinals themselves form a well-order (any nonempty class of ordinals has a least element — this is essentially the defining property of the ordinals), so $D$ has a least element; call it $\alpha$.

By minimality of $\alpha$, every ordinal $\beta<\alpha$ is not in $D$, i.e. every $\beta<\alpha$ satisfies $\beta \in C$.

But this is exactly the hypothesis of the theorem applied to $\alpha$: "$\beta \in C$ for all $\beta<\alpha$" implies $\alpha \in C$. So $\alpha \in C$.

This contradicts $\alpha \in D$ (i.e. $\alpha \notin C$). The contradiction shows no such least counterexample $\alpha$ can exist, so $D=\emptyset$: $C$ contains every ordinal. $\blacksquare$

Even though we cannot know the exact value of $2^{\aleph_0}$ from ZFC alone (Cohen's independence result), this theorem is one of the few things we CAN prove unconditionally about it: whatever it equals, you cannot approach it from below along an $\omega$-sequence of strictly smaller cardinals.

We first prove the general König inequality: if $\kappa_i < \lambda_i$ for every $i$ in an index set $I$, then $\sum_{i\in I}\kappa_i < \prod_{i\in I}\lambda_i$. Fix sets $B_i$ with $|B_i|=\lambda_i$ and subsets $A_i \subsetneq B_i$ with $|A_i|=\kappa_i$. The inequality $\sum_i \kappa_i \le \prod_i \lambda_i$ is routine (send each $a\in A_i$ to the tuple that is $a$ in coordinate $i$ and some fixed default value elsewhere), so the content is showing they are not equal.

Suppose, for contradiction, some function $h : \bigsqcup_{i\in I} A_i \to \prod_{i\in I} B_i$ is surjective. For each $i$, let $h_i:A_i\to B_i$ send $a \mapsto h(a)(i)$ (the $i$-th coordinate of $h(a)$). Since $|A_i|=\kappa_i<\lambda_i=|B_i|$, the map $h_i$ cannot be surjective onto $B_i$ (if it were, picking a preimage for each element of $B_i$ would inject $B_i$ into $A_i$, forcing $\lambda_i\le\kappa_i$ — contradiction). So choose $d_i \in B_i \setminus \operatorname{ran}(h_i)$ for every $i$, and let $g \in \prod_i B_i$ be the tuple with $g(i)=d_i$.

Since $h$ is surjective, $g=h(a)$ for some $a$, say $a \in A_j$. Then $g(j)=h(a)(j)=h_j(a) \in \operatorname{ran}(h_j)$. But $g(j)=d_j \notin \operatorname{ran}(h_j)$ by construction — a direct contradiction. So no surjection $h$ exists, giving $\sum_i\kappa_i < \prod_i\lambda_i$. (Setting $I=X$, $\kappa_i=1$, $\lambda_i=2$ recovers Cantor's classical diagonal argument $|X|<2^{|X|}$ as a special case.)

Now suppose, for contradiction, $\operatorname{cf}(2^{\aleph_0})=\aleph_0$. Then $2^{\aleph_0}$ is the sum of a strictly increasing $\omega$-sequence of smaller cardinals $\kappa_0<\kappa_1<\kappa_2<\cdots$, i.e. $2^{\aleph_0}=\sum_{n<\omega}\kappa_n$ with every $\kappa_n < 2^{\aleph_0}$. Apply König's inequality with $\lambda_n := 2^{\aleph_0}$ held constant for every $n$ (valid since $\kappa_n < 2^{\aleph_0} = \lambda_n$ for every $n$):

$$2^{\aleph_0} = \sum_{n<\omega}\kappa_n \;<\; \prod_{n<\omega}\lambda_n = \left(2^{\aleph_0}\right)^{\aleph_0} = 2^{\aleph_0\cdot\aleph_0} = 2^{\aleph_0}.$$

This says $2^{\aleph_0}<2^{\aleph_0}$, absurd. So $\operatorname{cf}(2^{\aleph_0})\neq\aleph_0$; since cofinality is never smaller than that (it is at least $\aleph_0$ for any infinite cardinal, and it cannot be finite), we conclude $\operatorname{cf}(2^{\aleph_0})>\aleph_0$. $\blacksquare$