Results 1 to 3 of 3

Math Help - inductive proof of size of power sets

  1. #1
    Newbie
    Joined
    Jul 2007
    Posts
    6

    inductive proof of size of power sets

    hi everybody,

    i have written an inductive proof of the statement that for any set S

     | \wp(S) | = 2 ^ {|S|}

    I am using my own notation for denoting set union with a disjoint set of cardinality 1, because it is such a convenience. is there some standard way of doing this? any tips/corrections, mathematical, stylistic, or notational will be highly appreciated.

    Let \psi(S) = |\wp(S)|

    and let

    S + 1

    denote S \cup T where T is some set disjoint from S and where |T| = 1, so that we can write

    | S + 1| = |S| + 1

    The following holds trivially for S = \emptyset and we will assume it to hold for any arbitrary set S as well

    [\frac{\psi(S + 1)}{2} = 2 ^ {|S|}] \wedge [\psi(S) = 2 ^ {|S|}]

    thus the following also holds for any S

    \psi(S) = 2 ^ {|S|}

    we take as our inductive hypothesis that

    [\psi(S) = 2 ^ {|S|}] \rightarrow [\psi(S + 1) = 2^{|S + 1|}]

    recall that for any set S we assume

    \frac{\psi(S + 1)}{2} = 2 ^ {|S|}

    which we can rearrange as follows

     \psi(S + 1) = 2 \times 2^{|S|}
     \psi(S + 1)                                      = 2^{|S| + 1}
     \psi(S + 1) = 2^{|S + 1|}

    which proves the inductive step and the theorem.

    thank again for any tips
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Jul 2007
    Posts
    6

    worries

    i'm just worried that the fact that my consequent is essentially included in my antecedent invalidates the proof, correct?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    Sorry, but I have absolutely no idea what you have done there!

    The usual way is to observe that \wp (\{ 1,2,...,n,n + 1\} ) contains \wp (\{ 1,2,...,n\} ) plus \left\{ {X \cup \{ n = 1\} :X \in \wp (\{ 1,2,...,n\} )} \right\}.
    Hence \wp (\{ 1,2,...,n, n+1\} ) contains twice as many sets as <br />
\wp (\{ 1,2,...,n\} ).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof of Union of Power Sets
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: February 24th 2010, 10:26 PM
  2. proof involving power sets, and intersection
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: January 12th 2010, 02:29 PM
  3. Induction proof: Cardinality of power sets
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 10th 2009, 04:59 PM
  4. [SOLVED] Proof involing power sets
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: February 11th 2009, 12:52 PM
  5. Power Sets Proof
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: September 20th 2007, 12:41 PM

Search Tags


/mathhelpforum @mathhelpforum