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

The Von Neumann hierarchy is defined by transfinite recursion:for every limit ordinal $\lambda$.

We prove simultaneously by transfinite induction that every $V_{\alpha }$ is a transitive set and that $V_{\alpha }\subseteq V_{\alpha +1}$. The claims are immediate for $V_0$. Suppose first that $V_{\alpha }$ is transitive. If $x\in y\in V_{\alpha +1}=\mathcal{P}(V_{\alpha })$, then $y\subseteq V_{\alpha }$, so $x\in V_{\alpha }$. Moreover, transitivity says that every $x\in V_{\alpha }$ satisfies $x\subseteq V_{\alpha }$, and henceThus $V_{\alpha +1}$ is transitive and $V_{\alpha }\subseteq V_{\alpha +1}$. At a limit $\lambda$, if $x\in y\in V_{\lambda }$, then $y\in V_{\beta }$ for some $\beta <\lambda$; transitivity of $V_{\beta }$ gives $x\in V_{\beta }\subseteq V_{\lambda }$. The inclusions at successor stages also imply

Finally, the rank of a set $x$ is the ordinalEvery $y\in x$ belongs to $V_{\mathrm{rank}(y)+1}\subseteq V_{\mathrm{rank}(x)}$, so $x\subseteq V_{\mathrm{rank}(x)}$. Thereforewhich proves that every set occurs in the hierarchy.

True. If $x$ is a nonempty finite set, thenThis maximum is a successor ordinal, whereas the empty set has rank $0$. Hence a set of nonzero limit ordinal rank cannot be finite and must be an infinite set.

False. Take $x=\mathcal{P}(\omega )$, the power set of the first infinite ordinal $\omega$. Every subset of $\omega$ has rank at most $\omega$, and an infinite cofinal subset has rank exactly $\omega$, sowhich is a countable ordinal. But Cantor theorem shows that $\mathcal{P}(\omega )$ is an uncountable set.

True. For each $y\in x$, the singleton set $\{y\}$ is a finite subset of $x$, so the hypothesis givesTaking the supremum over all $y\in x$ yields

True. Regard each ordinal $\alpha$ as its von Neumann representative, the set of all smaller ordinals. Transfinite induction givesThus the set $\alpha$ itself has rank $\alpha$.