I still haven’t quite got the hang of the whole “reading stuff in the news and commenting on it” side of blogging, so while you’re waiting for me to figure all that out, have some maths.

We’ll start with a crash course in set theory, using short words and familiar, non-threatening concepts. A *set*, in mathematics, is really nothing more than what it sounds like: it’s a collection, or “set”, of objects, grouped together and considered as a whole. There can be just one item in the set, or ten, or none at all, or infinitely many, and these items can be absolutely anything you like. Here’s an example of two perfectly valid mathematical sets, named **S** and **T**:

**S** = {giraffe, milk, 53, Frodo, purple}

**T** = {1, 2, 3, 4, 5}

There you go, two sets, each made up of five elements. You might’ve been expecting something a bit more numerical than the contents of **S**. We already have a system worked out to describe how numbers tend to behave around each other, so we’d be more likely to use sets like **T** in mathematics than **S**. We can all figure out what 5 – 1 equals, but what you get when you subtract giraffe from purple isn’t very intuitive.

You’d be quite welcome to make up some new and entirely consistent system using a set like **S**, where giraffe + giraffe = milk, and so forth, and this would be just as valid as any other mathematical construct. But, although valid, the workings of such a system would be needlessly wacky, so for the sake of convenience we’ll stick with regular numbers for now.

Look out, it’s a moderately long word you might not have heard before! The *cardinality* of a set is simply the number of elements it contains. **S** and **T** both have a cardinality of 5. Simple enough, just a little new terminology. Coping with all the jargon so far? Okay, here’s another bit: a *bijection* is a relationship that can exist between two sets, when each element from one set is mapped onto an element in the other.

This merits a little more explanation, so go back to **S** and **T** for a moment. One way to come up with a system of doing maths on the stuff in **S** is to act like the elements in there are just labels for the elements in **T**. So, giraffe corresponds to 1, milk to 2, and so on. As well as providing a basis for doing weird things like subtracting giraffe from purple (purple – giraffe = Frodo, since 5 – 1 = 4), matching up the elements in the two sets like this creates a bijection, or a *one-to-one* relationship between the two sets. You can do that if (and only if) the two sets have the same cardinality.

Say you were trying to find a bijection between **S** and another set **U**, where **U** is defined by:

**U** = {1, 2, 3, 4, 5, 6}

In this case, they can’t all be matched up; the number of elements (cardinality) in each is different, so you end up running out of giraffes and Frodos^{1} before you’ve matched each one to a number in **U**.

I can tell you’re getting impatient, so let’s hurry up and bring out what you’ve all paid to see, the main attraction: *infinity*. You can have sets with infinite cardinality too. **N** is commonly used to denote the set of all positive whole numbers:

**N** = {1, 2, 3, 4, 5, 6, …}

All the integers are in there, if you look hard enough, and clearly you can’t make a bijection between this and any of the sets we’ve seen so far. In fact, you obviously can’t map every single element from **N** onto any other set, unless that set *also* has infinite cardinality. For example, you could take all the negative numbers:

**V** = {-1, -2, -3, -4, -5, -6, …}

There’s one element there for every one in **N**, and you can easily draw the bijection: 1 goes with -1, 2 goes with -2, etc. You could also create the sets of odd and even numbers:

**W** = {1, 3, 5, 7, 9, 11, …}

**X** = {2, 4, 6, 8, 10, 12, …}

These obviously both have infinitely many elements as well, and a bijection can be formed between **W** and **X** in the same way: 1 maps to 2, 3 to 4, 5 to 6, etc. But there’s also a bijection from **N** to **W**, or from **N** to **X**. Just double every number in **N**, and it turns into **X**.

This might seem odd. To a certain intuitive understanding of “bigness” which can be hard to resist, **N** looks “bigger” than **X**. The set of all integers contains *all* the even numbers, *and* infinitely many more odd numbers on top of that. But although **X** is a subset of **N**, contained entirely within it with infinite room to spare, they have the same cardinality. There’s a limitless supply of both of them, once you stretch out to infinity.

This can make some intuitive sense too, if you look at it the right way. If something’s already infinitely big, you wouldn’t expect that doubling or halving its size would make a great deal of difference. Sisyphus wouldn’t consider it much of a reprieve if his sentence were slashed in half from the original eternity.

You could also take all the integers, positive and negative, and stick them in an infinite set together.

**Z** = {… -3, -2, -1, 0, 1, 2, 3, …}

This looks “bigger” than **N** in the same way, and might also look more difficult to map to **N**, because **Z** doesn’t have any obvious beginning. It goes off infinitely far in *both* directions, so you can’t just pick a place like 0 and start counting from there. But actually, it’s easy to rearrange things so that it looks just like the same old infinity we’ve already seen.

**Z** = {0, 1, -1, 2, -2, 3, -3, …}

This is obviously the same size as **N** now. There’s no simple formula that looks like *y = (clever mathsy stuff) x* which can take you from one to the other, but you don’t need any of that for a bijection to be there. Just map the first element of **Z** (which is 0, the way we’re listing it here) to the first element of **N**, namely 1. Then link the second element in each set together, then the third, and so on. If you can lay down all the elements of an infinite set in a list like this, as you’ve done with **Z**, then you can show that it corresponds with **N**, and you know that they must have the same cardinality.

This cardinality, by the way, is described as *countably infinite*, a term you may choose to find pleasingly ironic if you wish. At this point, it might not seem obvious that anything *un*-countably infinite should be able to exist. How hard can it be to put even an infinite selection of things in some sort of list, after all?

Well, let’s find out.

