Are Some Infinities Bigger Than Others?

Bibek’s first list is of the short decimals, the ones that stop: first the one-digit ones, 0.1, 0.2, …, 0.9, then the two-digit ones, 0.01, 0.02, …, 0.99 (leaving out 0.10, 0.20, …, already there as 0.1, 0.2, …), then the three-digit ones, and so on. Every decimal that stops is somewhere on it: 0.37 is row 43, and 0.31415926 is row 38,274,333.

Beating the 8 rows on the screen is easy. Type 9, and your number already differs from 0.1, 0.2, …, 0.8. But row 9 is 0.9, which starts the same way. Type 0.95, and row 9 is beaten, but row 95 is 0.95. Whatever digits you type, there is a row further down that starts with exactly those digits, so checking row by row can never finish.

Bibek’s second list is of the fractions between 0 and 1, in lowest terms, by their bottom number: 1/2, then 1/3 and 2/3, then 1/4 and 3/4, then 1/5, 2/5, 3/5, 4/5, and so on. Every fraction, such as 3/7 (row 14), is on it. Fractions crowd so thickly that there is one close to any number you type: a fraction starting 0.45555555 is 41/90, at row 2,466.

So checking won’t do. Aarati needs to choose her digits so that she knows her number differs from every row, even row 38,274,333, without looking at it.

Same size means a matching

What does “bigger” mean for collections that never end? You can’t count them to the end, but you can match them: two collections are the same size if their members can be paired off, one with one, with nothing left over on either side. A set that can be matched with the counting numbers 1, 2, 3, … is called countable; matching it with 1, 2, 3, … is the same as writing it as a list in which every member has a row of its own. The even numbers are countable (pair n with 2n), and so are the short decimals and the fractions, as Bibek’s lists show.

No list holds every decimal

Now Aarati’s argument. Suppose someone has a list of the numbers between 0 and 1, any list at all. Here are its first six rows, each going on forever:

Row	The number	Its diagonal digit
1	0.14285714… (1/7)	1
2	0.66666666… (2/3)	6
3	0.31415926…	4
4	0.25000000… (1/4)	0
5	0.55555555… (5/9)	5
6	0.70710678…	6
…	…	…

Build a new number, one digit at a time, by this rule: **if row n’s nth digit is 5, write 4; otherwise write 5.** The diagonal digits 1, 6, 4, 0, 5, 6 give

$$0.555545\ldots$$

and the rule carries on down the list forever. Is this number on the list? It isn’t row 1: they differ in the 1st digit. It isn’t row n, for any n, because they differ in the nth digit. Every row is ruled out in its own place, with no reading of the whole list.

So no list can hold every number between 0 and 1. Whatever list is offered, the diagonal rule builds a number it missed. The numbers between 0 and 1 are uncountable: there are too many of them to match with 1, 2, 3, …. This is Cantor’s diagonal argument, published by Georg Cantor in 1891.

And there are more of them than counting numbers, not just “different”: you can match the counting numbers with some of the decimals (1 with 0.1, 2 with 0.11, 3 with 0.111, …), but never with all of them. That is what “bigger” means for infinite sets: the smaller one matches part of the bigger one, and nothing matches the whole.

A short line and a long line. Does a 10 cm line have more points than a 2 cm line? Place the short line above the long one, and draw a ray from a point O through any point of the short line: it meets the long line in exactly one point, its partner, 5x cm along for a point x cm along. Every point of each line has exactly one partner on the other, so the two lines have the same number of points.

A short line and an endless line. Bend the 1 cm line, without its ends, into a half circle. A ray from the circle’s center through any of its points meets the endless line once: at the middle the partner is 0; at 0.9 cm along, about 9.2; at 0.99 cm, about 95.5; at 0.999 cm, about 955. Every point of the endless line, however far out, has a partner just short of an end. So a line 1 cm long has as many points as a line that never ends.

A square and a line. In 1874 Cantor asked his friend Richard Dedekind whether the points of a square could be matched with the points of a line, expecting no. In 1877 he found it was yes. Here is his first attempt. A point inside a square of side 1 has two coordinates, each written the usual way (not ending in endless 9s), say (0.1234…, 0.5678…). Weave their digits together, one from each in turn:

$$(0.1234\ldots,\ 0.5678\ldots) \longrightarrow 0.15263748\ldots$$

