Has decidability got something to do with primes?

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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 < q₁ < ... < q_k are positive rationals, the coefficient a₀ is an integer, and the remaining coefficients a₁,...,a_k are real algebraic numbers. Positivity is determined by the sign of the leading coefficient a_k; 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Δ₀) 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Δ₀. (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.

Answer 4

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!

Answer 5

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?'

Answer 6

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.