Transfinite Induction/Schema 1/Proof 1

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $P \left({x}\right)$ be a property

Suppose that:

If $P \left({x}\right)$ holds for all ordinals $x$ less than $y$, then $P \left({y}\right)$ also holds.


Then $P \left({x}\right)$ holds for all ordinals $x$.


Proof

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

Let $P \left({x}\right)$ be a property that satisfies the above conditions.

Aiming for contradiction, let $y$ be an ordinal such that $\neg P \left({y}\right)$.


By the Rule of Transposition, it follows that if $y$ is an ordinal such that $\neg P \left({y}\right)$, then there exists an ordinal $x \lt y \iff x \in y$ such that $\neg P \left({x}\right)$.

Let $\alpha$ be the smallest ordinal in $y$ such that $\neg P \left({\alpha}\right)$.

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


Since $\neg P \left({\alpha}\right)$, let $\beta$ be the smallest ordinal in $\alpha$ such that $\neg P \left({\beta}\right)$.

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 P \left({\beta}\right)$.

But since $\beta \lt \alpha$, this contradicts the fact that $\alpha$ is the smallest ordinal of $y$ such that $\neg P \left({\alpha}\right)$.

Therefore $P \left({x}\right)$ holds for all ordinals.


Hence the result.

$\blacksquare$