Problem: Prove there are infinitely many prime numbers.
Solution: First recall that an arithmetic progression with difference $ d$ is a sequence of integers $ a_n \subset \mathbb{Z}$ so that for every pair $ a_k, a_{k+1}$ the difference $ a_{k+1} – a_k = d$.
We proceed be defining a topology on the set of integers by defining a basis $ B$ of unbounded (in both directions) arithmetic progressions. That is, an open set in this topology is an arbitrary union of arithmetic progressions from $ -\infty$ to $ \infty$. To verify this makes sense, we need only check that $ B$ is a basis. Indeed, $ B$ covers $ \mathbb{Z}$ since $ \mathbb{Z}$ is itself an arithmetic progression with difference 1. And any two arithmetic progressions $ a_n, b_n$ have intersection which is again an arithmetic progression: if the two progressions have equal difference then the intersection is empty or $ a_n = b_n$, and if their differences are $ d_1 \neq d_2$, then the intersection has difference $ \textup{lcm}(d_1, d_2)$. (We discussed this idea in a different context in our post on design with prime numbers.)
Now we notice that the basis sets are both open (by definition) and closed. The latter follows from the fact that there are only finitely many shifts of an arithmetic sequence. That is, if $ a_n$ is an arithmetic sequence with difference $ d$, then its complement is the union of all $ a_n + k$ where $ k$ ranges from 1 to $ d-1$ (and each of these sets are open, so the union is open as well).
Further we notice that no finite set can be open. Indeed, since the arithmetic sequences which form our basis are all infinite, and any open set is a union of sets in a basis, every open set in this topology must be infinite.
Now for a prime $ p$, let $ U_p$ be the arithmetic progression with difference $ p$ containing zero, and let $ U$ be the union of all $ U_p$. Supposing there were only finitely many primes, $ U$ is a finite union of closed sets and hence closed in this topology. But the only integers which are not multiples of some prime are $ \pm 1$. So $ \mathbb{Z} – U = \{ 1, -1 \}$. Since $ U$ is closed, its complement is open, but as we mentioned above no finite sets are open. This is a contradiction, and so there must be infinitely many primes. $ \square$
Discussion: Even though the definition of a topology is basic knowledge for a mathematician, this proof shows that a topology alone can carry a lot of interesting structure. Even more so, the ability to pick a topology on a space to suit one’s needs is a powerful tool. It reminds this author of the more elementary idea of picking colorings on a chessboard. Indeed, the entire field of algebraic geometry lives in the setting of one particular kind of topology on real or projective space. As one might expect, the open sets in a custom topology must be related to the task at hand. In the case of algebraic geometry, they’re the solution sets of families of polynomials in finitely many variables. Considering how important polynomials are in mathematics, one can imagine how complex and rich the resulting theories are. We plan to cover both basic topology and algebraic geometry in the future of this blog.
This is just Euclid’s proof in disguise and does not use any topology beside words. Copied from a Mathoverflow comment: “Here is a version of Fuerstenberg’s proof that does not mention topology: We argue about periodic subsets of Z. The set of all numbers prime to a given
p is periodic and the intersection of two periodic
sets is periodic. If there were only finitely many primes the set {−1,1} would be periodic. –” Also, see the comments to the bottom answer here: http://mathoverflow.net/questions/34699/approaches-to-riemann-hypothesis-using-methods-outside-number-theory/34718#34718
The part about this proof that makes it worthwhile and interesting is that it relaxes the problem to the investigation of a particular structure on the integers. Euclid just invented a magical quantity (take the product and add 1) and his technique only barely generalizes. The idea of exploring a topology is much closer to the true nature of mathematics. So even if it is Euclid’s proof in disguise (and I think it takes a grain of insight to see the connection!) I would argue for its aesthetics, and at least a place in a gallery of proofs 🙂
Okay, maybe it takes some insight to actually see that both Euclid’s and Fürstenberg’s proof construct the quantity 1+p_1*…p_n. A lot cuter though is the quoted observation: that Fürstenberg’s proof is really a proof about periodic subsets of Z. (no topology involved)
And the pointed logician might say that all mathematics is just some logical framework in disguise and does not use any mathematics besides words 🙂
If you assume in the proof the number of primes is finite, you can not state:
“The only integers which are not multiples of some prime are $\pm 1$.”
This statement involves the assumption of infinity of primes implicitely.
Actually, no. That statement is just the existence part of the fundamental theorem of arithmetic, that every number greater than 1 has a prime factorization. Nothing in that theorem requires there to be infinitely many primes.
Ok, you are right. The proof of existence of the factorization of an integer proceed by induction and no assumption on number of primes is needed. Nice one. Thanks.
As a very unsophisticated reader of this blog, I was delighted by this proof and also puzzled. It didn’t seem to draw more from topology but a few definitions. But what kept me tossing and turning through a good part of last night was trying to understand why the proof worked. Can someone please explain how this proof is Euclid’s proof in disguise, and how Euclid’s construction is somehow hidden within it? Does this technique lend itself to other number theoretic proofs? Can it be used, for example, to say anything about arithmetic progressions of primes?
A little wakeful thinking and I finally see it. Basically, the proof involves showing that the intersection of the sets of numbers that aren’t multiples of any primes is {-1,1}. But if there are a finite number of primes, than the product of these primes plus one will certainly be in this intersection, which shows that this set must contain more than {-1,1}. In fact, it contains infinitely more elements, but that doesn’t really matter. As you folks said, it’s just Euclid’s proof in disguise. And yet, the “topological” proof never explicitly invokes divisibility but seems, at least to my unschooled eyes, highlight the combinatorics (if that’s the word) of how primes combine to create the integers.
Precisely! Perhaps more vaguely: since the sets that form the basis are defined in terms of divisibility (up to shifting the whole sequence by a constant), it naturally follows that their intersections will correspond to some kind of divisibility as well. In the special case that the sets we’re intersecting have no shift and are defined by divisibility by primes, it’s by divisibility of the least common multiple (i.e. the product) of the two primes.
So it definitely is Euclid’s old proof, but I think the perspective is valuable.
Although it looks like a lovely proof, there is something that concerns me: assuming primes are infinite, considere de the union of all arithmatic progressions containing 0 with prime difference. Since, by definition, those are open, their union is still open. But wouldn’t its complement be again {-1,1}? That would imply that the complement is closed, wich is contradiction, according to the topology defined here.
I think you are right about that. It seems like the author forgot about infinite unions in making his claim that all open sets are finite.
Ah, wait, I’ve figured it out. [-1, 1] is just both closed and open at the same time. (This is not impossible, for example, in any topology, the empty set is both closed and open.