Question

Given a set Ω, let P(Ω) denote the the power set of Ω, that is P(Ω) is the collection of all subsets of Ω. Prove that Ω and P(Ω) do not have the same cardinality. Hint: Given a function Φ : Ω → P(Ω), consider the set X := {ω ∈ Ω : ω /∈ Φ(ω)}.

Answer 1

Explanation:

As the hint says, for any function
`f:\Omega\to\mathcal{P}(\Omega)`, we can think of the set
`X=\{ \omega\in\Omega : \omega \\otin f(\omega)\}` (which is the set of all those elements of
`\Omega` which don't belong to their image). So
`X` is made of elements of
`\Omega`, and so it belongs to
`\mathcal{P}(\Omega)`.

Now, this set
`X` is NOT the image of any element in
`\Omega`, since if there was some
`a\in\Omega` such that
`f(a)=X`, then the following would happen:

If
`a\in X=f(a)`, then by definition of the set
`X`,
`a\\otin f(a)`, so we're getting that
`a\in f(a)` and also
`a\\otin f(a)`, which is a contradiction.

On the other hand, if
`a\\otin f(a)`, then by definition of the set
`X`, we would get that
`a\in X=f(a)`, so we're getting that
`a\in f(a)` and also
`a\\otin f(a)`, which is a contradiction again.

So in any case, the assumption that this set
`X` is the image of some element in
`\Omega` leads us to a contradiction, therefore this set
`X` is NOT the image of any element in
`\Omega`, and so there cannot be a bijection from
`\Omega` to
`\mathcal{P}(\Omega)`, and so the two sets cannot have the same cardinality.