Number of Primes is Infinite/Proof 2

From ProofWiki
Jump to: navigation, search

Theorem

The number of primes is infinite.


Proof

Define a topology on the integers $\Z$ by declaring a subset $U \subseteq \Z$ to be an open set if and only if it is either:

the empty set $\varnothing$

or:

a union of sequences $S \left({a, b}\right)$, where:
$S \left({a, b}\right) = \left\{{a n + b: n \in \Z}\right\} = a \Z + b$

In other words, $U$ is open if and only if every $x \in U$ admits some non-zero integer $a$ such that $S \left({a, x}\right) \subseteq U$.


The open set axioms are easily verified:


$(O1): \quad$ Any union of open sets is open:

For any set of open sets $U_i$ and $x$ in their union $U$, any of the numbers $a_i$ for which $S \left({a_i, x}\right) \subseteq U_i$ also shows that $S \left({a_i, x}\right) \subseteq U$.


$(O2): \quad$ The intersection of two (and hence finitely many) open sets is open:

Let $U_1$ and $U_2$ be open sets and let $x \in U_1 \cap U_2$ (with numbers $a_1$ and $a_2$ establishing membership).

Set $a$ to be the lowest common multiple of $a_1$ and $a_2$.

Then:

$S \left({a, x}\right) \subseteq S \left({a_i, x}\right) \subseteq U_1 \cap U_2$


$(O3): \quad$ By definition, $\varnothing$ is open: $\Z$ is just the sequence $S \left({1, 0}\right)$, and so is open as well.


The topology is quite different from the usual Euclidean one, and has two notable properties:

  1. Since any non-empty open set contains an infinite sequence, no finite set can be open. Put another way, the complement of a finite set cannot be a closed set.
  2. The basis sets $S \left({a, b}\right)$ are both open and closed: they are open by definition, and we can write $S \left({a, b}\right)$ as the complement of an open set as follows:
$\displaystyle S \left({a, b}\right) = \Z \setminus \bigcup_{j \mathop = 1}^{a - 1} S(a, b + j)$.

The only integers that are not integer multiples of prime numbers are $-1$ and $+1$, that is:

$\displaystyle \Z \setminus \left\{{-1, + 1}\right\} = \bigcup_{p \ \text{prime}} S \left({p, 0}\right)$

By the first property, the set on the left-hand side cannot be closed.

On the other hand, by the second property, the sets $S \left({p, 0}\right)$ are closed.

So, if there were only finitely many prime numbers, then the set on the right-hand side would be a finite union of closed sets, and hence closed.

Therefore by Proof by Contradiction, there must be infinitely many prime numbers.

$\blacksquare$


Also see


Historical Note

This proof was created by Hillel Furstenberg.

As such it is often referred to as Furstenberg's proof.