Transfinite Recursion Theorem/Corollary

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