Thread: Enderton 3.3 Problem 8

Let and be representable functions, and assume that




Show that 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?

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 as an argument in addition the previous value of f.

Originally Posted by emakarov

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,



where =the least s such that s is a sequence number of length a+1 and for i less than a+1, .
Now, g, h, and are representable(by Theorem 33P, page 222), and by catalog item 9 in the link in the post #1, f is representable.

Originally Posted by logics

I am having hard time understanding the above statement. Can you elaborate it more plz?

I was trying to say a similar thing.

Originally Posted by logics

By the primitive recursion,



where =the least s such that s is a sequence number of length a+1 and for i less than a+1, .
Now, g, h, and 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 for all arguments, not only when the first argument has the form a + 1. Also, should be replaced by .