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

U+D. By absoluteness of infinitude between transitive models, two transitive models of ZFC agree on the natural numbers and therefore on whether a shared set is a finite set or an infinite set.

D. Downward absoluteness of cardinalhood holds because, if the larger transitive model sees no bijection with a smaller ordinal, neither can the smaller model, whose functions form only a subset of those in the larger model. Cardinalhood is not described by an upward absolute formula, because the larger model can contain a new bijection collapsing an ordinal that the smaller model regards as a cardinal number.

U+D. The assertion that a given relation is a partial order quantifies only over its underlying set and checks that it is a reflexive relation, an antisymmetric relation and a transitive relation. It is therefore a bounded formula in set theory and is absolute between transitive models.

U+D. The natural numbers are absolute between transitive models of ZFC, and the statement $x\subseteq \mathbb{N}$ is the bounded assertion $\forall y\in x(y\in \mathbb{N})$. Hence the property of being a subset of $\mathbb{N}$ is absolute.

U. A witness in the smaller model that $x$ is a countable set remains a function in the larger model, so countability is described by an upward absolute formula. It is not downward absolute: the larger model may have a new enumeration of $x$ that is absent from the smaller model, as explained by upward absoluteness of countability.

N. A larger model may collapse a singular cardinal number, destroying cardinalhood, so the assertion is not described by an upward absolute formula. It may instead add a short cofinal function to a regular cardinal in the smaller model, so it is not described by a downward absolute formula. This is the nonabsoluteness of singular cardinalhood.

Suppose that the countable ordinal $\alpha$ satisfied $V_{\alpha }\models \mathsf{ZFC}$. The axioms force $\alpha$ to be a limit ordinal above $\omega$, so choose an externally countable cofinal function $n\mapsto {\alpha }_n$ into $\alpha$, with ${\alpha }_n+1<\alpha$. The internal Axiom of choice gives a bijection in $V_{\alpha }$ between each $V_{{\alpha }_n}$ and some ordinal below $\alpha$. Every such ordinal is externally a countable set, hence every $V_{{\alpha }_n}$ is externally countable. The countable union of countable sets is countable, sowould be countable. But $V_{\alpha }$ contains the full power set $\mathcal{P}(\omega )$, which is uncountable by Cantor theorem. This contradiction is the result Countable rank-initial segment cannot model ZFC, and therefore

Let $M$ be the given transitive model and suppose that its ordinal height of a model of set theory $\mathrm{Ord}\cap M$ were a countable set. For every $x\in M$, the internal Axiom of choice gives a bijection from $x$ to an ordinal of $M$; transitivity makes this an actual bijection, and the ordinal is externally countable. Thus every element of $M$ is externally countable.

For each $\alpha \in \mathrm{Ord}\cap M$, the internal rank $V_{\alpha }^M$ belongs to $M$ and is therefore countable. Every $x\in M$ lies in one of these ranks, so $M$ is a countable union of countable sets and is itself countable, contrary to the hypothesis. By uncountable transitive set model has uncountable ordinal height, $M$ contains uncountably many ordinals.

Let $N$ be a well-founded model of set theory of the complete theory $T$, and suppose that a Paris model $M\models T$ were ill-founded. Its internal ordinals would then contain an external descending sequenceFor every $n$, choose a first-order formula ${\phi }_n$ that uniquely defines ${\alpha }_n$ in $M$. The sentences asserting that ${\phi }_n$ uniquely defines an ordinal and that the object defined by ${\phi }_{n+1}$ belongs to the object defined by ${\phi }_n$ are true in $M$. Since $T$ is complete, all its models satisfy the same first-order sentences, so the corresponding uniquely defined ordinals in $N$ form an external descending membership sequence. This contradicts the well-foundedness of $N$. Thus Paris models are well-founded when their complete theory has a well-founded model proves that every Paris model of $T$ is well-founded.

By part (a), the Paris model $M$ is well-founded. Let $\pi$ be an automorphism of a first-order structure of $(M,{\in }^M)$. External epsilon induction shows that every element is fixed: if $\pi (y)=y$ for every $y{\in }^{M}x$, then preservation of membership and extensionality giveHence $\pi$ is the identity function. This is Paris models are rigid when their complete theory has a well-founded model, so every Paris model of $T$ is a rigid first-order structure.

