# Transfinite Recursion/Theorem 1

## Theorem

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

## Proof

### $K$ is a chain

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

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

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

### Domain of $F$ is an ordinal

$K$ is a chain of mappings.

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

Moreover, $\forall x \in B: f \left({x}\right) = F \left({x}\right)$, because $F$ is an extension of the mapping $f$.

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

\(\ds a \in \operatorname{Dom} \left({F}\right) \land x \in a\) | \(\implies\) | \(\ds \exists f: \exists \beta \in \operatorname{On}: \left({f: \beta \to \operatorname{Im} \left({f}\right) \land a \in \beta }\right)\) | Definition of $F$ (above) | |||||||||||

\(\ds \) | \(\implies\) | \(\ds a \in \operatorname{On} \land x \in \beta\) | Transitivity of $\beta$ and $\operatorname{On}$ | |||||||||||

\(\ds \) | \(\implies\) | \(\ds x \in \operatorname{Dom} \left({F}\right)\) |

From this it follows that $\operatorname{Dom} \left({F}\right)$ is an ordinal, since it is a transitive subset of $\operatorname{On}$.

### Domain of $F$ is $\operatorname{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 $\operatorname{Dom} F = \gamma$ for some ordinal $\gamma$. Define $C$ as follows:

- $C = F \cup \left\{{\left({\gamma, G \left({F {\restriction_\gamma}}\right)}\right)}\right\}$

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

- $\forall x < \gamma^+: C \left({x}\right) = G \left({F {\restriction_\gamma} }\right)$

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

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

So $C \subseteq F$.

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

Therefore, $\operatorname{Dom} \left({F}\right)$ cannot be a set and must therefore be the set of all ordinals $\operatorname{On}$.

$\Box$

### Value of $F$ is $G \left({F {\restriction_\alpha} }\right)$

- $\forall x \in \operatorname{On}: \exists f \in K: f \left({x}\right) = F \left({x}\right)$

Since $f \in K$:

- $f \left({x}\right) = G \left({f {\restriction_x} }\right)$

But $\forall y < x: f \left({y}\right) = F \left({y}\right)$, so by Equality of Restrictions:

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

Therefore,:

- $F \left({\alpha}\right) = G \left({F {\restriction_\alpha} }\right)$

$\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: H \left({x}\right) = F \left({x}\right)\) | \(\implies\) | \(\ds \left({H \restriction y}\right) = \left({F \restriction y}\right)\) | Equality of Restrictions | |||||||||||

\(\ds \) | \(\implies\) | \(\ds G \left({H \restriction y}\right) = G \left({F \restriction y}\right)\) | by hypothesis | |||||||||||

\(\ds \) | \(\implies\) | \(\ds H \left({y}\right) = F \left({y}\right)\) | by hypothesis |

So for all ordinals:

- $H \left({y}\right) = F \left({y}\right)$

Thus $H = F$.

$\blacksquare$

## Also see