Proof of Möbius function on subset poset

Question

Prove that Möbius function of subset poset of $[n]$ is following, given $A,B \subseteq [n]$.

$\mu (A,B)=\left\{ \begin{array}{l} (-1)^{|B|-|A|},& \text{if}\,\, A \subseteq B\\ 0,& \text{otherwise}\end{array} \right.$

I searched for the proof and in one paper they use induction. $A = B$ this is obvious. Assume this holds up to $|B|= |A| + n, A\subset B$. Then for $|B|=n+1$

$\mu (A,B)=- \sideset{}{_{A \subseteq C \subset B} (-1)^{|C|-|A|}} \sum = (-1)^{|B|-|A|}$

But I do not understand the last step. How
$\sideset{}{_{A \subseteq C \subset B} (-1)^{|C|-|A|}} \sum = (-1)^{|B|-|A|}$

Can anyone explain this or point me to a more detailed proof? Thanks

Answer 1

$\mathsf{Hint}$ (use the substitution $D=C\setminus A$):

$$\sum_{A\subseteq C\subseteq B}(-1)^{|C|-|A|}=\sum_{D\subseteq B\setminus A}(-1)^{|D|}=\sum_{\ell=0}^{|B\setminus A|}\binom{|B\setminus A|}{\ell}(-1)^\ell=(1-1)^{|B\setminus A|}=0.$$

Notice $C\color{Red}{\subseteq}B$ is used above, as opposed to $\color{Blue}{\subset}$ as used in the original expression.

Answer 2

The most important step is to bring the term $(-1)^{|B|-|A|}$ into the summation, so that instead of showing $-\sum_{A \subseteq C \subset B} (-1)^{|C|-|A|} = (-1)^{|B|-|A|}$ one will show the equivalent $ \sum_{A \subseteq C \subseteq B} (-1)^{|C|-|A|} =0 $ (under the assumption $A\subset B$).

Changing variables to $C'=C\setminus A$ this now follows easily $$ \sum_{A \subseteq C \subseteq B} (-1)^{|C|-|A|} =\sum_{C' \subseteq B\setminus A} (-1)^{|C'|} = 0 \qquad\text{since $B\setminus A\neq\emptyset$.} $$ The latter equality can be justified by recognising $\sum_{T\subseteq S}(-1)^{|T|}$ as the expansion of $\prod_{s\in S}(1-1)=0$ for the non-empty set $S=B\setminus A~$ (if you find this too cryptic, replace the terms $-1$ in each factor of the product by a separate variable $x_s$ which are then all set to $-1$; you may of course also use binomial coefficients).

A more advanced way to understand this Möbius function is to recognise the poset of subsets of $[n]$ as a product poset of $n$ copies of a $2$-element totally ordered set (namely the two subsets of a singleton $\{i\}$, one such copy for each $i\in[n]$). The Möbius function will then be the product of the Möbius functions of those basic orderings, as I've explained in this answer. Since always $\mu(X,Y)=0$ unless $X\subseteq Y$ and $\mu(X,X)=1$, the only interesting value of Möbius function $\mu_{\{i\}}$ of the subsets of $\{i\}$ is $\mu_{\{i\}}(\emptyset,\{i\})=-1$. The expression for the Möbius function of the subsets of $[n]$ then is $$ \mu(A,B)=\prod_{i\in[n]}\mu_{\{i\}}(A\cap\{i\},B\cap\{i\}) =\begin{cases}0&\text{if $A\not\subseteq B$,}\\ (-1)^{|B\setminus A|}&\text{if $A\subseteq B$.}\end{cases} $$