Transfinite Induction/Schema 2/Proof 2

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

Define the class:

$A := \left\{{x \in \operatorname{On}: \phi \left({x}\right) = \mathrm T}\right\}$.

Then $\phi \left({x}\right) = \mathrm T$ is equivalent to the statement:

that $x \in A$

The three conditions in the hypothesis become:

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

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

Therefore, $\operatorname{On} \subseteq A$.

Thus, $\phi \left({x}\right)$ holds for all $x \in \operatorname{On}$.

$\blacksquare$