Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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...)

share|cite|improve this question
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

1 Answer 1

up vote 1 down vote accepted

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.

share|cite|improve this answer
Sorry! I confused with the second equality in the answer! – user8186 Mar 17 '11 at 9:39
@William I am afraid I do not understand your comment: are you asking for some further explanations about a step of the proof in my post? If so, which one? – Did Mar 17 '11 at 9:47
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
Thanks! Now its clear! – user8186 Mar 17 '11 at 10:47

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.