# Transfinite Recursion

## Contents

## 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: f \left({x}\right) = G \left({f \restriction x}\right)$

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: g \left({x}\right) = G \left({g \restriction x}\right)$

Let $y \subseteq z$.

Then:

- $\forall x \in y: f \left({x}\right) = g \left({x}\right)$

### First Principle of Transfinite Recursion

Let $G$ be a mapping.

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

- the domain of $f$ is some ordinal $y$
- $\forall x \in y: f \left({x}\right) = G \left({f {\restriction_x} }\right)$

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 $\operatorname{On}$
- $(2): \quad \forall x \in \operatorname{On}: F \left({x}\right) = G \left({F {\restriction_x} }\right)$
- $(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: f \left({y}\right) = G \left({f \restriction y}\right)$

### Second Principle of Transfinite Recursion

Let $\operatorname{Dom} \left({x}\right)$ denote the domain of $x$.

Let $\operatorname{Im} \left({x}\right)$ denote the image of the mapping $x$.

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

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

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

- $(3): \quad \operatorname{Dom} \left({x}\right)$ is a limit ordinal and $y = \bigcup \operatorname{Rng} \left({x}\right)$.

Let $F \left({\alpha}\right) = G \left({F \restriction \alpha}\right)$ for all ordinals $\alpha$.

Then:

- $F$ is a mapping and the domain of $F$ is the ordinals, $\operatorname{On}$.
- $F \left({\varnothing}\right) = a$
- $F \left({\beta^+}\right) = H \left({F \left({\beta}\right)}\right)$
- For limit ordinals $\beta$, $\displaystyle F \left({\beta}\right) = \bigcup_{\gamma \mathop \in \beta} F \left({\gamma}\right)$
- $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$