# Transfinite Recursion Theorem/Theorem 1

This article needs to be linked to other articles.In particular: Just a few to be tidied upYou can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding these links.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 `{{MissingLinks}}` from the code. |

## Theorem

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

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

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

### Corollary

Let $x$ be an ordinal.

Let $G$ be a mapping

There exists a unique mapping $f$ that satisfies the following properties:

- The domain of $f$ is $x$
- $\forall y \in x: \map f y = \map G {f \restriction y}$

## Proof

First a lemma:

### Lemma

Let $f$ be a mapping with a domain $y$ where $y$ is an ordinal.

Let $f$ satisfy the condition that:

- $\forall x \in y: \map f x = \map G {f \restriction x}$

where $f \restriction x$ denotes the restriction of $f$ to $x$.

Let $g$ be a mapping with a domain $z$ where $z$ is an ordinal.

Let $g$ satisfy the condition that:

- $\forall x \in z: \map g x = \map G {g \restriction x}$

Let $y \subseteq z$.

Then:

- $\forall x \in y: \map f x = \map g x$

$\Box$

### $K$ is a chain

First, it is necessary to show that $K$ is a chain of mappings under the subset relation.

This article, or a section of it, needs explaining.In particular: Might be worth setting up a page defining exactly what a "chain of mappings" actually is in concrete termsYou 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. |

Take any $f, g \in K$.

Set $B$ equal to the domain of $f$ and set $C$ equal to the domain of $g$.

From Relation between Two Ordinals:

- $B \subseteq C \lor C \subseteq B$

From Lemma 1:

- $\forall x \in B \cap C: \map f x = \map g x$

So depending on whether $B \subseteq C$ or $C \subseteq B$:

- $f \subseteq g \lor g \subseteq f$

From Subset Relation is Ordering, it follows that $\subseteq$ is a total ordering on $K$.

$\Box$

### Domain of $F$ is an ordinal

Since the union of a chain of mappings is a mapping, $F$ is a mapping.

Moreover, $\forall x \in B: \map f x = \map F x$, because $F$ is an extension of the mapping $f$.

The domain of $F$ is a subset of the class of all ordinals because it is the union of a collection of mappings whose domains are themselves subsets of ordinals.

\(\ds a\) | \(\in\) | \(\ds \Dom F\) | ||||||||||||

\(\, \ds \land \, \) | \(\ds x\) | \(\in\) | \(\ds a\) | |||||||||||

\(\ds \leadsto \ \ \) | \(\ds \exists f: \exists \beta \in \On: \, \) | \(\ds f\) | \(:\) | \(\ds \beta \to \Img f\) | Definition of $F$ (above) | |||||||||

\(\, \ds \land \, \) | \(\ds a\) | \(\in\) | \(\ds \beta\) | |||||||||||

\(\ds \leadsto \ \ \) | \(\ds a\) | \(\in\) | \(\ds \On\) | Transitivity of $\beta$ and $\On$ | ||||||||||

\(\, \ds \land \, \) | \(\ds x\) | \(\in\) | \(\ds \beta\) | |||||||||||

\(\ds \leadsto \ \ \) | \(\ds x\) | \(\in\) | \(\ds \Dom F\) |

From this it follows that $\Dom F$ is an ordinal, since it is a transitive subset of $\On$.

### Domain of $F$ is $\On$

Assume the domain of $F$ is a set.

Since $F$ is a mapping, the range of $F$ is a set and $F$ is a set.

Then $\Dom F = \gamma$ for some ordinal $\gamma$.

Define $C$ as follows:

- $C = F \cup \set {\tuple {\gamma, \map G {F {\restriction_\gamma} } } }$

Then $C$ is a mapping with domain $\gamma^+$ and satisfies:

- $\forall x < \gamma^+: \map C x = \map G {F {\restriction_\gamma} }$

Therefore $C$ is a member of $K$ (note that $F {\restriction_\gamma} = C {\restriction_\gamma}$).

- $\ds C \in K \implies C \subseteq \bigcup K$

So $C \subseteq F$.

But if $F$ is a set, $F \subsetneq C$, a contradiction.

Therefore, $\Dom F$ cannot be a set and must therefore be the set of all ordinals $\On$.

$\Box$

### Value of $F$ is $\map G {F {\restriction_\alpha} }$

- $\forall x \in \On: \exists f \in K: \map f x = \map F x$

Since $f \in K$:

- $\map f x = \map G {f {\restriction_x} }$

But $\forall y < x: \map f y = \map F y$, so by Equality of Restrictions:

- $f {\restriction_x} = F {\restriction_x}$

Therefore:

- $\map F \alpha = \map G {F {\restriction_\alpha} }$

$\Box$

### $F$ is Unique

Finally, assume there is another mapping $H$ that satisfies the first two properties.

Then $H$ is equal to $F$ by transfinite induction:

\(\ds \forall x \in y: \, \) | \(\ds \map H x\) | \(=\) | \(\ds \map F x\) | |||||||||||

\(\ds \leadsto \ \ \) | \(\ds \paren {H \restriction y}\) | \(=\) | \(\ds \paren {F \restriction y}\) | Equality of Restrictions | ||||||||||

\(\ds \leadsto \ \ \) | \(\ds \map G {H \restriction y}\) | \(=\) | \(\ds \map G {F \restriction y}\) | by hypothesis | ||||||||||

\(\ds \leadsto \ \ \) | \(\ds \map H y\) | \(=\) | \(\ds \map F y\) | by hypothesis |

So for all ordinals:

- $\map H y = \map F y$

Thus:

- $H = F$

$\blacksquare$

## Also see