# Cantors Proof

How many numbers are there?

Silly question, right? They never stop!

Let’s talk about the counting numbers: 1, 2, 3, 4 ….

that … means “and so on”, and little kids know that there is no biggest number. It’s *infinity*.

How big is infinity? How should we think about infinity? Can we think about infinity in sensible ways that work with the rest of mathematics? Are all infinities the same? When a math result requires dealing with infinity, is it necessarily nonsensical?

People have been thinking about these sorts of questions since at least the time of ancient Greece. But their thinking was confused and contradictory until Georg Cantor came on the scene around 100 years ago. Some of what he said is strange, and he himself was certainly strange, but his methods for dealing with infinity solve paradoxes that had confused people for at least 2,000 years.

How many positive integers are there? There are an infinite number. You can tell this pretty simply, because there is no ‘biggest’ number. However big a number you name, I can just add one, or 10, or a million to it and get a bigger number.

How many even positive numbers are there? (The even numbers are those that are evenly divisible by 2 – 2, 4, 6, 8, and so on). Well, there’s no biggest even number, either, so there must be an infinite number of them, as well. Similarly, there must be an infinite number of odd numbers. But wait! That means that infinity plus infinity is infinity! Weird!

How about rational numbers (i.e. fractions, numbers that can be represented as ratios)? Surely there must be more rational numbers than integers! After all, between any two integers there are an infinite number of rational numbers. For instance, between 1 and 2 we have 1 1/2. But between 1 and 1 1/2 we have 1 1/4, and so on. But what could be bigger than infinity? Anything?

Cantor straightened all this out. The way he did it was to go back to the most elementary mathematical idea – one-to-one correspondence. Two sets of objects, he said, have the same size if you can put the two sets into one-to-one correspondence. What’s that? You may not have heard of it by those terms, but you’ve known about it since you were a little kid. Suppose you have a bunch of apples, and a bunch of people. Are there more apples, or people? You could count the apples, and count the people, and see which number was higher, but suppose there’s a LOT of each. You don’t want to count them all, that would be dull, and you might make a mistake.

So, just have each person take one apple. If there are apples left over, there were more apples than people. If there are people left over, there were more people than apples. If nothing is left over, then the two sets were equal.

Cantor applied this idea to infinite sets. If two sets can be put into one-to-one correspondence, they are equal. If not, not.

Let’s apply this to the problems above:

Positive integers: 1, 2, 3, 4….

Even integers: 2, 4, 6, 8….

It looks like they match up, but we can show that they always will:

For any positive integer x, the matching even integer is 2x. Similarly, for any positive integer x, we can find a matching odd integer 2x+1. So, weird as it seems, there are the set of even numbers is the same size as the set of integers.

We’re just getting started!

Cantor also showed that the set of rational numbers is the same size. This was a little trickier. The rational numbers are those that can be expressed as ratios, or fractions. Cantor came up with a way of numbering all of these. First, think of adding the numerator and denominator. Then, for each total, list them in terms of size of the numerator. Like this:

0/1

0/2…. 1/1

0/3…. 1/2…. 2/1

0/4…. 1/3…. 2/2…. 3/1

and so on

Eventually, you will get to every rational number. Most important, you can match a counting number to every rational number

0/1 = 1

0/2 = 2

1/1 = 3

0/3 = 4

1/3 = 5

and so on.

So, are *all* infinite sets of numbers the same size? Nope. Here’s where Cantor really got clever. He did the following:

First, he noticed that any real number can be shown as a decimal. Some will be repeating decimals (like 1/3 = 0.3333….), some will be terminating decimals (like 1/2 = 0.50000….) and some will be neither (pi = 3.1415….

Next, he thought that, if there were a countable number of these, he could list them all. Something like this:

0.500….

0.125….

0.314….

and so on (forever). After all, that’s what all the sets we’ve mentioned so far have in common – you can match the members to the counting numbers.

Then, he thought, what would happen if you read down the diagonal, reading the first digit first number, the second of the second, and so on, and then adding one to each digit? For the above, reading the diagonal you’d get 0.524…, and adding one to each digit you’d get 0.635…. Now, this number can’t be anywhere on the list. It can’t be the first number, because the first digit doesn’t match. It can’t be the second, because the second digit doesn’t match, and so on. No matter how many numbers you list, you always leave some out.

So, there are more irrational numbers than rational numbers.

Weird. Because, no matter how close two rational numbers are, you can always find another rational number in between. But you can find even more irrational numbers.