Results 1 to 4 of 4

Math Help - Question about transfinite recursion theorem

  1. #1
    Newbie
    Joined
    Mar 2014
    From
    Caribbean
    Posts
    2

    Question 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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785

    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))$.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2014
    From
    Caribbean
    Posts
    2

    Re: Question about transfinite recursion theorem

    Thanks for the reply.
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785

    Re: Question about transfinite recursion theorem

    I am not sure. It also seems to me that the ordinary transfinite recursion theorem is sufficient.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Question about recursion theorem
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: August 16th 2011, 07:32 AM
  2. [SOLVED] Transfinite Induction?
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: March 31st 2011, 10:34 PM
  3. Transfinite Recursion
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: September 10th 2010, 03:22 PM
  4. transfinite recursion
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 25th 2009, 08:57 PM
  5. Transfinite Induction
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 26th 2008, 09:46 PM

Search Tags


/mathhelpforum @mathhelpforum