Past exam of the analytic topology and axiomatic set theory course of the University of Oxford / 2007 / B / 5

Here $Z{F}^{\ast }$ denotes ZF without foundation. Transfinite recursion on ordinals defines the cumulative hierarchy byThe associated class is $V=\{x:\exists \alpha \in \mathrm{Ord}(x\in V_{\alpha })\}$. Each level is a set, while $V$ is a definable class. Without Foundation it need not contain every ambient set; it consists of the sets built by this well-founded hierarchy.

Use transfinite induction. The inclusion at zero is immediate. If $V_{\beta }\subseteq V_{\beta +1}$, monotonicity of the power set givesIf $\alpha$ is a limit and $x\in V_{\alpha }$, choose $\beta <\alpha$ with $x\in V_{\beta }$. The inductive inclusion $V_{\beta }\subseteq \mathcal{P}(V_{\beta })$ means that $x\subseteq V_{\beta }\subseteq V_{\alpha }$. Thus $x\in \mathcal{P}(V_{\alpha })=V_{\alpha +1}$. This proves $V_{\alpha }\subseteq V_{\alpha +1}$ for every ordinal. These successive inclusions and the union definition also give $V_{\beta }\subseteq V_{\alpha }$ whenever $\beta \le \alpha$.

The preceding inclusion is exactly $V_{\alpha }\subseteq \mathcal{P}(V_{\alpha })$. Therefore every $x\in V_{\alpha }$ is a subset of $V_{\alpha }$. Equivalently,which says that $V_{\alpha }$ is a transitive set. This uses the power set definition and the proved inclusion, without any ambient use of Foundation.

We prove the stronger ordinal identityby transfinite induction. It holds at zero. At a successor stage an ordinal $\gamma$ belongs to $\mathcal{P}(V_{\beta })$ exactly when every $\delta <\gamma$ belongs to $V_{\beta }$. By induction this means every $\delta <\gamma$ is less than $\beta$, equivalently $\gamma \le \beta$. Thus the ordinals in $V_{\beta +1}$ are precisely those less than $\beta +1$. At a limit the identity follows by taking unions.

Every $\beta <\alpha$ consequently belongs to $V_{\alpha }$, so $\alpha \subseteq V_{\alpha }$ and $\alpha \in \mathcal{P}(V_{\alpha })=V_{\alpha +1}$. But $\alpha \notin V_{\alpha }$, since an ordinal is not less than itself. HenceThe only well-foundedness used is that of the ordinal order, available independently of Foundation for arbitrary ambient sets.

Every set is a subset of itself, so $V_{\alpha }\subseteq V_{\alpha }$. By the successor definition,Membership and inclusion are different statements here; this argument establishes membership of the whole level in its successor.

The class $V$ is transitive because all its levels are transitive. Let $a\in V$ be nonempty. There is a least ordinal $\alpha$ for which $a\cap V_{\alpha }\ne \varnothing$: existence follows by choosing an element of $a$, which lies in $V$, and then minimizing within some witnessing ordinal bound. The least ordinal is neither zero nor a limit, so write $\alpha =\beta +1$. Choose $x\in a\cap V_{\beta +1}$. Then $x\subseteq V_{\beta }$, while minimality gives $a\cap V_{\beta }=\varnothing$. Thus $a\cap x=\varnothing$. Also $x\in V$, proving Foundation inside $⟨V,\in ⟩$.

By the given hypothesis this same class satisfies every axiom of $Z{F}^{\ast }$, and hence it satisfies every axiom of $ZF$. Translate any finite formal $ZF$ proof by restricting each quantifier to the definable class $V$. Within $Z{F}^{\ast }$ the translated axioms have proofs, logical steps remain valid, and the translated contradiction is still a contradiction. Substituting those axiom proofs therefore converts the original derivation effectively into a finite derivation of contradiction from $Z{F}^{\ast }$. Equivalently,This is the syntactic relative-consistency construction; it does not assume that $V$ is a set or that it equals the whole ambient universe.