Topological Magic: Infinitely Many Primes
The Basic Idea
A while ago, I wrote about the importance of open sets in topology and how the properties of a topological space $X$ are highly dependent on these special sets. In that post, we discovered that the real line $\mathbb{R}$ can either be compact or non-compact, depending on which topological glasses we choose to view $\mathbb{R}$ with. Today, I’d like to show you another such example - one which has a surprising consequence! It turns out that if you view the integers $\mathbb{Z}$ through the ‘correct’ topological lens - that is, if you define your opens sets just right - then you can prove that there are infinitely many prime numbers! This is particularly striking since the infinitude of the primes is a number theoretic fact, and instinctively number theory and topology are two separate realms. But by simply (though carefully!) choosing the right definition of “open,” we become the master of our topological destiny and discover a secret back door connecting those two worlds. Pretty magical, right?*
Now before moving on "from English to math," I should probably clarify one thing: a set $X$ (such as $\mathbb{R}$ or $\mathbb{Z}$) by itself is just that - a set. Just a plain, old set. So I'm not claiming that $X$ inherently possesses some topological properties that we can see if only we tilt our head and stare at $X$ at just the right angle. In other words, we can't even talk about juicy things like compactness or connectedness or continuous functions on $X$ unless we topologize $X$ first. In fact, $X$ is sort of like flour. Flour by itslef isn't very tasty. But the addition of sugar, eggs, cocoa powder and a little oil will enrich the flour and turn it into sweet concoction. Alternatively, we could add yeast, salt, some water and maybe a little rosemary to create a savory bread instead. So you see? On its own, flour is rather bland and not very useful. But by adding carefully-chosen additional 'information' to it (e.g. ingredients and a recipe), you can obtain different outcomes which fulfill different purposes. (So for instance, if your goal is to make a meal for dinner then you'd want to take a savory route. Unless you're like me and occasionally eat cookies for dinner. But I digress....)
Analogously, in what follows below, we will start with the set $\mathbb{Z}$ and add extra information to it -- the topology, i.e. a carefully-chosen definition of "open set" -- which will help us reach our goal of proving the infinitude of the primes.
From English to Math
Usually, we declare a subset $U$ of $\mathbb{Z}=\{\ldots,-2,-1,0,1,2,\ldots\}$ to be open if for every integer $m\in U$ there is an open interval $(a,b)$ so that $m\in (a,b)\cap\mathbb{Z}\subset U$. But today we'll declare a subset $U$ of $\mathbb{Z}$ to be open if for every $m\in U$, there is a set of the form $$N_{a,b}=\{a+nb:n\in\mathbb{Z}\},\quad{b>0}$$ such that** $m\in N_{a,b}\subset U$. This isn't as scary as it looks! As a concrete example, consider the case when $a=7$ and $b=3$. To get a grasp on $N_{7,3}$, simply start at 7 and shift to the right 3 units to get 10. Shift right 3 more units to get to 13, then shift 3 more units to get 16, and so on. But we also need to pick up the integers to the left of $7$, so starting at 7 we shift 3 units in the negative direction to obtain $4, 1, -2,$ etc. Visually we can plot it like this:
Notice that the pink dots continue indefinitely both to the left and right of 7. Other examples of such open sets look like this:
Now that we've defined our open sets, we need to make sure they satisfy the axioms of topology:
- (axiom #1) both the empty set and $\mathbb{Z}$ are open
- (axiom #2) a union of open sets is also open
- (axiom #3) a finite intersection of open sets is open
It's not too hard to check that these really are satisfied, but I want to get to the good stuff. So like all helpful math texts, I'll leave it as an exercise. Next, let's make a few observations. This is where the fun begins:
Observation #1: For any integers $a$ and $b$ with $b>0$, the set $N_{a,b}$ is both open and closed.
- (Side note: It is perfectly valid for a set to be both open and closed at the same time! We're not doing anything illegal. Some folks call these sets clopen.) By definition, $N_{a,b}$ is automatically open. After all, $N_{a,b}$ is contained in itself! And we say a set is closed if its complement - all of the stuff not in the set - is open. In our case, the complement of $N_{a,b}$ consists of a union of sets of the same form. It's easy to see this with our example: the complement of $N_{7,3}$ is $N_{8,3}\cup N_{9,3}$:
- Since a union of open sets is again open - this is axiom #2 - the complement of $N_{a,b}$ is indeed open. Hence $N_{a,b}$ is closed.
Observation #2: For any integer $k$ - besides*** $1$ or $-1$ - we can find a prime number $p$ so that $k\in N_{0,p}$.
- This is just the fancy way of saying $k$ is divisible by $p$, and it follows simply because every integer $k$ - except for $1$ or $-1$ - is divisible by a least one prime $p$. Mathematically, we can express our Observation #2 like this: $$\mathbb{Z}\smallsetminus \{-1,1\}=\bigcup_{p,\;\text{prime}}N_{0,p}.$$
Observation #3: No (non-empty) finite subset of $\mathbb{Z}$ can be open.
- To see this, suppose $A\subset\mathbb{Z}$ is a finite set. Then we can list its elements like so: $A=\{n_1,\ldots,n_k\}.$ And suppose to the contrary that $A$ is open. Then, by definition of open, $A$ must contain a set of the form $N_{a,b}$. But $N_{a,b}$ contains infinitely many integers! Therefore $A$ must contain infinitely many integers as well. Of course, this is a contradiction since we assumed $A$ is finite. So our observation holds
With these observations at hand, we're almost at the end of the road! Can you see it? Consider the set of all integers except $1$ or $-1$. As above, we can express this set as $$\mathbb{Z}\smallsetminus \{-1,1\}=\bigcup_{p,\;\text{prime}}N_{0,p}.$$ Now suppose to the contrary that there are only a finite number of primes, say $\{p_1,\ldots,p_m\}$. Then our union really looks like this: $$\mathbb{Z}\smallsetminus \{-1,1\}=N_{0,p_1}\cup N_{0,p_2}\cup \cdots \cup N_{0,p_m}.$$ By Observation #1, we know that each $N_{0,p_i}$ is closed. Hence $\mathbb{Z}\smallsetminus\{-1,1\}$, is also closed since it is a finite union of closed sets. (Okay, okay, I'm pulling a fast one here. By De Morgan's Laws, axiom #3 is the same as saying a finite union of closed sets is closed.) But wait! Observation #3 implies $\mathbb{Z}\smallsetminus \{-1,1\}$ is not closed since its complement $\{-1,1\}$ is a finite set and no finite set can be open. This is indeed a contradiction.
Conclusion? There must be infinitely many prime numbers! QED.
As an aside, the topology on $\mathbb{Z}$ we've been playing with today is sometimes called the arithmetic progression topology, and the proof above was originally discovered by American-Israeli mathematician Hillel Fürstenberg in 1955 while he was still an undergraduate student! Bravo, Dr. Fürstenberg!
Footnotes:
* At this point, the sophisticated reader who is already familiar with this proof may be thinking, "Bah humbug! This is just Euclid's proof cast in a different light." I prefer to leave such complaints to the experts.
**The open sets $N_{a,b}$ form what's called a basis for our topology on $\mathbb{Z}$. Intuitively, the $N_{a,b}$ are the basic building blocks from which we can obtain all other open sets.
***EDIT 4/11/17: This originally read, "...any integer $k$ - besides 0, 1, or -1..." (and throughout) but, of course, there is no reason to exclude 0. (It's divisible by everything!) Many thanks to a reader for catching this.