« previous section  « next section 


9.6  Cantor's theorem


From what was said in the previous section one can deduce that the only infinite cardinal numbers are alef0 and c. Most surprisingly, it is not so. The set of cardinal numbers greater than c is infinite. This fact follows from the following fundamental theorem proved by George Cantor.

Theorem 9.6.1

For every set X,  |X| < |2X|.

Proof.

If X is an empty set then the theorem is obviously true (|X|= 0 and |2 X| =1, see lecture 1).

Because we may construct a function g(x) = {x} which transforms the set X into P(X), namely into the family of one-element sets {{x}: x ∈ X}, then, of course, |X| ≤ |2X|.

Thus, it is enough to show that no subset of the set X is equipotent with 2X. Suppose for a contradiction that for some A ⊆ X there exists a bijection f : A → 2 X. Thus, for every a ∈ A, f(a) ⊆ X. Let Z = {a ∈ A : a ∉ f(a)}. Of course Z ⊆ X. Because the function f is a bijection onto the set of all subsets of X, then for some a0 ∈ A, f(a0) = Z. Let's consider two disjoint cases: the first case a0 ∈ Z, the second case a0 ∉ Z.

In the first case, from the assumption a0 ∈ Z and from the definition of  Z, we obtain a0 ∉ f(a0), that is a0 ∉ Z. Contradiction.

In the second case, if a0 ∉ Z then a0 ∉ f(a0), as f(a0) = Z. Hence, according to the definition of the set Z, we obtain a0 ∈ Z. Contradiction.

Because both cases lead to a contradiction, therefore, the set Z cannot be ever constructed. In consequence, there is no set A or function f which is bijection from the set A onto the set 2 X. ♦

Remark The method used in the proof of the theorem 9.6.1 is known as  “diagonalization argument”.

Cantor’s Theorem tells us that no matter how large a set we may have, we can always consider a set that is yet larger. Thus, it gives us the method for building infinite sets of different cardinal numbers.

All sets

have pairwise different powers. In particular, it follows that |N| < |2N|.

Another consequence of the Cantor's theorem is that the notion of the set of all sets is an inconsistent (we have studied this problem in the lecture 1.6).  Suppose for a contradiction, that such a set,  denoted here by X exists. Then for an arbitrary set A, the set of all subsets of set A is a subset of X, that is P(A) ⊆ X. In particular, P(X) ⊆ X. Therefore, |P(X)| ≤ |X|, but this  contradicts  the Cantor's theorem.


« previous section  « next section