Results 1 to 3 of 3

Thread: 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 $\displaystyle S$

    $\displaystyle | \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 $\displaystyle \psi(S) = |\wp(S)|$

    and let

    $\displaystyle S + 1$

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

    |$\displaystyle S + 1| = |S| + 1$

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

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

    thus the following also holds for any $\displaystyle S$

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

    we take as our inductive hypothesis that

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

    recall that for any set $\displaystyle S$ we assume

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

    which we can rearrange as follows

    $\displaystyle \psi(S + 1) = 2 \times 2^{|S|}$
    $\displaystyle \psi(S + 1) = 2^{|S| + 1}$
    $\displaystyle \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
    21,744
    Thanks
    2815
    Awards
    1
    Sorry, but I have absolutely no idea what you have done there!

    The usual way is to observe that $\displaystyle \wp (\{ 1,2,...,n,n + 1\} )$ contains $\displaystyle \wp (\{ 1,2,...,n\} )$ plus $\displaystyle \left\{ {X \cup \{ n = 1\} :X \in \wp (\{ 1,2,...,n\} )} \right\}$.
    Hence $\displaystyle \wp (\{ 1,2,...,n, n+1\} )$ contains twice as many sets as $\displaystyle
    \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: Feb 24th 2010, 10:26 PM
  2. proof involving power sets, and intersection
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Jan 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: Feb 11th 2009, 12:52 PM
  5. Power Sets Proof
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Sep 20th 2007, 12:41 PM

Search Tags


/mathhelpforum @mathhelpforum