Past exam of the mathematics course of the University of Cambridge / 2018 / iii / Paper 121 (Topics in Set Theory)

The Tarski-Vaught test says that $(M,\in )$ is an elementary substructure of $(N,\in )$ if and only if every existential statement true in $N$ with parameters from $M$ has a witness in $M$ that satisfies its matrix in $N$. Explicitly, for every first-order formula $\psi (x,\bar{y})$ and every parameter tuple $\bar{a}\in M^{|\bar{y}|}$, requireThe truth of the matrix in this test is evaluated in the larger structure $N$. Under this criterion, $(M,\in )\prec (N,\in )$ means that all first-order formulas with parameters from $M$ have identical truth values in the two structures.

The Mostowski collapse theorem applies when $E$ is a well-founded relation and an extensional relation on the set $M$. Extensionality here means that different points have different sets of $E$-predecessors. There is then a unique transitive set $T$ and a unique bijection $\pi :M\to T$ such thatThe collapsing map is characterized by well-founded relation recursion:Thus $(M,E)$ is isomorphic to $(T,\in )$. Both well-foundedness and extensionality are hypotheses of the theorem; well-foundedness alone does not make the recursive map injective.

A cardinal number is identified with an initial ordinal, namely an ordinal not in bijection with any smaller ordinal. An inaccessible cardinal, in the strong sense used here, is an uncountable regular cardinal that is also a strong limit cardinal. ThusA worldly cardinal is a cardinal number whose level of the Von Neumann hierarchy satisfies all of ZFC:Worldliness is this model-theoretic condition; regularity is not part of its definition. The original PDF asks for these two notions; the extra comma in the local TeX makes “cardinal” look like a separate requested item.

For every tuple of parameters $\bar{a}\in M^n$, a downward absolute formula transfers truth from the larger structure to the smaller one:The condition concerns every parameter tuple from $M$, not merely parameter-free sentences.

For every tuple of parameters $\bar{a}\in M^n$, an upward absolute formula transfers truth from the smaller structure to the larger one:These definitions of directional set-theoretic absoluteness do not themselves require the structures to be transitive.

A formula has set-theoretic absoluteness between these structures when both directions hold for every $\bar{a}\in M^n$:Equivalently, it is both a downward absolute formula and an upward absolute formula between them.

We construct the two transitive models together, taking care that the later collapse really retains the earlier model. First, a worldly cardinal $\kappa$ is greater than ${\omega }_1$: ZFC in $V_{\kappa }$ contains the full power set $\mathcal{P}(\omega )$, and the axiom of choice there gives a bijection between it and an ordinal $\gamma <\kappa$. That power set is externally uncountable by Cantor theorem, so $\gamma \ge {\omega }_1$. Infinity rules out the finite cardinals and $\omega$ before this argument is applied.

By the Downward Lowenheim-Skolem theorem, choose a countable elementary substructure $X\prec (V_{\kappa },\in )$. Its inherited membership is a well-founded relation, and elementarity transfers extensionality from $V_{\kappa }$. Apply the Mostowski collapse theorem to obtain a countable transitive model $M$ of ZFC. Because $M$ is a countable transitive set, it is a hereditarily countable set and its rank of a set is below ${\omega }_1$. In particular, $M\in V_{\kappa }$.

Now take the Skolem hull in $V_{\kappa }$ of the seedCall it $H$. The seed has external cardinality ${\aleph }_1$ and lies inside $V_{\kappa }$. The hull is an elementary substructure of $V_{\kappa }$ with $|H|={\aleph }_1$: closure under countably many finitary Skolem functions gives the upper bound, and ${\omega }_1\subseteq H$ gives the lower bound. Let $\pi :H\to N$ be its Mostowski collapse theorem map. Then $N$ is a transitive model of ZFC.

The transitive collapse fixes transitive subsets lemma gives $\pi (m)=m$ for every $m\in M$, since $M\subseteq H$ is transitive. Since also $M\in H$, the collapse sends that element to $M$ itself. Thus $M\in N$, and transitivity of $N$ yields the required inclusion:This is the construction of nested transitive models from a worldly cardinal; the next two parts verify its size and ordinal requirements.

For the model $M$ constructed in part (a), the collapsing map $X\to M$ is a bijection. The Downward Lowenheim-Skolem theorem supplied countable $X$, so $M$ is externally countable. It is infinite because it satisfies the axiom of infinity. ConsequentlyThis is external cardinality. A countable transitive model still regards many of its own sets and ordinals as uncountable, because external enumerations need not belong to it.

The collapse $\pi :H\to N$ is a bijection, so $|N|=|H|={\aleph }_1$. Every $\alpha <{\omega }_1$ and every element of $\alpha$ belong to $H$. The transitive collapse fixes transitive subsets lemma therefore gives $\pi (\alpha )=\alpha$, so every ambient countable ordinal belongs to $N$.

