Infinity and beyond

Infinity is not a number, it`s a free man

Infinity is not a number, and trying to treat it as one tends to be a pretty bad idea. At best you`re likely to come away with a headache, at worse the firm belief that $1 = 0$ .

You may have met various "paradoxes'' that play on this fact (and our instinct to ignore it) before. An infinitely long line, for instance, is surely infinitely many centimetres long. It`s also, equally surely, infinitely many miles long. But each centimetre is a great deal shorter than each mile, so does this mean an infinitely long line is two different lengths at once?

The answer, of course, is to assert confidently that the question is meaningless (and, if you`re in the mood to be unkind, just shows how little the asker knows about proper mathematics) and then go back about your business untroubled by such silly quibbles.

Or, as I will hopefully convince you over the course of this article, the answer is a simple "No.''

Counting the natural numbers

You shouldn`t, I said a few paragraphs above, treat infinity as a number. You can`t count up to it, and if you have an infinitely large set (a set is a collection of objects. They can be any sort of objects, although generally mathematicians use them to talk about mathematical objects, such as numbers. An infinitely large set is, of course, one containing infinitely many objects) you`ll never be able to count all of the objects in it. It seems counterintuitive, therefore, to talk about certain infinitely large sets being "countably infinite'', but that is indeed what I`m about to do.

Consider the natural numbers (the positive, whole numbers: $1, 2, 3, \dots$ ).

There are infinitely many natural numbers (if there were only a finite number of them, there would have to be a largest natural number - what would happen if you added 1 to that number?) so the set containing all the natural numbers must be infinitely large. You`ll never be able to count them all. However, you can list them in such a way that if you counted forever, you`d be sure not to miss any out.

The natural numbers are what we use for counting anyway, so we can think of them as coming ready-listed. There is an obvious starting point (1, I am told, is the Cambridge convention, although in my heart of hearts I know the natural numbers start at 0) and a sensible order ( $1, 2, 3, \dots$ ).

To illustrate what I mean by a sensible order, imagine what would happen if you tried to count them randomly. However long you counted, you`d never be sure you`d counted them all - you could check for individual numbers in your random list, but you'd never know if they were all there, or when (if ever) you were going to reach a particular one.

Now imagine what would happen if you tried to count the natural numbers by counting the odd numbers first and then the even ones. You`d count forever, and never even start counting the even numbers.

However, if you count them in the order given, you`ll know once you`ve reached 100 that you`ve counted everything between 1 and 100 once and only once. You might never reach the end (in a finite time, at least) but you`ll know you`ve not missed anything on the way and that it`s just a matter of time before you reach any given number.

So this is what we mean by saying the natural numbers are countably infinite.

Counting the integers

Any infinite set of numbers, therefore, that can be put in a sensible, systematic order with a clear beginning such that you're sure to get everything if you count forever is thought of as countable.

When we talk about comparing the sizes of two sets that contain finite numbers of objects (a set, $C$ , containing some cats and a set, $M$ , containing some baby mice, say) then one way to do so is to match each object in one set with exactly one object in another set and see if we have any left over. For the sets $C$ and $M$ , we can set each cat to catch exactly one baby mouse - no sharing allowed, nor hogging more than one mouse. If each cat does catch exactly one baby mouse - no more, no less - we know there are (or, at least, were) the same number of cats as mice. That is, the sets $C$ and $M$ were the same size. If any cats go hungry, there were more cats than mice ( $C$ was larger than $M$ ) and if any mice go free, there were more baby mice than cats ( $M$ was larger than $C$ ).

This is called putting the objects into one-to-one correspondence, and the same can be done when comparing the sizes of infinite sets.

Another way of thinking about countably infinite sets is that they are those sets whose objects can be put in a one-to-one correspondence with the set containing the natural numbers only. That is, if for each element in the set of the natural numbers there is exactly one - no more, no less - element in the set you`re trying to count then the set is the same size as the set containing the natural numbers: countably infinite.

Are the integers (all the whole numbers: $\dots, - 2, - 1, 0, 1, 2, 3, \dots$ ), therefore, countable?

At first, you might think not. First you need to find a sensible beginning, and that may not be obvious. With the natural numbers, we just started at the smallest and worked up. But the integers don`t have a smallest number (just as before, when showing there was no largest natural number, think to yourself: if there were a smallest integer, what would happen when you subtracted 1 from it?), so where can we begin?

Say we start at 1 and work up, as before with the natural numbers. Then we count $1, 2, 3, \dots$ , putting them into one-to-one correspondence as follows:

Natural numbers 1, 2, 3, ...

Integers 1, 2, 3, ...

Here, the problem is however long we count for, we`ll never start on the negative numbers. We`ll never even get to zero.

So how, then, can we count the integers?

Consider the following table:

Natural numbers 1, 2, 3, 4, 5, 6, 7, ...

Integers 0, -1, 1, -2, 2, -3, 3, ...

Is each number counted once and only once?

It may help (or it may not - don`t dwell on this if it just confuses you) to visualise the integers as distinct points on an infinitely long line. Think of 0 as the centre of the line, and imagine a circle, centre 0, which increases in radius as you count up, covering the numbers you've counted. After you`ve counted to the seventh integer on the list, say, the circle has a radius of 6, and covers every number from -3 to 3.

