Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 128 (Forcing and the Continuum Hypothesis)

First form the singleton set $\{b\}=F_1(b,b)$ and then use $F_2$ to take a set union:The unused second argument of $F_2$ may be any term. Since $x\cap c=x\setminus (x\setminus c)$, a term using only the prescribed operation symbols isAfter substituting the displayed term for both occurrences of $U$, this is literally a term in $F_1,F_2,F_3$, and its value is $(a\cup \{b\})\cap c$.

Work in the ambient universe and let $a,u\in L$. SupposeFor each $x\in a$, let $y_x$ be this unique witness. The relativization ${\phi }^L$ is a first-order formula, so the ambient Axiom schema of replacement collects the witnesses $y_x$ into a set. Every witness lies in the constructible hierarchy, hence there is an ordinal $\alpha$ such thatFor example, take the supremum of one constructible rank for each witness and then increase it by one.

The set $L_{\alpha }$ itself belongs to $L_{\alpha +1}\subseteq L$. Taking $b=L_{\alpha }$, every $x\in a$ has a witness $y\in b$ satisfying ${\phi }^L(x,y,u)$. Thereforewhich is the stated instance of Replacement.

Suppose $V=L$. If $x\in L_{{\omega }_1}$, then $x\in L_{\alpha }$ for some countable ordinal $\alpha$. The set $L_{\alpha }$ is transitive and countable, so the transitive closure of $x$ lies in a countable set. Thus $x$ is hereditarily countable, proving

Conversely, let $x\in H_{{\aleph }_1}$ and choose a sufficiently large $L_{\theta }$ containing $x$. By the Downward Lowenheim-Skolem theorem, there is a countable elementary substructure $N\prec L_{\theta }$ that contains every member of $\mathrm{TC}(\{x\})$. The Mostowski collapse theorem gives a transitive collapse of $N$, and the condensation lemma for the constructible universe identifies it with $L_{\beta }$ for a countable ordinal $\beta$. Because $N$ contains the transitive closure of $x$ pointwise, the collapse fixes $x$. Thus $x\in L_{\beta }\subseteq L_{{\omega }_1}$. Hence

The Fn forcing order isIt is ordered by reverse inclusion:so a stronger condition specifies more values. Its maximal, or weakest, element is the empty function $\varnothing$.

For a regular cardinal $\kappa$,Again $q\le p$ means $q\supseteq p$, and the maximal element is the empty function. The regularity of $\kappa$ ensures that the union of a descending sequence of fewer than $\kappa$ conditions still has domain of cardinality below $\kappa$ whenever the conditions form a compatible increasing chain of partial functions.

Let $A\subseteq \mathrm{Fn}(I,J)$ be uncountable. Apply the Delta-system lemma to the finite sets $\mathrm{dom}p$ for $p\in A$. After passing to an uncountable subset $A^{\prime }$, there is a fixed finite root $R$ such thatfor distinct $p,q\in A^{\prime }$. Because $J$ is countable and $R$ is finite, there are only countably many functions $R\to J$. A further uncountable subset $A^{\prime \prime }\subseteq A^{\prime }$ therefore has the same restriction to $R$.

Any two conditions in $A^{\prime \prime }$ agree on the intersection of their domains, so their union is a common stronger condition. Thus every uncountable family contains two compatible conditions, and no uncountable antichain exists. Therefore

Let $c=\bigcup G$ and $d(n)=c(2n)$. DefineThis is a filter: restrictions of finite pieces of $d$ remain in $H$, and the union of two members is a common stronger condition.

To prove genericity, take a dense set $D\in M$. Let $E_D$ consist of conditions $q\in \mathrm{Fn}(\omega ,2)$ for which some $p\in D$ satisfiesThe set $E_D$ is dense. Indeed, given $q$, first read its finitely many assigned even coordinates as a condition $p_0$ on $\omega$. Choose $p\le p_0$ in $D$, and extend $q$ by setting $q(2n)=p(n)$ at the remaining coordinates of $p$. Since $E_D\in M$, the generic filter $G$ meets it. For $q\in G\cap E_D$, the corresponding $p\in D$ is a finite subfunction of $d$, so $p\in H\cap D$.

Thus $H$ meets every dense subset belonging to $M$. Moreover, each singleton $\{(n,d(n))\}$ belongs to $H$, and hence

The forcing theorem has two parts. The definability lemma says that for every formula $\phi$, the relationis definable in $M$. The truth lemma says that if $G$ is generic over $M$, then

Assume the forcing relation and the forcing theorem have been constructed for $\phi (x,\vec{y})$. Defineto mean thatis dense below $p$. This definition is first-order over $M$, so the definability lemma is preserved.

Suppose $p\in G$ forces the existential statement. Genericity below $p$ gives $q\in G\cap D_p$ and a name $\sigma$ with $q⊩\phi (\sigma ,\vec{\tau })$. The truth lemma for $\phi$ yieldsso the existential statement is true. Conversely, if $M[G]\models \exists x\phi (x,{\vec{\tau }}^G)$, choose a name $\sigma$ for a witness. The truth lemma for $\phi$ gives $q\in G$ with $q⊩\phi (\sigma ,\vec{\tau })$, and then $q⊩\exists x\phi (x,\vec{\tau })$. This proves both directions of the forcing theorem for the existential formula.

