Looking for counterexamples where the output of a computable function always has a computably checkable property, but PA cannot prove this Suppose we have a computable function $f$, say over the naturals, and a decidable set $S$ of naturals, such that $f(x) \in S$ for all $x$. In this case, for any specific $x$, there is some specific number $y$ such that Peano arithmetic proves $y = f(x)$. (This follows from the fact that $f$ is computable.) Moreover, by our supposition $y \in S$, and since $S$ is decidable, PA proves that $y \in S$. So PA proves the statements $f(1) \in S, f(2) \in S, f(3) \in S, ...$. But yet it might not prove $\forall x (f(x) \in S)$.
I would like to see an example of a function $f$ and set $S$ for which this situation obtains: that is, $f$ is computable and $S$ is decidable, and $\forall x (f(x) \in S)$, but PA does not prove this.
 A: An obvious example is the function $f$ that takes values $0$ and $1$, and $f(n)=1$ iff $n$ codes a proof in $\mathsf{PA}$ of "$0=1$". Here, $S=\{0\}$ but we cannot prove $\forall x\,(f(x)=0)$ because of the second incompleteness theorem.
We can modify this example easily: Let $S$ be any decidable set other than $\mathbb N$ and $\emptyset$. Let $m\notin S$, and consider any Turing machine $T$ that gives us a computable function $f$ with range contained in $S$ (that is, for any input $n$, $T$ halts with output in $S$). Modify $T$ to a new machine $T'$ so that with input $n$, if $n$ codes a contradiction as above, then $T'$ halts with output $m$. Else, $T'$ executes $T$ with input $n$ (and halts when $T$ does, with the same output). Here, $\forall x\, \hat f(x)\in S)$ is not provable, where $\hat f$ is the computable function given by $T'$. One can easily modify this example to include the case $S=\emptyset$, where "$f(x)\in S$" is understood as "$x$ is not in the domain of $f$" (or "$T$ does not halt with input $x$", if you wish).
For a more interesting example, consider the typical true $\Pi^0_2$ statements unprovable in $\mathsf{PA}$, such as the strong Ramsey theorem, Goodstein's theorem, Hercules-Hydra theorem, the Kanamori-McAloon theorem, etc. All these are statements of the form "For all $n$ there is an $m$ such that $\psi(n,m)$", where $\psi(n,m)$ is provable in $\mathsf{PA}$ for each $n$ and appropriate $m$. In fact, for each $n$, the statement $\exists y\,\psi(n,y)$ is provable. But the full statement $\forall x\exists y\,\psi(x,y)$ is unprovable. Note that any such statement comes associated with a computable function $g$, where $g(n)=m$ iff $\psi(n,m)$ (and $m$ is least possible; this last requirement can be easily added in each of these cases without affecting computability). You may want to look at the paper 

Laurie Kirby, and Jeff Paris. Accessible independence results for Peano arithmetic, Bull. London Math. Soc., 14 (4), (1982), 285–293. MR0663480 (83j:03096).

What Kirby and Paris do in that paper is to develop the method of indicators from which most of these results can be verified. They show how, starting from a nonstandard model $M$ of $\mathsf{PA}$, one can identify a proper initial segment $I$ of the model that is also a nonstandard model of $\mathsf{PA}$ but such that $g$ is not a total function in $I$, that is, there is a nonstandard number $N$ such that $g(N)\in M\setminus I$. 
For any such $g$, we can give an example of the property you are interested: Simply let $f(n)=0$ iff $\mathsf{PA}$ proves that $g(n)$ is defined. Here, $\mathsf{PA}$ cannot prove that $\forall x\,(f(x)=0)$ or, equivalently, that $g$ is total, since this would mean that $g$ is total in all nonstandard models, including $I$, where it is not. For a different approach, you may want to read on the fast-growing hierarchy. This is a hierarchy of computable provably total functions indexed by ordinal numbers:


*

*$f_0(x)=x+1$.

*For $\alpha<\varepsilon_0$, $f_{\alpha+1}(n)=f_\alpha^n(n)$, where the superindex indicates that $f_\alpha$ is iterated $n$ times. 

*For limit $\alpha<\varepsilon_0$, $f_\alpha(n)=f_{d(\alpha,n)}(n)$.


Here, $(d(\alpha,n)\mid n\in\mathbb N)$ is an explicitly given, strictly increasing sequence of ordinals with limit $\alpha$, and $\varepsilon_0$ is the supremum of the sequence $\omega,\omega^\omega,\omega^{\omega^\omega},\dots$, where exponentiation is in the ordinal sense (so all these are countable ordinals). A theorem of Wainer shows that if a computable function $f$ is provably total in $\mathsf{PA}$, then there is some $\alpha<\varepsilon_0$ such that $f(n)<f_\alpha(n)$ for all but finitely many values of $n$ (for a proof, look at the references in my paper on Goodstein's function). The function $g$ associated to the examples above actually satisfies that for each $\alpha<\varepsilon_0$, we have $f_\alpha(n)<g(n)$ for all but finitely many $n$. Any such fast-growing $g$ gives us an example of a computable $f$ with the unprovability property under discussion.
