# Has decidability got something to do with primes?

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?

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.

-
The Godel encoding is totally irrelevant to the content of the incompleteness theorems; as is well-known, one can deduce the incompleteness theorems from the halting theorem in a straightforward manner without bringing this miscellaneous encoding stuff in (see for example scottaaronson.com/democritus/lec3.html). –  Qiaochu Yuan Mar 30 '10 at 18:05
Perhaps a better way to ask your question is whether every system of Bounded Arithmetic, for example, that can prove the Incompleteness Theorem (say) can also detect primes, enumerate primes, factor integers, etc. This can lead to very interesting questions. For example, although we know primes have a polynomial time detection algorithm, I don't think it's known whether this is provable in $S^1_2$. –  François G. Dorais Mar 30 '10 at 18:48
Qiaochu, you have merely internalized the encoding, as we all have, since the arithmetization of mathematics is now embedded everywhere. The same coding issue arises in the halting problem, which is about whether there is a program that can answer questions about programs. Of course, we are all used to the idea that programs or even pieces of literature can be coded as strings or numbers, such as with ASCII, and this is what arithmetization amounts to. –  Joel David Hamkins Mar 30 '10 at 18:52
@Qiaochu: You should be careful with words like "totally irrelevant". The relevant passage in Scott's notes is "(This is possible because the statement that a particular computer program halts is ultimately just a statement about integers.)" There's your encoding! This is also what Tran refers to when he says "the boring part"; it's often mentioned only in passing. –  aorq Mar 30 '10 at 19:01
<< One of the slogan of modern model theory is " Model theory = the geography of tame mathematics". >> Seems a little narrow-minded ... –  Simon Thomas Mar 30 '10 at 22:59

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 it's 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.

-
I am in a dilemma, it would be nicer if the answer is yes. On one hand I believe in you. On the other hand, I want to hold to the fleeting dream. :D So I wait. –  Tran Chieu Minh Mar 30 '10 at 18:20
To poke further holes in your dream, observe that arithmetization can be done with finite binary strings (just 0's and 1's). To encode and talk about such strings in the language of natural numbers you only need to know about the properties of the prime number 2, not all of them. Perhaps you just have to see an alternative arithmetization that does not rely on the Chinese Remainder theorem. –  Andrej Bauer Apr 2 '10 at 8:57
May you refer me to some source of different arithmetization that does not rely on Chinese Remainder theorem? –  Tran Chieu Minh Apr 2 '10 at 9:58
See Raymond Smullyan's Theory of Formal Systems (Princeton University Press, 1961). –  John Stillwell Apr 10 '10 at 22:15
Thank you for the reference. –  Tran Chieu Minh Apr 11 '10 at 12:57

In response to your statement: "It appears that the condition that primes are definable in the theory will implies incompleteness."

The primes being definable in an arithmetic theory does not necessarily lead to incompleteness. The theory of Skolem arithmetic ($Th(\langle\mathbb{N},*\rangle)$) is decidable and admits quantifier elimination (it is the elementary true theory of the weak-direct power of the standard model of Presburger arithmetic, so Feferman-Vaught quantifier-elimination lifting applies). A predicate for primality can easily be expressed in the language of this theory. This is due to Skolem and Mostowski initially, and to Feferman-Vaught when obtained in terms of weak-direct powers.

Moreover, Skolem arithmetic extended with the usual order restricted to primes is decidable, admits quantifier elimination, and in fact $Th(\langle\mathbb{N},*,<_p\rangle)$ and $Th(\langle\omega^\omega,+\rangle)$ are reducible to each other in linear time. This is due to Francoise Maurin (see "The Theory of Integer Multiplication with Order Restricted to Primes in Decidable" - J. Symbolic Logic, Volume 62, Issue 1 (1997), 123-130).

Note that in this latter case, the ordering cannot be the full ordering on the natural numbers, as this would allow one to define a successor predicate, and Julia Robinson showed successor and multiplication are sufficient for defining addition.

-
Interesting, reading from the paper that you gave, the theory of integer multiplication is decidable, but the theory of integer multiplication with the natural ordering is not. So the "infinite prime" has some job. :D –  Tran Chieu Minh Mar 30 '10 at 20:20
I had never heard of Skolem arithmetic before -- it's really cool to learn that either one of addition or multiplication is decidable, but the combination isn't. –  Neel Krishnaswami Apr 1 '10 at 7:47

Another evidence which I think might be relevant: The proof of the incompleteness theorems has some fancy part and some boring part. The fancy part involves Godel's Fixed point lemma and other things. The boring part involves the proof that proofs can be coded using natural number. I am kind of convinced that the boring part is perhaps 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.

