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.

Re: Enderton 3.3 Problem 8

Quote:

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,

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

Re: Enderton 3.3 Problem 8

Quote:

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.

Quote:

Originally Posted by

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