1. PF Contest - Win "Conquering the Physics GRE" book! Click Here to Enter
    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!

A proof in Set theory about the number of different subset in a Set

  1. Mar 23, 2010 #1
    hi guys, I am a physics major, recently doing a few self-reading on analysis, however, I got stuck at some excises of proofs.

    1. The problem statement, all variables and given/known data
    If a set A contains n elements, prove that the number of different subsets of A is equal to [itex]2^n[/itex].

    3. The attempt at a solution

    First, I teared apart the problem, attempting to draw a general equation from looking at the numbers of different subset one by one.

    E(m) regarded as the possible number of different subsets which contains m elements, whereas A has total n elements.

    [tex]E(2)=\frac{n^2}{2}-\frac{n}{2}[/tex] (this is obtained from a bit of analysis. Possibly be fault however.)
    [tex]E(3)=\frac{5n^3}{6} -\frac{n^2}{2}-\frac{n}{3}[/tex] (so is it.)

    However, I was almost driven crazy... I could't make the generl equation from it (which is hopefully [itex]2^n[/itex])

    Any other approaches? Or any mistakes I made during my approach?

    Thanks for reading!
  2. jcsd
  3. Mar 23, 2010 #2


    Staff: Mentor

    The formula above is incorrect. It should be (1/6)(n3 - 3n2 + 6n)
    In general, and using your notation, E(m) = the number of combinations of n things taken m at a time, or nCm, which is defined to be n!/(m! (n - m)!).

    For example, if n = 3, there are:
    1 set with nothing in it -- {}
    3 sets with 1 element -- {1}, {2}, {3}
    3 sets with 2 elements -- {1, 2}, {1, 3}, {2, 3}
    1 set with 3 elements -- {1, 2, 3}

    All together there are 1 + 3 + 3 + 1 subsets, or 8 subsets, or 23 subsets.

    By the same reasoning, it's easy to show that for a set with 4 elements, there are 24 subsets. You can use mathematical induction to show what you're trying to show; namely that for a set of n elements, there are 2n subsets.
  4. Mar 27, 2010 #3
    Thanks for answering!
    However, I would love to know how to prove nCm suitable here?
  5. Mar 27, 2010 #4


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    For the record, a direct counting argument is possible without any induction or summation identities -- you just need to find a different way to describe a subset than by first listing its size (say, m), and then by listing m elements.
  6. Mar 29, 2010 #5
    Probably my knowledge in Math induction is not enough.
    I have attempted to prove it via M.I.
    however, I was having some hard time

    my approach:
    1.) obviously it is true for n=1,0
    2.) I assume that it is true for [itex]2^k[/itex], where k belongs to natural set.
    3.) but how do I know/prove it is also true for [itex]2^{k+1}[/itex]? since I can't write such a function at all!
  7. Mar 29, 2010 #6
    besides, I always do not understand how the nCm stuffs have to do with the so-called "possibilities" of combinations?
  8. Mar 29, 2010 #7


    User Avatar
    Science Advisor

    Suppose A contains k+ 1 elements, with k> 0. Let [itex]a_0[/itex] be one of the elements of A. Every subset of A either contains [itex]a_0[/itex] or it does not. If it does not, it is a subset of [itex]A-\{x_0\}[/itex] which has k elements so there are 2^k of them. If it does not, it is the same as a subset of [itex]A- \{x_0\}[/itex] union [itex]x_0[/itex] so there are [itex]2^k[/itex] of them. Together there are [itex]2^k+ 2^k= 2(2^k)= 2^{k+1}[/itex] subsets of A.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook