Past exam of the mathematics course of the University of Cambridge / 2021 / ii / Paper 3 / 16G (Logic and Set Theory)

For cardinals, $\kappa <\lambda$ means that there is an injection $\kappa \to \lambda$ but no bijection. Under the axiom of choice, every set is well-orderable, so every infinite cardinal is the initial ordinal ${\aleph }_{\alpha }$ for a unique ordinal $\alpha$. Cantor theorem givesand minimality of the successor cardinal givesThe strict inequality ${\aleph }_{\alpha +1}<2^{{\aleph }_{\alpha }}$ printed in the conversion is not provable and can be false under the generalized continuum hypothesis; the intended symbol must be $\le$.

The map $a\mapsto \{a\}$ injects $x$ into $\mathcal{P}(x)$. Cantor's diagonal argument shows that no map $x\to \mathcal{P}(x)$ is surjective: for $f:x\to \mathcal{P}(x)$, the set $D=\{a:a\notin f(a)\}$ differs from every $f(a)$. Hence $\kappa <2^{\kappa }$.

If $f:x\to y$ is surjective, inverse image gives an injectionFor every infinite initial ordinal ${\omega }_{\alpha }$, transfinite recursion constructs a pairing of ${\omega }_{\alpha }\times {\omega }_{\alpha }$ with ${\omega }_{\alpha }$: at each stage fewer than ${\aleph }_{\alpha }$ earlier pairs have been used. Thuswithout invoking choice for arbitrary families.

Every ordinal below ${\omega }_{\alpha +1}$ has cardinal at most ${\aleph }_{\alpha }$ and can be coded by a well-ordering relation on a subset of ${\omega }_{\alpha }$. Sending such a relation to its order type, and all non-well-orders to zero, gives a surjectionUsing the pairing above to code relations as subsets of ${\omega }_{\alpha }$ yieldsAgain, strictness beyond this is independent of the usual axioms.