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

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.