Transfinite Recursion

From ProofWiki
Jump to navigation Jump to search

Theorem

Uniqueness

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)$


First Principle of Transfinite Recursion

Let $G$ be a mapping.


Let $K$ be a class of mappings $f$ that satisfy:

the domain of $f$ is some ordinal $y$
$\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 $F = \bigcup K$, the union of $K$.

Then:

$(1): \quad F$ is a mapping with domain $\operatorname{On}$
$(2): \quad \forall x \in \operatorname{On}: F \left({x}\right) = G \left({F {\restriction_x} }\right)$
$(3): \quad F$ is unique. That is, if another mapping $A$ has the above two properties, then $A = F$.


Corollary

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)$


Second Principle of Transfinite Recursion

Let $\Dom x$ denote the domain of $x$.

Let $\Img x$ denote the image of the mapping $x$.



Let $G$ be a class of ordered pairs $\tuple {x, y}$ satisfying at least one of the following conditions:

$(1): \quad x = \O$ and $y = a$


$(2): \quad \exists \beta: \Dom x = \beta^+$ and $y = \map H {\map x {\bigcup \Dom x} }$


$(3): \quad \Dom x$ is a limit ordinal and $y = \bigcup \Rng x$.



Let $\map F \alpha = \map G {F \restriction \alpha}$ for all ordinals $\alpha$.

Then:

$F$ is a mapping and the domain of $F$ is the ordinals, $\On$.
$\map F \O = a$
$\map F {\beta^+} = \map H {\map F \beta}$
For limit ordinals $\beta$, $\displaystyle \map F \beta = \bigcup_{\gamma \mathop \in \beta} \map F \gamma$
$F$ is unique.
That is, if there is another function $A$ satisfying the above three properties, then $A = F$.


Sources