Möbius inversion on posets

Remarks

In the incidence algebra the Möbius function is the inverse of the zeta function $\zeta$, which is $1$ on all pairs $y \le x$. The first equation says $g = f \zeta$ and the second says $f = g \mu$, where a function on $P$ is multiplied by an element of the incidence algebra on the right. Since $\zeta \mu = \mu \zeta = \delta$, each equation implies the other. There is a dual form with sums over $y \ge x$, under the hypothesis that every set $\set{y : y \ge x}$ is finite.

Example: for the subsets of a finite set ordered by inclusion, $\mu(S, T) = (-1)^{\abs{T \setminus S}}$, and the theorem becomes the inclusion–exclusion principle. For the positive integers ordered by divisibility, $\mu(d, n)$ is the number-theoretic Möbius function of $n/d$, and the theorem becomes the classical Möbius inversion formula. For the chain $0 < 1 < 2 < \dots$, $\mu(x, x+1) = -1$ and $\mu(x, y) = 0$ for $y \ge x + 2$, so $f(x) = g(x) - g(x-1)$: a difference undoes a partial sum.

The finiteness hypothesis is needed for the sums to make sense: on $\Z$ with its usual order, $\sum_{y \le x} f(y)$ is an infinite sum.

Going deeper

For a student

The theorem was put in this general form by Rota, and it unifies many counting techniques. To use it, compute $\mu$ for the poset at hand, often with product formulas or with the recursion. For the lattice of partitions of a set, $\mu$ of the whole interval is $(-1)^{n-1}(n-1)!$, and inversion counts connected structures from all structures. In the lattice of subspaces of $\F_q^n$, $\mu$ involves powers of $q$, and inversion counts subspaces avoiding given conditions.