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: 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


    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


    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted