#proof-theory #philosophy-of-math

Theorem 1 : There are infinitely many primes.

Euclid's proof of the infinitude of primes is one of the first examples of mathematical proof that students encounter. It goes roughly as follows:

Proof 1 (Euclid)
Suppose there are only finitely many primes $p_1<\cdots <p_k$, so that $p_k$ is the largest prime. Define $\pi :=1+\prod p_i$. Then none of the $p_i$ divide $\pi$, so $\pi$ must be prime, as every positive integer greater than $1$ admits a prime factorization. But $p_k<\pi$, contradicting the assumption that $p_k$ is the largest prime. Therefore, there are infinitely many primes.

It is elegant: it is succinct, effective, simple in structure, and uses few assumptions. It is methodologically pure: the techniques and auxiliary lemmas used are number-theoretic in nature. And it promotes understanding: the explicit construction of $p$ appears to convey why there cannot be finitely many primes. Indeed, this proof seems to be one of the most promising candidates for inclusion in "The Book," Pál Erdős' imagined collection of the most elegant mathematical proofs.

Of course, according to the peculiar mathematical tradition of re-proving established results, dozens of alternate proofs of Theorem 1 have since been proposed. A particularly striking example is Harry Furstenburg's 1955 proof, relying on (what he claimed was) a topological argument. Here is a sketch of Furstenburg's version:

Proof 2 (Furstenburg)
Observe that the collection of arithmetic progressions from $-\mathrm{\infty }$ to $\mathrm{\infty }$ furnishes a basis for a topology on $\mathbb{Z}$. Each arithmetic progression is also closed, as its complement is the union of finitely many other arithmetic progressions. Therefore, the union of finitely many arithmetic progressions is closed. Define $A=\bigcup A_p$, where $A_p$ is the set of multiples of $p$ and $p$ varies over the set of primes. Then $\mathbb{Z}\setminus A=\{-1,1\}$. Since $\{-1,1\}$ is not open, $A$ cannot be closed; in particular, $A$ is not a finite union of closed sets. Therefore, there are infinitely many primes.

While Furstenburg's argument hinges on properties of open and closed sets, it is not immediately clear that this appeal to a topological structure is actually essential to the argumentative structure of this proof. The integers are not an object that topological methods are "meant" to analyze: the intuitive schema of continuous transformations between continuous spaces, that motivated the the axioms of topological spaces in the first place, does not apply to the integers. Indeed, the integers are in a sense, (if viewed as an extension of the Peano characterization of the natural numbers) a fundamentally discrete, inductively generated collection. This suggest that Furstenburg's proof is not methodologically pure; the language of the proof differs significantly from the language used to formulate the proposition.

This is not to say that this sort of methodological impurity should be discouraged in mathematics. Divergence from purity of method is, in many cases, precisely that which drives mathematical discovery and insight. This is related to the concept of mathematical depth; a proof might be said to be deep if it unites ideas from different areas of mathematics in a novel or surprising way. Indeed, many of the most important (and deepest) branches of modern mathematical research are founded explicitly on cross-disciplinary connections that defy methodological boundaries. The abstraction that results from formalizing intuition into general mathematical definitions is a powerful tool; mathematics would certainly be impoverished if we could only apply "methodologically pure" tools to a given problem.

This note seeks to tease out the coincident underlying structure of Euclid's and Furstenburg's proofs, which exists independently of method. The ultimate aim of this study is to uncover structural and epistemic invariants of informal mathematical proofs, in analog to Dominic Hughes' combinatorial proofs as an invariant on proofs in propositional logic.

My claim is that Euclid's proof is a "minimal" representative in the equivalence class of proofs establishing Theorem 1, and that the mapping of any other proof in this class (Furstenburg's, say) to the proposition it establishes factors through Euclid's proof. That is, there is an explicit "structural" reduction of Furstenburg's proof that reduces it to Euclid's argument, which in turn establishes Theorem 1.

There is a straightforward notion of equivalence for propositions. Two propositions are equivalent if each entails the other. For equivalent propositions $P$ and $Q$, mathematicians often pass quite freely between proofs of one or the other, not even distinguishing between their teleological character. Sieg, for example, asked the question "The Cantor-Bernstein theorem: how many proofs?". The bulk of his analysis, however, is devoted to comparing proofs of Dedekind's "fundamental lemma," a statement which is equivalent to the Cantor-Bernstein theorem. Claiming that two proofs of the fundamental lemma are equivalent, this notion of equivalence in the collection of proofs of the fundamental lemma passes naturally to an equivalence of the associated proofs of the Cantor-Bernstein theorem.