Once you reach any integer on the list ( $p$ , say), any integer with a modulus (the modulus function (where $‖ n ‖$ is the modulus of $n$ ) is $n$ if $n ≧ 0$ and $- n$ if $n < 0$ ) smaller than $‖ p ‖$ will have been counted exactly once, and any number with a modulus larger than it well be yet to count. Whether $- p$ has been counted obviously depends on whether $p$ is greater or less than 0.

So, while at first glance it might seem that there are more integers than natural numbers, this is not the case. This is exactly what happens in the so-called paradox I mentioned at the start of this article - just as you might first think that for each natural number, $n$ , there are two integers, $\pm n$ , and so there are twice as many integers as naturals, which is not the case, so you might think an infinite number of miles takes you further than an infinite number of centimetres. In fact, the centimetres that go to make up the infinitely many miles can be put into one-to-one correspondence with the infinitely many centimetres, so both take you the same distance.

Counting the rationals

How about the rational numbers? (all the numbers that can be written as one integer divided by another: $\dots, - 2 / 3, 0 / 1, 1 / 1, 1 / 2, \dots$ )

In the case of the natural numbers and the integers, it was easy to check we`d counted every number in a given range. To check we`d counted all the natural numbers less than $n$ , we merely needed to have counted up to $n$ . To check we`d counted all the integers between $n$ and $m$ , we needed to check we'd counted as far as $‖ n ‖$ or $‖ m ‖$ , whichever is the largest.

However, we can`t count all the rational numbers in a given range, however small the range is.

