Uncountable vs. Infinite

What does it mean to be infinite? Never-ending? What about uncountable? Is the set of integers uncountable? How about the real numbers? What’s the difference?

Questions from a freshman math student, no doubt. The uncountable vs. infinite problem is a turning point in the quest for a bachelor’s degree in mathematics. To be crude, it’s the “shit or get off the pot time” for the aspiring undergrad. It’s also one of the coolest definitions in mathematics, because it’s paradoxical and basically impossible to explain without also proving it. Not very many problems are like that.

This problem has to do with the cardinality of sets: “prove that such-and-such set is countable”. Not surprisingly, this comes up a lot in discrete mathematics and group/ring theory, since both topics use sets as input and output to problems.

Infinitude

So what does it mean to be infinite? That’s actually the easy one: it goes on forever. The set of integers is infinite, because, for example, there’s no upper bound on how high you can count. The natural numbers [1, 2, ... n-1, n, n+1, ...] are also infinite, for the exact same reason. Yet it seems like the natural numbers should be half the size of the integers, since it’s really just the set of integers without the negative ones. Yet both sets are infinite, and we still have \mathbb{N} \subset \mathbb{Z}.

So we have two infinite sets, and one is a subset of the other. We already have a paradox, and I haven’t even gotten to countability yet. Isn’t math fun?

Countability

So, how is uncountable different? Well, actually, the definition of countable is really the interesting part here. The formal definition of countable is:

A set is considered countable if it is isomorphic to the natural numbers.

Like any good mathematical definition, it leaves you searching for a dictionary. Basically, it means that a set is countable if you can come up with a function that maps every element in the set to a distinct element in the natural numbers. If you think about that for a minute, it kind of makes sense. The natural numbers are also known as “the counting numbers”. If you can represent another set as a function that maps to [1, 2, 3 ...], then you’ve just proven that it’s fundamentally equivalent to the counting numbers, so it should be countable. Of course, a proof by grammar isn’t really acceptable, but for the purposes of comprehension, it might help. Or not. Whatever.

So, obviously, the natural numbers are countable, because the function f(x)=x|x\in\mathbb{N} maps every element x in the natural numbers (\mathbb{N}) to itself.

Diagonalization

Now, we come to Cantor, and his proof by diagonalization. Basically, Cantor came up with a simple of way of expressing the countability of sets using a matrix where the diagonals of the matrix are significant. But the theory of that is not important right now. Right now we’re going to use diagonalization to prove that the rational numbers (\mathbb{Q}) are countable.

Let’s put the rational numbers in a matrix, such that the pattern is obvious.

\left( \begin{array}{ccccc} 1/1 & 1/2 & 1/3 & 1/4 & \ldots \\ 2/1 & 2/2 & 2/3 & 2/4 & \ldots \\ 3/1 & 3/2 & 3/3 & 3/4 & \ldots \\ 4/1 & 4/2 & 4/3 & 4/4 & \ldots \\ \ldots & \ldots & \ldots & \ldots & \ldots \\ \end{array} \right)

If the pattern’s not obvious, we’re enumerating the rational numbers, starting in the top left corner with 1/1. To the east, the denominators increment, and to the south the numerators increment. By enumerating the rationals in this way, it should be equally obvious that given an infinitely large matrix, we would generate every single rational number. For example, where would 117/934 be? It would be at the intersection of the 117th column and the 934th row.

Now, Cantor’s diagonalization comes in to prove that the rationals are countable. If we use a pen and traverse the matrix starting at the top left corner at 1/1, we can traverse it in such a way that our pen never leaves the table, and we hit each number only once. This graphic should help visualize it:

diagonalization

QED.

How does this prove that the rationals are countable? Well, we just showed that we can enumerate every single rational number, and traverse them in a unique way such that we only hit each rational number once. There’s your isomorphism. If you really want, you can put that sentence in the form of a function, but I’ll leave that as an exercise to the reader.

February 27, 2010   Posted in: math

Leave a Reply