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.
More below the fold
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! WTF?
How about rational numbers? 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? WTF?
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?
Suppose there's a LOT of each. You don't want to count them all.
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, you will remember (possibly from my diary 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/3 1/2 2/1
0/4 1/3 2/2 3/1
and so on
eventually, you will get to every rational number.
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
and so on (forever)
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, 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.
This diary was just an intro to this stuff. If people are interested, I can write more. A good (if quirky) book on this material is David Foster Wallace's Everything and More (but see the comment below by danielbiss)