Is upper bound recursive function always primitive-recursive as well?

Question

If there is a constant upper bound for a function which is recursive is it enough to prove that the function is primitive-recursive? I saw this cause disagreements on whether or not the inverse Ackermann function is primitive-recursive or not.

Answer 1

No, this is not enough - and this is easy to see by diagonalization.

Let $(p_i)_{i\in\mathbb{N}}$ be the usual enumeration of primitive recursive functions of one variable. Then the function $$F:i\mapsto p_i(i)$$ is recursive (although of course not primitive recursive). Consider now the map $G$ defined by setting $G(i)=0$ if $F(i)=1$ and $G(i)=1$ if $F(i)\not=1$.

$G$ is total recursive and bounded by a constant (we always have $G(i)\le 1$), but not primitive recursive since $G(i)\not=p_i(i)$ for all $i$.

---

So what is enough to guarantee primitive recursiveness?

The key is to look at the function's graph: a total recursive function $f(x_1,...,x_n)$ is primitive recursive iff

• $f$ is bounded above by some primitive recursive function, and

• the characteristic function of the set $$Graph(f)=\{\langle a_1,...,a_n,b\rangle: f(a_1,...,a_n)=b\}$$ is primitive recursive.

The inverse Ackermann function satisfies the first and second properties, and so is primitive recursive; the function $G$ defined in the first half of this answer satisfies the first property (in a very strong way) but fails the second.