Moreover, $V_{\kappa }$ correctly regards each such $\alpha$ as countable. An injection $\alpha \to \omega$ has rank below $\max (\alpha ,\omega )+\omega <\kappa$, so a witness belongs to $V_{\kappa }$. Elementarity gives $H\models$ “$\alpha$ is a countable ordinal”. Transporting this statement across the collapse, which fixes $\alpha$, gives the same statement in $N$.

The collapse also fixes the element ${\omega }_1\in H$. No injection ${\omega }_1\to \omega$ exists externally, hence none belongs to $V_{\kappa }$; together with the countability witnesses below it, this shows that $V_{\kappa }$ correctly identifies ${\omega }_1$ as its first uncountable ordinal. Elementarity and the collapse preserve that identification. Thus the construction gives

Take the formula saying that a set is transitive:This is a bounded formula in set theory. If $x\in M$, transitivity of $M$ ensures that every $u\in x$ and every $v\in u$ is already in $M$, and the same holds in $N$. Both structures therefore run through exactly the same bounded witnesses and use the same actual membership relation. They agree on ${\phi }_1(x)$ for every $x\in M$, proving set-theoretic absoluteness.

Let $C(x)$ be the formula expressing cardinal number status:Ordinalhood and the assertion that a given set is a bijection between fixed sets are each expressible by a bounded formula in set theory. If $M$ regarded $x$ as a non-cardinal ordinal, a witnessing smaller ordinal and bijection would remain present and valid in $N$. Ordinalhood itself is absolute between the transitive models. Thus $N\models C(x)$ implies $M\models C(x)$: this is downward absoluteness of cardinalhood.

For failure in the other direction, put $\beta =({\omega }_1{)}^M$. This ordinal belongs to $M$, and $M\models C(\beta )$ with $\beta >\omega$. Externally $\beta$ is countable, since $\beta \subseteq M$ and $M$ is countable. By the construction of $N$, it contains a countability witness for $\beta$, and hence a bijection $\omega \to \beta$. Therefore $N\models \neg C(\beta )$. This formula is downward absolute and fails to be upward absolute.

Use the cardinalhood formula $C$ from part (b), and let a finite flag choose between it and its negation:Here $0,1$ abbreviate their parameter-free definitions as Finite von Neumann ordinals, and both belong to $M$. This is one first-order formula with two free variables.

For $\beta =({\omega }_1{)}^M$, part (b) proved $M\models C(\beta )$ and $N\models \neg C(\beta )$. The shared parameters $(\beta ,0)$ therefore make ${\phi }_3$ true in $M$ and false in $N$, disproving upward set-theoretic absoluteness. The shared parameters $(\beta ,1)$ make it false in $M$ and true in $N$, disproving downward set-theoretic absoluteness. Hence the same formula fails both directions, with explicit witnesses to each failure.

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.

Use standard notation for forcing, so $q\le p$ means that $q$ is stronger. Let $\check{p}$ be the canonical forcing name for the ground-model condition $p$. DefineHere $q\perp p$ means that they are incompatible forcing conditions. The checks and their collection are formed by recursion and Axiom schema of replacement in $M$, and the displayed set is selected by axiom schema of separation, so this is a forcing name in $M$.

By evaluation of a forcing name,If $p\in G$, directedness of the generic filter gives a common stronger condition for $p$ and each $q\in G$, so $p$ is absent from this value.

Conversely, for fixed $p\in \mathbb{P}$ the setis a dense subset of a forcing order belonging to $M$. A condition incompatible with $p$ is already in it, and one compatible with $p$ has a common extension below $p$. Genericity supplies $q\in G\cap D_p$. If $p\notin G$, upward closure of $G$ rules out $q\le p$, hence $q\perp p$. ThereforeThis forcing name for the complement of a generic filter works without a separativity assumption on the order.

We prove the implication from existence of a witness in the extension to a condition forcing the existential statement. If $M[G]\models \exists x\phi (x)$, choose a witness $a\in M[G]$ and a forcing name $\sigma \in M$ with $\mathrm{val}(\sigma ,G)=a$. The assumed instance of the truth lemma supplies $p\in G$ withThe syntactic forcing relation is monotone under stronger conditions, so every $q\le p$ also forces this same named instance. In particular, the conditions below $p$ having some forced witness are dense below a forcing condition $p$. The existential clause of syntactic forcing therefore givesOnly the truth lemma assumed for individual named instances and the recursive existential clause were used.

For the reverse implication, suppose $p\in G$ and $M\models p{⊩}^{\ast }\exists x\phi (x)$. By the existential clause of syntactic forcing, the setis dense below $p$; the existential quantifier ranges over forcing names of $M$. Definability of the syntactic forcing relation and axiom schema of separation put $D$ in $M$.