To go back, unweave: the odd-placed digits give the first coordinate and the even-placed ones the second, so 0.31415926… comes from (0.3452…, 0.1196…). Different points of the square give different points of the line.

Cantor wrote to Dedekind in June 1877 that until Dedekind agreed, he could only say je le vois, mais je ne le crois pas: “I see it, but I don’t believe it.” Often quoted as amazement, it was really a request to check his proof.

So are there just two sizes of infinity, the countable and the size of the line? No: there is no biggest one.

Teams from a group

How many teams can be picked from three friends, Asha, Bina and Chiran, counting the empty team and the team of all three? Each friend is in or out, two choices each, so 2 × 2 × 2 = 8: { }, {Asha}, {Bina}, {Chiran}, {Asha, Bina}, {Asha, Chiran}, {Bina, Chiran}, {Asha, Bina, Chiran}. With n people there are 2ⁿ teams, always more than n: 4 people make 16, 10 make 1,024. The collection of all the teams (subsets) of a set is its power set. Cantor’s argument shows there are more teams than members for every set, finite or infinite, without counting at all.

The argument never counted, so it works for any set, even an infinite one: pair each member with a team, and the team of “everyone not in their own team” is left over. This is Cantor’s theorem: every set has more subsets than members. If the rebel team reminds you of the village barber who shaves exactly the men who don’t shave themselves, it should: Can a Sentence Say It Is False? builds the barber from the same diagonal.

A team of counting numbers, like the even numbers or {2, 3, 5}, can be written as an endless string of 0s and 1s, a 1 in place n if n is in it, so these teams can’t be listed either. Then take the teams of those, and so on: each step gives a bigger infinity. There is no biggest infinity.

Cantor gave the sizes names. The size of the counting numbers is written ℵ₀ (aleph-null, after the first letter of the Hebrew alphabet), and the size of the line is 2 to the power ℵ₀, because the line has as many points as there are teams of counting numbers.

The line is bigger than the counting numbers. Is there a set in between: bigger than the counting numbers, smaller than the line? Cantor guessed no, in 1878, and never managed to prove it. His guess is called the continuum hypothesis (the continuum is the line). In 1900 David Hilbert put it first on his famous list of problems for the new century.

The answer, when it came, was stranger than yes or no. In 1940 Kurt Gödel proved that the usual rules (the axioms) on which mathematicians build set theory can never prove that the guess is false, as long as those rules don’t contradict themselves. In 1963 Paul Cohen proved that they can never prove it true either. So, from the axioms nearly all of mathematics rests on, the question cannot be settled at all; Cohen received the Fields Medal for this in 1966. Mathematicians could add a new axiom to decide it either way, and some study what each choice leads to, but there is no agreement on which one to add.

Between any two numbers, however close, there are endless fractions: between 0.3141 and 0.3142 lie 0.31415, 0.314151, …. Fractions are everywhere on the line, yet they are only a countable sliver of it. Here is how thin.

Lay a small cover over each fraction on Bibek’s list: 0.05 long over the first (1/2), 0.025 over the second, and so on, each half the one before. Every fraction gets a cover, and together the covers take up at most

$$0.05 + 0.025 + 0.0125 + \cdots = 0.1,$$

because halves added forever come to the whole (Can You Add Halves Forever and Still Get One?). Every fraction is hidden, and at least nine tenths of the line is bare. Start with 0.0005, and the covers add up to a thousandth.

The covers can be as small as you like, so the fractions take up no length at all: they have measure zero. The bare points, the numbers that are not fractions, are nearly all of the line. Pick a number between 0 and 1 truly at random, and the chance of a fraction is 0.

• Is There Room at a Full Hotel with Endless Rooms? (Grades 6–8) The countable infinities: one guest, an endless bus, endless buses.
• Can a Sentence Say It Is False? The barber and Russell’s paradox: the diagonal turned on sets themselves.
• Can You Square a Circle? π is transcendental; Cantor’s count shows almost every number is.
• Can You Add Halves Forever and Still Get One? (Grades 6–8) The endless sum behind the covers.
• How Long Can a Tiny Machine Run Before It Stops? (Computing, Going Further 9–12) Programs that never stop, and why no program can always tell. (Coming soon.)
• Grade 10, Sets and Optional Math, Grade 10, Continuity: sets and their cardinal numbers, and limits on the number line.