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

Discrete math, sets, power sets.

  1. Mar 1, 2012 #1
    1. The problem statement, all variables and given/known data

    If s (0,1), find
    |P(S)|, |P(P(S))|, |P(P(P(S)))|

    2. Relevant equations

    3. The attempt at a solution

    |P(S)| = {(0), (1), (0,1), ∅} = 4

    |P(P(S))| = {.........} = 16.

    |P (P(P(S)))| = {......} = 16 ^4 ....but how?

    as my lecturer explained it, it come from pascals triangle
    where the number of elements in the original set corresponds to the number from the triangle. So far so good, so in |P(S)| it contains 4 elements as shown above. Hence |P(P(S))| is equal to the sum of the corresponding (4) row of the triangle (1,4,6,4,1) = 16.

    But from this logic |P(P(P(S)))| should equal the sum of the (16) expansion, but this isnt the case... can some one explain why... what it is it that i'm not getting???
  2. jcsd
  3. Mar 1, 2012 #2
    from what i know lP(S)l=2^n
  4. Mar 1, 2012 #3
    Correct, I only just realised it... does this come from binomial theorem?
  5. Mar 1, 2012 #4
    I don't know why you would bring up binomial theorem? If you use that property of 2^n you should be able to easily solve lP(P(S)l and so on.
  6. Mar 1, 2012 #5
    It's used to prove the "power rule".
  7. Mar 1, 2012 #6
    Thanks for the quick reply!
  8. Mar 1, 2012 #7


    User Avatar
    Science Advisor

    two approaches to proving |P(A)| = 2|A|, for a finite set A.

    approach 1: induction on |A|.

    if |A| = 0, A is the empty set, in which case P(∅) = {∅} so |P(∅)| = 1 = 20.

    assume that |P(A)| = 2|A|, whenever |A| < n.

    now pick an element a in A. consider P(A-{a}). what sets are in P(A) that aren't in P(A-{a})? the sets containing a, right?

    show that every set in P(A) that contains a is equal to BU{a}, where B is in P(A-{a}). conclude there is a bijection from the sets of P(A) containing a to P(A-{a}).

    approach 2: just count.

    there are nCk ways to pick k elements of A, if |A| = n, where:

    nCk = n!/(k!(n-k)!)

    so we have:

    nCn (=1) subsets of A with n elements, namely A
    nC(n-1) subsets of A with n-1 elements
    nC2 subsets of A with 2 elements
    nC1 = n subsets of A with 1 element, namely the sets {a} with a in A,
    nC0 = 1 subset of A with no elements, namely, the empty set.

    now add these together (these are the numbers in the n-th row of pascal's triangle).

    of course, to prove:

    [tex]\sum_{k=0}^n \begin{pmatrix}n\\k \end{pmatrix} = 2^n[/tex]

    you'll probably have to use induction.
  9. Mar 1, 2012 #8
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook