1
$\begingroup$

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

  • 1
    This is a very standard exercise, if you look at a random textbook on the subject then the proof is probably there.2011-03-17

1 Answers 1

1

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.

  • 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)$.2011-03-17