What it means to list a set
The whole numbers never end, yet they can be put in a list: 0, 1, 2, 3, 4 and so on. The list is endless, but every whole number appears in it at some numbered place. The number 1000 is at place 1001, and no whole number is left out.
That is what listing an endless set means here: a first member, a second, a third, and so on, so that every member of the set turns up at some place in the list, however far along.
The whole numbers in order along a line. Walking along it one step at a time reaches every one of them.
Endless sets that can be listed
The even numbers can be listed: 2, 4, 6, 8 and so on, with 2n at place n. That pairs every even number with exactly one whole number, so there are as many even numbers as whole numbers, even though the even numbers are only part of them. In the same way the odd numbers, the square numbers, the prime numbers and the multiples of ten can all be listed in increasing order.
Each place in the list is paired with one even number, place n with 2n, and every even number has a place.
Going back and forth
The integers run endlessly in both directions, so listing them from the smallest is impossible: there is no smallest. Go back and forth instead: 0, 1, −1, 2, −2, 3, −3 and so on. Every integer appears; −50 is at place 101.
The integers listed by hopping back and forth across 0: 0, 1, −1, 2, −2, 3. Each hop reaches one number further out, so no integer is skipped.
Even the fractions
The positive fractions seem far too many: between any two of them there are more. Yet they can be listed too. Arrange them in a table with the numerator down the side and the denominator across the top, and go through the table one diagonal at a time. Along each diagonal the numerator and denominator have the same sum, so each diagonal holds only a few fractions.
The list begins ; , ; , ; , , , , skipping because it is again. Every fraction is on the diagonal where the sum is p + q, so it is reached.
The fractions with p and q from 1 to 4. The shaded diagonal, , , and , is where p + q = 5. Taking the diagonals in turn lists every positive fraction.
Suppose the decimals are listed
Now try the decimals between 0 and 1. Each one has an endless string of digits after the point: 0.5 is 0.50000…, and is 0.33333… with 3s forever. Suppose someone claims a complete list of them. Its first rows might be 0.41592…, 0.27182…, 0.33333…, 0.50000… and 0.14142…, each going on forever.
Write the list as a table, one row for each decimal and one column for each decimal place. Read down the diagonal: the 1st digit of row 1 is 4, the 2nd digit of row 2 is 7, the 3rd digit of row 3 is 3, the 4th digit of row 4 is 0, and the 5th digit of row 5 is 2.
The first five rows of the claimed list, five decimal places each. The shaded digits run down the diagonal: 4, 7, 3, 0, 2.
Change every diagonal digit
Build a new decimal one digit at a time, changing each diagonal digit. Add 1 to it, except that an 8 or a 9 becomes 1. The diagonal 4, 7, 3, 0, 2 becomes 5, 8, 4, 1, 3, so the new decimal starts 0.58413 and goes on in the same way.
It cannot be row 1, because its 1st digit is 5 and row 1 has 4 there. It cannot be row 2, because its 2nd digit is 8 and row 2 has 7. In general it differs from row n in the nth decimal place, whatever n is. So it is on no row at all, and the list has missed it.
Adding the missed decimal to the list does not help. The new list has its own diagonal, and changing that diagonal gives another decimal it misses. Every possible list misses some decimal, so the decimals between 0 and 1 cannot be listed.
Why the rule avoids 0 and 9
Some numbers have two decimal forms: 0.5000… and 0.4999… are the same number, one half. If the new decimal ended in endless 0s or endless 9s, it might be a number already listed in its other form. The rule only ever writes digits from 1 to 8, so the new decimal has one form, and it really is a number missing from the list.
Two sizes of infinity
A set that can be listed is called countable, and a set that is endless but cannot be listed is called uncountable. The whole numbers, the integers and the fractions are countable. The decimals between 0 and 1 are uncountable, and so are the decimals between 3 and 4, all the decimals on the number line, and the points a dart could hit on a line from 0 to 1.
So the decimals are a strictly bigger infinity than the whole numbers. Georg Cantor published this argument in 1891.
The usual mistakes
Thinking that endless means it cannot be listed. The whole numbers are endless and can be listed, one after another.
Thinking a part must be smaller. The even numbers are part of the whole numbers, yet they pair off with them exactly.
Applying the diagonal argument to a set that can be listed. For the whole numbers, the changed diagonal has endless digits that never become 0, so it is not a whole number, and the list has missed nothing.
Changing only some diagonal digits. The new decimal must differ from every row, so every diagonal digit is changed.