This flexibility is simply a consequence of the way these equivalences behave; they are defined such that the mapping from proofs to propositions is stable on equivalence classes. So why do mathematicians bother to re-prove theorems at all? This question has been well-treated by mathematicians and philosophers alike, with a prevailing point of view being that this practice promotes mathematical understanding, which can in turn catalyze the development of new techniques to enable mathematical discovery. More relevant to this context, new proofs of already established theorems may also differ from old proofs along dimensions of purity, depth, rigor, cognitive efficiency, or other qualitative features of informal proof.

In the case of purity, different methodological or syntactic instantiations of the same minimal proof structure are more (or less) well-suited to prove different members of the corresponding equivalence class of propositions. This inverts the usual notion of methodological purity; rather than the statement of the proposition determining the purity of proofs, the minimal proof of a class of propositions determines the minimal, or "purest," representative of that class. This suggests that the meaning of a proposition (rather, an equivalence class of propositions), is in this sense determined by the minimal representative of the the associated class of proofs.

These two claims are quite strong, and they require much substantiation: we will use Euclid's proof of the infinitude of primes as a case study. The goal of this note is to suggest that Euclid's proof is the minimal representative of the appropriate class of proofs, with a view toward finding a mathematical procedure to reduce Furstenburg's proof to Euclid's. In this way, the problem of the infinitude of primes is (unsurprisingly) number-theoretic in nature rather than, say, topological. On this basis, Euclid's argument is the most qualified candidate for a "Book" proof of the infinitude of primes.

Furstenburg $⟹$ Mercer

Over half a century after Furstenburg's proof, Idris Mercer, perhaps with similar considerations in mind, claimed to give a "variant of Furstenburg's proof that avoids topological language." This wording is striking: after removing the topological language, what remains of Furstenburg's proof? Mercer makes an implicit claim that Furstenburg's proof is not essentially topological. Thus, Mercer commits to the existence of an underlying argument structure that is independent of method. This attitude is not uncommon in mathematics. Authors often refer to "standard ___ arguments" to describe families of well-known proof techniques, even in contexts quite distant from those in which they first arose. The reader has surely encountered diagonal arguments, compactness arguments, fixed-point arguments, symmetry arguments, counting arguments, and so on.

Here is a sketch of Mercer's variant of Furstenburg's proof. He includes two lemmas, which are preserved here for later reference.

Proof 3 (Mercer)
Lemma 1: A finite intersection of arithmetic progressions is either empty or infinite.
Proof. Let $I=\bigcap _{i=1}^k\{\{n_i+d_i\mathbb{Z}\}\}$ be an intersection of a finite collection of arithmetic progressions. We may assume that $I$ has an element, as is trivial to construct an empty intersection. Let $x\in I$, so that $x\equiv n_i(\mathrm{mod}{d}_i)$ for all $i$. Then for all $y\in \{j\prod _i{d}_i:j\in \mathbb{Z}\}$, $x+y\in I$ as well.
Lemma 2: For a collection of sets $\mathcal{S}$, a finite intersection of finite unions of sets in $\mathcal{S}$ is a finite union of finite intersections of sets in $\mathcal{S}$.
Proof. This is immediate from the fact that set intersection distributes over union.
Let $\text{NM}(n)$ denote the set of integers not divisible by $n\ge 2$, and note that each $\text{NM}(n)$ is a finite union of arithmetic progressions: $\text{NM}(n)=(1+n\mathbb{Z})\cup \cdots \cup ((n-1)+n\mathbb{Z})$. Assume that there are finitely many primes $p_1<\cdots <p_k$. Then $\{-1,1\}=\text{NM}(p_1)\cap \cdots \cap \text{NM}(p_k).$ But by Lemma 2, this set is a finite union of finite intersections of arithmetic progressions, which is either empty or infinite by Lemma 1. This is a contradiction. Therefore, there are infinitely many primes.

