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

Homework Help: Please help me understand a set theory proof.

  1. Aug 7, 2010 #1
    1. The problem statement, all variables and given/known data

    Let A be a set and let P(A) denote the set of all subsets of A. Prove that A and P(A) do not have the same cardinality

    2. Relevant equations

    The authors proof is as follows:

    Suppose there is a bijection f:A -> P(A). Let B= {x[tex]\in[/tex] A| x [tex]\notin[/tex] f(x)}. There is a y [tex]\in[/tex] A such that f(y)= B, since f is onto. If y [tex]\in[/tex] B, then by definition of B we conclude that y[tex]\notin[/tex] B. Similarly, if y [tex]\notin[/tex] B, then we conclude y [tex]\in[/tex] B. In either case we get a contraditon, therefore, no such function exist.

    This proof probably make a lot of sense but I can't understand it. Why define a set B that only consist of elements of A but is not elements of f(x)? Isn't f(x) supposed to be all subsets of x, which means f(x) contains x and the subsets of x? How can the set B even exist ? I'm completely lost.

    3. The attempt at a solution

    Am not sure why the author provides the proof he does and I am having a hard time understanding it. But if I were to attempt it I would have given a counterexample. I know that cardinality is another word for number of elements when we are talking about finte sets.

    If i formed a set A= { 1,2} I know that P(A) has subsets [tex]\oslash[/tex],{1},{2},{1,2}

    Clearly they do not have the same cardinality. I am not sure if this is enough to prove the proposed statement partly because I didn't even talk about infinite sets. What do you guys think ?
  2. jcsd
  3. Aug 7, 2010 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member


    Since f is a function from A to P(A), f(x) must be an element of P(A). Equivalently, f(x) is a subset of A.

    A priori, f(x) has no interesting properties whatsoever; it's just the result of a function applied to a value.
  4. Aug 7, 2010 #3

    Okay, thanks for the clearification. But I still have a problem understading f(x). I believe it is an element of P(A) but what is its "value" ?

    Suppose I have A= {1,2}

    1 is an elements of A
    f(1) = ? what does this even mean ?

    Something about this is unsettling to me. From what I understand f is a mapping of a set to another set; why should it even work on elements of a set and not on sets themselves?

    f( {1}) = {[tex]\oslash[/tex], {1}} , would make sense to me .

    Can you explain a bit more, please ?
  5. Aug 7, 2010 #4
    Well, there is no explicit definition given for the function, f, so it would be impossible to tell you any value. All you know is that f is a bijection, which is surjective (onto) and injective (one-to-one), and its domain and co-domain.
  6. Aug 7, 2010 #5
    f is some bijection from A to P(A). i.e., for each element [tex]a \in A, [/tex] we have the element [tex] f(a) \in P(A). [/tex].

    There's no one correct answer, because the mapping f has not been fully defined. Right now, we're just supposing there is SOME bijection f. But if it would make things clearer to you, consider the following mapping:

    [tex] f: x \mapsto \left\{ x \right\} [/tex]

    So [tex] f(1) = \left\{ 1 \right\} [/tex] and [tex] f(2) = \left\{ 2 \right\}. [/tex]

    EDIT#2: I was right the first time:
    No, that does not make sense. The domain of f is the elements of A and the range of f is the elements of P(A). The type of elements of A is different than the type of elements of P(A). Do you understand?
    Last edited: Aug 7, 2010
  7. Aug 7, 2010 #6
    Okay if that is the case in the proof the author says :
    My problem is I don't understand what's going on with the set B.

    The elements of B are elements of A but are not elements of f(x). What does an element of f(x) even look like ?
  8. Aug 7, 2010 #7
    f(x) takes an element from A and does SOMETHING to make into an element of P(A). Elements of P(A) are all subsets of A, so it looks like a subset of A.

    EDIT: And, the elements of B are not elements of A. It takes its input from each member of A.
  9. Aug 7, 2010 #8
    I understand this.

    I understand there is a difference, ofcourse there is. I mean A has elements like 1,2 etc but P(A) has sets as elements.
  10. Aug 7, 2010 #9
    Like I said, the range of f is P(A). P(A) is the set of SUBSETS of A, i.e., the elements of P(A) are sets themselves. Thus, the elements of f(x) are sets themselves.

    e.g., Let A = {1 , 2}. Then P(A) = { {}, {1}, {2}, {1, 2} }.
  11. Aug 7, 2010 #10
    The point is that [tex] B \subseteq A [/tex]. Thus, we have by definition: [tex] B \in P(A). [/tex] This guarantees us a y such that f(y) = B.

    No, f(x) is simply some subset of A. It doesn't have to contain x. The point is that there aren't "enough" x in order for us to "count" all the subsets of A.

    If we assume that f is a bijection, then B cannot exist. This is exactly why we have a contradiction, i.e., we realize f cannot be a bijection.
  12. Aug 7, 2010 #11
    Great, that makes sense!

    So B= {x[tex]\in[/tex] A| x [tex]\notin[/tex] f(x)} has elements of A but x is not an element of f(x).

    What does this mean ? Does this mean we get x from A but x is not in P(A) ? This make sense the elements are of different types.
  13. Aug 7, 2010 #12
    Nice, this makes sense.

    So basically f since f is onto we have f(y) = B if y is an element of A. I got the contradiction part of the argument but I don't see the point that "there aren't "enough" x in order for us to "count" all the subsets of A."

    Basically B does not exist.
  14. Aug 7, 2010 #13
    It means that for all x such that x is a member of A, you take the elements not in f(x).

    EDIT: Actually, is that a typo? x can't be a member of A and not a member of f(x) because the set's elements are completely different.
    Last edited: Aug 7, 2010
  15. Aug 7, 2010 #14
    Okay I just tried to piece eveything together and I think I understand now. By following the assumption that f is a bijection and the definition of B we get that B[tex]\subset[/tex] A
    and B [tex]\in[/tex] P(A). Therefore, since f(y) = B, if y [tex]\in[/tex] B then y [tex]\in[/tex] f(y) which is a contradiction . Therefore, B does not exist if f is a bijection. So our assumption must be wrong.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook