Q:

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 := {ω ∈ Ω : ω /∈ Φ(ω)}.

Accepted Solution

A:
Step-by-step explanation:As the hint says, for any function [tex]f:\Omega\to\mathcal{P}(\Omega)[/tex], we can think of the set [tex] X=\{ \omega\in\Omega : \omega \notin f(\omega)\}[/tex] (which is the set of all those elements of [tex]\Omega[/tex] which don't belong to their image). So [tex]X[/tex] is made of elements of [tex]\Omega[/tex], and so it belongs to [tex]\mathcal{P}(\Omega)[/tex].Now, this set [tex]X[/tex] is NOT the image of any element in [tex] \Omega[/tex], since if there was some [tex]a\in\Omega[/tex] such that [tex]f(a)=X[/tex], then the following would happen:If [tex]a\in X=f(a)[/tex], then by definition of the set [tex]X[/tex], [tex]a\notin f(a)[/tex], so we're getting that [tex]a\in f(a)[/tex] and also [tex] a\notin f(a)[/tex], which is a contradiction.On the other hand, if [tex]a\notin f(a)[/tex], then by definition of the set [tex]X[/tex], we would get that [tex]a\in X=f(a)[/tex], so we're getting that [tex]a\in f(a)[/tex] and also [tex] a\notin f(a)[/tex], which is a contradiction again.So in any case, the assumption that this set [tex]X[/tex] is the image of some element in [tex]\Omega[/tex] leads us to a contradiction, therefore this set [tex]X[/tex] is NOT the image of any element in [tex]\Omega[/tex], and so there cannot be a bijection from [tex]\Omega[/tex] to [tex]\mathcal{P}(\Omega)[/tex], and so the two sets cannot have the same cardinality.