The Infinite. Part 7. Paradise.

[All parts may be found here.]
Last time, I briefly introduced you to Georg Cantor (1845-1918), a Russian-born Jewish Christian who became a well-known and in some quarters infamous, mathematician. Cantor systematized much of what perviously was just mystical respect for the infinite.

In the previous post, we encountered, courtesy of Galileo, the idea of “counting” infinite collections. Collections that can be “counted” are called denumerable or merely countable. Examples of infinite denumerable collections possibly include the number of electrons in the universe,[1] and definitely include things like (all!) the odd numbers: {1, 3, 5, 7, 9, 11, . . . }.

However, so far, they were all the same size.[2] Our goal this time is to show that counting infinite collections is actually interesting: not everything infinite is the size of N.[3]

There are two ideas I want to get at here. First, there are collections larger than N, that is, there are nondenumberable collections, 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 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₁d₂d₃d₄ . . .
where d₁, d₂, d₃, etc. are digits between 0 and 9. Clearly, any such decimal represents a number 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 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₁₁d₁₂d₁₃ . . .
2 <-> .d₂₁d₂₂d₂₃ . . .
3 <-> .d₃₁d₃₂d₃₃ . . .
4 <-> .d₄₁d₄₂d₄₃ . . .
5 <-> .d₅₁d₅₂d₅₃ . . .
.
.
.
etc.

Cantor showed no such correspondence can work, by showing that some decimal expansion must always 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 the assertion that the numbers betwixt 0 and 1 are denumerable. It will settle in if you give it a moment. (Observe that we did use 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 in the list by the following recipe: the new decimal looks like this:

.d₁₁±1d₂₂±1d₃₃±1d₄₄±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, the numbers between 0 and 1, which is *larger* than N.

Perhaps the shocking thing here is that *infinity* 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 difficult), 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.[4]

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, trouble in paradise. (Part eight is here.)

————-
[1] By universe, I don’t just mean the observable universe.

[2] 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², 10³, 10⁴, . . . }, etc., etc.

[3] 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. The idea will be important in theological matters to come.

[4] For a brief but rigorous account of the situation, see Paul J. Cohen, Set Theory and the Continuum Hypothesis. (New York: Benjamin, 1966).