Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 4 / 16H (Logic and Set Theory)

Assume the axiom of choice. By the well-ordering theorem, every set is bijective with an ordinal, and hence with an initial ordinal. Any two ordinals are comparable, so for any sets $K,L$ either $K$ injects into $L$ or $L$ injects into $K$. Transitivity is immediate, and antisymmetry on cardinalities follows from the Cantor-Schröder-Bernstein theorem. Thus cardinal comparison is a total order.

Conversely, assume the cardinal comparability principle. Given any set $X$, let $h(X)$ be its Hartogs ordinal. By Hartogs theorem, there is no injection $h(X)\to X$. Comparability therefore supplies an injection $X\to h(X)$. Pulling the ordinal order back to $X$ gives a well-order of $X$. Hence every set can be well-ordered, and the well-ordering theorem implies the axiom of choice.

Under the axiom of choice, identify every infinite cardinal $\kappa$ with its initial ordinal. We prove ${\kappa }^2=\kappa$ by transfinite induction on infinite cardinals. The countable case follows from the usual diagonal enumeration of $\mathbb{N}\times \mathbb{N}$.

For the induction step, well-order the Cartesian product $\kappa \times \kappa$ by first comparingand then using lexicographic order among pairs with the same maximum. The predecessors of $(\alpha ,\beta )$ lie in $(\eta +1)\times (\eta +1)$, where $\eta =\max \{\alpha ,\beta \}<\kappa$. Put $\mu =|\eta +1|<\kappa$. If $\mu$ is infinite, the induction hypothesis makes this predecessor set have cardinal at most ${\mu }^2=\mu <\kappa$; if $\mu$ is finite, the same conclusion is immediate.

Let $\theta$ be the order type of this well-order. Every proper initial segment of $\theta$ therefore has cardinal less than $\kappa$. Hence $\theta <{\kappa }^{+}$, since otherwise its initial segment of order type $\kappa$ would have cardinal $\kappa$. Thus $|\kappa \times \kappa |=|\theta |\le \kappa$. The map $\alpha \mapsto (\alpha ,0)$ gives the reverse injection, and the Cantor-Schröder-Bernstein theorem yields

Letbe the injection witnessing $\kappa \lambda \le \kappa +\lambda$, and fix $(k_{\ast },l_{\ast })\in K\times L$. Extend the inverse of $i$ to a surjectionby settingThis construction uses only the fixed pair, not the axiom of choice.

Restrict $p$ to the $K$-summand and take its second coordinate:If $r$ is onto, it is the required surjective function from $K$ to $L$.

Otherwise choose one $l_0\in L\setminus r[K]$. For each $k\in K$, surjectivity of $p$ gives a preimage of $(k,l_0)$. No such preimage lies in the $K$-summand, by the choice of $l_0$, so it lies in the $L$-summand. Unless $(k,l_0)=(k_{\ast },l_{\ast })$, this preimage is exactly $i(k,l_0)$ and is unique: all points outside the range of $i$ map only to the default pair. Distinct $k$ give distinct preimages because $i$ is injective.

If $l_0\ne l_{\ast }$, these unique preimages therefore define an injective function $K\to L$. The only exceptional case is $l_0=l_{\ast }$, where they initially define an injectionIf $j$ is onto, extend it arbitrarily at $k_{\ast }$ to obtain a surjection $K\to L$. If it is not onto, choose one $l^{\prime }\in L\setminus j[K\setminus \{k_{\ast }\}]$ and set $j(k_{\ast })=l^{\prime }$; this gives an injection $K\to L$. These cases prove the product-sum comparison lemma entirely in ZF.

Part (b) proves one implication. Conversely, assume in ZF thatfor every infinite cardinal $\kappa$. Let $X$ be any set and let $\gamma =h(X)$ be its Hartogs ordinal. Finite $X$ is already well-orderable, so suppose $X$ is infinite and form the disjoint unionBy hypothesis, $A\times A$ is bijective with $A$. Since $\gamma \times X$ injects into $A\times A$, we obtain

Apply part (c), with $K=\gamma$ and $L=X$. It gives either an injection $\gamma \to X$ or a surjection $s:\gamma \to X$. The first alternative contradicts Hartogs theorem. In the second, every fiber $s^{-1}(\{x\})$ is a nonempty set of ordinals and therefore has a least member. The mapis an injection of $X$ into the ordinal $\gamma$ and pulls its well-order back to $X$. Thus every set is well-orderable, so the well-ordering theorem gives the axiom of choice. This proves the Tarski cardinal-square theorem.