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 than 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 xX. 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: X2^X. Let's show that this assumption leads to a contradiction.

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

If aA={xX: xg(x)} then ag(a)=A. Contradiction.

If ag(a), then obviously, by the definition of A, we have to conclude that aA=g(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.

Self-reference and apparent self-reference

1. Does It Blink?
2. Apparent paradox
3. Set of all subsets
4. An Impossible Page
5. Russell's paradox
6. An Impossible Machine
7. A theorem with an obvious proof

Copyright © 1996-2008 Alexander Bogomolny