Stages and Ranks

Definition one in this chapter

Definition two in this chapter

Let $\tau(x)$source be a term; let $f$source be a function; let $\alpha$source be an ordinal. We say that $f$source is an $\alpha$source-approximation for $\tau$source iff both $\dom{f} = \alpha$source and $(\forall \beta \in \alpha)f(\beta) = \tau(\funrestrictionto{f}{\beta})$source.

Lemma: Bounded Recursion

[Bounded Recursion] For any term $\tau(x)$source and any ordinal $\alpha$source, there is a unique $\alpha$source-approximation for $\tau$source.

Proof

We will show that, for any $\gamma \leq \alpha$source, there is a unique $\gamma$source-approximation.

We first establish uniqueness. Let $g$source and $h$source (respectively) be $\gamma$source- and $\delta$source-approximations. A transfinite induction on their arguments shows that $g(\beta) = h(\beta)$source for any $\beta \in \dom{g} \cap \dom{h} = \gamma \cap \delta = \min(\gamma, \delta)$source. So our approximations are unique (if they exist), and agree on all values.

To establish existence, we now use a simple transfinite induction (theorem “Simple Transfinite Induction” in chapter “Ordinals”) on ordinals $\delta \leq \alpha$source.

The empty function is trivially an $\emptyset$source-approximation.

If $g$source is a $\gamma$source-approximation, then $g \cup \{\tuple{\gamma, \tau(g)}\}$source is a $\ordsucc{\gamma}$source-approximation.

If $\gamma$source is a limit ordinal and $g_\delta$source is a $\delta$source-approximation for all $\delta < \gamma$source, let $g = \bigcup_{\delta \in \gamma} g_\delta$source. This is a function, since our various $g_\delta$sources agree on all values. And if $\delta \in \gamma$source then $g(\delta) = g_{\ordsucc{\delta}}(\delta) = \tau(\funrestrictionto{g_{\ordsucc{\delta}}}{\delta}) = \tau(\funrestrictionto{g}{\delta})$source.

This completes the proof by transfinite induction.

Theorem: General Recursion

[General Recursion] For any term $\tau(x)$source, we can explicitly define a term $\sigma(x)$source, such that $\sigma(\alpha) = \tau(\funrestrictionto{\sigma}{\alpha})$source for any ordinal $\alpha$source.

Proof

For each $\alpha$source, by lemma “Bounded Recursion” in chapter “Stages and Ranks” there is a unique $\alpha$source-approximation, $f_\alpha$source, for $\tau$source. Define $\sigma(\alpha)$source as $f_{\ordsucc{\alpha}}(\alpha)$source. Now:

noting that $f_{\ordsucc{\beta}}(\beta) = f_{\ordsucc{\alpha}}(\beta)$source for all $\beta < \alpha$source, as in lemma “Bounded Recursion” in chapter “Stages and Ranks”.

Theorem: Simple Recursion

[Simple Recursion] For any terms $\tau(x)$source and $\theta(x)$source and any set $A$source, we can explicitly define a term $\sigma(x)$source such that:

Proof

We start by defining a term, $\xi(x)$source, as follows:

By theorem “General Recursion” in chapter “Stages and Ranks”, there is a term $\sigma(x)$source such that $\sigma(\alpha) = \xi(\funrestrictionto{\sigma}{\alpha})$source for every ordinal $\alpha$source; moreover, $\funrestrictionto{\sigma}{\alpha}$source is a function with domain $\alpha$source. We show that $\sigma$source has the required properties, by simple transfinite induction (theorem “Simple Transfinite Induction” in chapter “Ordinals”).

First, $\sigma(\emptyset) = \xi(\emptyset) = A$source.

Next, $\sigma(\ordsucc{\alpha}) = \xi(\funrestrictionto{\sigma}{\ordsucc{\alpha}}) = \tau(\funrestrictionto{\sigma}{\ordsucc{\alpha}}(\alpha)) = \tau(\sigma(\alpha))$source.

Last, $\sigma(\alpha) = \xi(\funrestrictionto{\sigma}{\alpha}) = \theta(\ran{\funrestrictionto{\sigma}{\alpha}})$source, when $\alpha$source is a limit.

Definition three in this chapter

The set $A$source is potent iff $\forall x((\exists y \in A)x \subseteq y \lif x \in A)$source.

Lemma two in this chapter

For each ordinal $\alpha$source:

1. Each $V_\alpha$source is transitive.

2. Each $V_\alpha$source is potent.

3. If $\gamma \in \alpha$source, then $V_\gamma \in V_\alpha$source (and hence also $V_\gamma \subseteq V_\alpha$source by item 1 of lemma two in chapter “Stages and Ranks”)

Proof

We prove this by a (simultaneous) transfinite induction. For induction, suppose that item 1 of lemma two in chapter “Stages and Ranks”--item 3 of lemma two in chapter “Stages and Ranks” holds for each ordinal $\beta < \alpha$source.

