This question relates to a discussion on another message board. Euclid's proof of the infinitude of primes is an indirect proof (a.k.a. proof by contradiction, reductio ad absurdum, modus tollens). My understanding is that Intuitionists reject such proofs because they rely on the Law of the Excluded Middle, which they don't accept. Does there exist a direct and constructive proof of the infinitude of primes?
Is there an intuitionist (i.e., constructive) proof of the infinitude of primes?
-
0This boils down to the fact that $\forall$ is no longer a direct contradiction of $\exists$. So you can't think in duality. One is false then the other is right. Maybe everything is a foam. – 2012-01-07
5 Answers
Due to a widely propagated historical error, it is commonly misbelieved that Euclid's proof was by contradiction. This is false. Euclid's proof was in fact presented in the obvious constructive fashion. See Hardy and Woodgold's Intelligencer article[1] for a detailed analysis of the history (based in part on many sci.math discussions [2]).
The key idea is not that Euclid's sequence $\ f_1 = 2,\ \ \color{#0a0}{f_{n}} = \,\color{#a5f}{\bf 1}\, +\, f_1\cdot\cdot\cdot\cdot\, f_{n-1}$ is an infinite sequence of primes but, rather, that it's an infinite sequence of coprimes, i.e. $\,{\rm gcd}(f_k,f_n) = 1\,$ since, if $\,k
Any infinite sequence of pairwise coprime $\,f_n > 1 \,$ yields an infinite sequence of distinct primes $\, p_n $ obtained by choosing $\,p_n$ to be any prime factor of $\,f_n,\,$ e.g. its least factor $> 1$.
A variant that deserves to be much better known is the following folklore one-line proof that there are infinitely many prime integers
$\rm\qquad\qquad N\ (N+1)\ $ has a larger set of prime factors than does $\rm\:N.$
because $\rm\,N+1>1\,$ is coprime to $\,\rm N\,$ so it has a prime factor which does not divide $\rm\,N.$ Curiously, Ribenboim believes this proof to be of recent vintage, attributing it to Filip Saidak. But I recall seeing variants published long ago. Does anyone know its history?
For even further variety, here is a version of Euclid's proof reformulated into infinite descent form. If there are only finitely many primes, then given any prime $\rm\:p\:$ there exists a smaller prime, namely the least factor $> 1$ of $\rm\ 1 + $ product of all primes $\rm \ge p\:.$
It deserves to be much better known that Euclid's constructive proof generalizes very widely - to any fewunit ring, i.e. any ring having fewer units than elements - see my proof here. $ $ The key idea is that Euclid's construction of a new prime generalizes from elements to ideals, i.e. given some maximal ideals $\rm\ P_1,\ldots,P_k\:,\: $ a simple pigeonhole argument employing $\rm CRT$ deduces that $\rm\ 1+P_1\:\cdots\:P_k\ $ contains a nonunit, which lies in some maximal ideal which, by construction, is comaximal (so distinct) from the initial max ideals $\rm\:P_1,\ldots,P_k\:.$
[1] Michael Hardy; Catherine Woodgold
Prime Simplicity.
The Mathematical Intelligencer, Volume 31, Number 4, 44-52.
DOI link $ $ or $ $ Springer link $ $ or $ $ free link
[2] Note: Although the article [1] makes no mention of such, it appears to have strong roots in frequent sci.math discussions - in which the first author briefly participated. A Google groups search in the usenet newsgroup sci.math for "Euclid plutonium" will turn up many long discussions on various misinterpretations of Euclid's proof.
-
3In constructive mathematics, the statement "there is not a finite number of primes" is weaker than "there is an injective function with domain $\mathbb{N}$ whose range includes only primes". The second is a much more interesting theorem for them, so that's the way that they would normally work with it, but they could use it to prove the weaker one if they wanted. They are used to the fact that classical statements often have to be reworded to be constructively interesting, because classical mathematicians often state things negatively when constructivists would prefer to work positively. – 2011-04-02
Your question is predicated on a common misconception. In fact Euclid's proof is thoroughly constructive: it gives an algorithm which, upon being given as input any finite set of prime numbers, outputs a prime number which is not in the set.
Added: For a bit more on mathematical issues related to the above algorithm, see Problem 6 here. (This is one of the more interesting problems on the first problem set of an advanced undergraduate number theory course that I teach from time to time.)
-
2@DavidKohler so, extend the algorithm with "and then factor the result" :) – 2013-05-19
Euclid's theorem is intuitionistic. Given any finite set S of primes, their product plus one is not divisible by any of the primes and hence is divisible by some prime not in S. This gives a concrete upper bound on the n-th prime as well -- though of course it's astronomical.
-
1@Zirui Wang Re law of excluded middle and Gödel's incompleteness theorem. Gödel's incompleteness theorem states that any consistent system has statments where neither the statment nor the negation of the statement can be proven. This is trivially true for constuctivistic logics. – 2014-01-09
Here's a simple direct proof that not only shows there is an infinite number of primes, but gives a lower bound on how many primes are less than $N$. The idea comes from Erdős.
Let $\pi(N)$ be the number of primes $\leq N$ for a positive integer N. Any positive integer $\leq N$ can be written in the form $B^2{p_1}^{e_1} {p_2}^{e_2} ... {p_{\pi(N)}}^{e_{\pi(N)}}$ where the $e_i$'s are 0 or 1 and $B\leq \sqrt N$.
There are at most $2^{\pi(N)}\sqrt N$ possible numbers of this form, and so we have $2^{\pi(N)}\sqrt{N}\geq N$ which gives us $\pi(N)\geq {\log{N}\over{2 \log 2}}$ which is clearly unbounded.
This idea is used in Erdos' nice proof that $\sum {1\over p}$ diverges, although that is a proof by contradiction and so would not satisfy the intuitionist school. It goes like this. Assume the sum converges. Then there is some $k$ such that ${\sum_{i \geq k+1}} {1\over p_i} < 1/2$. Call the primes $\leq p_k$ the "small" primes, and the primes $\geq p_{k+1}$ the "big" primes. We can divide the positive integers $\leq N$, for arbitrary N, into two groups: those that are divisible by a "big" prime, and those that are not. An upper limit on the number divisible by a "big" prime is $N/2$ (this comes from the assumption that the sum of the reciprocals of the big primes is $\leq 1/2$), and an upper limit on the number not divisible by a "big" prime is $2^k\sqrt N$. Since those two categories include all the positive integers $\leq N$, we must have $N/2+2^k \sqrt N \geq N$. However, that is not true for sufficiently large $N$, and so we have our contradiction, and the series diverges.
-
0But how do you prove that form, which is the heart of this proof? Do you have a reference? – 2012-01-07