# The Infinite, part 3. Parsing infinity – ever larger

January 15, 2010 Leave a comment

Last time we observed that in some sense, one can count infinite collections. However, so far, they were all the same size.[1] Our goal this time is to show that counting infinite collections is actually interesting: not everything infinite is the size of N.[2]

There are two main ideas we want to get at here. First, there are collections larger than N, and second, there are collections *much* larger than N. [grin] We begin with the notion of decimal expansion. Anyone familiar in the least with arithmetic has run on to the idea that every number, say like 1/3 or π (= the ratio of the circumference of a circle to its diameter) is expressible as an “unending” (ahhh) decimal expansion:

1/3 = .333333 . . .

π = 3.14159 . . .

Some such expansions might end with a string of zeros:

.3450000000000. . .

So it is not beyond the pale to consider all possible decimal expansions – anything of the sort

.d_{1}d_{2}d_{3}d_{4} . . .

where d_{1}, d_{2}, d_{3}, etc. are digits between 0 and 9. Clearly, any such decimal is between 0 and 1. Is the collection of all such numbers, represented by such decimal expansions, the same size as N? There are certainly infinitely many. In other words to use the terminology from the last post’s footnote, is the size of this collection of decimal expansions א_{o}? A clever argument by Georg Cantor can be used to show that this collection of decimals between 0 and 1 is actually larger than N. We shall employ the law of excluded middle (from post 1 in this series). We begin by supposing that in fact N and the said set of decimal expansions are the same size. That is, that there exists some correspondence between the two which we indicate abstractly as:

1 <-> .d_{11}d_{12}d_{13} . . .

2 <-> .d_{21}d_{22}d_{23} . . .

3 <-> .d_{31}d_{32}d_{33} . . .

4 <-> .d_{41}d_{42}d_{43} . . .

5 <-> .d_{51}d_{52}d_{53} . . .

.

.

.

etc.

Cantor showed that correspondence can’t work, by showing that some decimal expansion must be missing from the list on the right. Hence the assumption that there exists such a correspondence entails it’s own non-existence. A paradox that forces us to relinquish this assumption. So, no such correspondence exists. It will settle in if you give it a moment. (Observe that we used the law of excluded middle.)

So how does Cantor show that there is something missing from the list on the right? He constructs an expansion which is guaranteed to be different from each member of the list by

the following recipe: the new decimal looks like this:

.d_{11}±1d_{22}±1d_{33}±1d_{44}±1 . . .

In other words, Cantor runs down the list, adjusting the first digit by 1 from the first expansion, the second digit by 1 from the 2nd expansion, and so on (Wittgenstein beware).

This new decimal can’t match anything in the list! Therefore it was missing. Hence there was no correspondence with N. None can exist.

Since this set of decimal expansions is not the same size as N, is it larger or smaller? A natural question. A natural answer would result from observing a smaller collection of decimals which *is* the same size as N. That would make our collection of numbers between 0 and 1, larger than N.

Such a smaller collection of decimal expansions would be

.100000 . . .

.1100000 . . .

.11100000 . . .

.111100000 . . .

.

.

.

etc.

So we have an infinite collection, which is *larger* than N. Perhaps the shocking thing here is that *infinity* apparently is not an indivisible concept. It has texture. Just how rich a texture may be seen in part from another result of Cantor:

Cantor’s Theorem. If A is any set, then P(A), the “power set” of A, is larger than A.

The power set of A is the set consisting of all possible subsets of A. For the relevant ideas, and a proof of Cantor’s theorem (which is not complicated), you can click here.

P(N) is larger than N. What is the next largest infinity after א_{o}? We could call it א_{l}. A question of long standing was: how large is the decimal expansion set. It’s larger than N, but what relation does it have to א_{l}? The answer is (with some technical provisos) that it’s impossible to say. The longstanding assumption was that the decimal expansion set was the same size as P(N) whose size would be א_{l}). Known as the “continuum hypothesis,” the question took many years for resolution.[3]

Finally, we can now generate a string of infinite sets, each truly larger than its predecessor: N, P(N), P(P(N)), P(P(P(N))), . . . . Is that all there is? Nope. Things can get much worse. 😉

Next, recap and trouble in paradise.

————-

[1] Ok, we only have two examples of infinite sets the size of N. N itself, and {5, 10, 15, 20 . . .}. But others come to mind: the odd numbers {1, 3, 5, 7, 9, . . . } for example. The even numbers. The numbers divisible by 20. The set {10, 10^{2}, 10^{3}, 10^{4}, . . . }, etc., etc.

[2] It is true however, that N is in some sense the *smallest* infinite set. More precisely, it has the smallest size. Go any smaller, and you’re good old mundane finite.

[3] For an excellent but also rigorous account of the situation, see Paul J. Cohen, *Set Theory and the Continuum Hypothesis.* (New York: Benjamin, 1966).

## Recent Comments