# Transfinite Recursion/Theorem 2

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

- 1971: Gaisi Takeuti and Wilson M. Zaring:
*Introduction to Axiomatic Set Theory*: $\S 7.42$