# Transfinite Induction

## Theorem

### Principle 1

Let $\On$ denote the class of all ordinals.

Let $A$ denote a class.

Suppose that:

For all elements $x$ of $\On$, if $x$ is a subset of $A$, then $x$ is an element of $A$.

Then $\On \subseteq A$.

### Schema 1

Let $\map P x$ be a property

Suppose that:

If $\map P x$ holds for all ordinals $x$ less than $y$, then $\map P y$ also holds.

Then $\map P x$ holds for all ordinals $x$.

### Principle 2

Let $A$ be a class satisfying the following conditions:

• $\O \in A$
• $\forall x \in A: x^+ \in A$
• If $y$ is a limit ordinal, then $\paren {\forall x < y: x \in A} \implies y \in A$

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

Then $\On \subseteq A$.

### Schema 2

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