Past exam of the mathematics course of the University of Cambridge / 2026 / ii / Paper 4 / 16J (Logic & Set Theory)

A set $x$ is transitive when $y\in z\in x$ implies $y\in x$, equivalently $\bigcup x\subset x$.

$\mathrm{tcl}(x)$ is the least transitive set containing $x$, namely $x\cup \bigcup x\cup {\bigcup }^{2}x\cup \cdots$.

$V_0=\varnothing$, $V_{\alpha +1}=\mathcal{P}(V_{\alpha })$, and $V_{\lambda }={\bigcup }_{\alpha <\lambda }{V}_{\alpha }$ at limits.

The Mirimanoff rank is $\rho (x)=\min \{\alpha :x\subset V_{\alpha }\}={\sup }_{y\in x}(\rho (y)+1)$.

From $\rho (x)={\sup }_{y\in x}(\rho (y)+1)$, if every $\rho (y)<\gamma$, then every $\rho (y)+1\le \gamma$ and the supremum is at most $\gamma$, contradicting $\gamma <\rho (x)$.

Taking transitive closure adds only descendants of existing members, whose ranks are lower. Thus the supremum of member ranks, and hence the rank of the set, is unchanged: $\rho (x)=\rho (\mathrm{tcl}x)$.

Induct on $\gamma$. Part (b) gives a member of rank at least $\gamma$; transitivity and descent through a member of larger rank, using the induction hypothesis, produces a member of rank exactly $\gamma$.

If $x$ is hereditarily countable, its transitive closure contains only countably many ranks. Their supremum is a countable ordinal below ${\omega }_1$, so $x\in V_{{\omega }_1}$.

Every real $r\subset \omega$ is hereditarily countable, giving $2^{{\aleph }_0}\le |HC|$. Conversely each HC set is represented by a well-founded extensional relation on a subset of $\omega$; there are only $2^{{\aleph }_0}$ such relations. Hence equality.