How to invoke transfinite recursion

Question

Transfinite recursion states that

For any $F:\mathbf{V}\to \mathbf{V}$, there exists a unique $G:\mathbf{ON}\to\mathbf{V}$ such that $\forall\alpha[G(\alpha)=F(G\vert_\alpha)]$

where $\mathbf{V}$ denotes the universe of all sets and $\mathbf{ON}$ denotes the class of all ordinals. I want to use this theorem to define ordinal addition. Inuitively, I want to define it as such: Fix $\alpha\in\mathbf{ON}$. Then

• $\alpha+0=\alpha$,
• $\alpha+S(\beta)=S(\alpha+\beta)$,
• $\alpha+\beta=\sup\{\alpha+\xi:\xi<\beta\}$ if $\beta$ is a limit ordinal.

When invoking the theorem to prove that this definition makes sense, we want $G(\beta)=\alpha+\beta$. How do I define $F$ in order to invoke the theorem?

Answer 1

Here are a few hints:

• $F$ should be defined piecewise (i.e., by cases).
• It only matters how we define $F$ on sets that could be equal to $G|_\alpha$ for some $\alpha \in \textbf{ON}$. For all other "non-interesting" input sets, we can let $F$ be equal to anything.
• On the "interesting" input sets, we should define $F$ by cases depending on whether the input could be equal to $G|_\alpha$ for some ordinal $\alpha$ equal to zero, a successor, or a limit.

So, if we are using the standard definition of a "$x$ is a function" as "$x$ is a set of ordered pairs, with each first coordinate corresponding to a unique second coordinate," our definition of $F$ might look something like this:

$$F(x) = \begin{cases} ???? & x \text{ is not a function} \vee (x \text{ is a function} \wedge \text{dom}(x) \notin \textbf{ON}) \newline ???? & x \text{ is a function} \wedge \text{dom}(x) = 0 \newline ???? & x \text{ is a function} \wedge \text{dom}(x) = S(\beta) \text{ for some } \beta \in \textbf{ON} \newline ???? & x \text{ is a function} \wedge \text{dom}(x) = \beta \text{ for some limit } \beta \in \textbf{ON} \newline \end{cases},$$ where $\text{dom}(x)$ denotes the domain of $x$ and where you should fill in the ????'s with correct expressions depending on $x$.

To ensure that this method is rigorous, make note of the following facts:

• The $F$ that we define and the $G$ that the transfinite recursion theorem guarantees are not set functions, (i.e., neither of them is equal to a set in $V$). However, they are well-defined class functions, (i.e., each of them is captured by a formula in the language of set theory).
• In order to make sure that $F$ as written above is captured a formula in the language of set theory, make sure that the expressions "$x$ is a function," "$\text{dom}(x) = y$," "$x \in \textbf{ON}$," and "$x \text{ is a limit}$" are each captured by a formula in the language of set theory.

I hope these hints help!