Why does Mercer claim that his version is a variant of Furstenburg's, rather than a different proof altogether? The situation is clarified if the proofs are compared in a more standardized form, resembling the style of "natural formalization" Sieg uses to compare proofs of the Cantor-Bernstein theorem.

The "dest. H" and "contra. H" rules correspond to the introduction of the underlined hypothesis and the contradiction derived therefrom. Here, the ${\ell }_i$ and ${\lambda }_i$ correspond to applications of the following auxiliary lemmas:

Note that ${\lambda }_2$ is just Lemma 1 from the informal version of Mercer's proof. Mercer's Lemma 2 has here been reduced to an iff rule, as it is entailed by the meaning of the symbols $\cap$ and $\cup$. We have the following implications between lemmas:

This correspondence between auxiliary lemmas is likely what Mercer had in mind when he claimed that his proof is a variant of Furstenburg's, rather than a different proof altogether. There are at most as many lemmas used in Mercer's proof as Furstenburg's, with each being at most as general as the corresponding statement in Furstenburg's proof. This correspondence between auxiliary lemmas suggests that the topological language employed by Furstenburg was not essential to the structure of his proof, and was either more general than needed (in the case of ${\ell }_3⟹{\lambda }_3$) or did not play a role in the inferential steps. This similarity in structure is recognized immediately and intuitively by mathematical practitioners; this is why Mercer's statement that his proof was a variant of Furstenburg's did not need any explication. The next section argues that, in the same sense that Mercer claims his proof is a variant of Furstenburg's, Mercer's proof is a variant of Euclid's. Our eventual claim, however, will be that Mercer's proof is also slightly more general than Euclid's.

Mercer $⟹$ Euclid

We can also construct a "natural formalization" for Euclid's proof of the infinitude of primes.

where the auxiliary lemmas ${\mathfrak{l}}_i$ are as follows:

and the penultimate iff expresses the property of $\mathbb{Z}$ that it is closed under finite products. As before, we can map the ${\lambda }_i$ in Mercer's proof onto the ${\mathfrak{l}}_i$ in Euclid's proof:

The implication ${\lambda }_3⟹{\mathfrak{l}}_2$ is not immediately clear; its explication contains the central insight of both proofs. Mercer's proof of ${\lambda }_3$ is direct, and it includes a construction of (an infinite family of) witnesses $x+y$ to the infinitude of the intersection of arithmetic progressions. Mercer gives an inductive algorithm for generating new elements of a finite intersection of arithmetic progressions, in precisely the same way that Euclid's construction of the witness $p=1+\prod _{p\text{ prime}}p$ yields an inductive algorithm for generating a larger prime from any finite set of prime numbers. Interestingly, the method of proof of ${\lambda }_3$ is what corresponds to Euclid's argument, more so than the statement of ${\lambda }_3$ itself. Mercer's examination of the properties of $x+y$ is strictly weaker than the full statement of ${\lambda }_3$, but the properties of $x+y$ already entail ${\mathfrak{l}}_2$. This means that, much like Furstenburg's ${\ell }_3$ was more general than necessary, Mercer's ${\lambda }_3$ is also more general than necessary to prove Theorem 1, as evidenced by this mapping onto Euclid's proof.

To clarify this discussion, we can make the implication ${\lambda }_3⟹{\mathfrak{l}}_2$ more explicit. Recall that the set $\{kp:k\in \mathbb{Z}{\}}^{\prime }$ for a prime $p$ (i.e. the set of non-multiples of $p$) is a finite union of arithmetic progressions, as demonstrated in the informal version of Mercer's proof. Thus the intersection $I$ over all such sets is a finite intersection of finite unions of arithmetic progressions:

As demonstrated in Mercer's proof, $I=\{-1,1\}$, due to the characterization of integers in terms of primes given by the Fundamental Theorem of Arithmetic. Furthermore, since $\cap$ distributes over $\cup$, $I$ is a finite union of finite intersections, each of which contain each prime $p$ as a difference. In accordance with the proof of ${\lambda }_3$, $I$ is inhabited (say, $x=1\in I$, where $1$ belongs to a finite intersection term $\iota$ in the outer union), we can construct another element of $\iota \subset I$ as $x$ plus the product of differences of the arithmetic progressions in $\iota$.

