22.1.4. Proof of the General Formula

So, we have seen the principle of inclusion-exclusion for this case of 2 sets, for the case of 3 sets. We can generalize it to the case of n sets. So, the general formula says the following. If you have n sets they may be disjoint, there might be overlaps and so on. Then the formula says that if you want to find out the cardinality of the union of n sets then this is this formula. That means it says that it is same as you have to first individually take the summation of the cardinalities of the individual sets. Then you have to subtract the cardinality of pairwise intersection of sets. Then you have to add the cardinality of intersection of triplets of sets and so on. That means alternately, first we add then we subtract and we add and we subtract and so on.

The general formula for inclusion-exclusion allows you to compute the total number of elements in the union of multiple sets, accounting for any overlaps between the sets. You start off by adding the number of elements in each individual set. Then, you subtract the number of elements that were counted multiple times due to overlaps (pairwise intersections). After that, you add back the elements that were subtracted too many times (intersections of triplets of sets), and so forth, alternating between subtraction and addition for higher intersections. This ensures that each element is counted exactly once in the final total.

Imagine you have three different bags of candies: one bag has chocolate candies, another has gummy candies, and the last has lollipops. Some candies are in more than one bag. If you only count the candies in each bag, you'll overcount those that are in multiple bags. The inclusion-exclusion principle helps you find the actual number of unique candies by first counting all candies, then removing counts of those that belong to two bags, and finally adding back those candies that might’ve been removed more than necessary.

So, the idea here will be the following, so consider an element a which is present in the union of the n sets. It might be present in just one of the sets, it might be present in 2 of the sets we do not know in how many sets the element is present. We have to show that if at all an element a is present in the union of n states then by this complex looking argument, complex looking formula in the right hand side expression the element ais counted exactly once. And that is what we want to prove here basically. So, imagine that the element a is present in r number of sets out of the n sets where r is at least 1.

To prove the general formula, we consider an arbitrary element 'a' that might belong to any number of the n sets involved. We denote the number of sets containing 'a' as 'r', which can range from 1 (if 'a' is in just one set) to n (if 'a' is in all sets). The goal of our proof is to demonstrate that under this formula, 'a' will be counted exactly once. By analyzing how many times 'a' is added and subtracted as we apply the principle of inclusion-exclusion, we can establish that the counts will ultimately boil down to exactly one when considering overlaps.

Think of a school with multiple clubs: a sports club, a music club, and an art club. A student might belong to some of these clubs. In trying to count how many distinct students are in school, if we just blindly count members of each club, we may count the same student several times. The inclusion-exclusion principle helps clarify this: by understanding the overlaps of club memberships, we can accurately ascertain how many unique students there are.

Now what we have to show is our goal is to show that by the RHS expression the element A is counted exactly once overall. So, for that, we observe that the first part of the formula on the right hand side is where we are taking the summation of the cardinalities of the individual sets A1 to An. Now because of this, the element a will be counted C(r, 1) number of times. So, for instance if the element a is present, say in the first r sets, then because when we are taking the cardinality of A1 the element a was counted once. When we are taking the cardinality of A2 the element a is again counted once. When we are taking the cardinality of Ar the element a is again counted once and so on. When we are taking the cardinality of Ar+1 the element a is not increasing the count of the element a.

In further exploring how many times our element 'a' is counted, we start with the first part of the formula that sums up the sizes of all individual sets. When element 'a' is present in 'r' sets, it contributes to the count 'C(r, 1)', which is the number of ways to choose 1 set from the r sets that contain 'a'. Essentially, for every set 'A_i' containing 'a', it will increase the count once, which leads to a total count of 'C(r, 1)'. This observation lays the groundwork for understanding how overlaps add or subtract from the element's overall count.

Consider our earlier school example: if there are 5 clubs, and a student is in 3 of these clubs, then in tallying club memberships, they will be counted once for each club they are in. This mirrors the counting 'C(r, 1)', as each club (or set) adequately reflects the student’s membership distinctly until overlaps require further adjustments.

So now what we can say is that the total count of this element a by the RHS expression is the following C(r, 1) – C(r, 2) + C(r, 3) - … (-1)r+1C(r, r). This is because through the first part of the expression the element A is counted C(r, 1) number of times, through the second part of my expression the count of element A gets decremented by C(r, 2) number of times. Why decremented? Because of this minus. Then due to the third part of the expression, the count of element a gets incremented by C(r, 3) number of times and so on.

This expression summarizes the entire counting process: it captures how the element 'a' is counted as we apply the inclusion-exclusion principle. We start with the initial count from the first part, subtract counts from pairwise overlaps, add counts back from triplet overlaps, and continue this alternating approach up to the r-th overlaps. The essence of this alternating sum corresponds to the number of ways to select subsets of sets (using binomial coefficients), reaching the conclusion that the expression ultimately equals 'C(r, 0)', equating to 1, indicating 'a' is counted exactly once.

Imagine you are counting cookies made from different ingredients. The initial count gives you the total cookies, but then you find some have fewer ingredients (overlapping counts). You adjust for these overlaps, ensuring you get the exact number of unique cookie types. This careful balancing act mirrors the inclusion-exclusion approach, emphasizing how you must consider when elements are counted more than once across various categories or overlapping groups.

--