Results 1 to 3 of 3

Math Help - Induction proof: Cardinality of power sets

  1. #1
    Newbie
    Joined
    May 2009
    Posts
    6

    Induction proof: Cardinality of power sets

    I am trying to prove the following by induction:

    The cardinality of the power set of a set with n elements has 2^n elements


    Is there a property that says that the cardinality of a power set with x+1 elements is twice the cardinality of a set with x elements? Or how would I prove that this is the case?

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,959
    Thanks
    1783
    Awards
    1
    Quote Originally Posted by economanc View Post
    The cardinality of the power set of a set with n elements has 2^n elements
    Is there a property that says that the cardinality of a power set with x+1 elements is twice the cardinality of a set with x elements? Or how would I prove that this is the case?
    Well just think about it.
    If \mathcal{P}\left( {\left\{ {1,2,3, \cdots n} \right\}} \right) has 2^n elements then \mathcal{P}\left( {\left\{ {1,2,3, \cdots n,n+1} \right\}} \right)
    would have the same subsets as the former plus each one of those united with \{n+1\}.
    That does double the count.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2009
    Posts
    6
    Fair enough, I just wasn't sure if doing it that way would be "rigorous" enough of a proof. It does make sense however.

    Thanks again!
    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. Proof of Union of Power Sets
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: February 24th 2010, 11:26 PM
  3. Power sets and cardinality
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 28th 2009, 01:49 PM
  4. Induction with power sets
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: April 28th 2008, 08:17 AM
  5. Power Sets Proof
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: September 20th 2007, 01:41 PM

Search Tags


/mathhelpforum @mathhelpforum