3
$\begingroup$

Goodstein's theorem is an example of a statement that is not provable in PA. The Goodstein function, $\mathcal {G}:\mathbb {N} \to \mathbb {N}$, defined such that $\mathcal {G}(n)$ is the length of the Goodstein sequence that starts with $n$ is a total function that grows faster than any primitive recursive function.

Paris–Harrington theorem is another example of a statement not provable in PA. Wiki says "The smallest number $N$ that satisfies the strengthened finite Ramsey theorem is then a computable function of $n, m, k$, but grows extremely fast. ... It dominates every computable function provably total in Peano arithmetic, which includes functions such as the Ackermann function."

This question is perhaps a bit vague, but along the lines of the above examples, are there statements not provable in PA that only make use of functions that grow no faster than primitive recursive functions? (are fast growing functions in unprovable statements a coincidence or unrelated?)

$\endgroup$
2
  • 1
    $\begingroup$ How about $Con(PA)$? $\endgroup$
    – Karl
    Commented Feb 8 at 19:05
  • $\begingroup$ @Karl: Indeed, any $\Pi^0_1$ sentence that's not provably false in PA should do the job, right? Adding such a statement create no new proofs of totality. But the details depend on the specifics of PA (it's easy to create theories where thr abalogous property fails). If you sketch a proof, that's an answer to the question. $\endgroup$
    – Z. A. K.
    Commented Feb 9 at 7:34

1 Answer 1

0
$\begingroup$

In this paper, it's shown to be an "if and only if" situation. Theorem 3 states "Every function appearing in the Fast Growing Hierarchy below level $\epsilon_0$ is provably computable in PA". This means that every function which grows "fast" (ie, is not dominated by any $F_{\alpha}$) is unprovable in PA, and every function which is dominated by one of the fast growing functions is provable in PA. So the example you are looking for does not exist.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .