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

Question

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?

Answer 1

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.

Answer 2

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.