Monday, August 1, 2011

Infinite confusion

As any kid who has learned about infinity will tell you, infinity plus one is still infinity. “Even infinity plus a million?” Yep. “Even infinity plus infinity?” Yep. It's easy to think there's only one infinity. But there's not. It turns out there's an infinite number of infinities.

This remains one of the most interesting ideas I learned in college. In my discrete math class my freshman year, the professor went over Cantor's diagonalization argument, and I still haven't gotten over it. Briefly, the argument goes as follows. (And by “briefly” I mean I'm not going to include proof.)

There are an infinite number of whole numbers. If you add to the whole numbers all rational numbers, you still have the same number of numbers—infinity—because you can map each rational number to a whole number, one-to-one. But if you add to the rational numbers the irrational numbers—e.g., π, √2, etc.—you will have a greater infinity of numbers than with the rationals alone because you can't map each irrational number to a rational number. You'll have irrational numbers left over.

The neat thing about Cantor's argument is that it proves there's no possible one-to-one mapping from the irrationals to the rationals. Thus, some infinities are bigger than others. QED.

If that doesn't make you suspicious of your intuition about infinity, there's Berry's Paradox. It goes like this.

There exists an infinite number of whole numbers, and there exists a finite number of syllables (in English). Therefore, there exists an infinite number of whole numbers that can't be described in English in fewer than, say, twenty syllables. The question is: What is the smallest whole number that can't be described in fewer than twenty syllables?

A description is an unambiguous expression or name. Let's start from the beginning.

Number Description Syllables
1 “one” 1
2 “two” 1
3 “three” 1
4 “four” 1
5 “five” 1
6 “six” 1
7 “seven” 2
8 “eight” 1
9 “nine” 1
10 “ten” 1
11 “eleven” 3

Eleven is the first number whose name is more than two syllables, but it's describable as the “fifth prime,” which is two syllables. So:

11 “fifth prime” 2
12 “twelve” 1
13 “thirteen” 2

And so on. The key is that we're describing numbers, not just naming them. Any unambiguous description will do. For example, “one hundred twenty-one” (six syllables) is also “fifth prime squared” (three syllables). “One thousand one hundred eleven”(nine syllables) could be described as “four ones” (two syllables);—if we allow such shortcuts. But no matter how many shortcuts we allow—no matter what grammar we decide upon—because there are a finite number of syllables, eventually we'll run out of whole numbers describable in fewer than twenty, and that will be our smallest whole number that can't be described in fewer than twenty syllables.

But there's a problem. “Smallest whole number that can't be described in fewer than twenty syllables” is itself an unambiguous description of a number—a description that itself is fewer than twenty syllables. Thus, the smallest whole number that can't be described in fewer than twenty syllables can be described in fewer than twenty syllables by using this description. Paradox!

What's neat about Berry's Paradox is that it defines an infinite set of whole numbers for which there exists no smallest number—no first number, no “beginning” number. This is another property of infinity that runs counter to intuition.


Chad said...

Dude, your brain hurts my brain. Is this what you think about on long rides?

cmbrandenburg said...

Chad— I've learned from others' experiences that it's best to pay attention to one's surroundings when biking.