# Transfinite Recursion Theorem

## Theorem

### Formulation 1

Let $M$ be a class.

Let $g$ be a strictly progressing mapping on $M$.

Let $M$ be minimally superinductive under $g$.

For an arbitrary ordinal $\alpha$, let $M_\alpha$ be the $\alpha$th element of $M$ under the well-ordered class $\struct {M, \subseteq}$.

Then:

 $(1)$ $:$ Zeroth Ordinal: $\ds M_0$ $\ds =$ $\ds \O$ $(2)$ $:$ Successor Ordinal: $\ds \forall \alpha \in \On:$ $\ds M_{\alpha^+}$ $\ds =$ $\ds \map g {M_\alpha}$ $(3)$ $:$ Limit Ordinal: $\ds \forall \lambda \in K_{II}:$ $\ds M_\lambda$ $\ds =$ $\ds \bigcup_{\alpha \mathop < \lambda} M_\alpha$

where:

$\On$ denotes the class of all ordinals
$K_{II}$ denotes the class of all limit ordinals.

### Formulation 2

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

Let $S$ denote the class of all ordinal sequences.

Let $g$ be a mapping such that $S \subseteq \Dom g$.

Then there exists a unique mapping $F$ on $\On$ such that:

$\forall \alpha \in \On: \map F \alpha = \map g {F \restriction \alpha}$

where $F \restriction \alpha$ denotes the restriction of $F$ to $\alpha$.

### Formulation 3

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

Let $h$ and $f$ be mappings defined for all sets.

Let $c$ be a set.

Then there exists a unique mapping $F$ on $\On$ such that:

 $(1)$ $:$ $\ds \map F 0$ $\ds =$ $\ds c$ $(2)$ $:$ $\ds \forall \alpha \in \On:$ $\ds \map F {\alpha^+}$ $\ds =$ $\ds \map h {\map F \alpha}$ $(3)$ $:$ $\ds \forall \lambda \in K_{II}:$ $\ds \map F \lambda$ $\ds =$ $\ds \map f {F \sqbrk \lambda}$

where $K_{II}$ denotes the class of all limit ordinals.

### Formulation 4

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

Let $g$ be a mapping defined for all sets.

Let $c$ be a set.

Then there exists a unique $\On$-sequence $S_0, S_1, \dots, S_\alpha, \dots$ such that:

 $(1)$ $:$ $\ds S_0$ $\ds =$ $\ds c$ $(2)$ $:$ $\ds \forall \alpha \in \On:$ $\ds S_{\alpha + 1}$ $\ds =$ $\ds \map g {S_\alpha}$ $(3)$ $:$ $\ds \forall \lambda \in K_{II}:$ $\ds S_\lambda$ $\ds =$ $\ds \bigcup_{\alpha \mathop < \lambda} S_\lambda$

where $K_{II}$ denotes the class of all limit ordinals.

### Formulation 5

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

Let $h$ be a mapping.

Then there exists a unique mapping $F$ such that:

$\forall \alpha \in \On: \map F \alpha = \map h {F \sqbrk \alpha}$

## Also presented as

There are variants in how this result is presented, as the topic can be approached from a number of different directions.

Here are examples:

### First Principle of Transfinite Recursion

Let $G$ be a (class) mapping from $\On^{\On}$ to $\On$.

Let $K$ be a class of mappings $f$ that satisfy:

the domain of $f$ is some ordinal $y$
$\forall x \in y: \map f x = \map G {f {\restriction_x} }$

where $f {\restriction_x}$ denotes the restriction of $f$ to $x$.

Let $F = \bigcup K$ be the union of $K$.

Then:

$(1): \quad F$ is a mapping with domain $\On$
$(2): \quad \forall x \in \On: \map F x = \map G {F {\restriction_x} }$
$(3): \quad F$ is unique. That is, if another mapping $A$ has the above two properties, then $A = F$.

### Second Principle of Transfinite Recursion

Let $\Dom x$ denote the domain of $x$.

Let $\Img x$ denote the image of the mapping $x$.

Let $G$ be a class of ordered pairs $\tuple {x, y}$ satisfying at least one of the following conditions:

$(1): \quad x = \O$ and $y = a$

$(2): \quad \exists \beta: \Dom x = \beta^+$ and $y = \map H {\map x {\bigcup \Dom x} }$

$(3): \quad \Dom x$ is a limit ordinal and $y = \bigcup \Rng x$.

Let $\map F \alpha = \map G {F \restriction \alpha}$ for all ordinals $\alpha$.

Then:

$F$ is a mapping and the domain of $F$ is the class of all ordinals, $\On$.
$\map F \O = a$
$\map F {\beta^+} = \map H {\map F \beta}$
For limit ordinals $\beta$, $\ds \map F \beta = \bigcup_{\gamma \mathop \in \beta} \map F \gamma$
$F$ is unique.
That is, if there is another function $A$ satisfying the above three properties, then $A = F$.