Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Power set (set theory) question

  1. Oct 10, 2009 #1
    I'm reading a book about set theory and it introduced the concept of power set. Ok, I understand what is a power set and the entire concept but I have a question about the number of elements of a power set.

    There's written in the book that the number of elements of a power set is 2n where n is the number of elements of set that power set is of (very bad english, sorry). For example:

    A = {1; 2; 3}

    2A = {A; {1;2}; {1;3}; {2;3}; {1}; {2}; {3}; {null set}}

    n(2A) = 2n(A) = 23 = 8

    Using the concept of Pascal triangle we have the 2n expression comes from:

    8910d5b9c8f59852ed8b0cd9ab12ed51.png

    But I don't understand how can I manage this equation (before the "= 2n") to it be equals 2n

    I would be grateful if someone help me...

    Thank you very much
     
  2. jcsd
  3. Oct 10, 2009 #2

    statdad

    User Avatar
    Homework Helper

    Remember that

    [tex]
    (a+b)^n = \sum_{k=0}^n C^n_k a^kb^{n-k}
    [/tex]

    (Binomial Theorem}

    Set a = b = 1; then

    [tex]
    (1+1)^n = 2^n = \sum_{k=0}^n C^n_k 1^k 1^{n-k} = C^n_0 + \dots + C^n_n
    [/tex]
     
  4. Oct 10, 2009 #3
    Thank you very much statdad for reply, you helped me alot.
     
  5. Oct 11, 2009 #4

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    One can also prove that the power set of a set with n elements has 2n elements by induction.

    The empty set, with 0 elements, has 1 subset, itself. 20= 1.

    Induction hypothesis: assume that, for some k, a set containing k elements has 2k[/k] subsets.

    Let X be a set containing k+ 1 elements. Select one of the elements (which we can do- k+1> 0) and call it "a". All subsets of X are of two kinds, those that contain a and those that don't. Subsets of X that do not contain a are exactly the subsets of X- {a} which has k+1-1= k elements so there are 2k such subsets. Subsets of X that contain a can be written [itex]\left{a\right}\cup U[/itex] where U is now a subset of X that does not contain a. And, as above, there are 2k such subsets. Thus there are 2k+ 2k= 2(2k)= 2k+1[/sub] subsets of X.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Power set (set theory) question
Loading...