Transfinite Induction/Schema 2/Proof 1

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\phi \left({x}\right)$ be a property satisfying the following conditions:

$(1): \quad \phi \left({\varnothing}\right)$ is true
$(2): \quad$ If $x$ is an ordinal, then $\phi \left({x}\right) \implies \phi \left({x^+}\right)$
$(3): \quad$ If $y$ is a limit ordinal, then $\left({\forall x < y: \phi \left({x}\right)}\right) \implies \phi \left({y}\right)$

where $x^+$ denotes the successor of $x$.

Then, $\phi \left({x}\right)$ is true for all ordinals $x$.


Proof

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

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

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


It is noted that $y \ne \varnothing$.

Therefore $y$ must be either a successor ordinal or a limit ordinal.


If $y$ is a successor ordinal, then let $x$ be the ordinal such that $x^+ = y$.

By the Rule of Transposition, it is seen that $\neg \phi \left({x}\right)$.

By Set is Element of Successor, it follows that $x \in y$, and so $x \lt y$.


If $y$ is a limit ordinal, then by the Rule of Transposition there exists an ordinal $x \lt y \iff x \in y$ such that $\neg \phi \left({x}\right)$.


It has been shown that if $y$ is an ordinal such that $\neg \phi \left({y}\right)$, then there exists an ordinal $x \in y$ such that $\neg \phi \left({x}\right)$.

The rest follows from the proof of Schema 1.

$\blacksquare$