Past exam of the mathematics course of the University of Cambridge / 2015 / iii / Paper 24 / 4

A standard membership model of set theory has the actual membership relation:When “standard model” is used with the transitive-model convention, one also requires $M$ to be transitive: $x\in y\in M$ implies $x\in M$. Under a convention where standard means only actual membership, this extra requirement defines a transitive model. The set-theoretic absoluteness arguments below use transitive models of ZFC, so that bounded quantification and ordinals have their intended meaning.

The Mostowski collapse theorem states that if $R$ is a well-founded extensional relation on a set $X$, then there is a unique transitive set $M$ and a unique bijection $\pi :X\to M$ such thatExtensionality means that distinct elements of $X$ have distinct predecessor sets. The collapse is characterized by the recursionWell-founded recursion defines it, extensionality makes it injective, and its range is transitive. Uniqueness follows by well-founded induction. For a class version, the relation must also be set-like; its predecessor sets must be sets.

An absolute formula has the same truth value in the structures under comparison for parameters common to them. For transitive models $M\subseteq N$ and $a_1,\dots ,a_n\in M$, the requirement isOne specifies the relevant class of models, for example transitive models of ZFC. A formula is upward absolute when the forward implication holds and downward absolute when the reverse implication holds. Bounded formulas in set theory are absolute between transitive membership structures: all their quantifiers range over the same elements of their parameter sets.

The rank characterization holds for a set relation, or a set-like class relation. For such a well-founded relation, use well-founded recursion to defineThe predecessor set is a set, so the supremum is an ordinal. For a set-like class relation, the closure of the predecessors of any one point under finitely many predecessor steps is a set; perform the ordinary set recursion there. Uniqueness makes these local definitions agree, producing a class rank function. The formula immediately gives $xRy\Rightarrow \rho (x)<\rho (y)$.

Conversely, suppose such an ordinal-valued function exists. For any nonempty subset, or nonempty subclass in the class formulation, take an element whose rank is least among the ranks occurring. It has no predecessor in that subset or subclass, because a predecessor would have smaller rank. This proves well-foundedness.

There is a qualification in the printed class formulation. If well-founded class relations are defined to include set-likeness, it is already implicit and the assertion is correct. Under the minimal-element definition alone, it must be supplied. Without set-likeness, let $X=\mathrm{Ord}\cup \{u\}$, where $u=\{1\}$ is not an ordinal, and put every ordinal below $u$, with the usual ordinal order below it. Every nonempty subclass has a minimal element, so the relation is well founded. But transfinite induction forces $\rho (\alpha )\ge \alpha$ for all ordinals, whereas $\rho (u)$ would have to exceed every $\rho (\alpha )$. No such ordinal exists. Thus the unrestricted class assertion is false; set-likeness is necessary for this standard rank proof.

Let $M\subseteq N$ be transitive models of ZFC containing the set relation $R$ and its underlying set $X$. If $M$ judges $R$ well founded, it has an ordinal rank function for a relation $\rho \in M$ by the preceding rank characterization. Being a function to ordinals and satisfyingis absolute: the values are actual ordinals and the checks use only bounded formulas in set theory. The same rank function exists in $N$, so $N$ judges $R$ well founded.

Conversely, if $M$ judged it not well founded, it would contain a nonempty set $Y$ with no $R$-minimal element. The property of this particular $Y$ is bounded and remains true in $N$, contradicting well-foundedness there. ThusThis is absoluteness of well-foundedness. The hypotheses that both models are transitive and satisfy ZFC matter; a small transitive set without sufficient recursion axioms need not contain the required rank witness.

Put $\mathcal{V}=⟨V_{\kappa },\in ,R⟩$. Because $\kappa$ is inaccessible, $|V_{\xi }|<\kappa$ for every $\xi <\kappa$, and $\kappa$ is regular. Choose one witness in $V_{\kappa }$ for every existential formula of this expanded language and every finite parameter tuple for which a witness exists. These are Skolem functions; they can be chosen in the ambient universe even when $R$ is not definable inside $V_{\kappa }$.

For each $\xi <\kappa$, the ranks of all chosen witnesses with parameters from $V_{\xi }$ have supremum below $\kappa$: there are fewer than $\kappa$ such parameters and only countably many formulas. Choose $F(\xi )<\kappa$ strictly above those ranks. The limit closure pointsform a club set. At $\alpha \in C$, every existential assertion in $\mathcal{V}$ with parameters in $V_{\alpha }$ has a witness in $V_{\alpha }$. The Tarski-Vaught test yieldsThus the set $E$ of all such elementary levels is unbounded. It is also closed: the union at a limit of increasing elementary levels is an elementary substructure by the elementary chain theorem, and the union of their ranks is $V_{\alpha }$ with predicate $R\cap V_{\alpha }$. ThereforeThis is club reflection below an inaccessible cardinal.

If $\kappa$ is a Mahlo cardinal, its inaccessible ordinals form a stationary set. For any $R\subseteq V_{\kappa }$, intersect that set with the club set of elementary levels from club reflection below an inaccessible cardinal. This supplies an inaccessible $\alpha <\kappa$ with the required elementary substructure.

Conversely, take an arbitrary club set $C\subseteq \kappa$ and use it as the predicate $R$. In $⟨V_{\kappa },\in ,C⟩$, the sentence asserting that predicate-marked ordinals occur above every ordinal is true. Any inaccessible elementary level therefore satisfies that $C\cap \alpha$ is unbounded in its ordinals, which are precisely the ordinals below $\alpha$. Since $C$ is closed and $\alpha$ is a limit ordinal, $\alpha \in C$. The assumed reflection property consequently gives an inaccessible ordinal in every club set. Hence the inaccessible ordinals are stationary and

First express inaccessibility by universally excluding witnesses to its failure. Besides $\kappa$ being an ordinal greater than $\omega$, require that for every $\alpha <\kappa$ there is no function from $\alpha$ cofinal in $\kappa$, and no injection from $\kappa$ into $\mathcal{P}(\alpha )$. The first condition gives regular cardinalhood; the second says that $\kappa$ is a strong limit cardinal. Under the axiom of choice these are exactly the conditions for a strongly inaccessible cardinal.

These are Pi-one formulas modulo ZF: the only unbounded quantifiers universally range over possible functions. Being a function of the specified domain, having bounded or cofinal range in $\kappa$, and being an injection whose values are subsets of $\alpha$ can all be written with bounded formulas in set theory, without using a power-set object as an unbounded existential witness. Consequently inaccessibility is downward absolute to a transitive inner model of ZFC.

Now suppose $\kappa$ is Mahlo in $V$. It is inaccessible in the constructible universe $L$, and every $V$-inaccessible ordinal below it is also inaccessible in $L$. Let $C\in L$ be any set that $L$ regards as a club set in $\kappa$. Closure and unboundedness are absolute properties of this fixed set of ordinals, so $C$ is also a club set in $V$. By Mahloness in $V$, it contains an ordinal that is inaccessible in $V$, hence in $L$. Every $L$-club therefore meets the $L$-inaccessible ordinals below $\kappa$. Thus Mahloness is downward absolute to the constructible universe: