Irregular Webcomic! #2292

How many numbers are there?

Okay, that's a little unspecific. How many counting numbers are there? To give them a more formal name, how many natural numbers are there? These are the numbers you use to count things:

1, 2, 3, 4, 5, 6, ...

Some people like to include 0 in there as well. For the purposes of today's question, that's not important. We're talking about positive (or non-negative) whole numbers. No fractions, no irrational numbers, no other weird numbers. Okay, so how many are there?

Here's the thing. You use natural numbers to count the number of objects in a collection. It doesn't matter how big your collection of objects is, there needs to be a natural number matching it. (They don't need to be physical objects, by the way - you can count other things just as easily, for example the number of flavours of ice cream, or the number of times you've seen Star Wars.) But it doesn't matter how many objects are in your collection, it's always conceivable to add one more. And when you add one more, you need one more natural number to describe how many you have now.

So the natural numbers never "run out". There is no "biggest" natural number. Name any natural number you care to. I can name one that is bigger. Not to be outdone, you can always name one that is bigger than that. And so on.

So how many natural number are there?

A thousand? No - give me a thousand different natural numbers and I can name one you don't have already. A million? No - same deal. A billion? No again. If we start counting at 1, by the time we get to a billion, we've collected a billion natural numbers. But there's still a billion and one, and two billion, and a hundred billion, and 50 trillion, and... well, there are still lots of numbers we haven't counted yet.

And it doesn't matter how far you go, whatever number you count up to, I can name numbers you haven't counted yet. Lots of them.

So: How many natural numbers are there?

It should be pretty clear that we can't say how many natural numbers there are by giving the answer as a natural number itself. Because any number we name, we always find that there are more than that. Every single natural number we can think of is too small.

We describe this situation by saying that there are an infinite number of natural numbers.

Now, the concept of "an infinite number" is a very tricky idea, and it's incredibly easy to get a slightly incorrect understanding of what it really means. Some people think of "an infinite number" as essentially "a really, really big number". This is wrong. A really, really big number, no matter how big it is, you can count up to if you have enough time and enough patience. By "enough time" I may actually mean more time than the age of the universe - physical considerations don't come into it. Assuming you did (somehow) have all the time you needed, you could count up to any really, really big number. But you will never reach an infinite number. Never. Ever. That's what an infinite number means - it's a number you can never reach by counting, no matter how long you have.

All right, so there are an infinite number of natural numbers. Let's try a trickier question. How many integers are there? Integers are the set of positive and negative whole numbers (and zero):

... -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, ...

Let's start by comparing the integers to the naturals. The naturals start at 1 (or 0, if you prefer), and go off forever in one direction. Which gives us an infinite number of naturals. The integers kind of start in the middle, and go off forever in two directions. On the positive side, no matter how big an integer you name, I can name a bigger one (just like the naturals). But also on the negative side, no matter how big a negative number you name, I can name one even more negative.

So it looks like there are twice as many integers as there are naturals! That kind of seems to make sense. Only what is two times an infinite number? Well, we know there are no numbers bigger than an infinite number, so if you multiply it by 2, you must get... the same infinite number? Now things are getting slightly confusing. Are there twice as many integers as naturals, or the same number? Does this question even make sense?

The question does make sense, and here's how to think about. If we write the integers in a different order, we don't change how many there are, as long as they're all still there. So let's do this:

Naturals    0   1   2   3   4   5   6   7   8   9  10  11  12 ...
Integers    0   1  -1   2  -2   3  -3   4  -4   5  -5   6  -6 ...

On the bottom row, I've written the integers, starting at 0, then going to 1, followed by -1, and... well, you can see the pattern. I hope it's obvious that every single integer is in the list on the bottom row (which notionally extends forever). Any integer you can name, 17, -435, 983021, -4372745996273, is in that list of numbers. It's true, it takes twice as long to get there if you start at the 0 and work your way to the right one number at a time, but the number is there.

Now the interesting thing about this rearrangement is that we've gotten rid of the two-ended "going off forever" thing. The integers now start at one point and go off forever in only one direction! In fact, by using the list of natural numbers in the top row, we can count the number of integers. Not only can we count them, we can count them using exactly the same numbers we used to count the natural numbers. And we never miss any.

So how many integers are there? An infinite number of them, yes, but we can see that we can match the integers up one-for-one with the naturals. In some very real sense, there are exactly the same number of integers as natural numbers.

This is just one of the many surprising and counter-intuitive things that happens when you deal with infinite collections of things. The naturals are an infinite collection of things (numbers), and the integers are an infinite collection of things. And we can match them up one-for-one. Forget about the intuitive idea that there must be twice as many integers. If you take two collections of things and you can match them up one-for-one, and not leave any out in either collection, then the two collections are the same size.

