MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Is there any evidence for or against the idea that some of the important statements of number theory that have only been proved using infinite sets, are in fact undecidable in Peano arithmetic?

Most modern number theory is based, not on considering problems directly, but on applying some sort of complicated machinery. In particular, one works with infinite sets with various sorts of structure, like algebraic number fields, modular forms, and the Riemann zeta function.

I have sometimes wondered whether, with sufficient work and cleverness, one could reconstruct these proofs entirely in the language of elementary number theory. Theoretically, this should be possible, except for the fact that set theory is a stronger theory than Peano arithmetic or something else that represents elementary number theory. An example of this is the proof of the Ramsey theorem by way of the infinite Ramsey theorem. This proof cannot really be translated into arithmetic since it can also be used to prove the strengthened finite Ramsey theorem, which is undecidable in PA.

It is natural to conjecture that other results, like results about the distribution of primes which depend on zeta functions and related functions may also be undecidable. Is there any hard evidence that this is or is not the case?

share|cite|improve this question
The sets needed in most number theory are pretty benign. For instance, Riemann zeta function is computable, so there is no particular difficulty in defining it in first-order arithmetic. One can work with all the objects you mention (algebraic number fields, modular forms) in $\mathrm{ACA}_0$, which is a conservative extension of PA. A couple of weaks ago, Angus Macintyre had a tutorial at a meeting in Oberwolfach where he explained how one can formalize the basic concepts involved in the proof of Fermat’s last theorem in PA. – Emil Jeřábek Nov 24 '11 at 13:00
In the unlikely case that you are asking if there are statements in the language of PA that are decidable in ZFC but not in PA then the answer is positive, e.g. consistency of PA (or if you prefer the solvablity of the Diophantine equation corresponding to that). But I guess you have a more refined definition of what you mean by number theory. – Kaveh Nov 24 '11 at 18:38
See also this question:… – Kaveh Nov 24 '11 at 18:38
My question is whether relatively natural (e.g. short statement, and not contrived to be undecidable) statements, which mathematicians have, in practice, found very difficult to prove, are undecidable in PA. – Will Sawin Nov 28 '11 at 2:02
This can happen with combinatorial statements (Ramsey-like principles, Kruskal’s theorem, this kind of results). It usually does not happen in number theory, where proofs are often complex and ingenious, but relatively low level with respect to proof-theoretic strength. – Emil Jeřábek Nov 28 '11 at 12:59

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.