Recent Posts

Cardinality

19. May, 2013

It's time to make a post about MATHS.

Most people who know some mathematics know that there are infinitely many natural (whole) numbers. It's easy to see — you can always add one to a number and you get a brand new one. Clearly this also goes for many other sets: there are infinitely many even numbers, odd numbers, rational numbers (fractions) and real numbers (decimals). But one of these sets is not like the others — it is bigger than the rest!

Most people (unless they have inside knowledge) will think this is either obviously true or obviously false, and they will both be wrong! The first person will think that there are obviously more natural numbers than evens, more rational numbers than natural numbers, and more real numbers than rational numbers (since every fraction can be written as a possibly repeating decimal, but there are irrational numbers, like \pi.) The second will think that they are all just infinite, and therefore the same size — if you add something to infinity, you still have infinity.

The first person is right, to a point. However in mathematics once you get to dealing with infinite sets we need to pin down what we mean by "size", and the concept we landed on is "cardinality." The upshot is just that two sets are the same size if the elements of each set can be paired off with each other, so that all elements of set A have one and only one corresponding element in set B, and vice versa.

Thus there are as many natural numbers as even numbers, because we can pair each number n with the even number 2n. It's easy to see that there is one, and only one, 2n for each n, and one, and only one n for every even number — since an even number is a number in the form 2n:

\begin{array}{c|c} 1 & 2 \ 2 & 4 \ 3 & 6 \ 4 & 8 \ \vdots & \vdots\ n & 2n \ \end{array}

What we've done is exhibited a bijection between the set of natural numbers, \mathbb N, and the set of evens, 2\mathbb N. A set that is in bijection with the natural numbers is called countable. The link shows how it is possible to prove that the set of rational numbers is countable.

So, up until now the second person was correct, but no longer. Cantor proved in 1891 that there are more reals than there are naturals — that the set \mathbb R of reals is uncountable.

The proof is quite simple. Suppose \mathbb R is countable, and we will find a contradiction, so what we supposed is impossible, and \mathbb R must be of a different cardinality than \mathbb N. (And, since \mathbb N\subset\mathbb R, it is clearly bigger!)

To be countable, there must be a bijection — a function f from \mathbb N to \mathbb R pairing off the elements with each other. We can illustrate such a function as follows:

\setlength{\arraycolsep}{3pt} \begin{array}{c|c@{\hskip\arraycolsep.\hskip\arraycolsep}ccccc} n & \multicolumn{5}{c}{f(n)}\ \hline 1 & \boxed{0} & 4 & 5 & 2 & 6 & \cdots\ 2 & 8 & \boxed{2} & 0 & 2 & 2 & \cdots\ 3 & 3 & 1 & \boxed{4} & 1 & 9 & \dots\ 4 & 1 & 0 & 0 & \boxed{0} & 0 & \cdots\ \vdots \end{array}

Now we have to imagine that this table goes on forever down and right, since there are infinitely many ns, and each f(n) can be infinitely long if it is irrational, but that's OK. This table just illustrates what part of one possible potential bijection would look like, and we are about to argue about any candidate — it's important to remember that whatever f we try, this argument will still apply, whether we try to modify it slightly, or pick a completely new one. It also doesn't matter that we only showed numbers between zero and ten.

Suppose we had indeed paired off everything, so that every real had its n, then I will show how to find a new real number, x. The idea is that we will show that x does not appear anywhere in the table, and hence f will not be a bijection (if it were, then every possible real, including ones we cook up in fanciful ways, must be listed.) Then, we will have a contradiction, meaning that \mathbb R is not countable.

The contradiction follows from looking at the diagonal of the f(n)s. So, look at the first decimal digit of f(1) — above it is 0. If it's zero, then the first digit of x will be one, and otherwise it will be zero. So for the above table, x starts 1.. Then, look at the second digit of f(2). Do the same, so x now starts 1.0. Continuing in this way, we get 1.001\ldots, and the nth digit of x is 1 if the nth digit of f(n) is 0, otherwise it is 0.

Now, if f were indeed a bijection, as we want it to be, this x must be listed on the table somewhere — every real number is. But it is quite obvious that x does not appear, because it is different from f(1) at position 1, f(2) at position 2, and so on — it is different from f(n) at position n!

And that is the contradiction. Any possible bijection — one-to-one pairing — of the natural numbers with the reals has this problem, so no such pairing can exist. Hence there really are more real numbers than there are natural numbers.

Now, some people will be entirely convinced by this while others might have objections. The first common objection says, "why couldn't we just add this new number to the list?" But remember, the argument above works with any possible listing, so just adding a number (or infinitely many!) to the list won't help; we can run the same procedure and find a missing number still.

The second common objection is that the notion of cardinality must somehow not be fit for purpose. After all, if it produces such weird results, why should we accept it as the mathematical notion of "size"? Well, first of all, even if we rejected cardinality as the correct definition of size, we'd still be left with the fact that we can't pair off the natural numbers with the reals, and if that's not because there are more reals than naturals, why is it? Second, it turns out that this concept is much more robust than any other notion of size when applied to infinite collections of things and so weird as it may be, cardinality is the best tool for the job!