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

The rank is defined recursively byFor a nonzero limit ordinal $\alpha$, every function $f:\alpha \to \alpha$, viewed as a set of ordered pairs, has rank $\alpha$, and the set of all such functions consequently has rank $\alpha +1$.

The von Neumann hierarchy isfor limit $\lambda$. Foundation permits induction down the membership relation and shows that the ranks of all elements of a set form a set of ordinals. If $\rho =\mathrm{rank}(x)$, then every element of $x$ lies in $V_{\rho }$, so $x\subseteq V_{\rho }$ and hence $x\in V_{\rho +1}$. Thus every set occurs in the hierarchy.

Define ${\aleph }_0=|\omega |$, let ${\aleph }_{\alpha +1}$ be the least cardinal greater than ${\aleph }_{\alpha }$, and at a limit take the least cardinal above all earlier ${\aleph }_{\gamma }$. In ZFC every set is well-orderable, so every infinite cardinal is an initial ordinal and equals a unique ${\aleph }_{\alpha }$.

By transfinite induction on infinite well-ordered cardinals $\kappa$, order $\kappa \times \kappa$ first by $\max (\xi ,\eta )$ and then lexicographically. Every proper initial segment has cardinal below $\kappa$, using the inductive hypothesis for smaller infinite cardinals. Hence this well-order has cardinal at most $\kappa$, while the diagonal gives the reverse inequality, so ${\kappa }^2=\kappa$. Therefore, for ${\aleph }_{\alpha }\le {\aleph }_{\beta }$,

Finally suppose nonempty $x$ had a set $y$ containing every set equinumerous with $x$. For every ordinal $\gamma$, replacing each $z\in x$ by a tagged ordered pair $(\gamma ,z)$ gives a set $t_{\gamma }$ equinumerous with $x$ whose rank is at least $\gamma$. Then every $t_{\gamma }$ would belong to $y$, so the ranks of members of $y$ would be unbounded in the ordinals, contradicting the ordinal rank of $y$. This proves the displayed sentence.