Written by Colin+ in prime numbers, proof.

*One of my favourite quotes is from Stefan Banach: "A good mathematician sees analogies between theorems. A great mathematician sees analogies between analogies." This post is clearly in the former camp. I'm fairly sure it's a trivial thing, but it's not something I'd noticed before.*

One of the first serious proofs most mathematicians see is Euclid's proof1 that there are infinitely many primes. It's a proof by contradiction, which means you assume the thing you want to prove *isn't* true, and show you end up with something absurd. In this case, you suppose there's a finite number of primes.

Great! Finitely many primes - so, we could write them all out in a (presumably very long) list: 2, 3, 5, 7, 11... . And (the clever bit), we could multiply them together and add one to the result. Why is that clever? Well, the resulting number isn't a multiple of two, because the number before it is. It's not a multiple of three, because the number before it is. Similarly for 5 and 7. Eleven too. In fact, it's not divisible by any of the primes in the list.

We know that every number2 has at least one prime factor - but this number we've just constructed doesn't have any. Either the fundamental theorem of arithmetic is wrong3, or our assumption that we've listed all of the primes is. Whatever list of primes we started with is necessarily incomplete - so there are infinitely many primes.

[Aside: it's not necessarily the case that the resulting number is prime -- for example, if our original list went up to thirteen, our resulting number would be $2\times 3 \times 5 \times 7 \times 11 \times 13 + 1 = 30,031 = 59 \times 509$ - but its prime factors are both greater than the largest prime in the list.]

That's an old, old proof. Nearly 2,500 years later, up showed a chap called Georg Cantor.

Cantor wasn't especially interested in primes (at least, not in this proof), but in numbers generally. Up until this point, it had generally been assumed that "there are infinitely many numbers" was a simple5 and unambiguous statement. Cantor, however, showed otherwise: there are different flavours of infinity.

To start with, you need to understand the idea of *cardinality*. Two sets have the same cardinality if you can find a *one-to-one* correspondence between them. To take a famous example, the late BBC journalist Brian Hanrahan reported, during the Falklands War, "I am not allowed to say how many planes joined the raid, but I counted them all out and I counted them all back." Every member of the set "the planes that joined the raid" had a corresponding member in the set "the planes that returned from the raid", so the two sets were the same size.

So what? We already had a system for communicating the size of sets, something called "numbers". Very successful system, all things considered... as long as you're talking about a finite number of things.

Think, for example, about how many even numbers there are. "Infinitely many!", of course. But are there fewer even numbers than natural numbers? It sort of looks that way - if you start with infinitely many natural numbers and cross out all of the ones that aren't even, surely you have a smaller set than you had to begin with? I mean, you've crossed out infinitely many numbers!

The two sets, according to Cantor, have the same size: you can find a one-to-one correspondence between the natural numbers and the even numbers by matching 1 to 2, 2 to 4, 3 to 6, and generally $n$ to $2n$ - they have the same *cardinality*.

You can even show that the set of rational numbers (the fractions) has the same cardinality as the set of natural numbers, although it's a bit more complicated. For example, you could use the Farey sequence to list the fractions, or you could list all of the fractions whose top and bottoms add to 1 (just $\frac{0}{1}$), then all of those that add to 2 ($\frac{0}{2}$ we've already got, but $\frac{1}{1}$ isn't in our list) and keep going until you have them all. If you're worried about negative fractions, that's ok too - every time you write down a positive fraction, write its negative down next to it. Every positive or negative fraction is somewhere on that list, so the set of rational numbers has the same cardinality as the natural numbers.

But what about the real numbers, which are what you get when you introduce irrational numbers like $\pi$ and $e$ and $\sqrt{3}$? There, Cantor found, there's a problem - and he finds it in a way that echoes Euclid's primes proof!

First of all, he supposes you can find a one-to-one correspondence between the natural numbers and all of the real numbers. Cantor says6 "I can take your recipe and construct a number I know *for sure* isn't in your list."

Here's a possible strategy:

- write down "0."7
- Examine the first digit after the decimal point in the real number you have corresponding to 1. Write down a different digit.
- Examine the second digit after the decimal point in the real number you have corresponding to 2. Write down a different digit.
- Repeat this forever.

The number you have written down is different to the real number corresponding to 1, different to the real number corresponding to 2, and different to every real number you have in your infinitely long list. It's not in your list.

So, just like with Euclid's prime proof, either the idea of cardinality is wrong8, or the cardinality of the real numbers is greater than that of the natural numbers, and there are at least two different kinds of infinity.

*What are your favourite seemingly-unrelated proofs that have a key element in common?*

* Thanks to @ajk44 and @realityminus3 for the conversation that led to this.

* Edited 2017-27-02 because @christianp gets all grouchy when I leave 1 out, and because historians get funny about "accuracy" and "details".

- or - for strict historical accuracy, a variant on it [↩]
- OK, @christianp. Every integer greater than 1. [↩]
- it isn't [↩]
- I know that doesn't really work. Hsht. [↩]
- ok, simple-ish [↩]
- I'm not certain he
*actually*says it [↩] - This is bold: not only is he going to find a number that's not in your list, he's going to find one
*between 0 and 1*. [↩] - it's not [↩]

## Christian Lawson-Perfect

If you don’t like recipes whose last step is “repeat this forever”, you can rephrase the strategy as a game: given your list supposedly containing every real number, I think up a real number that isn’t in your list. Now you can ask me for the nth digit of my number, and I will reply with any digit that isn’t the nth digit of the nth number in your list.

You can ask me for digits as many times as you like, but hopefully you’ll get the idea after finitely many of them.

PS: this article makes a strong case that Euclid’s proof as it was originally written isn’t a proof by contradiction.