$f_{\epsilon_0}$ and provably total functions in $PA$

Question

A total recursive function $f(x)$ is provably total in $PA$ if there's some formula $\phi(x,y)$ such that

1. $f(x)=y \iff PA\vdash \phi(x,y)$ and
2. $PA\vdash \forall x \exists y \phi(x,y)$

I know (not in much detail) that a total recursive function is not provably total if it grows as fast as/faster than $f_{\epsilon_0}$ in a fast growing hierarchy, where $\epsilon_0=\omega^{\omega^{\omega^....}}$ (the Goodstein sequence would be an example). My question is, is the converse also true, i.e., every total recursive function dominated by $f_{\epsilon_0}$ is provably total in $PA$?

---

Edit: By Gro-Tsen's comment and Henry's answer, I know the answer to my above question is (almost trivially) no ... But if I strength my requirement a bit, and consider a total recursive function $f_\alpha$ with $\alpha<\epsilon_0$. If the fundamental sequences here leading up to $\epsilon_0$ are computable, is $f_\alpha$ guarantee to be provably total then? And how do we prove (or disprove) it?

Answer 1

I think usually one adds the condition that $\phi$ be a $\Delta_1$ (i.e. computable) formula.

As Gro-Tsen has pointed out, the answer is no: there are lots of functions which are provably total, dominated by $f_{\epsilon_0}$, but not provably total in PA. First of all, you're not stating the sharpest version of the theorem. The theorem is that any function provably total in PA is eventually dominated by some $f_\alpha$ with $\alpha<\epsilon_0$. So any function which grows faster than all the $f_\alpha$ but slower than $\epsilon_0$ is still not provably total in PA. One can get many of these by the method Gro-Tsen's comment suggests: taking $f_{\epsilon_0}$ and slow it down just a little: none of $\lceil \log_2f_{\epsilon_0}\rceil$, $f_{\epsilon_0}/2$ and $f_{\epsilon_0}-1$ are provably total in PA.

Similarly, one can modify the definition of $f_{\epsilon_0}$ to diagonalize the $f_\alpha$ more slowly: recall that $f_{\epsilon_0}(n)=f_{\omega_n}(n)$ (where $\omega_n$ is a tower of exponentials of $\omega$ of height $n$). Consider the function $g(n)=f_{\omega_{\lfloor \log_2 n\rfloor}}(n)$, or replace $\log_2$ with any other function (possibly one which grows very slowly): one still diagonalizes all the $f_\alpha$, but one can do this very, very slowly.

Speaking of slow growing functions, consider the inverse of $f_{\epsilon_0}$: $h(n)$ is the least $m$ such that $f_{\epsilon_0}(m)>n$. This function is clearly total recursive, but actually grows too slowly to be provably total in PA.

Additionally, there are functions which, despite being slow growing, are just fundamentally too complicated to be provably total in PA. A function might have only $0$ and $1$ values, and therefore be dominated by the constant function, and yet not be provable in PA. For instance, consider the following. First, pick a pairing function $p:\mathbb{N}\rightarrow\mathbb{N}^2$. Given $n$, let $p(n)=(a,b)$; if $a$ is not the Gödel code of a $\Delta_1$ formula whose only free variables are $x,y$, $f(n)=0$. Suppose $a$ is the Gödel code of $\phi(x,y)$; if there is a proof in PA with $<f_{\epsilon_0}(n)$ steps that $\phi(n,0)$ holds, $f(n)=1$. Otherwise, $f(n)=0$.