Transfinite Recursion Theorem/Corollary
Jump to navigation
Jump to search
Theorem
Let $x$ be an ordinal.
Let $G$ be a mapping
There exists a unique mapping $f$ that satisfies the following properties:
- The domain of $f$ is $x$
- $\forall y \in x: \map f y = \map G {f \restriction y}$
Proof
Construct $K$ and $F$ as in the First Principle of Transfinite Recursion.
Set $f = \paren {F \restriction x}$.
Then since $x \subseteq \Dom F$, the domain of $f$ is $x$.
\(\ds \forall y \in x: \, \) | \(\ds \map f y\) | \(=\) | \(\ds \map F y\) | from the fact that $f$ is a restriction | ||||||||||
\(\ds \) | \(=\) | \(\ds \map G {F \restriction y}\) | First Principle of Transfinite Recursion | |||||||||||
\(\ds \) | \(=\) | \(\ds \map G {f \restriction y}\) |
Thus such a mapping $f$ exists.
Suppose there are two mappings $f$ and $g$ that satisfy these conditions.
We will use the first principle of transfinite induction to show that $f = g$.
Take $y \in x$.
Suppose $\forall z \in y: \map f z = \map g z$.
Then:
- $\paren {f \restriction y} = \paren {g \restriction y}$
and so:
\(\ds \map f y\) | \(=\) | \(\ds \map G {f \restriction y}\) | Assumption | |||||||||||
\(\ds \) | \(=\) | \(\ds \map G {g \restriction y}\) | Substitutivity of Equality | |||||||||||
\(\ds \) | \(=\) | \(\ds \map g y\) | by hypothesis |
So $\map f y = \map g y$ for all $y \in x$ by transfinite induction.
Since $x$ is the domain of $f$ and $g$, it follows that $f = g$.
Thus the mapping $f$ is unique.
$\blacksquare$
Sources
- 1971: Gaisi Takeuti and Wilson M. Zaring: Introduction to Axiomatic Set Theory: $\S 7.41$