This is because the rationals are what is known as dense in themselves - between any two rationals, there is another rational. (If you're unconvinced, imagine $x$ and $y$ are two rationals between which there isn`t another rational. What is $(x + y) / 2$ ?) Between $- 2$ and 4 there are seven integers (including $- 2$ and 4) and four natural numbers. There are, however, infinitely many rationals. The question is, what kind of infinity?

It seems we need another trick.

Consider the table of positive rationals as follows:

$\frac{1}{1}$ $\frac{1}{2}$ $\frac{1}{3}$ $\frac{1}{4}$ $\frac{1}{5}$ $\frac{1}{6}$ ...

$\frac{2}{1}$ $\frac{2}{2}$ $\frac{2}{3}$ $\frac{2}{4}$ $\frac{2}{5}$ ...

$\frac{3}{1}$ $\frac{3}{2}$ $\frac{3}{3}$ $\frac{3}{4}$ ...

$\frac{4}{1}$ $\frac{4}{2}$ $\frac{4}{3}$ ...

$\frac{5}{1}$ $\frac{5}{2}$ ...

$\frac{6}{1}$ ...

$\cdot$

$\cdot$

$\cdot$

Is this a list of all the positive rationals? Consider the general term for a positive rational, $p / q$ , where both $p$ and $q$ are positive. If it`s on the table, then we know we`ve got all the positive rationals there. (If we hadn`t, there would be a positive rational that can`t be represented as $p / q$ , which is not the case.) Is it?

Yes, it`s on the $p^{th}$ row in the $q^{th}$ column.

So, we have a list. However, trying to count along each row or column in turn gives problems - each row and column is infinitely long, after all, and so we`ll never reach the end of the first to start on the second. Is there, then, a way of counting them without missing any out?

[[INSERT HERE DIAGRAM SHOWING HOW]]

So we know we`ve counted every rational at least once. Have we counted them at most once?

Obviously, we haven`t. $1 / 1 = 2 / 2 = 3 / 3 = \dots$ means 1 is the first, fifth and thirteen number in the list.

Why does this matter? It`s a good habit to get into, certainly, but more than that it`s useful here to convince ourselves that these sets of numbers are all the same size. If we don`t check we`re not counting the rationals too many times, what`s to stop there being more natural numbers than there are rational ones?

Intuitively, this seems to be a fairly silly fear (after all, the natural numbers are just the first column of the entire table of rationals) but by this stage you should be doubting your intuition.

We could just check each number we reach against all the previous numbers, making sure it`s not equal to any of them. That would work, but ignores the fact that the order in which we`re counting these numbers means the first time we meet each one, it`s in its simplest possible form.

Consider our trusty $p / q$ , in row $p$ , column $q$ . Assume this is the number in its simplest form - $p$ and $q$ have no common factors greater than 1. The next time we meet the same number, it`ll be $2 p / 2 q$ , which is in row $2 p$ , column $2 q$ , therefore on a diagonal further from our start point. $(n + 1) p / (n + 1) q$ is always further along than $np / nq$ (if you need convincing, find a formula to tell you which integer is the leftmost point on the diagonal passing through $y / x$ ).

So every time you reach a rational not in its simplest form, ignore it.

Hence the positive rationals can be put into one-to-one correspondence with the naturals, and so are countably infinite. Multiply by $- 1$ and we get a similar list of the negative rationals. Then, just as we did with the integers, start at 0 and interleave the two lists:

Natural numbers 1, 2, 3, 4, 5, 6, 7, ...

Rationals 0, 1/1, -1/1, 1/2, -1/2, 2/1, -2/1, ...

We know we will have every positive and every negative rational, and zero, once and only once.

Thus the natural numbers are countable, the integers are countable and the rationals are countable. What isn`t?

Counting the reals: Cantor`s Diagonal Proof

Are the real numbers countable? (Irrational numbers are those numbers than cannot be written as one integer divided by another: $π$ , $\sqrt{2}$ , $e$ , $\dots$ The real numbers are all the rationals and the irrationals together: 1, 4/5, $π$ , $\dots$ )

Everything else we've met so far has been. Each new set of numbers that feels as if it should be larger than the set of the natural numbers has been put into one-to-one correspondence with the natural numbers - it seems to be just a case of finding a slightly more complicated trick each time and then fiddling until it works.

The real numbers are made up of the rationals and the irrationals. The rationals are countable, so if the irrationals are countable then the reals must be countable - just interleave your two systematic lists and you`ll get another systematic list.

For the same reason, if the reals aren`t countable, we`ll know that the problem comes with the irrationals.

You`ve probably met rational numbers in at least two guises - one is that they can be written as one integer divided by another, and the other is that they can be written as decimal expansions that eventually become repeating patterns.

1/3 = 0. 33333 33333 33333 33333 ... - the threes repeat forever.

3/8 = 0. 37500 00000 00000 00000 ... - the zeros repeat forever.

22/7 = 3. 14285 71428 57142 85714 ... - 142857 repeats forever.

All real numbers can be represented as infinitely long decimal expansions. The rationals are the ones that eventually repeat and the irrationals are the ones that don`t.

$π$ = 3. 14159 26535 89793 23846 ... - at no point do a finitely long string of digits start repeating forever.

Now, suppose the real numbers were countable. Then we could write a systematic list of all the real numbers. What is more, we could do it as list of decimal expansions:

$a_{00} . a_{01} a_{02} a_{03} a_{04} a_{05}$

$a_{10} . a_{11} a_{12} a_{13} a_{14} a_{15}$

$a_{20} . a_{21} a_{22} a_{23} a_{24} a_{25}$

$a_{30} . a_{31} a_{32} a_{33} a_{34} a_{35}$

$a_{40} . a_{41} a_{42} a_{43} a_{44} a_{45}$

$.$

We might run into trouble with repeats (0.9 recurring = 1, for instance) but we can just check every number in our list off those that came before. It might be that the system we use to list the numbers lends itself to a neater method, but even if it doesn`t, this one will work.

But can we be certain we haven`t missed any out?

One way of answering this question is to assume our list is, in fact, infinitely long. Then will it contain every possible real number?

Consider the number $A = a_{00} . a_{11} a_{22} \dots a_{nn} \dots$

For all $m$ in the natural numbers (and $m = 0$ ), do the following:

If $a_{mm} \neq 5$ , let $b_{mm} = 5$ .

If $a_{mm} = 5$ , let $b_{mm} = 7$ .

Then you have a new number, $B = b_{00} . b_{11} b_{22} \dots b_{nn} \dots$

Is $B$ on our list?

Well, it`s not the first number, because the first digits don`t agree. And it`s not the second number, because the second digits don`t agree. And it's not the $n^{th}$ number, because the $n^{th}$ digits don`t agree...

So $B$ isn`t on our list. Since none of the digits of $B$ are 0`s or 9`s, we know that $B$ is a unique number, since repeats only occur with recurring 9`s and recurring 0`s. So the list isn`t complete. So however cunning your system, even if the list is infinitely long it won`t contain every real number.

This means that you can`t count all the real numbers - there are uncountably infinitely many.

The above argument is Georg Cantor`s (LINK TO BIOGRAPHICAL INFORMATION), and is known as Cantor`s Diagonal Proof.

Natural numbers	1,	2,	3,	4,	5,	6,	7,	...
Integers	0,	-1,	1,	-2,	2,	-3,	3,	...

$\frac{1}{1}$	$\frac{1}{2}$	$\frac{1}{3}$	$\frac{1}{4}$	$\frac{1}{5}$	$\frac{1}{6}$	...
$\frac{2}{1}$	$\frac{2}{2}$	$\frac{2}{3}$	$\frac{2}{4}$	$\frac{2}{5}$	...
$\frac{3}{1}$	$\frac{3}{2}$	$\frac{3}{3}$	$\frac{3}{4}$	...
$\frac{4}{1}$	$\frac{4}{2}$	$\frac{4}{3}$	...
$\frac{5}{1}$	$\frac{5}{2}$	...
$\frac{6}{1}$	...
$\cdot$
$\cdot$
$\cdot$

Natural numbers	1,	2,	3,	4,	5,	6,	7,	...
Rationals	0,	1/1,	-1/1,	1/2,	-1/2,	2/1,	-2/1,	...