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_{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 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_{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 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_{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, 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^{2}, 10^{3}, 10^{4}, . . . }, 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).

Each entry in this series contains increasing amounts of win. Love this stuff.

Paradise? If we were to diagram this out Plan of Salvation style, I’d be on the prison half of the orb.

Very interesting. I must say, as more of an applied mathematician, I’m a bit lost on the fascination with infinity beyond the abstractions we’ve made thus far. That is, what does the continuum hypothesis buy us? Can someone with more theoretical math prowess enlighten me?

jmb, this is a problem similar to the classical theological models. The big question surrounding it (continuum hypothesis) was whether you could get away with assuming it is true, or false without impacting the system. It’s a comfortable thing, to assume it I mean. But it induces all sorts of interesting structure if you don’t. Or, at least it can. But I will consider any “physical” impact it might have after dealing with the next three or so posts.

WVS. I’m loving this series. But I’m really scared you are going to go to P(R) and blow my mind.

I’ll do what I can Steve.

I am hoping this series never ends.