Take the 2-minute tour ×
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|improve this question
1  
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|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
1  
@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

 
discard

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