Question

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. :-(

Answer 1

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