14

Euclid's theorem that there are infinitely many prime numbers has multiple proofs, ranging from Euclid's original theorem that constructs a new prime from a finite list of such, to Euler's proof that requires the theory of infinite products and sums. The latter is clearly ingenious, but overkill, whereas the former is elegant, simple, and often shown as an example of a proof to people with little mathematical background (eg students, readers of popular mathematics books).

I'm curious to know what fragment of arithmetic is needed to perform Euclid's proof, or otherwise, if there is an even lower bound on the logical strength of the theorem.

Community
  • 1
David Roberts
  • 33,851
  • The existence of infinitely many natural integers and of irreducible factors for each of them is clearly needed. I'm not sure the unicity of the decomposition is needed. – Sylvain JULIEN Dec 28 '18 at 22:35
  • I think you need something morally equivalent to the well founded ness of the divisibility relation, as well as something asserting the infinitude of the natural numbers. After that the rest should be doable in a weak fragment of primitive recursive arithmetic. Gerhard "Need Room To Work In" Paseman, 2018.12.28. – Gerhard Paseman Dec 28 '18 at 22:42
  • 2
    There are some strange models of open induction in which $\sqrt{2}$ is rational, as discussed elsewhere here on MO. Can we find such strange models where the primes are bounded? – Joel David Hamkins Dec 28 '18 at 23:09
  • 12
    You can prove Euclid’s result in bounded arithmetic ($I\Delta_0$) plus the assumption that $x^{\log x}$ exists, or in bounded arithmetic plus a pigeonhole principle that there are no definable injections from $n+1$ to $n$. See Paris, Wilkie and Woods (JSL 1988), Provability of the Pigeonhole Principle and the Existence of Infinitely Many Primes. This is already quite weak, and has been further weakened more recently, but it’s an open question whether bounded arithmetic on its own would suffice. –  Dec 28 '18 at 23:34
  • @MattF. very nice. I guess you are referring to On bounded arithmetic augmented by the ability to count certain sets of primes (https://doi.org/10.2178/jsl/1243948322) by Woods and Cornaros? – David Roberts Dec 29 '18 at 01:48
  • I don’t know the recent results; I’d rather defer to @EmilJerabek if he wants to comment. –  Dec 29 '18 at 03:14
  • 7
    Nothing better is known that the argument from the Paris–Wilkie–Woods paper, which can be formalized in the fragment $S^1_2+\mathit{rWPHP}(\mathrm{FP}^{\mathrm{NP}[O(\log n)]})$ (included in $T^3_2$) of bounded arithmetic with the $x^{\log x}$ function ($I\Delta_0+\Omega_1$) if one pays attention to the complexity of the functions used. The Woods and Cornaros paper is not an improvement, but a tangent: it concerns $I\Delta_0$ augmented with certain prime-counting functions, which are not known (and unlikely) to be definable in $I\Delta_0+\Omega_1$, only in $I\Delta_0+\mathit{EXP}$. – Emil Jeřábek Dec 29 '18 at 08:23
  • 6
    @JoelDavidHamkins Absolutely. There are models of IOpen where primes are bounded. – Emil Jeřábek Dec 29 '18 at 08:26
  • 1
    @Emil thanks, that helps! This would make a good answer. – David Roberts Dec 29 '18 at 09:07
  • @EmilJeřábek : Entering IOpen into Google, I find an Australian software company, and I don't think that's what you meant. So if you post an answer, maybe that can be explained. However, I wonder if that would be a complete answer. Specifically, how much more than "IOpen" would be needed for Euclid's theorem to hold? $\qquad$ – Michael Hardy Dec 30 '18 at 19:11
  • 3
    For the record, Euclid showed that for every finite set $S$ of primes, the prime factors of $1 + \prod S$ are not in $S$. Euclid did NOT start by assuming the finite set $S$ contains all primes. The error or thinking that that's what Euclid did may have originated with Dirichlet's posthumous book on number theory, where that's very close to the beginning of the book. – Michael Hardy Dec 30 '18 at 19:13
  • $\ldots,$ maybe I should say Euclid considered $1 + \operatorname{lcm}(S).$ Same number, but that's what he did. Might there be some of these weak models of arithmetic in which the l.c.m. of a set of primes differs from their product? $\qquad$ – Michael Hardy Dec 30 '18 at 19:20
  • $\ldots,$weak THEORIES of arithmetic, I should have written. $\qquad$ – Michael Hardy Dec 30 '18 at 19:26
  • $\ldots,$and I should add, the original posting above is innocent of Dirichlet's error. $\qquad$ – Michael Hardy Dec 30 '18 at 19:27
  • 8
    A tangential comment, well-known but perhaps not as well-known as it should be: The hypothesis that $x^{\log x}$ exists is more natural than it looks. Call a natural number $n$ small if $2^n$ exists. Then the hypothesis says (in reasonable contexts) that any product of two small numbers is small. – Andreas Blass Dec 30 '18 at 22:32
  • Strongly related old post: https://mathoverflow.net/questions/19857/has-decidability-got-something-to-do-with-primes – François G. Dorais Dec 30 '18 at 22:54
  • @MichaelHardy you can see the definition of what I guess is IOpen in the answer https://mathoverflow.net/a/20944/4177 at the question mentioned by François – David Roberts Dec 31 '18 at 06:57

0 Answers0