The case of $\alpha = \emptyset$source is trivial.

Suppose $\alpha = \ordsucc{\beta}$source. To show item 3 of lemma two in chapter “Stages and Ranks”, if $\gamma \in \alpha$source then $V_\gamma \subseteq V_\beta$source by hypothesis, so $V_\gamma \in \Pow{V_\beta} = V_\alpha$source. To show item 2 of lemma two in chapter “Stages and Ranks”, suppose $A \subseteq B \in V_\alpha$source i.e., $A \subseteq B \subseteq V_\beta$source; then $A \subseteq V_\beta$source so $A \in V_\alpha$source. To show item 1 of lemma two in chapter “Stages and Ranks”, note that if $x \in A \in V_\alpha$source we have $A \subseteq V_\beta$source, so $x \in V_\beta$source, so $x \subseteq V_\beta$source as $V_\beta$source is transitive by hypothesis, and so $x \in V_\alpha$source.

Suppose $\alpha$source is a limit ordinal. To show item 3 of lemma two in chapter “Stages and Ranks”, if $\gamma \in \alpha$source then $\gamma \in \ordsucc{\gamma} \in \alpha$source, so that $V_\gamma \in V_{\ordsucc{\gamma}}$source by assumption, hence $V_\gamma \in \bigcup_{\beta \in \alpha} V_\beta = V_\alpha$source. To show item 1 of lemma two in chapter “Stages and Ranks” and item 2 of lemma two in chapter “Stages and Ranks”, just observe that a union of transitive (respectively, potent) sets is transitive (respectively, potent).

Lemma three in this chapter

For each ordinal $\alpha$source, $V_\alpha \notin V_\alpha$source.

Proof

By transfinite induction. Evidently $V_\emptyset \notin V_\emptyset$source.

If $V_{\ordsucc{\alpha}} \in V_{\ordsucc{\alpha}} = \Pow{V_\alpha}$source, then $V_{\ordsucc{\alpha}} \subseteq V_\alpha$source; and since $V_\alpha \in V_{\ordsucc{\alpha}}$source by lemma two in chapter “Stages and Ranks”, we have $V_\alpha \in V_\alpha$source. Conversely: if $V_\alpha \notin V_\alpha$source then $V_{\ordsucc{\alpha}} \notin V_{\ordsucc{\alpha}}$source

If $\alpha$source is a limit and $V_\alpha \in V_\alpha = \bigcup_{\beta \in \alpha}V_\beta$source, then $V_\alpha \in V_\beta$source for some $\beta \in \alpha$source; but then also $V_\beta \in V_\alpha$source so that $V_\beta \in V_\beta$source by lemma two in chapter “Stages and Ranks” (twice). Conversely, if $V_\beta \notin V_\beta$source for all $\beta \in \alpha$source, then $V_\alpha \notin V_\alpha$source.

Corollary one in this chapter

For any ordinals $\alpha, \beta$source: $\alpha \in \beta$source iff $V_\alpha \in V_\beta$source

Proof

Lemma two in chapter “Stages and Ranks” gives one direction. Conversely, suppose $V_\alpha \in V_\beta$source. Then $\alpha \neq \beta$source by lemma three in chapter “Stages and Ranks”; and $\beta \notin \alpha$source, for otherwise we would have $V_\beta \in V_\alpha$source and hence $V_\beta \in V_\beta$source by lemma two in chapter “Stages and Ranks” (twice), contradicting lemma three in chapter “Stages and Ranks”. So $\alpha \in \beta$source by Trichotomy.

Definition four in this chapter

Regularity. $\forall A \exists \alpha\, A \subseteq V_\alpha$source

Axiom: Foundation

[Foundation] $(\forall A \neq \emptyset)(\exists B \in A)A \cap B = \emptyset$source.

Definition five in this chapter

For each set $A$source, let:

We call $\text{trcl}(A)$source the transitive closure of $A$source.

Proposition one in this chapter

$A \subseteq \trcl{A}$source and $\trcl{A}$source is a transitive set.

Proof

Evidently $A = \text{cl}_0(A) \subseteq \text{trcl}(A)$source. And if $x \in b \in \trcl{A}$source, then $b \in \text{cl}_n(A)$source for some $n$source, so $x \in \text{cl}_{n+1}(A) \subseteq \text{trcl}(A)$source.

Lemma four in this chapter

If $A$source is a transitive set, then there is some $\alpha$source such that $A \subseteq V_\alpha$source.

Proof

Recalling the definition of “$\supstrict(X)$source” from definition nine in chapter “Ordinals”, define two sets:

Suppose $D = \emptyset$source. So if $x \in A$source, then there is some $\delta$source such that $x \subseteq V_\delta$source and, by the well-ordering of the ordinals, $(\forall \gamma \in \delta)x \nsubseteq V_\gamma$source; hence $\delta \in \alpha$source and so $x \in V_\alpha$source by lemma two in chapter “Stages and Ranks”. Hence $A \subseteq V_{\alpha}$source, as required.

