Past exam of the mathematics course of the University of Cambridge / 2019 / iii / Paper 121 / 1

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.