Proof that the #|P(A)|# (Power Set) is bigger than #|A|#?

This for A such that #|A|>= aleph_0#

I searched a proof but i didn't found. :-(

1 Answer
Feb 8, 2018

Please see below.

Explanation:

The usual method is to show that a function #f:ArarrP(A)# cannot be onto (surjective). (So it cannot be bijective.)

For any function #f:ArarrP(A)# , there is a subset of #A# defined by

#R = {x in A|x !in f(x)}#

Now we show that #R# is not in the image of #A#.

If #r in A# with #f(r) = R#, then #color(red)(r in R " and "r !in R# which is not possible, so there is no #r in A# with #f(r) = R#.

Consequently #f# is not onto (surjective).

To see #color(red)(r in R " and "r !in R# , notice that

#r in R rArr r in f(r) rArr r !in R# so #r in R rArr (r in R" and r !in R)#
and
#r !in R rArr r !in f(r) rArr r in R# so #r !in R rArr (r !in R" and r in R)#

We conclude that there is no #r in A# with #f(r) = R#.

Using a similar argument we could instead show that a function #f:P(A)rarrA# cannot be one-to-one (injective). (So it cannot be bijective.)