![]() How does one prove (4)? Assume that an element x ofīelongs to exactly r of the sets A i. Whether it's added or subtracted depends on n: for n = 2 it was subtracted, for n = 3 added - take a clue from here. The process goes on with sums being alternately added or subtracted until we come to the last term - the intersection of all sets A i. (The condition i < j < k assures that every intersection is counted only once.) We add the sum of the elements of intersections of the sets taken three at a time. Those are the elements that belong to at least three of the sets A i. When we subtract the sum of the number of elements in such pairwise intersections, some elements may have been subtracted more than once. Since A i∩ A j = A j∩ A i, to avoid duplications we arbitrarily decide to consider only pairs ( A i, A j) with i < j. ![]() We wish to consider every such intersection, but each only once. Those are the elements that belong to at least two of the sets A i, or the intersections A i∩ A j. as we already know, if the sets A i are not disjoint, some elements will have be counted more than once. On the right, we first count elements in each of the sets separately and add the up. What does (4) say? On the left is number of elements in the union of n sets. In the more general case where there are n different sets A i, the formula for the Inclusion-Exclusion Principle becomes: (4) It is then counted in every term of (2') - 4 times added and 3 times subtracted - again adding up to 1. Lastly, let x belong to all three sets A, B, C. On the right, it is counted in | A|, | B|, and | A∩ B| - twice added, once subtracted. Then on the right of (2') it is counted only once in | A|. As such, it's counted once in the left-hand side of (2'). But there is another approach with a more manageable generalization to the case of any finite number of sets, not just three. We could derive (2') from (2) in the manner of (3) - and this is a good exercise in using set-theoretical notations. What about if there are three sets: A, B, C? For three sets, the Inclusion-Exclusion Principle reads (2') Since A∩ B and B - A are disjoint as are A and B - A, and moreover A∪ B = A∪( B - A) and B = ( A∩ B)∪( B - A), it follows from (1) that (3) Here's an argument that may appear more rigorous. ![]() To obtain an accurate number | A∪ B| of elements in the union we have to subtract from | A| + | B| the number | A∩ B| of such elements. In short, counted twice were the elements of A∩ B. Which are they? The elements that were counted twice are exactly those that belong to A (one count) and also belong to B (the second count). Indeed, in | A| + | B| some elements have been counted twice (the common siblings of the two brothers). If A and B are not disjoint, we get the simplest form of the Inclusion-Exclusion Principle: (2) (Consider also such a question: two brothers have three siblings each. and this is how - by following its plot - we arrived at where we are today: masters of a vast amount of accumulated knowledge in control of fantastically powerful technology that could not have been foreseen at the beginning of the story. Well, what can one say? Is it not what is called Turning an idea around in one's mind? Once the humankind began composing the story of counting, the plot acquired life and logic of its own. Is it not too artificial to count sets that are not disjoint? After all, this would never happen with counting by grouping. The latter form is suggestive of the question, What if A and B are not disjoint? Or is it? with no common elements) wholes and combine them into one. Instead of splitting the whole into two groups, we start with two ( disjoint, i.e. ![]() This is exactly same statement with a somewhat different emphasis. Since X = A∪ B, the idea of counting by grouping can also be expressed as (1) We shall consider that statement on its own merits. If a group of objects X is split into two groups - denoted A and B, which means that they have no common elements ( A∩ B = Ø) and together combine into the whole ( X = A∪ B), then the number of elements | X| in the group X can be arrived at by first counting elements of A and then counting elements of B. The latter is a statement of legitimacy of counting by grouping. If X = A ∪ B and A ∩ B = Ø, then | X| = | A| + | B|.Every group of objects A can be associated with a quantity - denoted | A| - called the number of elements in A.The second describes its fundamental property. The first just states that counting makes sense. The Principle itself can also be expressed in a concise form. From the First Principle of Counting we have arrived at the commutativity of addition, which was expressed in convenient mathematical notations as a + b = b + a.
0 Comments
Leave a Reply. |
Details
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |