# A “dense” extension of the set of primitive recursive functions

Let $\mathcal{PR}$ be the set of primitive recursive functions. Let $\mathcal{PR}(f)$ be $\mathcal{PR}$ which we have amplified by adding (a recursive) $f$ the in the set of initial functions. To make this a true extension, assume $f$ outgrows all primitive recursive functions.

Now, $\mathcal{PR}$ is "dense" in the sense that it has the Ritchie-Cobham property, i.e. every function computable in primitive recursive time is primitive recursive and vice versa.

Does $\mathcal{PR}(f)$ have the Ritchie-Cobham property?

To me it seems natural the extension preserves the property and I would guess there is some "direct" argument for this, which I just fail to see.

• To clarify, by that property for PR(f) I guess you mean: if a computable function is computable in time bounded by a function in PR(f), then it is itself in PR(f). – Joel David Hamkins Jan 9 '18 at 11:45
• @JoelDavidHamkins Yes, exactly. – user39297 Jan 9 '18 at 11:46

Suppose a function $g$ is computable by a procedure $p$ whose computation running time is bounded by a function $h\in\newcommand\PR{\text{PR}}\PR(f)$. I claim that $g\in\PR(f)$.
To see this, let's first argue that $\PR(f)$ is closed under the bounded search operator $(x,z)\mapsto\mu y<z[R(x,y,z)]$, where $R$ is a relation whose characteristic function is in $\PR(f)$ and where the $\mu$ operator returns the least $y<z$ such that $R(x,y,z)$, if there is one, and otherwise returns $z$ as a signal that the search failed. The proof is just the usual proof that the primitive recursive functions are closed under bounded search, since one can easily define this instance of the $\mu$ operator by recursion, by using $R$. In other words, the usual argument is not sensitive to the particular functions one starts with in the $\PR$ hierarchy.
It follows now that $g$ is in $\PR(f)$, since we can say that $g(x)=y$ just in case there is a code for a computation of length $h(x)$ showing that the output of $g$ on $x$ is $y$ according to the fixed program $p$. This code can be checked using bounded search, since we can bound how big the code will be if we know how long the computation will be.