Aubrey asked in Science & MathematicsMathematics · 8 months ago

Is a set equivalent to its power set?

Relevance
• RockIt
Lv 7
8 months ago

No, an example ...

S={}, |S|=0,

P(S)={{}}, |P(S)|=1

• jibz
Lv 6
8 months ago

No. A set S is never equinumerous to its power set P(S). In fact P(S) is strictly larger than S. This is clearly the case when S is finite because |S| < 2^|S| = |P(S)|. NB: though technically used to denote the set of mappings from S to the ordinal 2, the more suggestive 2^S is often used in place of P(S) because the two are in fact isomorphic with respect to subsethood, even when S is infinite. A Cantor's diagonal-style argument shows that

Claim: |S| < |P(S)| for all sets S.

Proof: Ad absurdum, assume there exists a surjection f : S → P(S) witnessing P(S) ≤ S. Consider the following subset of S:

R := {x ∈ S : x ∉ f(x)}.

Since f is surjective and R is an element of P(S), there must exist y ∈ S such that

f(y) = R.

Then either y ∈ R or it isn't. But if y ∈ R then, by definition of R, y ∉ f(y) = R, a contradiction. On the other hand if y ∉ R, then y ∉ f(x) which means that y ∈ R, again a contradiction. Thus the assumption that S could be surjected onto P(S) must be invalid, q.e.d.