# Transfinite Recursion/Uniqueness of Transfinite Recursion

Jump to navigation
Jump to search

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