The definable power set isThus it contains exactly the subsets of $A$ definable over the structure $(A,\in )$ using finitely many parameters from $A$.

Fix $a\in L$. Inside the ambient transitive model $M$, the Axiom of power set makes the collection of constructible subsets of $a$ a set. For each such subset $x$, choose the least stage of the constructible hierarchy at which $x$ appears. The Axiom schema of replacement and the supremum of a set of ordinals give an ordinal $\beta$ bounding all these stages; enlarge $\beta$ so that $a\in L_{\beta }$.

Nowis definable over $L_{\beta }$ with parameter $a$. It therefore belongs to the definable power set $\mathcal{D}(L_{\beta })=L_{\beta +1}\subseteq L$. This set contains exactly the subsets of $a$ that belong to the constructible universe, so it witnesses the Axiom of power set in $L$. Therefore $L\models$ Power Set.

The definable power set $\mathcal{D}(A)$ performs one definability step over the single structure $(A,\in )$, whereas the constructible power set ${\mathcal{P}}^L(A)$ contains subsets of $A$ created at arbitrarily late stages of the constructible hierarchy.

For the concrete case $A=\omega$, there are only countably many first-order formulas and finite tuples of natural-number parameters, so $\mathcal{D}(\omega )$ is a countable set. In contrast, the constructible universe satisfies ZFC, and Cantor theorem makes its full power set ${\mathcal{P}}^L(\omega )$ uncountable inside $L$. Consequentlyso the two notions do not agree in general.

Take a transitive model $M\models \mathsf{ZFC}+2^{{\aleph }_0}={\aleph }_2$. In $M$, choose a bijection $e:{\omega }_2\to \mathcal{P}(\omega )$ and encode its graph by a set $A\subseteq {\omega }_2$, using a fixed bijection between ${\omega }_2\times \omega$ and ${\omega }_2$. The relative constructible universe $L(A)$ can decode $e$, and therefore contains every real number of $M$; being an inner model of $M$, it has no additional reals.

Models with the same reals have the same first uncountable ordinal, because their reals code exactly the same countable well-orders. If $L(A)$ satisfied the Continuum hypothesis, its bijection between ${\omega }_1$ and the reals would also belong to $M$, contradicting $M\models 2^{{\aleph }_0}={\aleph }_2$. This is the construction in relative constructible universe can violate the continuum hypothesis, and it gives

For a condition $p\in \mathbb{P}$, a set $D\subseteq \mathbb{P}$ is dense below a forcing condition $p$ whenThus every extension of $p$ can be strengthened into $D$.

A set $G\subseteq \mathbb{P}$ is a filter when it is upward closed toward weaker conditions and downward directed: if $p\in G$ and $p\le q$, then $q\in G$, while any $p,q\in G$ have some $r\in G$ with $r\le p,q$. It is a generic filter over $M$ when

The forcing order $\mathbb{P}$ has the chain condition for forcing at $\kappa$ when every antichain in a forcing order has cardinality below $\kappa$:When this assertion is evaluated inside $M$, both the quantified subsets and their cardinalities are those of $M$.

Let $\lambda \ge \kappa$ be a cardinal number of $M$. If forcing collapsed $\lambda$, some condition would force a surjective function $\dot{f}:\mu \to \lambda$ for an ordinal $\mu <\lambda$. Replacing $\mu$ by its ground-model cardinality lets us assume that $\mu$ is a cardinal.

For each $\xi <\mu$, choose in $M$ a maximal antichain in a forcing order deciding $\dot{f}(\xi )$. The chain condition for forcing makes its size less than $\kappa$, so the set $B_{\xi }$ of possible values of $\dot{f}(\xi )$ has size below $\kappa$. This is the possible-values lemma for chain-condition forcing. Every interpreted range is contained in $B={\bigcup }_{\xi <\mu }{B}_{\xi }$. If $\mu <\kappa$, the fact that $\kappa$ is a regular cardinal gives $|B|<\kappa \le \lambda$; if $\kappa \le \mu <\lambda$, infinite cardinal arithmetic gives $|B|\le \mu <\lambda$. Either way $B$ cannot contain the range of a surjection onto $\lambda$, a contradiction. By cardinal preservation by chain-condition forcing, $\mathbb{P}$ preserves every cardinal at least $\kappa$.

