Sunday, December 6, 2009

My Favorite Theorem

After it showed up as a Twitter thread, Nick suggested we publish a post about our favorite theorem. I think this is the season for favorite things, right? Or is that only in Vienna? I don't know. Anyway.

I immediately chose Cantor's proof of the nondenumerability of the reals, for its counterintuitive-ness and yet easiness to understand if you can hang with a pretty simple argument. It's the best way to show the uninitiated that math is beautiful that I've ever found. And not because you drew a pretty picture of a golden rectangle, but because the ABSTRACT ARGUMENT all by itself is BEAUTIFUL and once you get it makes you go ooh and aah. I've explained this to middle school kids, roommates, people in elevators, my mom, and one time (disastrously) a boy I had a crush on.

The big, impressive, revolutionary idea embedded in here is that there is more than one size of infinity. It takes most people a while to stretch their brains around that. It drove Georg Cantor to an asylum, so no need for anyone to feel bad if it takes them a while.

Children's first encounter with infinity is (usually, I think) when they realize that the counting numbers never stop. There's no last one. You can keep counting incrementing by one forever and you will never...reach...the end.

What if you count just the even numbers? Nope. By fives? Nope. Tens? Nope. Hundreds? Millions? Brazillions? You get the idea.

What if we want to compare how many counting numbers there are to how many even numbers? We obviously can't count them and see which set has more. It makes intuitive sense to conjecture that there are more counting numbers than even numbers. Seems like there should be twice as many.

Cantor's genius move was to invent a way to compare the 'sizes' of these infinite sets, which he called 'cardinality.' Instead of trying to count the number of elements in each set, which is impossible, he said let's look at it another way. For example, when I take attendance in my class, I don't count the number of students, and count the number of chairs, and compare the two counts. I just see if every chair is matched with a butt. If there are no chairs left over, I know the sets are the same size, and I mark All Present.

Cantor applied the same logic to infinite sets. He said if we can match every element in one set to an element in the other, then they are the same size. Since both sets go forever, we don't have to worry about leftovers. They both keep going forever, so every element will match something in the other set, and they are the same size. Sets that can be matched this way are said to be in a one to one correspondence.

Looked at this way, there are the same number of elements in the counting numbers as there are in the even numbers. We can match 1-2, 2-4, 3-6, 4-8, 5-10, and so on, forever. The elements of the sets can be placed in a one to one correspondence, so they are the same size.

You can make a matching to show that the cardinality of the counting numbers = the integers. The counting numbers = the multiples of ten. And even, with a little clever organization, the counting numbers = the rationals.

Intuition resists this conclusion. Sometimes with students, I have to stop here. They just aren't ready to concede the point, and I'm not about to make them push the "I believe" button on something we're doing for fun. I think it's healthier to let them be bothered by it. And if you don't believe that part, you definitely won't come along with me for the rest of the ride.

So you believe that all these infinite sets that can be matched with the counting numbers are the same size. Great! Then what? There's just that one size of infinity?

Nope.

There's an infinity bigger than that. Infinitely bigger than that. And that infinity is located, for an example, on a number line between zero and one.

It takes a little meditation to absorb that statement, too. There are infinitely more numbers between zero and one than there are counting numbers.

Here's where my favorite proof starts. :-) Quite the setup, I know.

Let's say that that conjecture is NOT true. Let's say that there are the same number of elements in the set between zero and one as there are counting numbers.

If that's true, then I can make a list of all of them. It will be infinitely long, but a list can be made. Much like you can list the counting numbers.

So here's the beginning of my list:

0.124598560
0.7463728642893
0.00033033845788
0.1111111111111....
0.7465564748383
0.123123123123123...
0.141592653589...
0.799999999999...
.
.

You get the idea. The decimal expression of every rational and irrational number between zero and one will be in my list.

Now, I'm going to write a new number. But I'm going to write it in a very particular way. The first digit will not be a 1. The second digit will not be a 4. The third digit will not be a 0. The fourth digit will not be a 1. The fifth digit will not be a 5. etc*.


By doing this, my new number must be different from any number in my list, because for the nth list item, it differs in the nth digit.

But wait! We said we were going to list ALL the numbers between 0 and 1! What gives?!

What gives, is that the only thing that could be wrong here is our original supposition. When we said, "Let's say that there are the same number of elements in the set between zero and one as there are counting numbers." that must have been wrong.

Which means there must be MORE elements in the set between zero and one, than there are in the counting numbers.

Another size of infinity. Cool, right? That's why it's my fave.

*A little caveat needs to go here about not choosing 0's or 9's for your new number, since for example 0.50000.... = 0.499999....