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!

Finding Cardinality of Power Set

  1. May 20, 2014 #1
    1. The problem statement, all variables and given/known data

    Let S be the set of functions from a set A to {0,1} Prove that |P(A)|= |S|

    2. Relevant equations

    P(A) is the power set of A

    3. The attempt at a solution
    I have no idea how to do this... If A is finite then A has n elements, and we can write out the elements from one to n (1,2,3,...,n) in the power set if the element is in the set we can write one for the element. If not we can write zero for it, and thus there are 2n binary strings of length n. We would do the same for S. to show that |S|=2n. Surely, we wouldn't be able to extend this process to any uncountable sets. Maybe it's possible to construct a bijective f from P(A) to S, but I don't see any ways to do this.
     
  2. jcsd
  3. May 21, 2014 #2

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Hint: Picking some elements of A to make a subset B is similar to having a function f on A such that for each a in A, f(a) = 1 if a is to be in B and f(a) = 0 if a isn't in B.
     
  4. May 24, 2014 #3
    Well, could we just define a subset of A by assigning a "0" or "1" to each element aεA? Then the set of all subsets would be the set of all functions from A to {0,1}.
     
  5. May 24, 2014 #4

    verty

    User Avatar
    Homework Helper

    Yes, you certainly could decide that functions are more elementary than subsets. Usually it is the other way around but that is certainly logical. But a more standard thing to do is to show there is a bijection between the two sets, which means their cardinality must be the same.
     
  6. May 24, 2014 #5

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    The assignment of subset X to the function that is 0 if the variable is in X and 1 if x is not in X is a bijection between the subsets of A and the functions from A to {0, 1}
     
  7. May 24, 2014 #6

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    @crownedbishop: You have to show that the map that maps a subset of A to its corresponding function is a bijection. It's easy but you can't just assert it. Show that map is 1-1 and onto.
     
  8. May 25, 2014 #7
    @LCKurtz, I didn't assert that it is just a bijection, but that it is an identity map. Perhaps, this is not the standard definition of a subset, though.
     
  9. May 25, 2014 #8

    verty

    User Avatar
    Homework Helper

    Crownedbishop, you were saying that binary strings can't be extended to the uncountable case, but do you know that you can generate the function directly with a set comprehension? That way, you can work with functions instead of binary strings.

    The one caveat is that you must write it in the correct way to comply with the separation axioms. But anyway, a short verbal proof will surely be adequate.
     
  10. May 25, 2014 #9

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    How can it be an identity map when the domain and range are different? The domain is P(A) and the range is the set of functions from A to {0,1}.
     
  11. May 25, 2014 #10
    The identity map is from P(A) to S.
    Anyways, if we define f(a)= 1 if a[itex]\in[/itex]C and f(a)=0 if a[itex]\notin[/itex]. Then, [itex]\forall[/itex]C[itex]\in[/itex]P(a) and [itex]\forall[/itex]d[itex]\in[/itex]S, we define CRd if f(a)=d(a). Wouldn't it suffice to show that the relation R is a bijective function?
     
  12. May 25, 2014 #11

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    The identity function on a set maps the set to itself. ##P(A)\ne S##. You are wanting to show these two sets have the same cardinality by finding a bijection between them, and it isn't the identity.

    Just so you know, there is a standard name and notation for this function. It is called the characteristic function of a subset and is usually denoted by ##\chi_C## (different subscript for different subset).

    Yes it would. That is what you have to do. But I think you could phrase it more simply by stating that the map ##\eta:P(A)\to S## defined by ##\eta(C) = \chi_C## for ##C\in P(A)## is 1-1 and onto. But my whole point in my replies is that that needs to be done.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Finding Cardinality of Power Set
  1. Power Sets (Replies: 3)

  2. Cardinalities of Sets (Replies: 3)

Loading...