The set **R** is generally defined as being the set of all *real* numbers. The integers in **Z** up there can go on forever, but they only appear sporadically along the number line, individual points with lots of gaps in between. There’s no room for 1.38, or ^{3}/_{7}, or the square root of 12, in **Z**. But **R** is the complete line, with all the integers, all the fractions, and all the other stuff in between. If it can be written as a decimal, even one which needs an infinite string of digits to represent it and so could never technically be written down, it’s in **R**.

**R** = {1.38, ^{3}/_{7}, sqrt(12), pi, all of those integers up there… and a whole bunch of other stuff}

Okay, I’m struggling for a way to write it down in the kind of terms we’ve been using so far. But is there some way it could be done? Is this still just the same kind of infinity we’ve been looking at up till now, basically equivalent to **N** when you get right down to it? I mean, they’re both *infinite*, what more can you want?

Let’s take a subset of **R**, and call it **M**, simply because I’m running out of letters. **M** is going to contain all the real numbers in **R** that come between 0 and 1. If you have a number that looks like 0.123456789, say, whatever series of numbers comes after the decimal point, and however long it carries on for, then it’s in **M**. (Strictly speaking, any real number from 0 to 1 can be considered to carry on infinitely past the decimal point; 0.5 is the same thing as 0.500000000…)

If you were to list everything that’s in **M**, then, it might start something like:

0.500000000…

0.123456789…

0.111111111…

0.135792468…

0.333333333…

The first number there is just 0.5, or one half. That second one might just be 0.123456789, or the pattern of digits might keep looping infinitely after the decimal, or there might be something else entirely going on where I’ve let it just drift off with those dot dot dots. You can’t tell for sure from the finite way I’ve written it, but we can choose to define it any particular way we like. The third is an infinite string of 1’s beyond the decimal point, which is the decimal representation of the fraction ^{1}/_{9}. And so on.

The list carries on infinitely, but let’s just look at those five elements we’re starting it off with first. If you’re trying to compile this list of all real numbers, and you want to come up with something new to add to the list which isn’t already on it, how would you go about doing that? At the moment, of course, it’s not much of a challenge – just put a zero, then a point, then mash your palm onto the number-pad of your keyboard, and you’re bound to come up with something new. But ignore that for now, and try to think of some systematic way of picking new numbers, which are in **M** but haven’t already been listed.

Any new number you add has to be different from each of the numbers on the list. So, if you make sure that it has at least one different digit from everything already there, then you can be sure of having something new. Let’s call our new number *x*.

*x = 0.abcdefghi…*

The letters beyond the point each stand for a digit, from 0-9, whatever they might turn out to be. First of all, you need to make sure that *x* isn’t the same as the first thing on our list, 0.5. Easy enough – just make sure that *a* doesn’t equal 5. Decimal representations of real numbers are unique^{2}, so if you make sure that *x* starts off, say, 0.1… then you can be sure that you’re not just repeating the first element already on your list.

But you might be repeating one of the other elements. There may be others which also begin 0.1… – and indeed there are. The second item on the list is 0.123456789. You’ve already chosen *a* to equal 1, so now you want to choose *b* specifically so that *x* turns out differently from 0.123456789. So, let’s say *b* = 4. Now you know that your new number *x* begins 0.14… and so it’s definitely not the same as either of the first two elements already on your list.

At a glance, you can see that nothing else on your list starts with 0.14… which means that, however you write *x* after that, it’s not already among those five. But keep on with this pattern anyway, as if there were more elements on the list you want to be sure of avoiding, so you can see how it can be generalised later, to a longer list. The third element is 0.111111111; its third digit after the point is 1; so you make sure that *c*, in *x*, doesn’t equal 1, to make sure that 0.111111111… is not the same as *x*. Similarly with the fourth, and the fifth, and so on.

If this is all getting a bit abstract, look at the list like this:

0.500000000... 0.123456789... 0.111111111... 0.135792468... 0.333333333... 0.abcdefghi...

The underlined digits are the ones you’ve been avoiding in constructing your new element *x*. This is how you ensure that *x* is different from every real number already on the list, however long that list is. You could then add *x* to the list, and a load more real numbers, and you could still use this method to make sure that the next one you add to it isn’t already listed, just by making sure that the new number you choose is different from every number already there, by at least one digit. And the list can be as long as you like for this to still work.

Even… *infinitely* long?

Or did I just *blow your mind*?

Since there are infinitely many digits after the decimal point, there’s no reason you can’t take an infinitely long list of all these real numbers, and still construct a new number which is different from all the numbers already there. This works just the same as what you did with *x* above, and will let you construct a new number that isn’t on this infinite list. In fact, even if you assume that you’ve listed every single element of **M**, every real number that exists between 0 and 1, you can still make up some number *x*, starting 0.abcdefghi… just like you already have done. So, *x* turns out to be a real number between 0 and 1 that’s *not* on the list… even though the list was supposed to contain every real number between 0 and 1.

So… what’s the deal there? Did you just break maths?

Fortunately, no. An inconsistent result like this generally means that some mistake has been made somewhere in your assumptions. In this case, the thing you’ve assumed is that the infinitely many numbers in the set **M** can be listed at all. Actually, there is no way to describe a list like that, because as we’ve just shown, you can always use this method to find an element which *isn’t* on the list, thus sending your assumption that *everything* is on the list straight to buggery.

So, the elements of the set **M** cannot be listed like this; they cannot be arranged into some order where you can say that this is the first element, this is the second, and so on. By extension, this is also true of the real numbers **R**, of which **M** is a subset. This is the same thing as saying that the real numbers can’t be matched up to the positive integers 1, 2, 3… which, in turn, means that there exists no bijection, no precise one-to-one correspondence, between **N** and **R**, and *this*, at long last, means that **N** and **Z** must not have the same cardinality. Saying that there are “infinitely many” elements in the set means something different in each case. They’re both infinite, but one’s bigger.

… Any questions?

## Leave a Reply