Ask a question... Solution Assuming the question is: Prove that a set A which co

Question

Ask a question...

Explanation / Answer

Assuming the question is: Prove that a set A which contains n elements has 2n different subsets. Proof by induction on n: Base case (n = 0): If A contains no elements then the only subset of A is the empty set. So A has 1 = 20 different subsets. Induction step (n > 0): We assume the induction hypothesis for all n smaller than some arbitrary number k (k > 0) and show that if the claim holds for sets containing k - 1 elements, then the claim also holds for a set containing k elements. Given a set A which contains k elements, let A = A' u {.} (where u denotes set union, and {.} is some arbitrary subset of A containing a single element no in A'). Then A' has k - 1 elements and it follows by the induction hypothesis that (1) A' has 2k-1 different subsets (which also are subsets of A). (2) For each of these subsets we can create a new set which is a subset of A, but not of A', by adding . to it, that is we obtain an additional 2k-1 subsets of A. (*) So by assuming the induction hypothesis (for all n

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.