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

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.