One of the important – indeed central – aspects of mathematics is the idea of abstracting out interesting structures in order to study those structures in general. The study of groups, rings, fields, vector spaces, category theory, and so on, are examples of this. Other types of abstractions are general methods and principles, such as proof by induction or the Pigeonhole Principle. One such principle caught my attention recently, namely the Inclusion-Exclusion Principle.

I was looking at an expression of the form lcm( a₁, …, a_n ), and realized that I could restate this using the gcd's of subsets of the a's, in a way similar to the Inclusion-Exclusion principle. This made me wonder if I could generalize the principle in a way that both the original principle and my lcm/gcd version would follow easily. This is what I came up with:

Theorem (General Inclusion-Exclusion Principle): Let (L, ∧, ∨) be a distributive lattice, let G be an abelian group, and let φ: L → G be a mapping that satisfies φ(a ∧ b) φ(a ∨ b) = φ(a) φ(b). Then, for a₁, …, a_n ∈ L, the following equation holds:

φ( a₁ ∨ … ∨ a_n ) = ∏ _{I: ∅ ≠ I ⊆ {1,…,n}} φ(∧_{i∈ I} a_i )^(-1)|I|-1

Proof by induction on n. For n = 1 the theorem is trivial, and for n = 2 the theorem reduces to the functional equation for φ. Let n > 1, and assume the theorem holds for smaller values of n. Using the functional equation for φ, the fact that L is distributive, and the induction hypothesis, we have:

Example 1: Take L to be the power set P(X), for some set X, with the usual subset ordering. The supremum and infimum operators will then just be the usual set union and intersection, and these are known to be distributive. Take G to be the integers with addition as operator, and define φ(S) = |S|, noting that |S ∩ T| + |S ∪ T| = |S| + |T|, then the conclusion of the theorem becomes:

|S₁ ∪ … ∪ S_n| = ∑ _{I: ∅ ≠ I ⊆ {1,…,n}} |∩_{i ∈ I} S_i| (-1)^|I|-1

Which is what is traditionally known as the Inclusion-Exclusion Principle. If we reverse the ordering of L we will get the same equation, but with union and intersection exchanged:

|S₁ ∩ … ∩ S_n| = ∑ _{I: ∅ ≠ I ⊆ {1,…,n}} |∪_{i ∈ I} S_i| (-1)^|I|-1

(These equations can be generalized a bit by replacing the counting measure, |⋅|, by any measure μ, requiring L to be a subset of the power set containing only measurable sets and to be closed under finite unions and intersections.)

Example 2: Take L to be the real numbers with the usual ordering, and G to be the real numbers with addition. With φ being the identity mapping – i.e. the mapping that takes every element to itself – we get:

max( a₁, …, a_n ) = ∑ _{I: ∅ ≠ I ⊆ {1,…,n}} (-1)^|I|-1 min _{i ∈ I} (a_i)

As with Example 1 we can reverse the ordering to get a similar result, but with min and max exchanged.

Example 3: Let L be the natural numbers with "a divides b" as the ordering, and take G to be the positive rational numbers with multiplication. Note that the supremum and infimum operators become least common multiple and greatest common divisor respectively. With φ being the identity mapping, and noting that gcd(a, b) lcm(a, b) = a b, we get:

lcm( a₁, …, a_n ) = ∏ _{I: ∅ ≠ I ⊆ {1,…,n}} (gcd _{i ∈ I} (a_i))^(-1)|I|-1

Example 4: The Möbius Inversion Formula. Let f be any function from the natural numbers into an abelian group G, and define g(n) = ∑_d|n f(d). Then the Möbius inversion formula states that f(n) = ∑_d|n μ(d) g(n/d), where μ is the Möbius function.

Let L be the power set of the natural numbers, ordered by inclusion, and define φ(S) = ∑_d∈S f(d). Let p₁,…,p_k be the distinct primes dividing n and set S_i = {d: d | n/p_i}. The inclusion-exclusion principle now gives:

A little bit of rearranging now yields the Möbius inversion formula.