Transfinite Induction

From ProofWiki
Jump to navigation Jump to search

Theorem

Principle 1

Let $\operatorname{On}$ denote the class of all ordinals.

Let $A$ denote a class.


Suppose that:

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


Then $\operatorname{On} \subseteq A$.


Schema 1

Let $P \left({x}\right)$ be a property

Suppose that:

If $P \left({x}\right)$ holds for all ordinals $x$ less than $y$, then $P \left({y}\right)$ also holds.


Then $P \left({x}\right)$ holds for all ordinals $x$.


Principle 2

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

  • $\varnothing \in A$
  • $\forall x \in A: x^+ \in A$
  • If $y$ is a limit ordinal, then $\left({ \forall x < y: x \in A }\right) \implies y \in A$

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


Then $\operatorname{On} \subseteq A$.


Schema 2

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