Anonymous
Anonymous asked in Science & MathematicsMathematics · 1 decade ago

Set theory question (power sets)?

Prove that for a set with n elements, a power set has 2^n elements. (If possible, prove by induction.)

3 Answers

Relevance
  • 1 decade ago
    Favorite Answer

    Slightly sloppy proof:

    Assume, without loss of generality, that S = { 1 , 2 , ... , n }

    There are 2 choices at every step to construct a subset T of S:

    1) Is 1 in T? Yes or no.

    2) Is 2 in T? Yes or no.

    ...

    n) Is n in T? Yes or no.

    Because you have independent choice in each step, multiply to count:

    2×2×...×2 = 2^n

    --------- --------- --------- --------- --------- --------- --------- --------- --------- --------- ---------

    More formal proof:

    Consider |S|=n.

    We will find a bijection between the power set P(S) and the set {0,1,2,...,2^n-1}. We will represent this set by binary integers. For example, in binary, if n=4 then the list is:

    0 = 0000

    1 = 0001

    2 = 0010

    3 = 0011

    4 = 0100

    5 = 0101

    6 = 0110

    7 = 0111

    8 = 1000

    9 = 1001

    10 = 1010

    11 = 1011

    12 = 1100

    13 = 1101

    14 = 1110

    15 = 1111

    Label the elements:

    S = { s0 , s1 , ... , s(n-1) }.

    For each subset T of S, define F(T) to be the binary number whose kth digit are 1 if sk is in T, and 0 if sk is not in t. For example:

    S = { a , b , c , d } so that a=s1, b=s2, d=s3, c=s4 gives:

    0 = 0000 = F( { } )

    1 = 0001 = F( {a} )

    2 = 0010 = F( {b} )

    3 = 0011 = F( {a,b} )

    4 = 0100 = F( {c} )

    5 = 0101 = F( {a,c} )

    6 = 0110 = F( {b,c} )

    7 = 0111 = F( {a,b,c} )

    8 = 1000 = F( {d} )

    9 = 1001 = F( {a,d} )

    10 = 1010 = F( {b,d} )

    11 = 1011 = F( {a,b,d} )

    12 = 1100 = F( {c,d} )

    13 = 1101 = F( {a,c,d} )

    14 = 1110 = F( {b,c,d} )

    15 = 1111 = F( {a,b,c,d} )

    The function F is obviously a bijection, and that completes the proof.

    --------- --------- --------- --------- --------- --------- --------- --------- --------- --------- ---------

    Proof by induction:

    Assume that if |A|=n-1 then | P(A) | = 2^(n-1).

    Then consider |S|=n. Fix a specific s in S.

    The set S-s (remove s from S) is how big?

    | S-s | = 2^(n-1)

    Now, P(S-s) is in P(S), since subsets of S-s are subsets of S.

    Furthermore, each subset of S-s can also have s added to it to make a new subset of S (one that cannot possibly be in P(S) ). In fact, it is obvious that:

    | P(S) | = [ # T⊆S with s not in T ] + [ # T⊆S with s in T ]

    We can compute:

    (a) [ # T⊆S with s not in T ] = P(S-s) = 2^(n-1)

    from the induction.

    (b) [ # T⊆S with s in T ] = P(S-s) = 2^(n-1)

    since each of the sets counted here can be turned into one counted in (a) by simply removing s.

    Thus:

    | P(S) | = 2^(n-1) + 2^(n-1) = 2 (2^(n-1)) = 2^n

    And by induction, the claim is true for all n, assuming we know the base case. But the base case is n=0, meaning S is the empty set. And it is true then becuase:

    | S |= | ∅ | = 0

    | P(S) | = | { ∅ } | = 1 = 2^0

    • Login to reply the answers
  • Anonymous
    1 decade ago

    Power set = a set containing all subsets of a given set.

    Number of subsets of any set with n elements = 2^n

    Since each subset is an element of the power set, the power set has 2^n elements.

    Not sure how exactly this can be done by induction though

    • Login to reply the answers
  • TueLom
    Lv 4
    4 years ago

    This seems fairly trivial... (AnB)^c = U - (AnB) from the definition of the complement. (AnB)^c = (U-A) u (U-B) from de Morgan's law. (AnB)^c = A^c u B^c from the definition of the complement. Maybe they're asking for a proof of de Morgan's law, which you can do with a Venn diagram.

    • Login to reply the answers
Still have questions? Get your answers by asking now.