Does this method show that the projections $K$ and $L$ of an enumeration are primitive recursive?

112 Views Asked by At

In the fifth edition of Boolos et al's Computability and Logic, Exercise 6.5 asks the following (modified to provide background definitions):

Define $K(n)$ and $L(n)$ to be the first and second entries of the pair of natural numbers coded (by the enumeration $J$, given below) by the number $n$, so that $J(K(n), L(n)) = n$.

The enumeration $J$ of pairs of natural numbers by natural numbers is defined by $J(a,b) = J_0(a+1,b+1)-1$, where $J_0(a,b) = (a^2+2ab+b^2-b-3a+2)/2$ is an enumeration of pairs of positive integers by positive integers.

Show that the functions $K$ and $L$ are primitive recursive.

Doing an earlier exercise, I have already shown $J$ to be primitive recursive. Here is, then, how my solution goes: First, observe that $J(x,y) \ge x$ and $J(x,y) \ge y$ or, equivalently, $n \ge K(n)$ and $n \ge L(n)$. Second, we know from an example in the text (and Proofwiki) that the function

$$ \begin{equation} g(n,x,y) = \sum_{i=0}^x\sum_{j=0}^y f(n,i,j) \end{equation} $$

is primitive recursive if $f$ is primitive recursive; so, by the inequalities, if we put the limits to be $n$ for both sums, we are guaranteed to get a unique pair $(i,j)$ that is coded by the number $n$ (for if two different pairs were coded by the same $n$, $J$ wouldn't be an injective enumeration).

Construct, then, a function $f$ that returns $x$ whenever the pair $(x,y)$ is coded by $J$, and $0$ otherwise. One such function is given by $f(n,x,y)=x \cdot \overline{\operatorname{sg}}(|J(x,y)-n|)$, where $\overline{\operatorname{sg}}$ is a primitive recursive function that returns $1$ whenever its argument is $0$, and returns $0$ otherwise. This function $f$ is composed from known primitive recursive functions and is thus primitive recursive.

Now we plug $f$ into the double-bounded-sum expression, and set both limits to $n$, obtaining $g(n,n,n)$. Then, in the summation, a summand is nonzero exactly once, and equals $x$ when that occurs, so $g(n,n,n)=x$ is a primitive recursive function that does what we need. Define, then, $K(n) = g(n,n,n)$, and we are done. The case of $L$ is similar.

But the next exercise is again about projections of enumerations:

[...] $n=2^{k(n)}(2l(n)+1)\mathop{\dot -}1$. Show that the functions $k$ and $l$ are primitive recursive.

If I am not missing anything and my method is correct, the method should work for this exercise as well, with trivial modifications. But this is not an exercise-drill-type-of-book, which leads me to believe I am missing something the author intended me to see, or that my method is incorrect.

What am I missing?