Anonymous

# 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.)

Relevance

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

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
• 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