This witness of the intersection, guaranteed by the proof of ${\lambda }_3$, is precisely the $\pi$ constructed in Euclid's proof (note that we could have also defined $\pi$ as $-1+\prod _{p\text{ prime}}p$). Therefore Euclid's construction of $\pi$ is an instantiation of the more general construction outlined by Mercer, and we can conclude that ${\lambda }_3⟹{\mathfrak{l}}_{\mathfrak{2}}$. Therefore, we can claim that Mercer's proof is more general than needed to prove the infinitude of primes, as Euclid manages to prove the same proposition with a slightly weaker auxiliary lemma. Therefore, the sense in which Euclid's proof is "minimal" is that it is the least general argument needed to establish the truth of Theorem 1.

The idea of constructing an implication from ${\lambda }_3$ to ${\mathfrak{l}}_2$ on the basis of a correspondence of the proofs of ${\lambda }_3$ and ${\mathfrak{l}}_2$ is the same as constructing an implication from Mercer's (resp. Furstenburg's) proof to Euclid's (resp. Mercer's) proof. In principle, each of the implications ${\ell }_i⟹{\lambda }_j$ and ${\lambda }_i⟹{\mathfrak{l}}_j$ could be decomposed structurally in the same way, in a recursive process that eventually terminates: the analysis done in this note is only the "first level" of this recursion. In any case, this structural decomposition of the proofs is a demonstration of the earlier claim that the meaning of a proposition is carried by its proof. This more detailed analysis is a topic that merits further study (determining if this process actually terminates, if there is a more standard and satisfactory way of determining the auxiliary lemmas used in informal proofs, and so on).

As a final note, though both Mercer and Euclid's proofs are presented as proofs by contradiction, the fact that they each rely on only the Fundamental Theorem of Arithmetic and this inductive algorithm for generating a larger prime from any finite set of primes means that either could be construed as a direct proof; just demonstrating this algorithm implies Theorem 1, without a need to pass to a contradiction.

Summary: Furstenburg $⟹$ Euclid

We can compose the implications ${\ell }_i⟹{\lambda }_j$ with the ${\lambda }_i⟹{\mathfrak{l}}_j$ to obtain

and to assert that Furstenburg's proof is also a more general version of Euclid's. We thus obtain the following picture

If, for example, these were the only possible proofs for the infinitude of primes, then the strong claim that there is a "terminal object" in the equivalence class of proofs of a proposition would hold in this case: Euclid's proof is the "minimal" proof of the infinitude of primes, on the basis that it is the least general proof needed to establish the truth of the proposition.

However, the difficulty lies in showing that this chain of implications in an equivalence class of proofs actually terminates in a single, minimal, proof object. As Euclid's proof is number-theoretic in method (it relies only on the Fundamental Theorem of Arithmetic and an algorithm for constructing prime numbers), this would suggest, on the basis of the discussion in the introduction, that the statement of Theorem 1 is the "minimal" representative in the class of equivalent propositions, and that, no matter the language used to formulate such equivalent propositions, this property is essentially number-theoretic in nature. This is why Furstenburg's proof might "feel" less natural to a mathematician than Euclid's. Whether this determination of the methodological nature of a problem is applicable to more complicated propositions, or even whether it's a meaningful property in the first place, is also a topic for further study.

The discussion in this note is quite suggestive that this claim is true, but this analysis should be taken with a grain of salt; as discussed, Euclid's proof is exceptionally simple, elegant, and pure compared to the proofs of most mathematical propositions. And, though the method here examines the lemmas in detail, simply repeating this ad hoc approach for every mathematical proposition is not a viable approach. Realistically, this procedure for finding minimal proofs of a proposition cannot rely on the particular properties of the auxiliary lemmas, in the way that we discussed the intricacies of, say, ${\lambda }_3⟹{\mathfrak{l}}_2$; instead we need a better way of comparing the structure of proofs that does not rely on the precise mathematical formulation of the inferential steps.

Even without justification for this more general claim, that Euclid's proof is the "minimal" proof of the infinitude of primes, we can still make the more modest assertion that Furstenburg's and Mercer's proofs are really just generalizations of the structure of Euclid's proof, disguised in topological and set-theoretic clothing. The hope is that this method of analysis of Theorem 1 will lead to a suitable generalization of structural comparison between proofs.