- #1
Happyzor
- 9
- 0
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?