Hello, reader! If you intend to post a link to this blog on Twitter, be aware that for utterly mysterious reasons, Twitter thinks this blog is spam, and will prevent you from linking to it. Here's a workaround: change the .com in the address to .ca. I call it the "Maple Leaf Loophole." And thanks for sharing!

## 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....

1. Kate, I too have recited this proof to people at parties, dinners, bars, and elevator rides. It is the proof that really made me fall in love with mathematics in the first place. Infinity is literally awesome.

However, my favorite proof to share with the math illiterati is the demuerability of the rationals. It's a little easier to grasp, and a little more fun to draw on a napkin.

As far as my personal favorite proof? Although Cantor's diagonalization argument is what drew me into the business of infinity in the first place, I prefer the quirky proof that bears his name: the cardinality of the power set of A is strictly greater than the cardinality of A. The non-denumerability of the reals gives you one new infinity, but Cantor's Theorem guarantees you infinitely many of them.

2. This is absolutely my favorite theorem and proof as well. When I first learned about it I was going around shaking my head in amazement for days. I have also shared it with many people young and old. My favorite way to "tell the story" is to start with the even numbers versus natural numbers, as you did, then show that the sets of integers and natural numbers are the same size, then look at the rational numbers. Almost always if you ask someone at this point, they'll guess that the set of rational numbers is a larger infinity, because the rationals are dense. So you show that the rationals are also countable. Then when you prove the the reals are uncountable the punchline has a lot more weight.

3. Odd b/c I think I was the only one on Twitter who picked this as my favorite.

Maybe we should have a 'best retelling of a Cantor proof' contest.

4. I like the way the question is being asked here. When I first saw it mentioned, I couldn't think of my favorite. But my favorite to show others, that's probably not a real theorem.

You mentioned it in a footnote, Kate. The fact that .999... = 1 uses the weirdness of infinity, which enchanted me too, and short enough to keep people's attention more easily.

Hmm, among theorems, I like showing root 2 is irrational (although I saw a nicer proof recently than the one I use, and I don't remember how it goes). And I like proofs of the Pythagorean theorem.

5. Alison, the neat thing about P(A)>A is that it's really the exact same proof! In fact, this exact proof shows up over and over in all sorts of different situations. One of my favorite versions is using it to define recursive functions as fixed points of other functions.

For example, let's define a function F(f,n) which takes a function f and a number n. If n is zero, we say

F(n,0) = 1

Otherwise we say

F(f,n) = n*f(n-1)

A fixed point g will be some function so that

g(n) = F(g,n)

for all n. That is,

g(0) = F(g,0) = 1
g(n) = F(g,n) = n*g(n-1) n>0

the factorial function. And how do we know that such a fixed point exists? By the same diagonalization proof!

6. It's not my favorite theorem, but it reminded me of my favorite book on the subject "The Cat in Numberland" by Ivar Ekeland http://bit.ly/5VV41i. All math texts should be written like this.

I can't believe a used copy goes for \$215 on Amazon. 60 pages with large print and lots of illustrations. Go figure.

-Ihor

7. I'm so glad Ihor mentioned that (I was going to and forgot). I love that book!!

We've talked on Living Math Forum about how to get it republished. I think I'll go review that discussion. I just emailed the publisher and the author to see if there's anything we can do.

8. I wrote to the author, and he wrote back! Cat in Numberland is going to be republished in 2010.

Hi! I will have to approve this before it shows up. Cuz yo those spammers are crafty like ice is cold.