Note: I have modified the question to make it clearer and more relevant. That makes some of references to the old version no longer hold. I hope the victims won't be furious over this.
Motivation:
Recently Pace Nielsen asked the question "How do we recognize an integer inside the rationals?". That reminds me of this question I had in the past but did not have chance to ask since I did not know of MO.
There seems to be a few evidence which suggest some possible relationship between decidability and prime numbers:
1) Tameness and wildness of structures
One of the slogan of modern model theory is " Model theory = the geography of tame mathematics". Tame structure are structures in which a model of arithmetic can not be defined and hence we do not have incompleteness theorem. A structure which is not tame is wild.
The following structures are tame:
-
Algebraic closed fields. Proved by Tarski.
-
Real closed fields e.g $\mathbb{R}$. Proved by Tarski.
-
p-adic closed fields e.g $ \mathbb{Q}_p$. Proved by Ax and Kochen.
Tame structures often behave nicely. Tame structures often admits quantifier elimination i.e. every formula are equivalent to some quantifier free formula, thus the definable sets has simple description. Tame structures are decidable i.e there is a program which tell us which statements are true in these structure.
The following structures are wilds;
-
Natural number (Godel incompleteness theorem)
-
Rational number ( Julia Robinson)
Wild structure behaves badly (interestingly). There is no program telling us which statements are true in these structures.
One of the difference between the tame structure and wild structure is the presence of prime in the later. The suggestion is strongest for the case of p-adic field, we can see this as getting rid of all except for one prime.
2) The use of prime number in proof of incompleteness theorem
The proof of the incompleteness theorems has some fancy parts and some boring parts. The fancy parts involves Godel's Fixed point lemma and other things. The boring parts involves the proof that proofs can be coded using natural number. I am kind of convinced that the boring part is in fact deeper. I remember that at some place in the proof we need to use the Chinese Remainder theorem, and thus invoke something related to primes.
3) Decidability of Presburger arithmetic and Skolem arithmetic ( extracted from the answer of Grant Olney Passmore)
Presburger arithmetic is arithmetic of natural number with only addition. Skolem arithmetic is arithmetic of natural number with only multiplication.
Wishful thinking: The condition that primes or something alike definable in the theory will implies incompleteness. Conversely If a theory is incomplete, the incompleteness come from something like primes.
Questions:
(following suggestion by François G. Dorais)
Forward direction: Consider a bounded system of arithmetic, suppose the primes are definable in the system. Does it implies incompleteness.
Backward direction: Consider a bounded system of arithmetic, suppose the system can prove incompleteness theorem, is primes definable in the system? is the enumeration of prime definable? is the prime factoring function definable?
Status of the answer:
For the forward direction: A weak theory of prime does not implies incompleteness. For more details, see the answer of Grant Olney Passmore and answer of Neel Krishnaswami
For backward direction: The incompleteness does not necessary come from prime. It is not yet clear whether it must come from something alike prime. For more details, see the answer of Joel David Hamkins.
Since perhaps this is as much information I can get, I accept the first answer by Joel David Hamkins. Great thanks to Grant Olney Passmore and Neel Krishnaswami who also point out important aspects.
Recently, Francois G. Dorais also post a new and interesting answer.
Best Answer
Goedel did indeed use the Chinese remainder theorem in his proof of the Incompleteness theorem. This was used in what you describe as the `boring' part of the proof, the arithmetization of syntax. Contemporary researchers often agree with your later assessment, however, that the arithmetization of syntax is profound. This is the part of the proof that reveals the self-referential nature of elementary number theory, for example, since in talking about numbers we can in effect talk about statements involving numbers. Ultimately, we arrive in this way at a sentence that asserts its own unprovability, and this gives the Incompleteness Theorem straight away.
But there are other coding methods besides the Chinese Remainder theorem, and not all of them involve primes directly. For example, the only reason Goedel needed CRT was that he worked in a very limited formal language, just the ring theory language. But one can just as easily work in a richer language, with all primitive recursive functions, and the proof proceeds mostly as before, with a somewhat easier time for the coding part, involving no primes. Other proofs formalize the theory in the hereditary finite sets HF, which is mutually interpreted with the natural numbers N, and then the coding is fundamentally set-theoretic, also involving no primes numbers especially.