Transfinite Induction/Schema 1/Proof 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
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$