Transfinite Induction/Schema 1

Theorem

Let $\map P x$ be a property

Suppose that:

If $\map P x$ holds for all ordinals $x$ less than $y$, then $\map P y$ also holds.

Then $\map P x$ holds for all ordinals $x$.

Proof 1

It should be noted that for any two ordinals, $x < y \iff x \in y$.

Let $\map P x$ be a property that satisfies the above conditions.

Aiming for a contradiction, suppose $y$ is an ordinal such that $\neg \map P y$.

By the Rule of Transposition, it follows that if $y$ is an ordinal such that $\neg \map P y$, then there exists an ordinal $x < y \iff x \in y$ such that $\neg \map P x$.

Let $\alpha$ be the smallest ordinal in $y$ such that $\neg \map P \alpha$.

We can choose such an element because an ordinal is strictly well-ordered by definition.

Since $\neg \map P \alpha$, let $\beta$ be the smallest ordinal in $\alpha$ such that $\neg \map P \beta$.

Since $y$ is transitive by definition:

$\beta \in \alpha \land \alpha \in y \implies \beta \in y$

And so $\beta$ is an ordinal in $y$ such that $\neg \map P \beta$.

But since $\beta < \alpha$, this contradicts the fact that $\alpha$ is the smallest ordinal of $y$ such that $\neg \map P \alpha$.

Therefore $\map P x$ holds for all ordinals.

Hence the result.

$\blacksquare$

Proof 2

It should be noted that for any two ordinals, $x < y \iff x \in y$.

Let $\map P x$ be a property that satisfies the above conditions.

Aiming for a contradiction, suppose $y$ is an ordinal such that $\neg \map P y$.

Let $S$ be the set defined as:

$S = \set {x \in y^+: \neg \map P x}$

It is seen that this set is non-empty because by Set is Element of Successor:

$y \in y^+$

$y^+$ is an ordinal because of Successor Set of Ordinal is Ordinal.

By Element of Ordinal is Ordinal, $S$ is a set of ordinals.

By the Rule of Transposition, it follows that for every $x \in S$, there exists an ordinal $\alpha < x \iff \alpha \in x$ such that $\neg \map P \alpha$.

But by transitivity:

$\alpha \in x \land x \in y^+ \implies \alpha \in y^+$

So the epsilon restriction $\in_S$ is a right-total relation on $S$.

Therefore by the Axiom of Dependent Choice there exists a sequence $\sequence {x_n}_{n \mathop \in \N}$ in $S$ such that:

$\forall n \in \N: x_{n + 1} \in x_n$

But this contradicts No Infinitely Descending Membership Chains.

Thus $\map P x$ holds for all ordinals.

Hence the result.

$\blacksquare$

Sources

• 2011: Kenneth Kunen: Set Theory: $\S 1.9$