Transfinite Recursion Theorem/Uniqueness

Theorem

Let $G$ be a mapping.

Let $f$ be a mapping with a domain $y$ where $y$ is an ordinal.

Let $f$ satisfy the condition that:

$\forall x \in y: \map f x = \map G {f \restriction x}$

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: \map g x = \map G {g \restriction x}$

Let $y \subseteq z$.

Then:

$\forall x \in y: \map f x = \map g x$

Proof

Proof by transfinite induction:

Suppose that:

$\forall x \in \alpha: \map f x = \map g x$

for some arbitrary ordinal $\alpha < y$.

Then $\alpha < z$.

This article, or a section of it, needs explaining. In particular: Find the link to the result proving this. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by explaining it. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Explain}} from the code.

Hence:

\(\ds \forall x \in \alpha: \, \)

\(\ds \map f x\)

\(=\)

\(\ds \map g x\)

\(\ds \leadsto \ \ \)

\(\ds f \restriction \alpha\)

\(=\)

\(\ds g \restriction \alpha\)

Equality of Restrictions

\(\ds \leadsto \ \ \)

\(\ds \map G {f \restriction \alpha}\)

\(=\)

\(\ds \map G {g \restriction \alpha}\)

Substitution

\(\ds \leadsto \ \ \)

\(\ds \map f \alpha\)

\(=\)

\(\ds \map g \alpha\)

by hypothesis

So applying induction:

$\forall \alpha < y: \map f \alpha = \map g \alpha$

$\blacksquare$

Sources

• 1971: Gaisi Takeuti and Wilson M. Zaring: Introduction to Axiomatic Set Theory