Past exam of the mathematics course of the University of Cambridge / 2015 / ii / Paper 4 / 13I (Logic and Set Theory)

The Axiom of foundation states that every nonempty set $A$ has a member $a$ with $a\cap A=\varnothing$. The principle of epsilon induction states that a formula $\varphi$ satisfying $\forall x[(\forall y\in x\varphi (y))\Rightarrow \varphi (x)]$ holds for every set $x$.

Assume Axiom of foundation and suppose a progressive formula has a counterexample $a$. In the transitive closure of $\{a\}$, use axiom schema of separation to collect the counterexamples into a nonempty set $B$. Foundation supplies $b\in B$ having no member in $B$. Since the closure is transitive, every member of $b$ satisfies $\varphi$, contradicting progressiveness. Conversely, if a nonempty set $A$ had no foundation-minimal member, every $x\in A$ would have a member $y\in x\cap A$. The formula $x\notin A$ is then progressive: if every member of $x$ lies outside $A$, $x$ cannot belong to $A$. Epsilon induction would make $A$ empty, a contradiction. This proves equivalence in the presence of the other Zermelo–Fraenkel set theory.

To obtain the cumulative hierarchy, perform epsilon induction on the assertion that $x$ belongs to some $V_{\alpha }$. If this holds for each member $y$, Axiom schema of replacement collects their least such ordinals into a set. Choose an ordinal $\beta$ above them all. Then $x\subseteq V_{\beta }$ and $x\in V_{\beta +1}$. Thus every set occurs in the hierarchy. Use the rank of a set convention $\mathrm{rk}(x)={\sup }_{y\in x}(\mathrm{rk}(y)+1)$, equivalently the least $\alpha$ with $x\subseteq V_{\alpha }$.

An ordinal has rank equal to itself. Thus the rank of a set here is $\sup \{\omega +2,\omega +3,\omega +4\}=\boxed{\omega +4}$.

Use the Kuratowski ordered pair $(m,n)=\{\{m\},\{m,n\}\}$. Its rank of a set is $\max (m,n)+2$. Every pair in the Cartesian product has finite rank, but those ranks are unbounded in $\omega$. Therefore $\mathrm{rk}(\omega \times \omega )={\sup }_{m,n<\omega }(\max (m,n)+3)=\boxed{\omega }$.

Represent a function by its graph of Kuratowski ordered pairs. For $f:\omega \to {\omega }^2$,The bound is attained by $f(n)=\omega n$, which is a cofinal function into ${\omega }^2$. Taking the rank of the set of all such functions adds one at this attained maximum. Thus $\boxed{\mathrm{rk}(({\omega }^2{)}^{\omega })={\omega }^2+1}$. The extra successor is essential: unlike the previous product, this set actually contains a member of rank ${\omega }^2$.