Möbius

§1Inclusion-Exclusion

Often in math, we find ourselves in the following situation:

Let $\mathcal A=\{A_1, A_2, \ldots, A_n\}$ be a collection of sets in a universe $U$. We can easily calculate the size of the intersection of any sub-collection of $\mathcal A$, and our task is to calculate $\left|\bigcup A_i\right|$.

This problem often appears in a certain form. There is a universal set $U$, for which each $A_i \subset U$. Each $A_i$ represents some condition, and we want to find the size of the complement of $\bigcup A_i$. Some examples are as follows.

1. Computing the number of permutations on a set without fixed points
2. Computing the number of proper colorings of a graph
3. Computing the number of surjective maps from one set to another (this one is particularly important)

The base case of 1 set is trivial: $|U-A_1|=|U|-|A_1|$. We can start with two sets.

Then, $|U-(A_1\cup A_2)| = |U| - |A_1-A_1\cap A_2|-|A_2-A_1\cap A_2| - |A_1 \cap A_2|$. By induction, we know how to calculate $|A_1-A_1\cap A_2|$ and $|A_2-A_1\cap A_2|$ here.

We can also do 3 sets.

We again want to find the elements which are "new" to $U$, that is, not in any lower set. This is the total size of $U$, minus the number of elements which are new to each set below $U$. This relies on each element having a lowest set containing it. We can again calculate these by induction.

Let's actually calculate how many elements are new to $U$ using only the size of each set. Letting $n=|U|$, $n_i=|A_i|$, $n_{ij}=|A_i\cap A_j|$, and $n_{123}=|A_1\cap A_2\cap A_3|$, and counting new elements from the bottom up, we have¹

§2Inclusion-Exclusion for structures

In a more general sense, knowing the structure of $A$, $B$, and $A \cap B$ can often tell us the structure of $A \cup B$ (Or, depending on the kind of structure, $A+B$).

In the case where $A\cap B$ is empty, this becomes the categorical notion of the coproduct. Some examples of coproducts are:

1. The disjoint union of two sets
2. The direct sum of two abelian groups (or rings, vector spaces, modules, etc)
3. The disjoint union of topological spaces (or manifolds)

When $A\cap B$ is non-empty, this generalizes from a coproduct to a specific type of pushout. For sets, this is just the union, but for other categories, it is simplest to define it as a quotient of the coproduct, where all the elements of $A$ and $B$ that intersect are identified. (Note that by default, a coproduct treats $A$ and $B$ as completely disjoint, even if they are not).

Notable is the absence of groups from this list, the coproduct object for groups is quite ugly (free product), though the same principles should apply.

Inductively, we can understand a union/sum of three structures if we understand every intersection between them. (We can understand $A \cup B$ and $C$, and then $(A\cup B)\cap C=(A\cap C)\cup(B\cap C)$, which we can understand by understanding $(A\cap C)\cap(B\cap C)=A\cap B\cap C$).