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

The constructible hierarchy is defined by transfinite recursion using the definable power set. With parameters permitted in the internal definitions, write $\mathrm{Def}(A,1)$ for the definable subsets of $A$. ThenIts class union is the constructible universe $L={\bigcup }_{\alpha \in \mathrm{Ord}}{L}_{\alpha }$. Only subsets definable over $(L_{\alpha },\in )$ using a first-order formula and finitely many parameters from $L_{\alpha }$ enter at a successor stage.

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

Let $\theta =M\cap \mathrm{Ord}$ be the ordinal height of a model of set theory. First $\theta \ge {\omega }_1$. Indeed, if $\theta$ were countable, the internal axiom of choice would give, for every $x\in M$, a bijection in $M$ between $x$ and some ordinal below $\theta$. Such a bijection is also valid externally, making $x$ externally countable. In particular every internal rank $V_{\xi }^M$, $\xi <\theta$, would be countable. Every element of $M$ lies in one of these internal ranks, sowould be a countable union of countable sets, a contradiction. This is why an uncountable transitive set model has uncountable ordinal height.

For $\xi <\theta$, absoluteness of constructible levels gives $L_{\xi }^M=L_{\xi }$, and that level is an element of $M$. The reason is that satisfaction in a fixed set structure uses the same domain and finite formulas in both universes, so successor definitions agree; transfinite recursion then also makes limit stages agree. Transitivity consequently givesIt remains to locate a countability witness. Given an ambient countable ordinal $\alpha$, choose an injection $f:\alpha \to \omega$. Since $V=L$, it belongs to the constructible universe. Its transitive closure, together with $f$ itself, is countable. Choose a countable elementary substructure $X\prec L_{\eta }$ of a sufficiently large limit level containing this closure pointwise. The condensation lemma for the constructible universe identifies the collapse with $L_{\beta }$ for some countable $\beta$. The collapse fixes $f$, since all its hereditary members were included. Thus $f\in L_{\beta }\subseteq L_{{\omega }_1}\subseteq M$.

The ordinal $\alpha$ itself is in $M$, since $\alpha <{\omega }_1\le \theta$. Being an injection between these fixed sets is a bounded formula in set theory, so $M$ recognizes $f$ as a countability witness. This proves countable-ordinal correctness under constructibility:The use of condensation supplies a witness below the height of $M$; merely knowing that $f$ belongs somewhere to $L$ would not be sufficient.

We give a relative-consistency argument using a finite-function collapse to countable size. The assumed consistency implies that ZFC is consistent. Passing to the constructible universe gives consistency of $\mathsf{ZFC}+V=L$, which also satisfies the Generalized continuum hypothesis. Work in this ground theory, let $\delta ={\omega }_1^L$, and force with finite partial functions $\omega \rightharpoonup \delta$, ordered by reverse inclusion.

The union of a generic filter $H$ is a total surjection $h:\omega \to \delta$: prescribing a new domain coordinate is dense, and putting any specified $\gamma <\delta$ into the range is dense. Hence $\delta$ becomes countable. Set forcing preserves ordinals, and absoluteness of constructible levels implies that the extension has the same constructible universe as the ground model. Its ${\omega }_1^L$ is therefore still the old $\delta$, so it satisfies the stated countability of constructible omega-one condition.

We must also verify GCH after the collapse. The order has ground-model size $\delta$, hence the ${\delta }^{+}$-chain condition. By cardinal preservation by chain-condition forcing, all old cardinals at least ${\delta }^{+}$ survive. Every old ordinal below ${\delta }^{+}$ has size at most $\delta$ and becomes countable, so the old ${\delta }^{+}$ is exactly the new ${\omega }_1$.

A name for a subset of a fixed ground-model ordinal $\lambda$ can be chosen as a set of pairs $(\check{\xi },p)$ with $\xi <\lambda$ and $p$ a condition: use an antichain deciding membership at each coordinate. Thus the number of such names in the ground model is at most $2^{|\lambda \times \mathbb{P}|}$. For subsets of $\omega$ this is $2^{\delta }={\delta }^{+}$ by ground-model GCH. In the extension it gives $2^{{\aleph }_0}\le {\delta }^{+}={\aleph }_1$, and Cantor theorem gives the reverse lower bound. For every old cardinal $\lambda \ge {\delta }^{+}$ the bound isin the ground model. Both $\lambda$ and ${\lambda }^{+}$ remain cardinals, so again the upper bound and Cantor theorem give the extension's equality $2^{\lambda }={\lambda }^{+}$. These are all its uncountable cardinals. This proves GCH preservation by a finite-function collapse in the required case.

The forcing relative-consistency theorem now yieldsThe construction in fact only needs consistency of ZFC. This argument uses the formal inner-model and forcing consistency theorems; it does not infer the existence of a countable transitive model merely from consistency.