But let's not stop there. How many rational numbers are there? These are the numbers formed by dividing one integer by another non-zero integer. Fractions.

Well. With naturals and integers there are obvious gaps between the numbers - between 1 and 2 there are no other natural numbers. But with rationals, there is always another number between any two rational numbers. Between 1/3 and 1/2 there is 5/12. Between 5/12 and 1/2 there is 11/24. And so on. You can always add any two rational numbers together and divide by 2 to get another rational number in between. No matter how close together they are (assuming they're not actually the same number to start with).

If you think about it for a minute, this means that between 1 and 2, there are an infinite number of rational numbers! Because it doesn't matter how many rationals you name, you can always find more, by splitting the gaps. The gaps will get incredibly small, but you can always keep splitting them with more in-between rational numbers. Good lord. Between 1 and 2 we already have an infinite number of rationals! How are we ever going to count them all?

rational number counting Well, rearranging worked for the integers. Let's try a similar thing here. Take a look at the diagram (based on an original diagram by Cronholm144 and released under Creative Commons Attribution ShareAlike). I've written the natural numbers along the top and down the side of a grid. In the grid, each position is filled with a rational number formed by dividing the row number by the column number. The grid continues forever to the right and downwards. Since every (positive) rational number can - by definition - be written as one natural number divided by another, this means that every positive rational number is in this grid somewhere.

17/235? It's in the 17th row, 235th column. 561 and 34/291? That equals 163285/291, and sits in the 163285th row, 291st column.

Okay. But the grid has an infinite number of rows, and an infinite number of columns. This is even worse than the integers, which went on forever in two directions. The rationals head off forever in an infinite number of different rows and columns!

But take a look at the grey arrows. They start at 1/1, head down to 2/1, then diagonally up to 1/2, then across to 1/3, then diagonally through 2/2 to 3/1, down again, diagonally up, and so on. If you follow this path, you cover every slot in the grid. It doesn't matter which slot of the grid you pick, you'll be able to get there by following this path. That means that whatever positive rational number you can think of, you can reach by following this path.

At this point notice that some of the numbers in the grid are actually the same number. 2/2 for example, is just 1, which is the same as 1/1. Likewise 3/3, 4/4 and so on. And 2/4 is the same as 1/2. If we follow the grey arrow path, whenever we reach a number that is equal to a number we've already seen (in a different form), we'll shade it red and skip over it, so we don't count it more than once. Okay, so by following the grey arrows we can reach every positive rational number, and we don't count any of them more than once.

To add the negative rational numbers, we just do the same trick we did with the integers. And we can add 0 at the beginning to cover that as well. So, take a look at this list:

Naturals    0   1   2   3   4    5     6    7     8   9  10  11  12   13    14   15    16   17    18 ...
Rational    0   1  -1   2  -2  1/2  -1/2  1/3  -1/3   3  -3   4  -4  3/2  -3/2  2/3  -2/3  1/4  -1/4 ...

Because we're following the grey path on the diagram, every single positive rational number is in this list somewhere, and because we follow it with the negative, every negative rational number is there too, and so is 0. In other words, every single rational number is in this list, matched one-for-one with a natural number.

So the collection of natural numbers can be matched one-for-one with the collection of rational numbers. Which means the collections are the same size. Sure, there are an infinite number of rationals, but it's the same infinite number as the infinite number of naturals. Wow.

All right, let's get even more ambitious. How many real numbers are there?

Real numbers can be thought of as any number you can express with decimal notation, with any finite string of digits before the decimal point and any string of digits at all, finite or infinitely long, after the decimal point. All rationals are real numbers, since any fraction can be expressed as a finite or infinitely repeating string of decimal digits. But there are real numbers which aren't rational - numbers such as the square root of 2, or π. These numbers are only expressible as an infinitely long sequence of decimal digits that does not fall into a recurring pattern.

Such numbers are densely packed, like the rationals. Between any two different real numbers, we can always find another real number. For example, between these two real numbers:

0.32984573286498143827395826...
0.32984573286498143827395841...

is the number:

0.32984573286498143827395839...

All you have to do is find the first digit in the decimal expansion where the numbers differ, and you can insert something in between. (Or in cases where they only differ by 1, like 0.3434 and 0.4294 you do the inserting in the next place, like so: 0.3728) So, like the rationals, there are an infinite number of real numbers between 1 and 2, for example.

Okay, so by now you may be thinking that I can pull out some tricky re-ordering of the real numbers to show how you can match them up one-for-one with the naturals, just like I did with the rationals. Well, actually, the guy who first came up with that clever piece of ordering of the rationals was Georg Cantor, a German mathematician of the late 19th century.

real number counting Right then, let's assume we can order the real numbers in such a way that we match them all up one-for-one with the naturals. For now, it doesn't much matter what this particular ordering is, let's just assume we can do it. An example of what such an ordering might look like is shown in the diagram on the right. This time we're listing the numbers down the page: the naturals down the left and the reals down the right, paired up one-for-one. Each real number carries on for an infinite number of decimal places, and both lists of numbers carry on down the page for an infinite number of numbers. Ignore the bit below the line for now; we'll get to that very soon. Let's think about that diagram for a bit.

Notice that some of the digits are red. The first digit after the decimal point in the first real number, the second digit in the second number, the third in the third, and so on. Below the line, I'm going to write down all the red digits, in their respective decimal places. This forms a new number, the number shown below the line in red. So far, so good.

Now I'm going to make a new number, by simply writing down a different digit to the red number in each decimal place. Where the red number has a 2 right after the decimal place, I'm going to write a 7. The next red digit is a 9, I'll write a 4. And so on down the line - I pick a different digit to the red digit immediately above at every decimal place. [There is a tiny extra detail here that I don't want to go into today. If you know what I'm talking about, then rest assured I know about it too. If you don't, then don't worry, it doesn't affect the basic argument.]

