1. Not finding help here? Sign up for a free 30min 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!

Prove of number of subsets of a set

  1. Jul 3, 2015 #1
    1. The problem statement, all variables and given/known data
    A= {a1,.....am}, B= {b1,.....an}. If f: A→B is a function, then f(a1) can take any one of the n values b1,.....bn. Similarly f(a2). Then there are nm such function. I understand this part.

    So in my book, using this principle,
    nC0 + nC1 + ..... + nCn = 2n is proved.

    It has taken a set A= {a1,.....an}. For each subset B of A, there is a function fB : A→ {0,1} given by fB(a1) = 1 if a1 ∈ B and fB(a1) = 0 otherwise. Conversely, for every f: A→ {0,1}, B = {a1 : fB(a1) =1 } ⊂ A anf f = fB. Thus there is a one-to-one correspondense between the subsets of A and the functions f: A→ {0,1}. From the above formula, hence we have
    nC0 + nC1 + ..... + nCn = 2n

    2. Relevant equations


    3. The attempt at a solution The prove given is so short for me to understand anything.
     
  2. jcsd
  3. Jul 3, 2015 #2

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    It may help to take the principle you are applying and restate it using other variables.

    Let D= {d1, ... , dm}, R= {r1, ... , rn}. If f: D→R is a function, then f(d1) can take any one of the n values r1, ... , rn. Similarly for f(d2). Then there are nm such functions.​

    Now apply this to the subset situation.
     
  4. Jul 3, 2015 #3
    Sorry, that is the problem, I am unable to link the subset to the above mentioned situation.
     
  5. Jul 3, 2015 #4

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    What's stopping you? What part don't you understand? Simply saying "I don't get it" isn't very helpful.
     
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: Prove of number of subsets of a set
Loading...