Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Question about the powerset.

  1. Mar 7, 2012 #1
    Im trying to understand this proof by Cantor.
    For every set [itex] X, |X|<|P(x)| [/itex]
    Proof. Let f be a function from X into P(x)
    the set [itex] Y=(x \in X: x \notin f(x) ) [/itex]
    is not in the range of f:
    if [itex] z \in X [/itex] where such that f(z)=Y, then [itex] z \in Y [/itex]
    if and only if [itex] z \notin Y [/itex], a contradiction. Thus f is not
    a function of X onto P(x).
    Hence |P(x)|≠|X|, the function
    f(x)={x} is a one-to-one function of X into P(x) and so
    |X|≤|P(x)|. it follows that
    I dont understand why z cant be in Y and f(z).
    I guess thats because they defined it that way.
    Is it because we want to find a one-to-one function from
    the set to the power set, and because we want it to be one-to-one
    we want to map every x to a unique element in the power set we don't want x to get mapped to itself. Is that the reason. And do we need z to be in Y and f(z) for it to be onto.
  2. jcsd
  3. Mar 7, 2012 #2


    User Avatar
    Science Advisor
    Homework Helper

    but x can't get mapped to itself … x and f(x) are in different spaces
  4. Mar 7, 2012 #3
    so if x got mapped to itself, it wouldn't be onto.
  5. Mar 7, 2012 #4
    We CAN'T map x to itself. Since x is not an element of P(X).
  6. Mar 7, 2012 #5
    The element x is not in P(X).
    P(X) contains the set containing x (that is, it contains {x}), but it does not contain x itself. Remember that the power is the set of subsets of X.
  7. Mar 7, 2012 #6
    this might be a dumb question, but maybe we didn't do a very good job of defining our funtion from the set to the powerset. why cant x be in P(x)
  8. Mar 7, 2012 #7
    The elements of P(X) are subsets, not elements, of X. P(X) contains {x}, but not x itself.
  9. Mar 7, 2012 #8
    A simple example will help you. Take X={1,2,3}, then P(X)=\{∅,{1},{2},{3},{1,2},{2,3},{1,3},{1,2,3}}. As you see, 1 is not an element of P(X). But {1} is an element of P(X).
  10. Mar 7, 2012 #9
    ok thanks for the responses, it makes more sense now.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook