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

A definable continuous hierarchy is a definable class function $\alpha \mapsto H_{\alpha }$ on the ordinals, with set-valued levels, such that $H_{\alpha }\subseteq H_{\beta }$ for $\alpha <\beta$ andfor nonzero limit ordinals. Its union is a definable class in set theory $H$. Often the definition additionally requires every level to be a transitive set; the following statement also works without that requirement.

The reflection theorem for definable hierarchies says that for any finite collection $\mathcal{F}$ of first-order formulas, there is a closed unbounded class of ordinals $\alpha$ such that, for every $\phi \in \mathcal{F}$ and every parameter tuple from $H_{\alpha }$,A useful justification is the witness-closure proof. Close $\mathcal{F}$ under subformulas. At each level and for each existential subformula, bound the least level containing a witness for each parameter tuple for which a witness exists in $H$. Axiom schema of replacement bounds these indices. Iterating the finitely many bounds through $\omega$ produces a limit level containing all required witnesses. Induction on the first-order formulas, equivalently the finite-formula version of the Tarski-Vaught test, yields agreement. Continuity gives closedness of the reflecting class, and starting above any prescribed ordinal gives unboundedness. This is finite reflection, not a claim that all first-order formulas reflect simultaneously in an arbitrary hierarchy.

Fix the base convention $L_0(X)=X$. For a transitive set $X$, the relative constructible hierarchy isHere the definable power set isThe satisfaction for a set structure in this definition is a definable set-theoretic relation, obtained by finite syntax coding and recursion on a first-order formula. The transfinite recursion therefore defines a class in ZF.

Each level is a transitive set. For transitive $A$, every $a\in A$ is a subset of $A$ definable using the parameter $a$, so $A\subseteq \mathrm{Def}(A)$; also $A\in \mathrm{Def}(A)$ using the always-true first-order formula. Thus the levels increase and $X\in L_1(X)$. Starting instead with $X\cup \{X\}$ is another common indexing convention, but it is not the convention used here. The relative universe need not satisfy axiom of choice: arbitrary $X$ need not have an internally available well-order.

Use relative constructible level recognition. The finite coding conditions matter here: merely writing “every set is relatively constructible” inside an arbitrary transitive set does not ensure that its computations are correct.

Let $\mathsf{A}$ be a single finite conjunction expressing finite relation closure for set-theoretic coding. Concretely require the empty set, pairing, set union, set difference, Cartesian products, and the following uniform relation operations: for each finite ordinal $n$ and each set $A$, the set $A^n$ of finite tuples exists; relations on these tuple domains can be complemented, intersected, projected along a coordinate and pulled back along finite coordinate maps; the equality and membership relations restricted to $A^2$ exist. These are finitely many first-order closure assertions with $n$ quantified, not an axiom schema. Each operation is specified by its usual elementwise membership equivalence. Transitivity makes the operations correct externally. Finite tuple domains are also correct: every individual finite tuple is already present by pairing and union.

These conditions make satisfaction for a set structure absolute. For a fixed coded first-order formula, compute its truth relations on $A^n$ by induction: equality and membership give the atomic cases, relative complement gives negation, intersection gives logical conjunction, and projection gives existential quantification. All required truth tables exist by $\mathsf{A}$ and agree with the actual ones. Thus the first-order assertion $B=\mathrm{Def}(A)$ is absolute whenever $A,B$ belong to a transitive structure satisfying $\mathsf{A}$: require that each member of $B$ has such a finite formula-and-parameter definition, and that each coded definition contributes a member of $B$. Codes are finite objects; no truth predicate for the ambient universe is being used.

Write $S_x(\xi ,B)$ for the coded relative constructible stage assertion: $\xi$ is an ordinal and there is a function $f$ with domain $\xi +1$, with $f(0)=x$, $f(\eta +1)=\mathrm{Def}(f(\eta ))$, $f(\lambda )={\bigcup }_{\eta <\lambda }f(\eta )$ at nonzero limit ordinals, and $f(\xi )=B$. Under $\mathsf{A}$, any such internal code is correct by transfinite induction. Restrictions of a code to shorter domains exist by the relation operations. Define the one-free-variable first-order formulaAll displayed abbreviations expand into first-order formulas of the membership language.

Suppose $M$ is transitive, $X\in M$, and $M\models \Phi (X)$. Let $I$ be the externally defined set of indices of stage codes in $M$. It contains $0$, is downward closed by restricting codes, and has no largest member by the last conjunct. Thus $I$ is a nonzero limit ordinal $\alpha$. Correctness of stage codes gives $L_{\xi }(X)\in M$ for $\xi <\alpha$, hence $L_{\xi }(X)\subseteq M$ by transitivity. Conversely the exhaustion conjunct puts every $y\in M$ in some such level. Therefore

