Results 1 to 4 of 4

Thread: Enderton 3.3 Problem 8

  1. #1
    Junior Member
    Joined
    Nov 2011
    Posts
    59

    Enderton 3.3 Problem 8

    Let $\displaystyle g$ and $\displaystyle h$ be representable functions, and assume that

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

    Show that $\displaystyle 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,577
    Thanks
    790

    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 $\displaystyle 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,

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

    where $\displaystyle \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, $\displaystyle (s)_i=h(s \upharpoonright i, i, b)$.
    Now, g, h, and $\displaystyle \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,577
    Thanks
    790

    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,

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

    where $\displaystyle \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, $\displaystyle (s)_i=h(s \upharpoonright i, i, b)$.
    Now, g, h, and $\displaystyle \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 $\displaystyle f$ for all arguments, not only when the first argument has the form a + 1. Also, $\displaystyle (s)_i=h(s \upharpoonright i, i, b)$ should be replaced by $\displaystyle (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: Jan 5th 2012, 11:49 AM
  2. Enderton 3.5 Problem 1
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Dec 27th 2011, 10:59 AM
  3. Enderton 3.3 Problem 5
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: Dec 19th 2011, 07:34 AM
  4. Enderton 3.1 problem 1 (p.193)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: Dec 4th 2011, 10:30 AM
  5. Enderton 3.1 Problem 6 (p. 193)
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: Dec 3rd 2011, 12:12 PM

Search Tags


/mathhelpforum @mathhelpforum