# Homework Help: Prove Power Set equation by Induction

1. Jan 17, 2010

### Happyzor

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

(a) Use induction to show that if n(A) = n then n(P(A)) = 2^n.

n(A) is the cardinality of set A.
P(A) is the power set of A.

2. Relevant equations

We apply induction to prove the claim.
If n = 0 then A = null and in this case P(A) = {null}. Thus n(P(A)) = 1 = 2^0.
As induction hypothesis, suppose that if n(A) = n then n(P(A)) = 2^n. Let B = {a1, a2, · · · , an, an+1}. Then P(B) consists of all subsets of {a1, a2, · · · , an} together with all subsets of
{a1, a2, · · · , an} with the element an+1 added to them. Hence, n(P(B)) =
2^n + 2^n = 2 · 2^n = 2^n+1.

3. The attempt at a solution

Can someone explain the step

"Then P(B) consists of all subsets of {a1, a2, · · · , an} together with all subsets of {a1, a2, · · · , an} with the element an+1 added to them. "

Why is this the case? Shouldn't P(B) just all the subsets {a1,a2,...,an,an+1)? So that's the power set of {a1,a2,...,an} plus something else, but what is that something else?

The answer seems to say that the something else is all subsets of {a1, a2, · · · , an} with the element an+1 and that is equal to 2^n but why is that the case? How do we know that it is equal to 2^n?

2. Jan 17, 2010

### tiny-tim

Hi Happyzor!

(try using the X2 and X2 tags just above the Reply box )
That's rather unclear.

I'd prefer to say:

P(B) consists of:
i] all subsets of {a1, a2, · · · , an+1} which do include an+1
plus
ii] all subsets of {a1, a2, · · · , an+1} which don't include an+1.

That's the same number as the number of:
i] all subsets of {a1, a2, · · · , an}
plus
ii] all subsets of {a1, a2, · · · , an}.

3. Jan 17, 2010

### Happyzor

Why are they both equal to 2n? I understand why n*P({a1, a2, · · · , an}) is equal to 2n but why is the other one also 2n? Thanks for your help.

4. Jan 17, 2010

### tiny-tim

the sets in i] all include an+1.

So each set in i] is of the form (A U {an+1}) where A is a subset of {a1, a2, · · · , an}.

Different sets in i] have different As, and every A corresponds to a set in i].

ie there's a one-to-one correspondence between the sets in i] and P({a1, a2, · · · , an})

ie they have the same number.

5. Jan 17, 2010

### Happyzor

Thanks for your help. I didn't really understand what you meant, but I got help from someone else. I really appreciate it!