Transfinite Induction/Schema 2/Proof 1

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\map \phi x$ be a property satisfying the following conditions:

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

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

Then, $\map \phi x$ is true for all ordinals $x$.


Proof

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

Let $\map \phi x$ be a property that satisfies the above conditions.

Aiming for a contradiction, suppose $y$ be an ordinal such that $\neg \map \phi y$.


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

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 \map \phi x$.

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 \map \phi x$.


It has been shown that if $y$ is an ordinal such that $\neg \map \phi y$, then there exists an ordinal $x \in y$ such that $\neg \map \phi x$.

The rest follows from the proof of Schema 1.

$\blacksquare$