16 | July | 2009 | Not About Apples

Counting to Infinity (Part II)

16 July 2009

In the previous article in the series, we looked at what it means for a set to be infinite. We mostly looked at countable sets, sets whose elements can be “listed”. This time we set our sights higher, and look at even bigger sets, the uncountable sets that have too many elements to list.

Bounded Intervals

We have seen one uncountable set so far — the set of all real numbers between o and 1, usually written $[0,1]$ . The set of all real numbers is usually written $\mathbb{R}$ . We know $\mathbb{R}$ is uncountable, since it contains the interval $[0,1]$ , but it is the same size? In other words there are at least as many real numbers as there real numbers between 0 and 1, but it is true that there are more real numbers than real numbers between 0 and 1?

We’ll start with an easier question. The notation $[a,b]$ means the interval of all real numbers that are at least $a$ and at most $b$ .

$[a,b] = \{x : a\leq x\leq b\}$

Can we compare the intervals $[a,b]$ and $[c,d]$ ? Geometrically, these are line segments on the number line; the former has length $b-a$ and the latter has length $d-c$ . If one of the lines is much longer, we might expect it to be larger as a set.

However, the relation $y=\frac{c}{a}x+\frac{d-c}{b-a}$ gives abijection between points $x$ in the interval $[a,b]$ and points $y$ the interval $[c,d]$ . (Don’t be intimidated by the algebra notation — the correspondence just matches the left endpoint of one interval to the left interval of the other and rescales so that the right endpoints match up.)

So every interval is the same size (in the set -counting sense), no matter how long it is. (Geometric length and set size are fundamentally different ways of measuring.)

Then it’s probably not unexpected that it doesn’t matter whether or not we include the endpoints of the various intervals involved. So all the different types of bounded intervals.

$[a,b] = \{x : a\leq x\leq b\}$

$[a,b) = \{x : a\leq x< b\}$

$(a,b] = \{x : a< x\leq b\}$

$(a,b) = \{x : a< x< b\}$

are the same size as sets, no matter what numbers are used.

Lines and Squares

Now lets try to find a set that really is larger than an interval. Lines are one-dimensional, so a good guess is something two-dimensional. How does the number of points in a line segment compare to the number of points in a square.

The points on a square can be represented by pairs of numbers in a certain range. So it will be enough to know the following (counter-intuitive) fact.

Theorem. The set of all numbers $0\leq x <1$ is the same size as the set of pairs of numbers $0\leq x,y<1$ .

Proof. Starting with a number $x$ , write it is a decimal expansion $x= 0.a_1a_2a_3a_4\cdots a_n\cdots$ . If $x$ has two decimal expansions, use the one that ends in all zeroes, not the one that ends in all nines. Then cluster the digits so that each 9 or group of 9s is attached to the following digit. So, if a number began

$0.23950939934929993\cdots$ ,

I would think of it as

$0.(2)(3)(95)(0)(93)(993)(4)(92)(9993)\cdots.$

Then form a pair of numbers by taking alternate clusters. Hard to verbalize, easy to do:

$0.2959349993\cdots$

$0.3099392\cdots$

This associates to each number in the range a pair of numbers in the range. It turns out that every pair of numbers shows up in this way exactly once. This is a one-to-one correspondence.

If you’re wondering why I do that strange trick with the clustering digits instead of just alternating digits, it has to do with avoiding that technicality I mentioned in the previous article, so that numbers with two decimal expansions still only show up once.

We can repeat this trick to see that line segements, squares, and cubes are all the same size as sets. Since we know that a bounded line segment has the same number of points as $\mathbb{R}$ , it’s probably not any more surprising that it already was when I tell you that an entire plane and all of three-dimensional space each has the same number of points as $[0,1]$ .

But wait a minute. It seems intuitively clear that a line segment and a square are not the same size. You could “stack” millions and millions and millions of line segments inside a square without making any progress toward filling the square up. Put another way, a square has an area. A square which is 1 unit on a side has area 1, while a line segment which is 1 unit long has area 0. How can we reconcile this with what we just said? Stay tuned, friends…we will answer this question in a future article.

…and beyond. Way beyond.

So far we have found infinite sets of two different sizes. We have all the countably infinite sets, as well as the set of real numbers (or equivalently the set of points in a line segment or square), which is larger. Are there more possible sizes? Can we list all the possible sizes of sets? Is there a largest infinite number (because if there is, it’s sets of that size we should really call infinite)?

Questions like this get deep and philosophical in a hurry, so for now I’ll settle for showing you why there is no largest infinite set.

This theorem is due to Georg Cantor, who is in fact responsible for all the essential concepts in this article. My style of presentation is no doubt influenced by many writers, not least of whom is Raymond Smullyan. A very clever alternate presentation can be found in the outstanding book The Heart of Mathematics by Berger and Starbird.

To progress, we need the notion of the power set. If $A$ is any set, then $P(A)$ is the collection of all the subsets of $A$ . So if $A=\{a,b,c\}$ , then $P(A) = \{\{a,b,c\},\{a,b\},\{a,c\}.\{b,c\},\{a\},\{b\},\{c\},\{\} \}$ . In this case the original set has 3 elements while its power set has 8.

Theorem. No matter what set $A$ is, $P(A)$ is a strictly larger set.

This is pretty obvious for finite sets. If a set has $n$ elements, it’s not hard to show that its power set has $2^n$ (think about why). This is “yardstick” thinking, though, and it won’t do us much out here in the realms of infinity. Remember that the set of pairs of integers was no bigger than the set of integers. So intuition can be misleading. But here is a reason.

Proof. Let $A$ be any set, and consider its power set $P(A)$ . It should be apparent that $A$ is not bigger than its power set (but think about why if it is not clear). So the only issue is whether it is possible that there could be a bijection between a set and its power set.

Suppose that $A$ is a set which can be placed in a one-to-one correspondence with $P(A)$ . Then we can take every subset of $A$ and label it with an element of $A$ . Every element is used as a label once and once only, and every subset of $A$ is labelled. Now, for an particular element of $A$ , it may belong to the subset it labels, or then again it may not. Call an element of $A$ good if it so happens to belong to the set it labels, and bad otherwise. Then we can split $A$ up into two pieces — $G$ , the set of good elements, and $B$ , the set of bad elements.

We know that $B$ has a label, which we shall call $x$ . Now $x$ can’t be good, because if it were, it would have to be in the set it labels, $B$ , but only bad elements are in there. Likewise $x$ cannot be bad — if it were bad it would belong to $B$ , and since it belongs to the set it labels, it cannot be bad. This is impossible.

The conclusion is that $A$ cannot possibly be put in one-to-one correspondence with $P(A)$ .

In particular, there are more sets of integers than there are integers. It turns out, actually, that there are the same number of sets of integers as there are real numbers.

So there is no such thing as an “ultimate” infinity. Given any set we can describe, however incomprehensibly huge, we can describe another set which is strictly bigger. If we start with any infinite set (such as the smallest infinite set, $\mathbb{Z}$ ), we can build a tower of progressively larger infinite sets.