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.)