A colleague of mine was stating there are no known undecidable statements that have explicit connection with prime numbers. What does this mean? I understand that it is unknown whether Goldbach conjecture, twin prime conjecture etc are not known to be undecidable.
Is there non-trivial examples of statements in number theory that involve properties of prime numbers?
Best Answer
I believe there are not (or rather, if there are they are highly contrived), but that this is mostly a symptom of our lack of techniques for showing undecidability.
How can I prove that $PA$ does not prove $\varphi$? Well, this requires that I build a model of $PA+\neg\varphi$. Unfortunately, we don't really know how to build models of $PA$. Set theory is easier, surprisingly - forcing is a powerful tool there. However, forcing doesn't reach the arithmetic part of the set-theoretic universe; precisely, Shoenfield absoluteness states that forcing can't change the truth value of any $\Pi^1_2$ sentence with real parameters, and this contains (and greatly exceeds) the class of sentences expressible in the language of $PA$.
In fact, basically the only way we know how to show that $PA$ doesn't prove $\varphi$ (besides proving $\neg\varphi$ in some theory we trust) is to show that $\varphi$ implies the consistency of $PA$, and then use Goedel's theorem. Now, how do we do that?
One direction is to bring proof theory into play: beginning with work of Gentzen, it was discovered that the consistency of a theory like $PA$ can be proved assuming "sufficient induction," and that that in turn can be extracted from fast-growing functions.
So, the types of sentences we know how to prove independent of $PA$ are those which
(1) are provably true in some stronger theory we believe in (say, $ZFC$), so that we're confident they are not disproved by $PA$, and
(2) imply the consistency of $PA$, usually via the construction of a sufficiently fast-growing function.
So if you're looking for an undecidable sentence in arithmetic, the best place to start is a field with truly ludicrous upper bounds . . .
. . . like Ramsey theory! And indeed this is where the principle studied by Paris and Harrington lives, among many others. By contrast, thinking about Twin Primes (for example), there is no reason to believe that twin primes are particularly "sparse" (see e.g. http://www.ams.org/samplings/feature-column/fc-2014-11), so we have no reason to believe that the "Next Twin Prime" function would be fast-growing enough for our purposes.
Another direction - more recent - is the use of Ramsey-type principles to build models of strong theories, which imply the consistency of $PA$. I know much less about these methods, but I believe they implicitly go through fast-growing functions as well; certainly they stay firmly within the realm of combinatorial (or analytic) principles, rather than the truly number-theoretic.
See this paper of Bovykin for more details (on all types of independence proofs in arithmetic, really), as well as this paper by Putnam presenting a model-theoretic proof (due to Kripke) of the incompleteness of $PA$.