The set of all subsets of a given set is bigger than the set itself

Let there be a set X. Notation 2^X stands for the set of all subsets of X. Two sets X and Y are said to be equivalent or have the same cardinality if there exists between them a 1-1 correspondence. We say that X is bigger than Y if they are not equivalent but there exists a 1-1 correspondence between Y and a subset of X. If X is bigger than Y then Y is smaller than X.

We show that 2^X is bigger than X in two steps. Firstly, let's consider one element subsets of X: {x}, where x ∈ X. Then f(x) = {x} is a 1-1 correspondence of X onto the subset of 2^X that consists of one element subsets of X. Secondly, assume that X and 2^X are equivalent, i.e. there exists a 1-1 g: X → 2^X. Let's show that this assumption leads to a contradiction.

It must be noted that for every x ∈ X, g(x) ∈ 2^X. In other words, g(x) is a subset of X, g(x) ⊂ X. Thus, either x ∈ g(x) or x ∉ g(x). Let's define the set A = {x ∈ X: x ∉ g(x)}. This is a subset of X. Now we have an interesting situation. Since we assumed g is a 1-1 correspondence between X and 2^X there exists a ∈ X such that g(a) = A. It's legitimate to ask whether a ∈ A. Let's check this.

If a ∈ A = {x ∈ X: x ∉ g(x)} then a ∉ g(a) = A. A contradiction.

If a ∉ g(a), then obviously, by the definition of A, we have to conclude that a ∈ A = g(a). A contradiction again.

The only conclusion we may draw is that our original assumption that X and 2^X are equivalent, leads to a contradiction. Hence it's false.

(This proof is often referred to as the diagonal argument and there is a The Diagonal Argument page that explains why.)

Self-reference and apparent self-reference

40612212