1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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