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: 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(0)=1[/tex]
    [tex]E(1)=n[/tex]
    [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.)
    .
    .
    .
    [tex]E(n)=1[/tex]

    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

    Mark44

    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

    Hurkyl

    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?
    thanks!
     
  8. Mar 29, 2010 #7

    HallsofIvy

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