22.1.1. Introduction to the Principle of Inclusion-Exclusion

The principle of inclusion-exclusion states that to find the cardinality of the union of two sets, you take the summation of the cardinalities of the individual sets and subtract the cardinality of their intersection.

The principle of inclusion-exclusion helps us accurately calculate how many unique elements are in either of two sets without counting any element in both sets more than once. For instance, if Set A has 3 elements and Set B has 2 elements, if they overlap with 1 common element, simply adding the two sets' totals (3 + 2) would count the common element twice. Therefore, we subtract the overlapping count (1), resulting in the correct total of 4 unique elements.

Imagine you have a basket of fruits: 3 apples (Set A) and 2 oranges (Set B). If one of the oranges is counted as an apple (the common element), just adding them gives you 5 fruits. However, since one is counted twice, you remove the extra count, realizing you actually have 4 distinct fruits: 3 apples and 1 orange.

When extending the principle to three sets, the cardinality of their union involves summing individual cardinalities, subtracting pairwise intersections, and adding back the intersection of all three sets.

For three sets A, B, and C, to find the number of unique elements, first add the size of each set: |A| + |B| + |C|. Then, subtract the sizes of the overlaps between each pair (A ∩ B, A ∩ C, B ∩ C), since those elements were counted twice. Finally, add the intersection of all three sets (A ∩ B ∩ C) back, because those were subtracted too many times. This method ensures that every element is counted exactly once.

Picture three overlapping circles where each circle represents a different group of friends. If you want to know how many total friends you have, count each circle, subtract the ones you double-counted from the overlaps, and then add back the friends who belong to all three groups, ensuring no one is left out.

The principle can be generalized to n sets, which follows a specific alternating pattern of addition and subtraction of intersections.

In generalizing to n sets, the principle states that the cardinality of the union of n sets is found by summing the sizes of all individual sets, then subtracting the sizes of all pairwise intersections, adding the sizes of all triple intersections, and continuing this pattern of alternating sign until all intersections are accounted for. This ensures accurate counting across multiple sets, effectively managing any overlaps.

Think about a club with multiple overlapping committees. To find out how many total members are in the club, you would start by counting all members from each committee (the individual sets), subtract those who belong to two committees (double counting), add back those who belong to all three committees (because they were subtracted too much), and repeat this process until all combinations are considered. This ensures you know exactly how many unique members are involved.

The proof concept shows how each element is counted exactly once in the application of this principle by analyzing its presence across the sets.

When proving the principle, one can analyze a single element's presence across the n sets. If the element exists in r sets, it contributes to the total in a combinatorial way, counting how many times it appears through intersections. The resultant counts follow from applying binomial coefficients, leading to a general count of C(r, 0), which equals 1, confirming that any element in the union contributes exactly once.

Imagine tracking attendance at several classes. Each student might attend different classes but not all classes. By counting how many classes a particular student has attended and considering overlaps, you ensure each student is counted appropriately without duplication across sessions.

An alternate form of inclusion-exclusion is useful for counting elements from a set A that do not possess certain properties.

This variant focuses on counting elements that lack specific properties P1, P2,..., Pn within a set A. By first identifying the number of elements with at least one property (through union) and subtracting that from the total number of elements, we can effectively count those that have none of the properties.

Consider a health screening where you want to find out how many people are healthy, meaning they have no diseases. First, count how many have any disease, then subtract this from the total number of people screened. The result gives you the number of people who are disease-free.

--