Principle of Transfinite Recursion

Statement

Given that $G$ is a function, there is a function $F$ such that:

• $F$ is a function with domain $\operatorname{On}$
• $\forall x \in \operatorname{On}: F(x) = G(F\restriction x)$
• $F$ is unique. If another function $H$ has the above two properties, then $H = F$.

Proof Sketch

We begin by constructing a chain of functions $K$ which satisfy the first two properties. $K = \{ f : \exists \beta \in \operatorname{On} ( f \text{ is a function with domain } \beta \land \forall \alpha \in \beta ( f(\alpha) = G(f\restriction \alpha) ) ) \}$

$F$ is the union of $K$, $F = \bigcup K$.

Since the union of a chain of functions is a function, $F$ is a function.

The domain of $F$ is a subset of the ordinals because it is the union of a collection of functions whose domains are themselves subsets of ordinals. Assuming that $a$ is a member of the domain of $F$ implies that $a$ is a member of the domain of some element of $K$, and thus is a subset of $F$. Therefore, because the domain of $F$ is both transitive and a subset of the ordinals, it is itself an ordinal.

Assume the domain of $F$ is a set. Since $F$ is a function, the range of $F$ is a set and $F$ is a set. This means that we can take the successor of the domain of $F$ and create another set $C$ which satisfies the conditions necessary to be an element of $K$. But then, $C$ is a subset of $F$, which is a contradiction, since $C$ strictly contains $F$ if we assume that $F$ is a set. Therefore, $F$ cannot be a set and its domain must be the class of all ordinals.

To prove the next part, notice that $F$ contains all of its elements, but if $f$ is an element of $F$, then $f(x) = F(x)$ for all $x$ in the domain of $f$. Therefore, given an $\alpha \in \operatorname{On}$, we can create a set $f$ where $\alpha$ is a member of the domain of $f$. Furthermore, $F \restriction \alpha$ will equal $f \restriction \alpha$. Therefore, $F(\alpha) = f(\alpha) = G(f\restriction \alpha) = G(F \restriction \alpha)$.

Finally, assume there is another function $H$ that satisfies the first two properties. Then, $H$ is equal to $F$ by transfinite induction. $\forall x \in y H(x) = F(x) \implies ( H \restriction y ) = ( F \restriction y )$. This, in turn, implies that $H(y) = G(H\restriction y) = G(F \restriction y) = F(y)$, so, by transfinite induction, $H(\alpha) = F(\alpha)$ for all ordinals $\alpha$. So $H = F$.

See Also

• Well-founded Recursion
• Principle of Transfinite Induction

Source

• Gaisi Takeuti: Introduction to Axiomatic Set Theory (1971): $7.40$
• Metamath: Theorem tfr1: Principle of Transfinite Recursion, part 1 of 3