# 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 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.

• 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. – abcdxyz 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? – abcdxyz 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
• @AndrejBauer: You don't even need the prime 2. You could use the base $n$ expansion for any $n$ (such as $n=10$), regardless of whether it's prime... The main thing you're relying on is that $n^k > \sum_{i=0}^{k-1} n^i$ for any natural numbers $n,k$. – Joshua Grochow Mar 8 '18 at 18:25

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 – abcdxyz 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

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 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. – abcdxyz Apr 10 '10 at 19:01
• Note that they don't mention the connection with Robinson's Q, computability, and incompleteness. – François G. Dorais Apr 10 '10 at 19:03
• I'm enormously pleased to see mention of the ring with unboundedly many primes in which all are $1$ modulo $4$, as I have harboured a vague gut feeling there's some as yet unfound relation between the "positive" square roots and the "negative" square roots in $\Bbb{Z}_2^{\times}$ which extends the idea of $2$ being the "most prime prime"; and extends onwards to define limit points in $\Bbb{Z}_2^{\times}$ which end $\ldots01$ as opposed to $\ldots11$ as "special" in logic. – samerivertwice Mar 7 '18 at 13:45

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

You might be interested in A. Grzegorczyk's paper "Undecidability without arithmetization." (Studia Logica, 79(2): 163-230, 2005) in which he dispenses with arithmetization altogether (but does not dispense with coding, of course). You might also be interested in the following short paper that preceeded it: "Decidability without mathematics." (Annals of Pure and Applied Logic, 126(2004) 309-312). His formal theory of interest is a theory of concatenation he calls $TC$, which he is is able to prove undecidable. A clue as to how he does this is contained in the abstract to his paper "Decidability without mathematics.":

"The paper proposes a new definition of effectiveness (computability, general recursiveness, algoritmicity). A good name for this version of effectiveness is discernibility. This definition is based on the fact that every computation may be reduced to the operation of discerning the fundamental symbols and concatenation of formulas. This approach to effectiveness allows us to formulate the proof of undecidability in such a way that arithmetization of the syntax may be replaced by the use of concatenation in metalogic."

This (to me, at least) begs the following generalization of your question:

'What principle(s) of concatenation allow(s) for this to take place?'

• I think it's the inherent assumption that strings are closed under concatenation. In particular, if concatenation was replaced by a 3-input predicate-symbol $c$ such that $c(x,y,z)$ is intended to assert that $x+y=z$, and that uniqueness of $x$ is guaranteed for each $y,z$ if it exists, and likewise for $y$, then we escape the incompleteness theorems, I think. – user21820 Mar 28 '17 at 18:15

I know this is old, but there are still two unmentioned results that can shed some light.

The first is closely related to recursion (computability) theory and it follows from the diagonal lemma (see https://en.wikipedia.org/wiki/Diagonal_lemma for the basics). The assertion is that in order to prove the existence of an unprovable sentence in theory $T$, the theory must be able to represent all primitive recursive functions.

The diagonal lemma intuitively says that in all such $T$ there exists a sentence that is the fixed point of a function that assigns predicates to the Gödel numerals of sentences in $T$.

A different angle was pursued by Lawvere in "Diagonal Arguments and Cartesian Closed Categories". This approach is category-theoretic, but it yielded similar results. Lawvere proved that Tarski's undefinability theorem, Gödel incompleteness theorem, Cantor's powerset theorem, and Russel's paradox all follow from a fixed-point theorem in cartesian closed categories.

The basic requirements for the fixed-point theorem is that:

• $T$ must have a model that is a cartesian closed category (CCC).
• $T$ must prove the existence of an object $A$ and a map $f:A\longrightarrow Y^A$ that is weakly point-surjective in the CCC (see Lawvere's paper for details, it roughly concerns recovering truth values of maps to function spaces).

In conclusion, it seems that prime numbers are not specifically required for diagonal arguments. In general, decidability appears to be a more general concept that is independent of prime numbers. There is, however, a lot of information to be retrieved by analyzing the links between primitive recursive functions together with Gödel numberings, on the one hand, and CCCs together with weakly point-surjective morphism, on the other.