Okay so let's try to do it with as little proof by contradiction as possible. The set of arithmetic progressions (meaning sets of the form { an + b : n ∈ Z } for integers a,b) forms a basis for a topology on Z. Fine. All progressions with the same common difference (meaning they are 'cosets' of one another) partition Z, so each of these basic open sets is also closed. In particular, Z is totally disconnected. In fact, Z is also Hausdorff, as you can always find two cosets that contain either point.

As a first-countable space, the topological properties of Z are fully determined by the limiting behaviour of sequences. When does a sequence (aᵢ) converge to n? That's if the difference n - aᵢ is eventually divisible by every number as i increases. So the topology has a certain metric quality, where you can measure the distance between two points as inversely proportional to the number of factors of their difference. This doesn't actually satisfy the triangle inequality, though (the sum of two very composite differences might be prime, for example).

Anyway, it's also clear that any open set that contains at least one point contains an arithmetic progression, and therefore must be infinite. Together with Hausdorffness this shows that no point is isolated. Now say you have any finite set of prime numbers. The combined set of all their multiples is a finite union of arithmetic progressions, hence a closed set. Its complement is open and contains 1 and so must be infinite, and therefore there exists a number not divisible by any of these primes, QED.

So no proof by contradiction necessary, really. It's actually a rather constructive proof. So if I have a finite set of prime numbers, how does Harry Furstenberg find us a new prime? Well, for a single prime p we get that its set of multiples is a basic open set, and its cosets are too. So pick the coset containing 1 and you have numbers not divisible by p. In essence, for the proof it suffices that p+1 is not divisible by p, hence it is divisible by another prime number.

Now for two primes p₁, p₂, their sets of multiples are basic open sets, but because their cosets are too we find that their complements

U₁ = { n ∈ Z : n is not divisible by p₁ }, U₂ = { n ∈ Z : n is not divisible by p₂ },

are open as well. Now the next step is that the union of the multiples is a finite union of closed sets, hence closed. This corresponds to the fact that the intersection U₁ ∩ U₂ is open. In fact, all we need for the proof is that U₁ ∩ U₂ contains at least one basic open set.

Why is this? I sort of glossed over this, but the fact that the arithmetic progressions form a basis for a topology is a somewhat non-trivial fact. It follows from the fact that the intersection of two arithmetic progressions { an + b } and { cn + d } is either empty or another arithmetic progression. If they intersect at the number k, then adding any multiple of the least common multiple lcm(a,b) lands in the intersection again, and if the difference between m and k is not divisible by lcm(a,b) (so not by both a and b), then m cannot lie in the intersection. So

{ an + b } ∩ { cn + d } = { lcm(a,b) ⋅ n + k }.

The story of Icarus always spoke to me deeply as a Black boy who grew up trying to find his wings. Mixed with the African Folklore I grew up with I found something magic. We launch on Kickstarter in just 13 Days, follow our page on Kickstarter and help us take Flight 🪽💫