MAT102H5 Lecture Notes - Lecture 13: Implementation Force
88 views3 pages
![MAT102H5 Full Course Notes](https://new-docs-thumbs.oneclass.com/doc_thumbnails/list_view/2236404-class-notes-ca-utm-mat102h5-lecture25.jpg)
71
MAT102H5 Full Course Notes
Verified Note
71 documents
Document Summary
Mat102: mathematical and logical-lecture 13: chapter 3 induction (continue ) This is not a statement (can"t be proven). For n=2, s={a,b}, then the subsets are {a}, {b}, {a,b}, (4 subsets). For n=1, s={a}, then the subsets are ,{a} (2 subsets). For n=3, s={a,b,c}, then the subsets are ,{a},{b}, {c}, {a,b}, {a,c},{b,c},{a,b,c} (8 subsets) Claim: a set s with n elements has 2 n subsets (including s and ). Proof: base case: if n=1, then s has only 2 elements (s and ). Assume that a set with k elements has 2 k subsets, and consider. S= {a 1 ,a 2 , ,a k ,a. The set s= {a 1 ,a 2 , ,a k ,a. } has, by assumption, 2 k subsets: b 1 ,b 2 , ,b k^2. 1+k form a complete list of all the subsets of s . By pmi, the claim holds for all n together with b 1 ,b 2 , ,b k^2.