Discrete Structures

Today we look at the following Theorem (Inclusion-Exclusion). Let A1, A2, An be finite sets. The size of the union of the Aj is JA; (-1),J1+1 na; JC{1,2,...,n} J0 where the sum is over all subsets of {1, 2, ..., n}. 104, i=1 jEJ 1. (i) Write down what the theorem asserts when there are just two sets A1 and A2. Draw a Venn diagram to explain why this true. (ii) Write down what the theorem asserts for three sets A1, A2 and A3. Prove that the statement holds in this special case by setting B1 = A1 U A2 and B2 A3 and now counting the elements in the union of these two sets. = (iii) Do the same with four sets A1, A2, A3, and A4. This time, prove that the statement holds by assuming that it holds for three sets and working with B1 = A1 U A2 U A3 and B2 = A4. (iv) Write down the beginning of a proof by induction that the theorem holds for any finite collection of sets (you don't need to formally complete the proof). 2. Use the theorem to count the number of natural numbers between 1 and 200 that are not divisible by 3, 5, 7 or 11. Today we look at the following Theorem (Inclusion-Exclusion). Let A1, A2, An be finite sets. The size of the union of the Aj is JA; (-1),J1+1 na; JC{1,2,...,n} J0 where the sum is over all subsets of {1, 2, ..., n}. 104, i=1 jEJ 1. (i) Write down what the theorem asserts when there are just two sets A1 and A2. Draw a Venn diagram to explain why this true. (ii) Write down what the theorem asserts for three sets A1, A2 and A3. Prove that the statement holds in this special case by setting B1 = A1 U A2 and B2 A3 and now counting the elements in the union of these two sets. = (iii) Do the same with four sets A1, A2, A3, and A4. This time, prove that the statement holds by assuming that it holds for three sets and working with B1 = A1 U A2 U A3 and B2 = A4. (iv) Write down the beginning of a proof by induction that the theorem holds for any finite collection of sets (you don't need to formally complete the proof). 2. Use the theorem to count the number of natural numbers between 1 and 200 that are not divisible by 3, 5, 7 or 11