# 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} that consists of one element subsets of X. Secondly, assume that X and 2^{X} are equivalent, i.e. there exists a 1-1 ^{X}.

It must be noted that for every x ∈ X, ^{X}.^{X} there exists

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

If a ∉ g(a), then obviously, by the definition of A, we have to conclude that

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

- Does It Blink?
- Apparent paradox
- Set of all subsets
- An Impossible Page
- Russell's paradox
- An Impossible Machine
- A theorem with an obvious proof
- The Diagonal Argument
- A link to a very similar puzzle

|Front page| |Contents| |Algebra| |Up|

Copyright © 1996-2018 Alexander Bogomolny

64642281 |