Transfinite Induction/Schema 1/Proof 1

From ProofWiki
Jump to navigation Jump to search

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$