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?

Printable View

- Dec 18th 2011, 04:57 AMlogicsEnderton 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? - Dec 18th 2011, 11:56 AMemakarovRe: 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 as an argument in addition the previous value of f. - Dec 19th 2011, 04:59 AMlogicsRe: Enderton 3.3 Problem 8
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. - Dec 19th 2011, 05:46 AMemakarovRe: Enderton 3.3 Problem 8