So it suffices to show that $D = \emptyset$source. For reductio, suppose otherwise. By Foundation, there is some $B \in D \subseteq A$source such that $D \cap B = \emptyset$source. If $x \in B$source then $x \in A$source, since $A$source is transitive, and since $x \notin D$source, it follows that $\exists \delta\ x \subseteq V_\delta$source. So now let

As before, $B \subseteq V_\beta$source, contradicting the claim that $B \in D$source.

Theorem three in this chapter

Regularity holds.

Proof

Fix $A$source; now $A \subseteq \trcl{A}$source by proposition one in chapter “Stages and Ranks”, which is transitive. So there is some $\alpha$source such that $A \subseteq \trcl{A} \subseteq V_\alpha$source by the lemma on Transitive Well Founded

Definition six in this chapter

The theory $\Z$source adds Foundation to $\Zminus$source. So its axioms are Extensionality, Union, Pairs, Powersets, Infinity, Foundation, and all instances of the Separation scheme.

The theory $\ZF$source adds Foundation to $\ZFminus$source. Otherwise put, $\ZF$source adds all instances of Replacement to $\Z$source.

Definition seven in this chapter

For each set $A$source, $\setrank{A}$source is the least ordinal $\alpha$source such that $A \subseteq V_\alpha$source.

Proposition two in this chapter

$\setrank{A}$source exists, for any $A$source.

Proof

Left as an exercise.

Exercise one in this chapter

Prove proposition two in chapter “Stages and Ranks”.

Proposition three in this chapter

For any ordinal $\alpha$source, $V_\alpha = \Setabs{x}{\setrank{x} \in \alpha}$source.

Proof

If $\setrank{x} \in \alpha$source then $x \subseteq V_{\setrank{x}} \in V_\alpha$source, so $x \in V_\alpha$source as $V_\alpha$source is potent (invoking lemma two in chapter “Stages and Ranks” multiple times). Conversely, if $x \in V_\alpha$source then $x \subseteq V_\alpha$source, so $\setrank{x} \leq \alpha$source; now a simple transfinite induction shows that $x \notin V_\alpha$source.

Exercise two in this chapter

Complete the simple transfinite induction mentioned in proposition three in chapter “Stages and Ranks”.

Proposition four in this chapter

If $B \in A$source, then $\setrank{B} \in \setrank{A}$source.

Proof

$A \subseteq V_{\setrank{A}} = \Setabs{x}{\setrank{x} \in \setrank{A}}$source by proposition three in chapter “Stages and Ranks”.

Theorem: the membership relation-Induction Scheme

[$\in$source-Induction Scheme] For any formula $\phi$source:

Proof

We will prove the contrapositive. So, suppose $\lnot \forall A \phi(A)$source. By Transfinite Induction (theorem “Transfinite Induction” in chapter “Ordinals”), there is some non-$\phi$source of least possible rank; i.e.\ some $A$source such that $\lnot \phi(A)$source and $\forall x(\setrank{x} \in \setrank{A} \lif \phi(x))$source. Now if $x \in A$source then $\setrank{x} \in \setrank{A}$source, by proposition four in chapter “Stages and Ranks”, so that $\phi(x)$source; i.e.\ $(\forall x \in A)\phi(x) \land \lnot \phi(A)$source.

Proposition five in this chapter

$\setrank{A} = \supstrict_{x \in A}\setrank{x}$source.

Proof

Let $\alpha = \supstrict_{x \in A}\setrank{x}$source. By proposition four in chapter “Stages and Ranks”, $\alpha \leq \setrank{A}$source. But if $x \in A$source then $\setrank{x} \in \alpha$source, so that $x \in V_\alpha$source by proposition three in chapter “Stages and Ranks”, and hence $A \subseteq V_\alpha$source, i.e., $\setrank{A} \leq \alpha$source. Hence $\setrank{A} = \alpha$source.

Corollary two in this chapter

For any ordinal $\alpha$source, $\setrank{\alpha} = \alpha$source.

Proof

Suppose for transfinite induction that $\setrank{\beta} = \beta$source for all $\beta \in \alpha$source. Now $\setrank{\alpha} = \supstrict_{\beta \in \alpha}\setrank{\beta} = \supstrict_{\beta \in \alpha}\beta = \alpha$source by proposition five in chapter “Stages and Ranks”.

Proposition: working in set theory Z F minus plus Regularity

[working in $\ZFminus + \text{Regularity}$source] Foundation holds.

Proof

Fix $A \neq \emptyset$source, and some $B \in A$source of least possible rank. If $c \in B$source then $\setrank{c} \in \setrank{B}$source by proposition four in chapter “Stages and Ranks”, so that $c \notin A$source by choice of $B$source.