Transfinite Recursion/Uniqueness of Transfinite Recursion

From ProofWiki
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$


Sources