To apply genericity, augment it to the globally dense setA condition compatible with $p$ has an extension below $p$, then one in $D$, and an incompatible condition already lies in $D^{\prime }$. Thus $D^{\prime }$ is a dense subset of a forcing order in $M$. The generic filter meets it. Since $p\in G$, directedness prevents $G$ from containing a condition incompatible with $p$, so some $q\in G\cap D$ exists.

There is consequently a name $\sigma \in M$ with $M\models q{⊩}^{\ast }\phi (\sigma )$. The assumed truth lemma gives $M[G]\models \phi (\mathrm{val}(\sigma ,G))$, and henceTogether with part (a), this completes the existential step of the forcing theorem without assuming the desired existential truth lemma in advance.

A Delta-system is a family $\mathcal{A}$ of sets with a fixed root $r$ such thatThe Delta-system lemma says that every uncountable family of finite sets has an uncountable subfamily forming a Delta-system. The root may be empty. Finiteness is a hypothesis on the family to which this lemma is applied, rather than a requirement in the general definition of a Delta-system.

A cardinal-preserving forcing over $M$ leaves every ground-model cardinal number a cardinal in every generic extension. In the present notation, for every $M$-generic filter $G$ and every ordinal $\kappa \in M$,Set forcing preserves ordinals, and an old bijection witnessing that an ordinal is not a cardinal remains available. Thus this condition also means that the two models have exactly the same cardinals. Cardinality here is computed inside the respective models, not from their external sizes.

The countable chain condition for forcing says that every antichain in a forcing order is a countable set. Equivalently,In this question the assertion is evaluated inside $M$. Although every subset of the countable set $M$ is externally countable, that observation does not establish the internal chain condition: $M$ need not contain an enumeration of an antichain.

Assume $M$ satisfies the countable chain condition for forcing. We prove cardinal preservation by chain-condition forcing using the possible-values lemma for chain-condition forcing, and give the argument explicitly for ccc.

Let $\kappa$ be an uncountable cardinal of $M$. If it ceased to be a cardinal, some ordinal $\mu <\kappa$ would admit a surjection onto $\kappa$ in an extension. By the forcing theorem, there would be a condition $p$ and a forcing name $\dot{f}$ such thatInside $M$, for each $\xi <\mu$ choose a maximal antichain in a forcing order below $p$ deciding the ordinal value of $\dot{f}(\xi )$. Conditions deciding that value are dense below $p$. The chain condition makes the chosen antichain countable in $M$, so the corresponding set $B_{\xi }\subseteq \kappa$ of possible decided values is countable in $M$.

A generic filter containing $p$ meets the downward closure of every such maximal antichain, so its value $f(\xi )$ belongs to $B_{\xi }$. Therefore its whole range lies in the ground-model setThe last inequality is infinite cardinal arithmetic and uses only that $\kappa$ is uncountable and $\mu <\kappa$; no regularity of $\kappa$ is needed. Some ordinal in $\kappa \setminus B$ exists already in $M$ and cannot occur in the range, contradicting the forced surjectivity.

Finite cardinals cannot collapse, and $\omega$ cannot become finite: a finite domain has finite image, and transitive models agree on the natural numbers. Old non-cardinals cannot become cardinals because their old bijections persist. Thus

Let $s_p$ be the finite stem of a condition $p=(n_p,s_p,A_p)$, and defineThe stems of two conditions in the generic filter agree on their common domain, because they have a common stronger extension. Hence this union is a function. For every $\ell \in \omega$, the set of conditions with $n_p\ge \ell$ is dense: append values from the nonempty infinite reservoir until the desired length is reached. Genericity therefore makes $f$ total on $\omega$. The generic stems, and thus their union, are available in $M[G]$.

Fix $g\in M\cap {\omega }^{\omega }$ and $K\in \omega$. In $M$ form the setWe show that it is a dense subset of a forcing order. Given $p=(n,s,A)$, put $k=\max (n,K)$. Fill the new positions $n,\dots ,k-1$ with any fixed element of $A$, and choose $a\in A$ with $a>g(k)$ for the new position $k$. This is possible because an infinite subset of $\omega$ is unbounded. Let $t$ be the resulting stem of length $k+1$, and keep the reservoir $A$ unchanged. ThenEvery new stem value came from the old reservoir, exactly as required by the extension relation. The construction is performed in $M$, so $D_{g,K}\in M$ and is internally dense.

Genericity gives a condition in $G\cap D_{g,K}$. Its witnessing coordinate remains fixed in every later stem and hence in $f$, so some $k\ge K$ satisfies $g(k)<f(k)$. Since this holds for every $K$, there are infinitely many such $k$. As $g$ was arbitrary,Thus this infinite-reservoir stem forcing produces an unbounded real over a model, which is precisely the stipulated meaning of bounding $M$.