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

Step-by-step explanation:

As the hint says, for any function , we can think of the set (which is the set of all those elements of which don't belong to their image). So is made of elements of , and so it belongs to .

Now, this set is NOT the image of any element in , since if there was some such that , then the following would happen:

If , then by definition of the set , , so we're getting that and also , which is a contradiction.

On the other hand, if , then by definition of the set , we would get that , so we're getting that and also , which is a contradiction again.

So in any case, the assumption that this set is the image of some element in leads us to a contradiction, therefore this set is NOT the image of any element in , and so there cannot be a bijection from to , and so the two sets cannot have the same cardinality.

cosine

step-by-step explanation: