# Transfinite Recursion

## Theorem

### Uniqueness

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

This article, or a section of it, needs explaining.What is $G$?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 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$

### First Principle of Transfinite Recursion

Let $G$ be a mapping.

This article, or a section of it, needs explaining.What are the domain and range of $G$?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 $K$ be a class of mappings $f$ that satisfy:

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

Let $F = \bigcup K$, 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}$

### 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.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.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.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.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 ordinals, $\On$.
- $\map F \O = a$
- $\map F {\beta^+} = \map H {\map F \beta}$
- For limit ordinals $\beta$, $\displaystyle \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

- 1971: Gaisi Takeuti and Wilson M. Zaring:
*Introduction to Axiomatic Set Theory*: $\S 7.40, \ \S7.41, \ \S7.42$