Transfinite Recursion/Theorem 2

From ProofWiki
Jump to navigation Jump to search

Theorem

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


Proof

\(\displaystyle \map F \O\) \(=\) \(\displaystyle \map G {F \restriction \O}\) Hypothesis
\(\displaystyle \) \(=\) \(\displaystyle \map G \O\) Restriction of $\O$
\(\displaystyle \) \(=\) \(\displaystyle a\) Definition of $G$

$\Box$


\(\displaystyle \map F {\beta^+}\) \(=\) \(\displaystyle \map G {F \restriction \beta^+}\) Hypothesis
\(\displaystyle \) \(=\) \(\displaystyle \map H {\map {F \restriction \beta^+} {\bigcup \beta^+} }\) Definition of $G$
\(\displaystyle \) \(=\) \(\displaystyle \map H {\map F \beta}\) Union of successor set is the original set by Union of Ordinals is Least Upper Bound

$\Box$


\(\displaystyle \map F \beta\) \(=\) \(\displaystyle \map G {F \restriction \beta}\) Hypothesis
\(\displaystyle \) \(=\) \(\displaystyle \bigcup \Img {F \restriction \beta}\) Definition of $G$
\(\displaystyle \) \(=\) \(\displaystyle \bigcup_{\gamma \mathop \in \beta} \map F \gamma\)

$\Box$


We can proceed in the fourth part by Transfinite Induction.


Basis for the Induction

\(\displaystyle \map F \O\) \(=\) \(\displaystyle a\) First part
\(\displaystyle \) \(=\) \(\displaystyle \map A \O\) Hypothesis

This proves the basis for the induction.

$\Box$


Induction Step

\(\displaystyle \map F \beta\) \(=\) \(\displaystyle \map A \beta\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle \map H {\map F \beta}\) \(=\) \(\displaystyle \map H {\map A \beta}\) Substitutivity of equality
\(\displaystyle \leadsto \ \ \) \(\displaystyle \map F {\beta^+}\) \(=\) \(\displaystyle \map A {\beta^+}\) Second part

This proves the induction step.

$\Box$


Limit Case

\(\, \displaystyle \forall \gamma \in \beta: \, \) \(\displaystyle \map F \gamma\) \(=\) \(\displaystyle \map A \gamma\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle \bigcup_{\gamma \mathop \in \beta} \map F \gamma\) \(=\) \(\displaystyle \bigcup_{\gamma \mathop \in \beta} \map A \gamma\) Substitutivity of equality
\(\displaystyle \leadsto \ \ \) \(\displaystyle \map F \beta\) \(=\) \(\displaystyle \map A \beta\) Third part

This proves the limit case.

$\blacksquare$


Sources