Results 1 to 4 of 4

Math Help - Enderton 3.3 Problem 8

  1. #1
    Junior Member
    Joined
    Nov 2011
    Posts
    59

    Enderton 3.3 Problem 8

    Let g and h be representable functions, and assume that

    f(0, b) = g(b),
    f(a+1, b) = h ( f(a, b), a, b).

    Show that f is representable.

    The necessary definitions are found in

    http://cs.nyu.edu/courses/fall03/G22...c/lec11_h4.pdf (slides 16-20)

    Any hint to start this problem?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,504
    Thanks
    765

    Re: Enderton 3.3 Problem 8

    The idea is that f(a,b) = c iff there is a sequence of pairs of numbers <<f(0,b),0>, <f(1,b),1>, ..., <f(a,b),a>> where the first element is <g(b),0>, the last element is <c,a>, and each subsequent element is obtained from the previous one using h. You only need to prove that the set of such sequences is representable; then you can use the minimization operator to express f (slide 20).

    It is possible to write a formula that takes n and says that n is the code of a sequence as above. The important thing is that all quantifiers can be bounded by n because all numbers involved (e.g., each sequence component, the length of the sequence, etc.) are <= than the code of the sequence.

    The idea of having a sequence of pairs <f(i,b),i> and not just a sequence of numbers f(i) comes from the fact that h takes the counter a as an argument in addition the previous value of f.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2011
    Posts
    59

    Re: Enderton 3.3 Problem 8

    Quote Originally Posted by emakarov View Post
    The idea is that f(a,b) = c iff there is a sequence of pairs of numbers <<f(0,b),0>, <f(1,b),1>, ..., <f(a,b),a>> where the first element is <g(b),0>, the last element is <c,a>, and each subsequent element is obtained from the previous one using h.
    I am having hard time understanding the above statement. Can you elaborate it more plz?

    Can you also check if the following is OK or needs corrections plz?

    By the primitive recursion,

    f(a+1, b)=h(f(a, b), a, b)=h(\bar{f}(a+1, b)_a, a, b),

    where \bar{f}(a+1, b)=the least s such that s is a sequence number of length a+1 and for i less than a+1, (s)_i=h(s \upharpoonright i, i, b).
    Now, g, h, and \bar{f} are representable(by Theorem 33P, page 222), and by catalog item 9 in the link in the post #1, f is representable.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,504
    Thanks
    765

    Re: Enderton 3.3 Problem 8

    Quote Originally Posted by logics View Post
    I am having hard time understanding the above statement. Can you elaborate it more plz?
    I was trying to say a similar thing.

    Quote Originally Posted by logics View Post
    By the primitive recursion,

    f(a+1, b)=h(f(a, b), a, b)=h(\bar{f}(a+1, b)_a, a, b),

    where \bar{f}(a+1, b)=the least s such that s is a sequence number of length a+1 and for i less than a+1, (s)_i=h(s \upharpoonright i, i, b).
    Now, g, h, and \bar{f} are representable(by Theorem 33P, page 222), and by catalog item 9 in the link in the post #1, f is representable.
    What about f(0, b)? You need a formula that describes the value of f for all arguments, not only when the first argument has the form a + 1. Also, (s)_i=h(s \upharpoonright i, i, b) should be replaced by (s)_{i+1}=h((s)_i,i,b).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Enderton Problem 3.5
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 5th 2012, 11:49 AM
  2. Enderton 3.5 Problem 1
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 27th 2011, 10:59 AM
  3. Enderton 3.3 Problem 5
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: December 19th 2011, 07:34 AM
  4. Enderton 3.1 problem 1 (p.193)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: December 4th 2011, 10:30 AM
  5. Enderton 3.1 Problem 6 (p. 193)
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: December 3rd 2011, 12:12 PM

Search Tags


/mathhelpforum @mathhelpforum