# Is the collection of primitive recursive functions a lower set in the poset of computable functions?

If $$g:\mathbb{N}\to\mathbb{N}$$ is primitive recursive and $$f:\mathbb{N}\to\mathbb{N}$$ is computable such that $$f(n) \leq g(n)$$ for all $$n\in \mathbb{N}$$, does this imply that $$f$$ is primitive recursive?

No. Let $$g$$ be the constant function 1.

Let $$\{h_n\}$$ be a computable list of all primitive recursive functions and let $$f_n(x)=\min(h_n(x),1)$$.

So $$\{f_n\}$$ is a computable list of all primitive recursive functions bounded by 1.

Now let $$F(n)=1-f_n(n)$$. Then $$F$$ is another computable function bounded by 1, distinct from all the $$f_n$$, so $$F$$ is not primitive recursive.

No, as Bjørn explained in his answer, but it is a lower set in the class of functions with primitive recursive graphs. Specifically, if $$f:\mathbb{N}^k\to\mathbb{N}$$ is such that

• The function $$g:\mathbb{N}^{k+1}\to\{0,1\}$$ such that $$g(x_1,\ldots,x_k,y) = 1 \iff f(x_1,\ldots,x_k) = y$$ is primitive recursive, and
• There is a primitive recursive function $$h:\mathbb{N}^k\to\mathbb{N}$$ such that $$f(x_1,\ldots,x_k) \leq h(x_1,\ldots,x_k)$$,

then $$f$$ is primitive recursive.

The reason is that we can recover $$f$$ by bounded search: $$f(x_1,\ldots,x_k) = \mu y \leq h(x_1,\ldots,x_k)\,[g(x_1,\ldots,x_k,y) = 1].$$

Note that there are many functions that are not primitive recursive but whose graphs are primitive recursive, for example the Ackermann function has a primitive recursive graph. This fact is useful to show that the inverse Ackermann function is primitive recursive, for example.