If $g:\mathbb{N}\to\mathbb{N}$ is [primitive recursive](https://en.wikipedia.org/wiki/Primitive_recursive_function) and $f:\mathbb{N}\to\mathbb{N}$ is [computable](https://en.wikipedia.org/wiki/Computable_function) such that $f(n) \leq g(n)$ for all $n\in \mathbb{N}$, does this imply that $f$ is primitive recursive?



Is the collection of primitive recursive functions a lower set in the poset of computable functions?
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.


