# Math Help - Question about transfinite recursion theorem

1. ## Question about transfinite recursion theorem

I'm having some difficulty understanding some material in a book I'm reading, Introduction to Set Theory 3rd ed. by Hrbacek and Jech.
The question is about a proof of a theorem given on page 118 in the book.

The theorem that I'm having difficult with is Theorem 3.6 (given on page 113):

Let G be an operation.For any set a there is a unique infinite sequence an|nN such that
(a)a0= a
(
b)an+1= G (an,n)for all nN

The proof provided in the book on page 118 is as follows:

Let G be an operation. We want to find, for every set a, a sequencean|nN such that a0 = a and an+1= G(an,n) for all nN.
By the parametric version of the Transfinite Recursion Theorem 4.11,
there is an operation F such that F(0) = a and F(n+1)=G(F(n),n) for all nN.
Now we apply the Axiom of Replacement: There exists a sequence
an|nNthat is equal to Fω and the Theorem follows.

Note:
The parametric version of the Transfinite Recursion Theorem 4.11 is as follows:
Given binary operations G1,G2, and G3 there is an operation F such that for all z

F(z,0) = G1(z,0),
F(z,α+1) = G2(z,Fz(α)) for all ordinals α, and
F
(z,α) = G3(z,Fzα)for all limit ordinals α.

Now, I understand everything in the proof of Theorem 3.6 except how the parametric version of Theorem 4.11 is used to derive the operation F in the proof. Can can someone please help me fill in blanks?

2. ## Re: Question about transfinite recursion theorem

I assume your problem is with the parameter $n$ of $G$ in $G(F(n), n)$. In the transfinite recursion theorem, the step function $G_2$ takes only the previous value $F_z(\alpha)$ and not $\alpha$ itself. The trick is to use the recursion theorem to produce an operation that returns not just the final answer, but also the counter $\alpha$. That is, we define $F'(n)$ such that
\begin{align}
F'(0) &= (a, 0)\\
F'(n+1) &= (G(\pi_1(F'(n)),\pi_2(F'(n))),\pi_2(F'(n))+1)
\end{align}
where $\pi_i(x_1,x_2)=x_i$ is the projection function. Then $\pi_2(F'(n))=n$ for all $n$ and the right-hand side of the second equation is a function of only $F'(n)$, not $n$. In the end we can define $F(n)=\pi_1(F'(n))$.

3. ## Re: Question about transfinite recursion theorem

You are correct that my problem is with the parameter n of G in G(F(n),n).
I understood what you wrote,
but I don't see how the parameter z in the parametric transfinite recursion theorem (The parametric version of the Transfinite Recursion Theorem 4.11 as stated) is being used. What is the role of the parameter z in proof of Theorem 3.6 that makes the use of the parametric transfinite recursion theorem essential?
The existence of the operation F you specified could have just have easily been justified by the use of the Transfinite Recursion Theorem 4.11 (see pg. 117 in the text) which is as follows:

Given binary operations G1,G2, and G3 there is an operation F such that
F(0) = G1(0),
F(α+1) = G2(F(α)) for all ordinals α, and
F
(α) = G3(Fα)for all limit ordinals α.

Why did the authors choose to use the parametric version of the Transfinite Recursion Theorem 4.11 in the proof when apparently the "ordinary" Transfinite Recursion Theorem 4.11 would have sufficed? I know the text leaves you to fill in the blanks at times, but this seems as a bit of hand waving to me.

4. ## Re: Question about transfinite recursion theorem

I am not sure. It also seems to me that the ordinary transfinite recursion theorem is sufficient.