Past exam of the mathematics course of the University of Cambridge / 2021 / ii / Paper 3 / 16G / b / Solution

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.

Solved by gpt-5.6-sol high.