The key bit in the incompleteness proof is the fact that multiplication is total. This is what lets you freely build representations of terms out of representations of terms.

Dan Willard has given "self-verifying" logics, which are logics to which a self-consistency principle can be consistently added. There, the trick is to remove addition and multiplication, and replace them with subtraction and division. In these logics, the totality of multiplication is not provable, and so the logic can represent its Godel encodings, but cannot do enough with them to let the fixed point lemma go through.

Since multiplication and primes go together like hazelnuts and chocolate, such tweaks to the status of multiplication probably suggest that there are deep connections to number theory. But I don't know enough to say!

-
+1 Very good point. It's worth pointing out that Willard's system does express multiplication in terms of division, as a relation, but it fails to prove the multiplication relation expresses a total function, although all and only the expected constant instances are true. Since Willard's system thereby has the same prime numbers as usual arithmetic, and has their primality as theorems, we have the converse to Joel's point: presence of (a weak theory of) primes together with completeness. –  Charles Stewart Mar 31 '10 at 8:18

The role of primes in Gödel's Incompleteness Theorem can be better understood by looking at Robinson's Q, which is one of the weakest theories of arithmetic for which Gödel's Incompleteness Theorem holds. Robinson derived his original axioms for Q by looking at the axioms of PA that were used in the proof that every computable function can be represented in PA, which is the key part of Gödel's argument.

A simple theory that interprets Robinson's Q is the theory of discrete ordered rings with induction for open formulas, i.e. the schema φ(0) ∧ ∀x(φ(x) → φ(x+1)) → ∀x(x ≥ 0 → φ(x)), where φ is a quantifier-free formula in the language of ordered rings which may contain free variables other than x. (The only existential quantifier in the axiomatization of Q, namely in the axiom x = 0 ∨ ∃y(x = Sy), can be eliminated since we now have subtraction.)

The theory of discrete ordered rings with open induction has interested many logicians. The first to study this theory was Shepherdson (A non-standard model for a free variable fragment of number theory, MR161798) who showed that this theory cannot prove that √2 is irrational. It follows that Robinson's Q also cannot prove the irrationality of √2. Since the irrationality of √2 is a consequence of unique factorization into primes, Robinson's Q cannot prove that either.

Shepherdson's model where √2 is rational is the ring S whose elements are expressions of the form $$a_0 + a_1T^{q_1} + \cdots + a_kT^{q_k}$$ where T is an indeterminate, the exponents 0 < q1 < ... < qk are positive rationals, the coefficient a0 is an integer, and the remaining coefficients a1,...,ak are real algebraic numbers. Positivity is determined by the sign of the leading coefficient ak; this corresponds to making T infinitely large. The fact that this satisfies open induction is very remarkable. In this ring S, the only primes are the primes from ℤ, so there are simply no infinite primes. Therefore, Robinson's Q cannot prove that the primes are unbounded.

Still stranger discrete ordered rings with open induction have been constructed by Macintyre and Marker (Primes and their residue rings in models of open induction, MR1001418). For example, they construct such a ring where there are unboundedly many primes, but all infinite primes are congruent to 1 modulo 4.

It is apparently still unknown whether the induction axiom for bounded quantifier formulas (IΔ0) proves the unboundedness of prime numbers. This problem was raised by Wilkie and the first partial answer came from Alan Woods who linked it to a pigeonhole principle, together Paris, Wilkie, and Woods (Provability of the pigeonhole principle and the existence of infinitely many primes, MR973114) showed that the unboundedness of prime numbers is provable in a very small extension of IΔ0. (See also this recent article by Woods and Cornaros MR2518806.)

The above shows that a sound theory of primes and factorization is not necessary for Gödel's Incompleteness Theorem. However, this should be taken with a grain of salt. The key feature of Robinson's Q is that it correctly interprets the basic arithmetic as far as the standard natural numbers are concerned, and nothing more. The fact that Robinson's Q doesn't say much about what is happening outside the standard integers does not mean that the certain features, like primality, that make up the rich and complex structure of the standard integers is completely irrelevant to Gödel's Incompleteness Theorem.

-
I don't understand why you answer is community wiki? –  Tran Chieu Minh Apr 10 '10 at 18:25
The question was edited too often, once the question is community wiki then so are all new answers... –  François G. Dorais Apr 10 '10 at 18:32
Ah, sorry for that, my fault :( –  Tran Chieu Minh Apr 10 '10 at 18:42
Don't worry. It's of no important consequence. –  François G. Dorais Apr 10 '10 at 18:45
I was surprised that Wilkie, Macintyre and Marker wrote something on this topic. I thought they are model theorists and this question is more toward recursion theory. –  Tran Chieu Minh Apr 10 '10 at 19:01