P(X) be
such a one-to-one and onto function.2. We shall use a proof by contradiction to show that there cannot be a one-to-one correspondence between a set and its power set. Note that this is quite a tricky proof, so take your time when working through it.
Suppose that there was a one-to-one correspondence between a set X and its power set
P(X), and let f : XP(X) be
such a one-to-one and onto function.
Then for every element x in the set X we have an image f(x) in the set P(X), in other words, f(x) is a subset of X. There are two possibilities for any element x of the set X, either:
f(x) (that is, x is an
element of the set f(x)); orNow define a new set S to be S = {xX | x is not an element of f(x)}. So S is the set of all
elements of X which are not elements of their image under the function f. Note that S is a
subset of X and hence S is an element of the power set of X, P(X). Since f is an
onto function, we know that there must exist at least one element u in the set X, such
that f(u) = S. But where is this element u? Does it belong to the set S?
If u is in the set S, then by the definition of S, u is
not an element of f(u), so u is not in S.
If u is not in the set S, then by definition of S, u is an
element of f(u), so u is in S.
Either way, this leads to a contradiction, so there cannot be a function f which is a one-to-one correspondence between a set X and its power set P(X).