Definition of addition by transfinite recursion.

Question

Transfinite recursion theorem from T.Jech Set Theory:

Let G be a function (on V), then (2.6) below defines a unique function F on Ord such that $F (α) = G(F \restriction α)$ for each α.

(2.6) $$(F(α) = x) ↔ \mbox{there is a sequence} \langle a_ξ : ξ < > α\rangle \mbox{such that:}$$ $$(i)\quad(∀ξ < α) a_ξ = G(\langle a_η : > η < ξ\rangle);$$ $$(ii)\quad x = G(\langle a_ξ : ξ < α\rangle).$$

Question: I want to define addition on ordinals. Then I need to define G somehow firstly. How? I calculated that $$G(\emptyset)=\alpha,$$ $$G(\{\langle 0, \alpha \rangle\})=\alpha+1,$$ $$G(\{\langle 0, \alpha \rangle, \langle 1, \alpha+1 \rangle\})=(\alpha+1)+1$$ $$...$$ How to define G? We need to use some formula with two free variables; then prove that it defines an operation on all sets; then introduce functional symbol G; then apply transfinite recursion theorem. Which formula should I use and start with?

How to obtain G from this:

Definition 2.18 (Addition). For all ordinal numbers α $$(i) α + 0 = > α,$$ $$(ii) α + (β + 1) = (α + β) + 1, \mbox{for all β},$$ $$(iii) α + β = > \lim_{ξ→β} (α + ξ)\mbox{ for all limit β > 0}.$$

Answer 1

The idea is that $\alpha+\beta=\gamma$ iff there is some function $F$ such that

• $F(0)=\alpha$;
• $F(\delta+1)=F(\delta)+1$; and
• $F(\delta)=\sup_{\xi<\delta}F(\xi)$ for $\delta$ a limit;

and $\beta\in \mathrm{dom}(F)$ and $F(\beta)=\gamma$. Transfinite recursion is what allows you to get such an $F$.

But your question is what $G$ gives you this $F$? Well, the natural one as we've been given: for a set $X$, we break down into cases. In particular, take $G(X)$ to be $\alpha$ if $X=\emptyset$ or isn't a function with its domain an ordinal, and otherwise define

$$ G(X) = \begin{cases} \sup \mathrm{ran}(X)+1 & \text{if }\mathrm{dom}(X)\text{ is a successor ordinal}\\ \sup \mathrm{ran}(X)&\text{if }\mathrm{dom}(X)\text{ is a limit ordinal.} \end{cases}$$

As is usual for things defined by recursion, $G$ is just some function that doesn't depend on $F$ or $F\restriction \alpha$. We use the restrictions in defining $F$, not $G$. $G$ just tells you how to step forward, and (for the most part) can just be broken down into cases like the above definition.