Transfinite Induction/Schema 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$.

Proof 1

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.


Proof 2

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


In proofs by transfinite induction using this particular schema, the following terms are used.

Basis for the Induction

The proposition $\map \phi \O$ is called the basis for the induction.

Induction Step

The proposition $\map \phi x = \T \implies \map \phi {x^+} = \T$ is called the inductive step.

It says that the propositional function will pass from an ordinal number to its successor.

Limit Case

$\paren {\forall x < y: \map \phi x = \T} \implies \map \phi y = \T$ is called the limit case.

It states that if $\phi$ is true for every ordinal strictly less than $y$, then $\phi$ is true for $y$.

It is essentially proving that the proposition will hold for limit ordinals.

Then, this formulation of transfinite induction says that if the basis for the induction, inductive step, and limit case are all satisfied, then the statement holds for all ordinals.