BROWSE
ALPHABETICALLY
LEVEL:
Elementary
Advanced
Both
INCLUDE TOPICS:
Basic Math
Algebra
Analysis
Biography
Calculus
Comp Sci
Discrete
Economics
Foundations
Geometry
Graph Thry
History
Number Thry
Physics
Statistics
Topology
Trigonometry
|
|
Cantor’s Theorem
For any set X, the power set of X is cardinally larger than X.
antor’s Theorem tells us that no matter how large a set we may have, we can always consider a set that is yet larger. This is trivial if our set is finite, but not so obvious if the set in question is infinite.
 We consider two sets (and in particular two infinite sets) to be the same size, that is, to have the same cardinality, if we can form a “one-to-one match-up” between the elements of the two sets, with none left over on either side. If we can show that between two infinite sets such a “one-to-one match-up” can never be constructed, then we know that one of the sets must be cardinally greater than the other. (For a full discussion of infinite sets, read the Infinity Minitext.)
To prove his theorem, Cantor used his now famous “diagonalization argument,” which is a proof by contradiction. That is, we assume that there is a largest infinite set, and then demonstrate that there must be one even larger. So, suppose that X is an infinite set, and let us represent it thus:
X = {a, b, c, d, e, . . . }
We use the letters to indicate the elements of the set, and we are supposing that there are an infinite number of these elements. In particular, we are going to assume now that X is the largest size of set that there is – that is, that no other set can be a “bigger infinity.” Now we recall that we can always form the power set of X, denoted by P(X), by forming the set containing all of the subsets of X.
P(X) = { {a }, { a, b }, { b, c, e }, { a, c }, { e }, . . . }
We observe that P(X) is itself a set, of course. And we are keeping in mind that according to our assumption it cannot be larger than X, for we assumed X was as large as a set can get. However, it obviously cannot be smaller than X, since it contains all of the singletons of X, that is, it contains an element of the form { a }, { b }, { c }, ... for each element a, b, c, ... in X. Consequently, these sets must be the same size. That is, we must be able to form a one-to-one match-up between the elements of X and the elements of P(X), with none left over on either side. Such a match-up would look something like this:
Notice that some of the elements of X are matched with subsets that contain them. For example, here the element e is matched with the subset { a, c, e }. Other elements are matched with subsets that do not contain them. For example, here the element a is matched with the subset { c, d }. Consider the set of all the elements of X that are not matched with subsets that contain them. This set, call it F say, is itself a subset of X, so it must appear somewhere in our match-up listing above.
But what could the element of X be that matches with F? It cannot be a member of F, since F was specially constructed to contain only those elements of X which do not match to sets containing them. On the other hand, if the element of X that matches with F is not contained in F then . . . well, then it must be contained in F, again by the definition of F!
This is a contradiction, and the existence of this contradiction shows that no element of X can be matched with this subset. Our match-up cannot be complete. And since we cannot make a one-to-one match-up between X and P(X), and since we already saw that P(X) cannot be smaller than X, the only possible conclusion is that P(X) must be larger than X. This completes the proof of Cantor’s Theorem.
Take a minute to ponder what this means. Cantor’s Theorem shows that given any set, there is another set which is “larger” in the special sense of being a bigger kind of infinity. Hence, there can be no “largest infinity” either! The kinds of infinity are therefore – infinite!
|
|
|