Suppose first that $p{⊩}^{\ast }\phi$. If $G$ is any generic filter over $M$ containing $p$, the forcing theorem gives $M[G]\models \phi$. Hence $p⊩\phi$ in the semantic forcing relation.

Conversely, suppose $p/{⊩}^{\ast }\phi$. By the stated density equivalence for the syntactic forcing relation, some $r\le p$ satisfies $r{⊩}^{\ast }\neg \phi$. The Rasiowa–Sikorski lemma supplies a generic filter $G$ over the countable model $M$ containing $r$, and upward closure then gives $p\in G$. The forcing theorem yields $M[G]\models \neg \phi$, so $p/⊩\phi$ semantically. Therefore

Fix names $\dot{x},{\dot{a}}_1,\dots ,{\dot{a}}_n\in M$ and a first-order formula $\phi$. Using the syntactic forcing relation, form in $M$ the nameThis is a set by the axiom schema of separation in $M$. If $(\tau ,r)\in \dot{y}$ and $r\in G$, then the forcing theorem gives both ${\tau }^G\in {\dot{x}}^G$ and $\phi ({\tau }^G,{\dot{a}}_1^G,\dots ,{\dot{a}}_n^G)$. Conversely, if $z\in {\dot{x}}^G$ satisfies $\phi$, choose $(\tau ,q)\in \dot{x}$ with $q\in G$ and ${\tau }^G=z$. The truth direction of the forcing theorem supplies $s\in G$ forcing $\phi (\tau ,{\dot{a}}_1,\dots ,{\dot{a}}_n)$; directedness of $G$ gives $r\in G$ below both $q$ and $s$, so $(\tau ,r)\in \dot{y}$.

ThusEvery instance has such a witness, so separation in a generic extension proves $M[G]\models$ Separation.

Let $F=\bigcup G$, the generic union for the Finite-condition Lévy collapse, and fix an infinite cardinal number $\lambda <\kappa$ in $M$. For every $n\in \omega$, the set of conditions defining a value at $(\lambda ,n)$ is dense: extend a condition at that fresh coordinate with any value below $\lambda$. Hence $F_{\lambda }(n)=F(\lambda ,n)$ is a total function $\omega \to \lambda$.

For every $\beta <\lambda$, the set of conditions assigning the value $\beta$ at some fresh coordinate $(\lambda ,n)$ is also dense. Genericity therefore makes $F_{\lambda }$ surjective. Thusso $\lambda$ is a countable set in $M[G]$. Finite cardinals are already countable.

Assume that $\kappa$ is regular and uncountable in $M$, as required for this claim. If an antichain $A\in M$ had size $\kappa$, apply the delta-system lemma at a regular uncountable cardinal inside $M$ to the finite domains of its conditions. After thinning, their domains form a delta-system with finite root $R$.

There are fewer than $\kappa$ possible restrictions to $R$, because each coordinate $(\alpha ,n)\in R$ has fewer than $\kappa$ possible values. Since $\kappa$ is a regular cardinal, we can thin again to $\kappa$ conditions agreeing on $R$. Any two now have disjoint domains outside $R$ and agree on $R$, so their union is a common extension. This contradicts that $A$ is an antichain. ThereforeIf the word “regular” is allowed to include $\kappa =\omega$, the printed claim needs the additional hypothesis that $\kappa$ is uncountable; the finite-condition order can have an infinite antichain when $\kappa =\omega$.

Suppose first that $\kappa$ is regular and uncountable in $M$. Part (b) and cardinal preservation by chain-condition forcing show that $\kappa$ remains a cardinal number in $M[G]$, while part (a) makes every infinite ground-model cardinal below $\kappa$ countable. Every ordinal below $\kappa$ has ground-model cardinality below $\kappa$ and is therefore countable in the extension. Thus $\kappa$ is the least uncountable ordinal there:

Conversely, suppose $M[G]\models \kappa ={\aleph }_1$ and $\kappa$ were singular in $M$. Let $\mu ={\mathrm{cf}}^M(\kappa )<\kappa$ and take in $M$ a cofinal function $f:\mu \to \kappa$. Part (a) makes $\mu$ countable in $M[G]$, while the same $f$ remains cofinal there. This would give $\kappa$ countable cofinality, contradicting first uncountable ordinal is regular. Hence $\kappa$ was regular in $M$, and for the intended uncountable $\kappa$,