Results 1 to 12 of 12

Math Help - cardinality of finite sets

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    20

    cardinality of finite sets

    Can someone please help me prove this:

    Show that |P(X)| = 2 ^ (|X|) for all finite sets X

    Any help would be greatly appreciated!! Thank you!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by pseudonym View Post
    Can someone please help me prove this:

    Show that |P(X)| = 2 ^ (|X|) for all finite sets X

    Any help would be greatly appreciated!! Thank you!


    Prove it by induction on |X| (hint: if A is any subset of a set \{x_1,\ldots,x_{n-1}\} with n-1 elements, how many subsets of \{x_1,\ldots,x_{n-1},x_n\} can be formed out of it ?)

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by pseudonym View Post
    Can someone please help me prove this:

    Show that |P(X)| = 2 ^ (|X|) for all finite sets X

    Any help would be greatly appreciated!! Thank you!
    Let f(n) denote the number of subsets of \left\{1\cdots,n\right\}. Consider the power set of \left\{1,\cdots,n,n+1\right\}. Partition set into two blocks B_1=\left\{A\in\wp\left(\left\{1,\cdots,n+1\right\  }\right):n+1\in A\right\} and \wp\left(\left\{1,\cdots,n+1\right\}\right)-B_1=B_2. Clearly, we have that \left|B_2\right|=f(n). And, with the exception of \{n+1\} we may (and can) only put \{n+1\} into each of the subsets of in B_1. Thus, we have that f\left(n+1\right)=f(n)+f(n)+1...almost...we double counted one thing (what is it??). So f(n+1)=f(n)+f(n)+1-1=2f(n). Thus, it follows by induction that the recurrence relation f(n+1)=2f(n) has solution f(n)=C\cdot 2^n for some C. Noting though that f(0) is the number of subsets of the empty set we may conclude that f(0)=1=C\cdot 2^0=C. The conclusion follows.


    EDIT: I am sorry tonio. I didn't see your post!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Why so complicated? Just notice that if you want to construct a subset S of X, you have two possibilities for every element of X: either you include it, or you exclude it. So in total you have 2^{|X|} possibilities.

    Another proof : clearly the number of subsets of X is

    {n \choose 1} + {n \choose 2} + \dots + {n \choose n} = (1+1)^n = 2^n
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Bruno J. View Post
    Why so complicated? Just notice that if you want to construct a subset S of X, you have two possibilities for every element of X: either you include it, or you exclude it. So in total you have 2^{|X|} possibilities.

    Another proof : clearly the number of subsets of X is

    {n \choose 1} + {n \choose 2} + \dots + {n \choose n} = (1+1)^n = 2^n
    I feel as though what I said is exactly what you said.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Which of the two proofs is exactly like yours?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Bruno J. View Post
    Which of the two proofs is exactly like yours?
    I didn't mean exactly exactly . I only meant that the first one is the exact point of my proof. I just did it in a slightly different way.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Your proof relies on induction whereas my proof relies on a combinatorial argument... I don't think they're similar at all!
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Bruno J. View Post
    Your proof relies on induction whereas my proof relies on a combinatorial argument... I don't think they're similar at all!
    The induction is merely the formality of it. The point was that if you fix an element in \left\{1,\cdots,n+1\right\} it only has two places to go. I really do think we are saying the exact same thing, just the means of conveyance is different.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    I'm just teasing you at this point.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Bruno J. View Post
    I'm just teasing you at this point.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by Bruno J. View Post
    Why so complicated? Just notice that if you want to construct a subset S of X, you have two possibilities for every element of X: either you include it, or you exclude it. So in total you have 2^{|X|} possibilities.

    Another proof : clearly the number of subsets of X is


    {n \choose 1} + {n \choose 2} + \dots + {n \choose n} = (1+1)^n = 2^n

    The "another proof" is not so unless you first prove that there are \binom{n}{k} subsets with k elements out of a set with n elements, k\le n, and also you forgot the number \binom{n}{0} in the sum and also, and perhaps most important, this another proof relies on "hidden induction": after all, we need to show that's true for all n, just like the formal proof of Newton's binomial theorem is usually, and as far as I am aware uniquely, done by induction.

    Tonio
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Cardinality of Sets and Power Sets
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 8th 2011, 06:26 PM
  2. Replies: 1
    Last Post: November 5th 2009, 07:14 PM
  3. finite cardinality proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 25th 2008, 09:56 PM
  4. Cardinality of sets
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 18th 2007, 04:30 PM
  5. Finite groups of even cardinality
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: February 26th 2006, 11:49 AM

Search Tags


/mathhelpforum @mathhelpforum