This new number I've made, the black one at the bottom, is a real number. It's an infinitely long string of decimal digits, and that's what a real number is. So it's definitely a real number. If it's a real number, it must be somewhere in the (infinitely long) list of all the real numbers that we have above the line. Where is it?

Well, it's not in the first place on the list, since the first digit after the decimal is different to that one. It's not in the second place, since the second digit is different. It's not in the third place, since the third digit is different. And so on. In fact, it's not equal to any of the real numbers in our "list of all the real numbers", because whatever entry in the list we look at, our new number is different in the corresponding decimal place. (It's guaranteed to be different, since that's how we made this new number.)

So we have a real number that is not in our "list of all the real numbers". This cannot possibly be the case, so we've made a mistake somewhere. The mistake we made was in assuming that we could write down this "list of all the real numbers" in a one-for-one pairing with the natural numbers. We've just proved that you can't match the collection of real numbers one-for-one with the collection of natural numbers. It doesn't matter how you try to do such a matching, there will always be real numbers left over that you haven't matched up to a natural.

This is mind-blowing stuff.

We've shown that:

The integers, although they look to be twice as numerous as the naturals, match up one-for-one with the naturals. There are, effectively, the same number of integers as there are natural numbers. You can pack all the integers into the same space as the natural numbers.
The rationals, although they look to be much more numerous than the naturals, also match up one-for-one. There are effectively the same number of rational numbers as there are natural numbers. You can pack all the rationals into the same space as the natural numbers.
The reals, although they don't particularly look all that much more numerous than the rationals, actually cannot possibly be matched one-for-one with the naturals. There are, in a very deep and true sense, more real numbers than rational numbers. You cannot pack all the reals into the same space as the natural numbers.

Georg Cantor also came up with this proof that you can't match up the reals with the naturals. For reasons that should be obvious looking at the diagram and the red digits, it is called Cantor's diagonalisation argument.

And for those Star Wars geeks who have read this far, I'm aware that a dianoga is canonically a squid-like creature, but you only ever see enough of it in the movie to make it look feasibly snake-like. And cut me some slack; I needed it to be more one-dimensional than three-dimensional or the pun wouldn't have worked.

Well, it would have worked even less than it did.

2022-05-07 Rerun commentary: The trash in the compactor includes an upside down desk, on the left in front of Luke. Well, an upside down Lego model that I use to represent a desk in other comics, at least.

I guess the workers on the Death Star have to replace their desks sometimes when they get old.

The "tiny extra detail" that I mention in the above explanation of Cantor's diagonalisation argument... Well, I guess now's as good a time as any to go into it. Actually, it's a great time, since I've since written a thorough explanation of it in the annotation of another comic.

Look at the last diagram above, the one illustrating the diagonalisation argument. The tiny detail occurs if beyond a certain decimal place the red digits are either all 0, or all 9. As we saw in the annotation for comic #3374, decimal strings ending in repetitions of the digit 0 represent the same real number as a decimal string ending in repetitions of the digit 9. In particular, for example: 0.7999... = 0.8000...

So if we end up with a red number that ends with either all zeroes or all nines, we just need to be slightly careful that we don't choose our final black number to be a different representation of the same number that just happens to have no digits in common. But we can do this easily enough just by choosing any other digit than 0 or 9 in one of the critical places, so the argument still stands.