For the converse, every $L_{\alpha }(X)$ with nonzero limit $\alpha$ satisfies $\mathsf{A}$: each listed operation on parameters from one level is definable at finitely many later levels, still below $\alpha$. Moreover stage histories appear below every limit constructible level. Here is the essential limit step of that lemma. If the histories $f_{\eta }$ for $\eta <\lambda$ are available in $L_{\lambda }(X)$, the correct predicate $S_X$ defines their graph of endpoints as a subset of $L_{\lambda }(X)$. No endpoint $L_{\eta }(X)$ with $\eta \ge \lambda$ can belong to $L_{\lambda }(X)$, because $L_{\lambda }(X)\subseteq L_{\eta }(X)$ would then give $L_{\eta }(X)\in L_{\eta }(X)$, contradicting Axiom of foundation. The defined graph therefore has domain exactly $\lambda$. Adjoining its final pair $(\lambda ,L_{\lambda }(X))$ takes finitely many more stages. Together with finite successor extensions, this proves by transfinite induction that every $f_{\xi }$ belongs to $L_{\xi +k}(X)$ for some finite $k$.

Thus all histories for $\xi <\alpha$ belong to $L_{\alpha }(X)$. Exhaustion follows from continuity, and $\xi +1<\alpha$ supplies a larger represented stage. Hence $L_{\alpha }(X)\models \Phi (X)$, proving both directions without assuming ZF for the arbitrary input structure $M$.

A suitable relative condensation lemma fixes the base pointwise. Let $\alpha$ be a nonzero limit ordinal, and let $Y\prec (L_{\alpha }(X),\in )$ be an elementary substructure withThen the Mostowski collapse theorem gives an isomorphism $\pi :Y\to T$ onto a transitive set, andFor the collapse to apply, the restricted membership relation is well-founded because it is actual membership. It is extensional: if two members of $Y$ differ, an element distinguishing them in $L_{\alpha }(X)$ can be chosen in $Y$ by elementary substructure structure. Since $X$ is transitive and all its members are in $Y$, transfinite induction on their rank of a set shows that $\pi$ fixes every member of $X$, and then $\pi (X)=X$.

By the preceding relative constructible level recognition, $L_{\alpha }(X)\models \Phi (X)$. Elementary substructure agreement transfers this to $Y$, and the collapse isomorphism transfers it to $T$. Thus $T\models \Phi (X)$ and $T=L_{\beta }(X)$ for a nonzero limit ordinal $\beta$.

For the bound, let $\rho =X\cap \mathrm{Ord}$. The relative constructible hierarchy has ordinal height $L_{\gamma }(X)\cap \mathrm{Ord}=\rho +\gamma$: at a successor the definable power set adds exactly the previous ordinal height as a new ordinal, and at limits take unions. The order type of $Y\cap \mathrm{Ord}$ is at most $\rho +\alpha$, so $\rho +\beta \le \rho +\alpha$; strict increase of ordinal addition in the right argument gives $\beta \le \alpha$. The requirement $X\subseteq Y$ is essential to this version: merely having $X\in Y$ need not make the collapse fix the base.

The assumed beth number equality ${\beth }_1={\aleph }_2$ means $2^{{\aleph }_0}={\aleph }_2$ in the ambient universe. Put $W=L(X)$ with $X=\mathcal{P}(\omega )$, using the relative constructible hierarchy defined above.

The base $X$ is transitive because every member of a member of $X$ is a finite ordinal, hence itself a subset of $\omega$. Moreover $X\subseteq W$ and $X\in W$, and $W$ is an inner model of ZF. The latter standard fact follows from the hierarchy and reflection: bounded-rank witnesses give pairing and union; reflection gives separation and replacement; ambient replacement bounds the stages of all relatively constructible subsets of any fixed set, giving power set. It does not require axiom of choice inside $W$. Since no new subsets of $\omega$ can appear in an inner class,

Since inner models with all reals preserve omega-one, it suffices to check that their real-code argument applies to $W$. Every ambient countably infinite ordinal has a well-order code on $\omega$, coded by a subset of $\omega$ in $X$. Finite ordinals and $\omega$ are already shared. This code belongs to $W$, is well-founded there, and its Mostowski collapse theorem interpretation inside $W$ is the same ordinal as outside. Hence the ordinal is countable in $W$. Conversely, any countability witness in $W$ remains a witness in the ambient universe. Thus ${\omega }_1^W={\omega }_1$.

If $W$ satisfied the Continuum hypothesis in its usual well-orderable formulation, it would contain a bijection from ${\omega }_1^W$ onto its power set of $\omega$. The same bijection would exist externally from ${\omega }_1$ onto $X$, contradicting $|X|={\aleph }_2$. ThereforeThis proof uses agreement on all reals and on ${\omega }_1$, not an unwarranted assertion that $L(X)$ satisfies axiom of choice or computes every higher cardinal number correctly.