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$