pretendy

Why some infinities are larger than others

The questions ‘how many even numbers are there?’ and ‘how many natural numbers are there?’ would both seem to have the answer ‘infinity’. Our intuition would tell us that there are twice as many even numbers as natural numbers (as for every even number, there is also an odd number too) and we rationalise this internally by thinking “2 x ∞ = ∞”.

However, is it really justified to assert that there are twice as many naturals as evens? Actually it turns out that it isn’t. This can be proven quite easily by arranging them into sets. Let set A contain all the natural numbers and B contain the even numbers.

Two sets contain the same number of elements when you can construct a one-to-one mapping between elements of each set, such that every element is paired only to one other element and no elements are left over. For example, the set {dog, table, fork} can be proven to contain the same number of elements as the set {cat, chair, spoon} through the mapping:

We have now formalised the notion of counting. This makes it extraordinarily easy for us to assess the relative sizes of very large and possibly infinite sets. By finding a neat way to construct a mapping from set to set, we’ve abolished the need to explicitly count out each element on our fingers and toes.

With the sets A and B we can now construct the following mapping:

This should be enough to convince you that the sets A and B are identical in size and there are just as many natural numbers as evens!

Now let’s ask the question, ‘which set is bigger: the set of natural numbers, N, or the set of rational numbers, Q?’. Q is the set of all numbers that can be written as a fraction of integers, ie. 1/2, 321/45, 19/1238912 are all members of Q. ‘There are an infinite number of rational numbers just in the range [0:1] and so for every member of N there are ∞ members of Q so of course they must far exceed the naturals!’ - would be the rational intuition of any human being. But again, it can be shown that Q and N
are the same size.

All of the rational numbers can be written out in an infinite table:

With a little bit of thought, you can see that every rational number you can think of will be contained in the above table somewhere. This represents the table of all elements of Q. With some more thought you can see that by following the path shown on the right, you will traverse the whole table, reaching any given element in a finite number of steps.

In otherwords, for every member of Q, there corresponds a unique member of N: we have constructed our one-to-one mapping and shown that the rational numbers are ‘countably infinite’ like the natural numbers.

Don’t start getting the idea that all infinite sets are the same, though. There are infinte sets whose elements are ‘uncountably infinite’ - where no mapping (to N) exists which ensures that any given element may be counted within a finite number of steps. One such set is that of the real numbers, R. This set contains all the rational and irrational numbers. An irrational number is one that cannot be written in the form a/b, meaning that it has an infinite decimal expansion. Examples of irrational numbers include:

Let’s now imagine that there was some mapping that paired up each member of N with that of R. This might be some complicated map that wasn’t as obviously ordered as the one before. Imagine that it looked something like this:

A neat argument from Georg Cantor shows that such a mapping cannot exist. You have to imagine that this table (like the one for Q) contains every member of R precisely once. We can now take the ith digit of the ith number in the list, add 1 to it, and add it to a new number that we construct:

The number we have constructed, 1.394125794…, is an irrational number that differs from every number in the list, but the list was meant to contain every irrational number in the first place! This proves by contradiction that no such mapping can have ever existed at all!

Now this is really weird. Before, it was quite easy to just vaguely say ‘Well, infinity is infinity so anything that is infinite is just as infinite as anything else that is infinite…’ but we now realise that infinity itself is a much more rigid concept, and there are different levels of infinity. The set of real numbers is necessarily larger than both the set of naturals and the set of rationals.

Freaked out? It might be worth mentioning that Cantor, who most of this work is attributed to, was institutionalised for most of his later years, and died in the sanitarium in 1918.

(Photo: Marek Uliasz)