Prove Power Set equation by Induction

[Happyzor]

Homework Statement

(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.

Homework Equations

The answer is
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.

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?

 

[tiny-tim]

Hi Happyzor!

(try using the X² and X₂ tags just above the Reply box )

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.

That's rather unclear.

I'd prefer to say:

P(B) consists of:
i] all subsets of {a1, a2, · · · , an+1} which do include a_n+1
plus
ii] all subsets of {a1, a2, · · · , an+1} which don't include a_n+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}.

 

[Happyzor]

Hi Happyzor!

(try using the X² and X₂ 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 a_n+1
plus
ii] all subsets of {a1, a2, · · · , an+1} which don't include a_n+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}.

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

 

[tiny-tim]

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

the sets in i] all include a_n+1.

So each set in i] is of the form (A U {a_n+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.

 

[Happyzor]

the sets in i] all include a_n+1.

So each set in i] is of the form (A U {a_n+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.

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