Transfinite Recursion Theorem/Formulation 1/Proof 1
Theorem
Let $M$ be a class.
Let $g$ be a strictly progressing mapping on $M$.
Let $M$ be minimally superinductive under $g$.
For an arbitrary ordinal $\alpha$, let $M_\alpha$ be the $\alpha$th element of $M$ under the well-ordered class $\struct {M, \subseteq}$.
Then:
\((1)\) | $:$ | Zeroth Ordinal: | \(\ds M_0 \) | \(\ds = \) | \(\ds \O \) | ||||
\((2)\) | $:$ | Successor Ordinal: | \(\ds \forall \alpha \in \On:\) | \(\ds M_{\alpha^+} \) | \(\ds = \) | \(\ds \map g {M_\alpha} \) | |||
\((3)\) | $:$ | Limit Ordinal: | \(\ds \forall \lambda \in K_{II}:\) | \(\ds M_\lambda \) | \(\ds = \) | \(\ds \bigcup_{\alpha \mathop < \lambda} M_\alpha \) |
where:
- $\On$ denotes the class of all ordinals
- $K_{II}$ denotes the class of all limit ordinals.
Proof
Let $\On$ denote the class of all ordinals.
By the Superinductive Class under Strictly Progressing Mapping is Proper Class, $M$ is not a set; it is a proper class.
From Minimally Superinductive Class is Well-Ordered under Subset Relation, $\struct {M, \subseteq}$ is indeed a well-ordered class.
By definition, $M$ is a $g$-tower.
Hence from $g$-Tower is Well-Ordered under Subset Relation:
- $(1): \quad \O$ is the smallest element of $M$.
- $(2): \quad$ The immediate successor of $x$ under the well-ordering $\subseteq$ is $\map g x$.
- $(3): \quad$ For a limit element $x$ of $M$:
- $x = \bigcup x^\subset$
- where $\bigcup x^\subset$ denotes the union of the lower section of $x$.
From the Counting Theorem, there exists a unique order isomorphism from $\On$ to $M$.
Let $M_\alpha$ denote the element of $M$ corresponding to $\alpha$ under this order isomorphism.
We refer to $M_\alpha$ as the "$\alpha$th element of $M$".
By the definition of order isomorphism, it is immediate that $M_0$ is the smallest element of $M$ under the well-ordering induced by $\subseteq$.
Hence:
- $M_0 = \O$
It is also immediate that $M_{\alpha^+}$ is the immediate successor of $M_\alpha$, that is:
- $M_{\alpha^+} = \map g {M_\alpha}$
Let $\lambda$ be a limit ordinal.
Then $M_\lambda$ is a limit element of $M$:.
Hence $M_\lambda$ is the union of the set of all $M_\alpha$ such that $\alpha < \lambda$.
That is:
- $\ds M_\lambda = \bigcup_{\alpha \mathop < \lambda} M_\alpha$
Hence the result.
$\blacksquare$
Sources
- 2010: Raymond M. Smullyan and Melvin Fitting: Set Theory and the Continuum Problem (revised ed.) ... (previous) ... (next): Chapter $6$: Order Isomorphism and Transfinite Recursion: $\S 5$ Transfinite recursion theorems: Theorem $5.1$