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_\alpha \)

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

This article, or a section of it, needs explaining. In particular: We infer that $x$ is a mapping, but what is its context? You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by explaining it. 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 {{Explain}} from the code.

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$

This article, or a section of it, needs explaining. In particular: What is $a$? You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by explaining it. 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 {{Explain}} from the code.

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

This article, or a section of it, needs explaining. In particular: What is $H$? You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by explaining it. 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 {{Explain}} from the code.

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

This article, or a section of it, needs explaining. In particular: Is this invoking well-founded recursion? You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by explaining it. 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 {{Explain}} from the code.

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

Sources

• 2010: Raymond M. Smullyan and Melvin Fitting: Set Theory and the Continuum Problem (revised ed.) ... (previous) ... (next): Chapter $6$: Order Isomorphism and Transfinite Recursion: $\S 5$ Transfinite recursion theorems: Theorem $5.1$