Monday, July 11, 2011

Sizes of Infinity

Everyone knows about infinity, but most people don’t know that there are actually different sizes of infinity: the transfinite numbers. This may out odd at first; after all, how do you define the size of something that is infinite?

For example: there are an infinite number of even numbers. But, to be more precise, there is a “countable infinity” of even numbers; in other words, you can enumerate them.

Say we start at 0 and call it the first even number; then we say that 2 is the second even number, -2 is the third, 4 is the fourth, -4 is the fifth, et cetera. In this way we can assign an integer to each even number. (Note that we can choose any numbering scheme we like; what’s important isn’t how we enumerate them, but rather that we can.) Therefore, the size of the even numbers is as big as the size of the integers, and that size is “countable infinity”, often represented by the symbol aleph zero. A similar argument can be given for odd numbers, positive numbers, negative numbers, primes, and so forth.

On the other hand: when one tries to count the real numbers, a problem arises. For any two real numbers there will always exist another between them. It is not possible to create a one-to-one correspondence between the real numbers and the integers; in other words, they are impossible to count. For a rigorous proof of this fact see Cantor’s diagonal argument.

Notice that between any two rational numbers (numbers of the form a/b) there is also always another number; nevertheless, we can construct a an isomorphism between the rationals and the integers. So, in fact, there are just as many rationals as there are integers! One such isomorphism is the Calkin-Wilf tree.