Conditions in $G$ are compatible finite functions, so their union $F=\bigcup G$ is a function $({\omega }_1{)}^M\rightharpoonup ({\omega }_1{)}^M$. For each $\alpha <{\omega }_1$, the setis dense: choose a normal function extending $p$ and add its value at $\alpha$. Genericity makes $F$ total.

If $\alpha <\beta$, choose a condition in the filter extending conditions that decide both values. It is contained in a normal function on an ordinal, so $F(\alpha )<F(\beta )$. Thus $F$ is strictly increasing.

It remains to prove continuity. For every limit $\delta <{\omega }_1$ and $\gamma <{\omega }_1$, let $D_{\delta ,\gamma }$ contain the conditions $p$ such that $\delta \in \mathrm{dom}p$ and eitheror there is some $\alpha <\delta$ in $\mathrm{dom}p$ with $p(\alpha )>\gamma$. This set is dense. Given $p$, extend it to a normal function $f$ and add $(\delta ,f(\delta ))$; if $f(\delta )>\gamma$, continuity of $f$ supplies an $\alpha <\delta$ with $f(\alpha )>\gamma$, which may also be added.

Now fix $\gamma <F(\delta )$. Since $G$ meets $D_{\delta ,\gamma }$, compatibility with the condition deciding $F(\delta )$ rules out the first alternative and gives $\alpha <\delta$ with $F(\alpha )>\gamma$. Therefore values below $\delta$ are cofinal in $F(\delta )$. Strict increase supplies the reverse bound, soHence $F$ is normal on $({\omega }_1{)}^M$ in $M[G]$.

The Lévy reflection theorem states that for every finite collection $\Phi$ of formulas and every ordinal $\gamma$, there is an ordinal $\alpha >\gamma$ such that, for every $\phi \in \Phi$ and all parameters $\vec{a}\in V_{\alpha }$,Indeed, the ordinals $\alpha$ reflecting all formulas in $\Phi$ form a closed unbounded class.

Let $\alpha =({\omega }_1{)}^M$ and takeThis formula is upward absolute between transitive models: if the smaller model contains such an $f$, the assumed absoluteness of “function”, domain, range, and $\omega$ shows that the same witness works in the larger model.

The generic union $g=\bigcup G$ is a total map $\omega \to \alpha$, because the conditions deciding each input form a dense set. For every $\beta <\alpha$, the conditions putting $\beta$ somewhere in the range are also dense, so $g$ is surjective. Thus $M[G]\models {\phi }_1(\alpha )$. But $M/\models {\phi }_1(\alpha )$ because $M$ regards $\alpha$ as its first uncountable ordinal. Hence ${\phi }_1$ is not downward absolute between $M$ and $M[G]$.

With the same parameter $\alpha =({\omega }_1{)}^M$, letThis formula is downward absolute: if the larger transitive model has no such function, then neither can the smaller model, since any witness in the smaller model would remain a witness in the larger one. The model $M$ satisfies ${\phi }_2(\alpha )$, while the generic surjection $\bigcup G$ makes it false in $M[G]$. Therefore it is not upward absolute.

Assume $\phi (\vec{a})$ is a Delta-one formula in set theory. Thus ZF proves it equivalent to a ${\Sigma }_1$ formula $\sigma$ and to a ${\Pi }_1$ formula $\pi$. Only finitely many axioms of ZF occur in these two formal proofs; collect them, together with the finite fragment needed for bounded-formula absoluteness, into $T$.

Let $M$ be a transitive class containing $\vec{a}$ and satisfying $T$. If $M\models \phi$, then $M\models \sigma$, and upward absoluteness of ${\Sigma }_1$ formulas gives $V\models \sigma$, hence $V\models \phi$. If $V\models \phi$, then $V\models \pi$, and downward absoluteness of ${\Pi }_1$ formulas gives $M\models \pi$, hence $M\models \phi$. Therefore ZF proves that $\phi$ is absolute for every such $M$.

Conversely, suppose a finite $T\subseteq \mathrm{ZF}$ has the stated absoluteness property. LetBecause $T$ is finite, every satisfaction assertion here can be replaced by the corresponding formula relativization to a class. All quantifiers in the matrix are bounded by $N$, so $\sigma$ is ${\Sigma }_1$. Define the ${\Pi }_1$ formula

By the Lévy reflection theorem, ZF proves that for any parameters $\vec{a}$ there is a level $V_{\alpha }$ containing them and satisfying the finite fragment $T$. The assumed absoluteness says that every such transitive set agrees with $V$ about $\phi$. Consequently ZF provesThus $\phi$ is both ${\Sigma }_1^{\mathrm{ZF}}$ and ${\Pi }_1^{\mathrm{ZF}}$, so it is ${\Delta }_1^{\mathrm{ZF}}$.