# Möbius inversion formula

Let $X$ be non-empty set and $S$ be the set of all subsets of $X$, which will be a poset, under subset relation.

Let $\phi \colon S\rightarrow \mathbb{Z}$ be any function and for each $H\in S$, define $\sigma(H)=\sum_{K\leq H}\phi(K)$.

$\mu$ be the Möbius function defined by $\sum_{K\leq H} \mu(H)=\delta_{K,X}$.

How to show that $\sum_{H\leq X} \sigma(H)\mu(H)=\phi(X)$?

(I considered LHS, and substituted for $\sigma(H)$, interchanged the sum, but I couldn't proceed further...)

-
This is a very standard exercise, if you look at a random textbook on the subject then the proof is probably there. –  Yuval Filmus Mar 17 '11 at 8:13

As you said, $$\sum_{H\le X}\sigma(H)\mu(H)=\sum_{H\le X}\sum_{K\le H}\phi(K)\mu(H)=\sum_{K\le X}\phi(K)\tau_X(K)$$ with $$\tau_X(K)=\sum_{K\le H\le X}\mu(H),$$ hence all there is to show is that $\tau_X(X)=1$ and $\tau_X(K)=0$ for every $K\subset X$, $K\ne X$. This is how you defined the Möbius function $\mu$, hence the proof is complete.
I am sorry! I couldn't understand the equality $\sum_{H\leq X}\sum_{K\leq H}\phi(K)\mu(H)=\sum_{K\leq X}\phi(K)\tau_{X}(K)$ –  user8186 Mar 17 '11 at 9:50
@William This is simply the interversion of the summations over $H$ and over $K$, and the definition of $\tau_X(K)$ as the sum over $H$ that one gets for the coefficient of $\phi(K)$. –  Did Mar 17 '11 at 10:11