Is a set equivalent to its power set?

2 Answers

Relevance
  • RockIt
    Lv 7
    2 months ago

    No, an example ...

    S={}, |S|=0,

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

  • jibz
    Lv 6
    2 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.

Still have questions? Get your answers by asking now.