Transfinite Recursion/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: f \left({y}\right) = G \left({f \restriction y}\right)$


Proof

Construct $K$ and $F$ as in the First Principle of Transfinite Recursion.

Set $f = \left({F \restriction x}\right)$.

Then since $x \subseteq \operatorname{Dom} F$, the domain of $f$ is $x$.

\(\displaystyle \forall y \in x: f \left({y}\right)\) \(=\) \(\displaystyle F \left({y}\right)\) from the fact that $f$ is a restriction
\(\displaystyle \) \(=\) \(\displaystyle G \left({F \restriction y}\right)\) Transfinite Recursion: Theorem 1
\(\displaystyle \) \(=\) \(\displaystyle G \left({f \restriction y}\right)\)

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: f \left({z}\right) = g \left({z}\right)$.

Then:

$ \left({f \restriction y}\right) = \left({g \restriction y}\right)$

and so:

\(\displaystyle f \left({y}\right)\) \(=\) \(\displaystyle G \left({f \restriction y}\right)\) Assumption
\(\displaystyle \) \(=\) \(\displaystyle G \left({g \restriction y}\right)\) Substitutivity of Equality
\(\displaystyle \) \(=\) \(\displaystyle g \left({y}\right)\) Hypothesis

So $f \left({y}\right) = g \left({y}\right)$ 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