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? Think about what it would mean if the element u did belong to the set S and then think about what it would mean if the element u did not belong to the set S.