# 3.6 Cantor's Theorem

## WHICH IS BIGGER?

• Set A is larger than set B if the elements of B can be put into one-to-one correspondence with a subset of the elements of A, but cannot be put into one-to-one correspondence with all of the elements of A.

What, in fact, is meant by the statement that one number is bigger than another number? In terms of cardinalities, this question basically means, "When is one set bigger than another?" Looking at sets of cardinality 5 and 3, for example, we see that:

For simplicity's sake, "3" means "a set of cardinality 3," and "5" means "a set of cardinality 5." So, "3" can be put into one-to-one correspondence with a subset of "5." Also, "3" cannot be put into one-to-one correspondence with all of "5." In other words, there is a one-to-one correspondence between "3" and part of "5," but not between "3" and all of "5." Intuitively, we can see that "5" must be bigger. This idea can be generalized. A set N is bigger than another set M, if:

There is a one-to-one correspondence between M and a subset of N.

AND

There is not a one-to-one correspondence between M and all of N.

We can use these conditions to consider the relationship between and c. Let's choose a set of size , such as the natural numbers. The real numbers will be our set of size c.

Checking for compliance with the first condition given above, we ask if there is a one-to-one correspondence between the natural numbers and a subset of the reals. Well, the set of real numbers includes the set of natural numbers, so the answer is "yes."

To verify that the second condition is also met, that there is not a one-to-one correspondence between the natural numbers and the reals, we can simply appeal to the same diagonal argument we made two sections ago. Recall that the natural numbers were not numerous enough to be put into one-to-one correspondence with the reals between 0 and 1. So, we have established firmly now that c is indeed larger than .

This exercise answers the first question posed at the end of the last section, and in doing so, it gives us a way to determine whether a certain set is bigger than another set. Let's now turn to the second question: could there be a transfinite cardinality larger than c? In other words, is there an infinity bigger than that exhibited by the set of real numbers?

## BEYOND INFINITY

• Given a set of any non-zero size, it is possible to create a larger set by taking the set of subsets of the original.

Suppose we have a set N, consisting of {A,B,C,D}. We can then identify set S as the set of all subsets of N. We can conduct a little mental experiment by asking a friend to write the members of N in a row and then the members of S in another row below the first, like so:

N = A B C D

S = {} {A} {B} {C} {D} {AB} {AC} {AD} {BC} {BD} {CD} {ABC} {ABD} {ACD} {BCD} {ABCD}

Next, we ask the friend to circle four elements of S and to match them up with the elements of N.

We can find an element of S that is not matched up by asking our friend whether an element of set N is matched with a subset that contains it. For example, say that our friend tells us "yes" for A, "no" for B, "no" for C, and "yes" for D. With this information, we can be sure that the subset {BC} has not been matched with any member of N. Because every element of N has been matched with an element of S, and there is at least one "leftover" element of S, we can say that S is definitely larger than N. Note that we did not have to count the members of either set to figure this out.

This strategy works for a finite set, but does it also work for an infinite set? The fact that we did not have to count anything to prove that S is bigger than N is a good sign. Let's see if anything changes if we let N be an infinite set and S be the set of subsets of N.

N={A,B,C,D, ...}

S={ {}, {A}, {AB}, {ABC}, ...}

Let's again attempt to match up every member of N with a member of S. We can ask the "yes or no" questions from before to find out which members of N are paired up with subsets that contain them. Let's say that any members of N for which the answer is "no" go into a new set called W. The set W is then the subset of N containing members that are not paired up with a subset that contains them.

Because W is a subset of N, it must be in S, which is the set of all subsets of N. Can W be matched up with some element of N? Let's say that w, a member of N, is matched up with W.

If w is in W, then it is matched up with a subset that contains it, which by definition means that it cannot be in W; therefore, we have a logical contradiction.

If, on the other hand, w is not in W, then it is not matched up with a subset that contains it, which is the requirement for being a member of W. However, we've already established that w is not in W, so again we have a logical contradiction. Our only viable explanation is to assume that w cannot be matched up with W. This means that there are members of S that cannot be matched with any members of N; consequently, S must be bigger than N. We have now seen that in both the finite and infinite cases, the set of subsets is always larger than the original set.

To return to the cardinalities of infinity, we can create a set larger than or c by taking the set of the subsets. We can clearly keep doing this as long as we please, so we have to conclude that there truly is an infinite number of differentsized infinities! This mind-boggling thought is one of the pure beauties of mathematics. It would be as if, having climbed the highest mountain in the world, one could see that there were peaks of heights previously unimaginable.

With his observations, Cantor spelled out the logical consequences of believing in actual infinity. Such an idea is "beyond human," which is partly why Cantor's ideas received so much criticism. In mathematics, however, there are many occasions to believe in concepts that are "beyond human," such as infinitely long lines in geometry (can anyone check?) or our modern acceptance of infinitely long decimals as numbers. Cantor showed that one can make logical sense out of infinity by thinking in terms of the sizes, or cardinalities, of sets. In doing this, he shored up the foundations of all the mathematical concepts that relied upon infinity. While there is still debate about some of the philosophical underpinnings of infinity in mathematics, most mathematicians do not have to concern themselves with it. This is due, in large part, to the work of Cantor. David Hilbert, one of the truly great mathematicians of Cantor's time, recognized the enormity of his contribution in the immortal thought:

"No one shall expel us from the paradise which Cantor has created."