Cantor's theorem

In set theory, Cantor's theorem states that the set which contains all subsets of a set has a greater cardinality (a formal definition of "size") than the set itself. Georg Cantor showed this in an article he published in 1890. The theorem is valid both for finite and infinite sets.

 Proof 
 Definitions 
We will refer to our starting set as  (short for "universe"), and the set of its subsets as  (another name for "set of all subsets of " is "the power set of ").

In set theory, the informal idea of "size" is more formally defined as the cardinality of a set. Two sets have the same cardinality if and only if there is a bijection between the two sets: that is, a relation that connects one element of one set to one element of the other set, with all elements used exactly once (nothing is repeated or left out).

Cantor's theorem is a proof by contradiction: it assumes the existence of a bijection , and then shows that this gives us an impossible result.

 Argument 
The proof of Cantor's theorem is similar to Cantor's diagonal argument.

First, we assume the two sets have the same cardinality, which means there must be a function  and its inverse .

Since this function sends every element  to a subset , we can use it to define a unary relation based on a simple property: "Does the set  contain the value ?"

More formally, we want to look at all the values  where this property does not hold,

This can be read as "the set of all elements of  whose corresponding set in  does not contain that element". This statement is similar to Russell's paradox, which arises from "sets that do not contain themselves" in naive set theory.

Now, we must consider our set . Since  contains only elements of , then by definition  and . This means that there must exist some .

This gives rise to a contradiction:
 If , then , which contradicts the definition of .
 If , then , so by definition  - an explicit contradiction.
From the contradiction, it follows that our premise must be flawed. Thus, no bijection exists between the set  and the set of its subsets , so they must have different cardinality.

Category:Mathematical theorems
Category:Set theory