Transfinite Induction/Schema 2/Proof 2

From ProofWiki
Jump to navigation Jump to search


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$.


Define the class:

$A := \set {x \in \On: \map \phi x = \T}$.

Then $\map \phi x = \T$ is equivalent to the statement:

that $x \in A$

The three conditions in the hypothesis become:

$(1a): \quad \O \in A$
$(2a): \quad x \in A \implies x^+ \in A$
$(3a): \quad \paren {\forall x < y: x \in A} \implies y \in A$

These are precisely the conditions for the class $A$ in the second principle of transfinite induction.

Therefore, $\On \subseteq A$.

Thus, $\map \phi x$ holds for all $x \in \On$.