Results 1 to 6 of 6

Math Help - Counting Subsets of a Finite Set

  1. #1
    Junior Member mremwo's Avatar
    Joined
    Oct 2010
    From
    Tampa, FL
    Posts
    53

    Counting Subsets of a Finite Set

    Let B be a finite set.
    Set m= |B|.

    Prove that B has 2^m subsets.

    Help?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by mremwo View Post
    Let B be a finite set.
    Set m= |B|.

    Prove that B has 2^m subsets.

    Help?
    There are like forty different ways to do this. Three approaches:

    1) Let [k]=\{1,\cdots,k\}. Show that 2^{[k+1]} can be partitioned into two blocks, the elements of 2^{[k]} and the elements of 2^{[k]} united with \{n+1\}. Conclude that if a_n=\#\left(2^{[n]}\right) then a_{n+1}=2a_n.

    2) Note that \displaystyle \#\left(2^{[n]}\right)=\sum_{k=0}^{n}{n\choose k} (why?)

    3) Show that \#\left(2^{[n]}\right)=\#\left(\{0,1\}^n\right) by showing that f:2^{[n]}\to\{0,1\}^n by mapping E\subseteq[n] to \mathbf{1}_{E} (the indicator function) is a bijection.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Dec 2010
    Posts
    470
    A subset picks elements from B.

    Think about how we form a subset of B. For each element of B, we can either put it in the subset or leave it out.
    So for each element there are 2 possibilities (in the subset / not in the subset)
    There are m elements, this gives 2*2*2*..[m times]...*2 possibilities, or just 2^m possible subsets.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    Irrelevant to the thread: I see you are from Tampa. Do you go to USF? I go to UT.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member mremwo's Avatar
    Joined
    Oct 2010
    From
    Tampa, FL
    Posts
    53
    i actually liked his response. really helped me think about in terms that make sense. any comment that makes me feel stupid for not realizing it before is always helpful. thanks snowtea
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member mremwo's Avatar
    Joined
    Oct 2010
    From
    Tampa, FL
    Posts
    53
    And to answer your question dwsmith, I don't go to school in Florida.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] counting inverses of finite group
    Posted in the Advanced Algebra Forum
    Replies: 8
    Last Post: June 22nd 2011, 10:45 PM
  2. Question on counting finite sets.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 20th 2010, 09:44 PM
  3. Replies: 0
    Last Post: December 11th 2009, 11:00 AM
  4. Is a set the union of its finite subsets?
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 13th 2009, 01:09 PM
  5. Counting ordered k-tuples of subsets...
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 1st 2008, 07:50 PM

Search Tags


/mathhelpforum @mathhelpforum