Past exam of the mathematics course of the University of Cambridge / 2018 / iii / Paper 121 / 2 / ii

We prove simultaneously that each $L_{\alpha }$ is a transitive set and that $L_{\alpha }\subseteq L_{\alpha +1}$. The key observation is that if $A$ is transitive and $x\in A$, then $x\subseteq A$ andThis is an internal definition with parameter $x$, so $x\in \mathrm{Def}(A,1)$. Hence $A\subseteq \mathrm{Def}(A,1)$. Every $z\in \mathrm{Def}(A,1)$ is a subset of $A$; if $y\in z$, then $y\in A\subseteq \mathrm{Def}(A,1)$. Thus the definable power set is transitive too.

Start with the empty set. At successor stages the observation proves transitivity and inclusion. At a limit stage the union of the earlier transitive sets is transitive, and the same observation then proves its inclusion in its own definable power set. This completes the transfinite induction and gives

The argument in part (a) established $L_{\alpha }\subseteq L_{\alpha +1}$ for every ordinal $\alpha$. A transfinite induction on $\beta$ now proves that every earlier level is contained in $L_{\beta }$. If $\beta =\gamma +1$, use the inductive inclusions into $L_{\gamma }$ followed by $L_{\gamma }\subseteq L_{\gamma +1}$. At a limit stage, every earlier level is one of the sets in the defining union. Equality of indices is trivial. ThusThe constructible hierarchy is a nondecreasing family of sets.

Induct on $\alpha$ using the transitivity and inclusion already established. The zero stage is immediate. Suppose $L_{\alpha }\cap \mathrm{Ord}=\alpha$. Being an ordinal is expressible by a bounded formula in set theory, for example transitivity, transitivity of all members, and membership comparability. It is therefore absolute for the transitive set $L_{\alpha }$. The subset of its elements that are ordinals is internally definable, soBy inclusion, all smaller ordinals are present as well. Conversely, if an ordinal $\gamma$ belongs to $L_{\alpha +1}$, then $\gamma \subseteq L_{\alpha }$, since every member of a definable power set is a subset of the preceding domain. All members of $\gamma$ are ordinals, so $\gamma \subseteq L_{\alpha }\cap \mathrm{Ord}=\alpha$ and $\gamma \le \alpha$. Hence the ordinal part of the successor level is exactly $\alpha +1$.

At a nonzero limit ordinal $\lambda$,Thus