Question

18. Use induction to prove the following: For any set A, if IA] = n for some finite number n E N, then IP(A) 2
0 0
Add a comment Improve this question Transcribed image text
Answer #1

Proof:

For all n∈N, let P(n) be the proposition:

|A|=n⟹|P(A)|=2n

where P(A) is the powerset of A

Basis for the Induction:

  1. It holds A=∅⟺|A|=0
  2. Then P(A)={∅}, such that |P(A)|=1=20
  3. from (1.) and (2.) it follows that proposition P(0)holds.

Induction Hypothesis:

We need to show that, if P(k) is true, where k≥2, then it logically follows that P(k+1) is true. So if this is our Induction Hypothesis:

|A|=k⟹|P(A)|=2k

We need to show that:

|A|=k+1⟹|P(A)|=2k+1

Induction Step:

  1. Let |A|=k+1 and let x∈A
  2. Consider the set A′=A∖{x} , where x is some element of A. We see that |A′|=k
  3. We now adjoin x to all the subsets of A' . Counting the subsets of A , we have: all the subsets of A' with x adjoined to them.
  4. From the Induction Hypothesis, there are 2k subsets of A'. Adding x to each of these, does not change their number, so there are another 2k subsets of A , consisting of all the subsets A′ with x adjoined to them.
  5. In total that makes 2k+2k=2⋅2k=2k+1 subsets of A. So P(k)⟹P(k+1) and the result follows by the principle of mathematical induction.
  6. Therefore: ∀n∈N:|A|=n⟹|P(A)|=2ⁿ
Add a comment
Know the answer?
Add Answer to:
18. Use induction to prove the following: For any set A, if IA] = n for...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions
ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT