# Transfinite Recursion/Uniqueness of Transfinite Recursion

## Theorem

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

## Proof

Proof by transfinite induction:

Suppose that:

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

for some arbitrary ordinal $\alpha < y$.

Then $\alpha < z$.

Hence:

 $\displaystyle \forall x \in \alpha: f \left({x}\right) = g \left({x}\right)$ $\implies$ $\displaystyle \left({f \restriction \alpha}\right) = \left({g \restriction \alpha}\right)$ Equality of Restrictions $\displaystyle$ $\implies$ $\displaystyle G \left({f \restriction \alpha}\right) = G \left({g \restriction \alpha}\right)$ Substitution $\displaystyle$ $\implies$ $\displaystyle f \left({\alpha}\right) = g \left({\alpha}\right)$ By hypothesis

So applying induction:

$\forall \alpha < y: f \left({\alpha}\right) = g \left({\alpha}\right)$

$\blacksquare$