Transfinite Induction/Schema 2

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

$\blacksquare$

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

$\blacksquare$

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.

This article needs proofreading. Please check it for mathematical errors. If you believe there are none, please remove {{Proofread}} from the code. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Proofread}} from the code.

This needs considerable tedious hard slog to complete it. In particular: It's a start, but we still need links to induction hypothesis and limit case. And the wording needs to be adjusted so that the contents equals the heading. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Finish}} from the code. If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.

Sources

• 2008: Paul Halmos and Steven Givant: Introduction to Boolean Algebras ... (previous) ... (next): Appendix $\text{A}$: Set Theory: Induction