# Thread: Enderton 3.3 Problem 8

1. ## 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?

2. ## 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.

3. ## Re: Enderton 3.3 Problem 8

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,

$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.

4. ## Re: Enderton 3.3 Problem 8

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,

$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)$.