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 proof ((or - for strict historical accuracy, a variant on it)) 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.

But that’s… problematic.

We know that every number ((OK, @christianp. Every integer greater than 1.)) has at least one prime factor - but this number we’ve just constructed doesn’t have any. Either the fundamental theorem of arithmetic is wrong ((it isn’t)), 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.

You Cantor ways get what you want ((I know that doesn’t really work. Hsht.))

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 simple ((ok, simple-ish)) 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!

Nut-uh.

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.

A real mess

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 says ((I’m not certain he actually says it)) “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.” ((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.))
  • 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 wrong ((it’s not)), 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”.