Hall's Theorem states that:

$u(x,y) = C_0-C_1+C_2-C_3+\cdots$

where $C_k$ is number of chains of length $k$

If $x\neq y$ then $C_0=0$ and $C_1=1$

But my question is why does $C_1$ have to equal one? I've drawn a few different Posets where $C_1$ appears to be zero.


In an interval $[x,y]$ in a poset, with $x\neq y$, there is only one chain of length one. It is the chain $x<y$. Since the chain must begin with the element $x$ and end with the element $y$, there are no other options.

As an example let’s compute the Mobius value $\mu(a,d)$ in the chain $a<b<c<d$.

First, there is no chain of length zero beginning at $a$ and ending at $d$, so $C_0(a,d)=0$. There is one chain of length one, namely $a<d$, so $C_1(a,d)=1$. There are two chains of length two, $a<b<d$ and $a<c<d$, so $C_2(a,d)=2$. Finally, there is one chain of length three, i.e. $a<b<c<d$, so $C_3(a,d) = 1$. Using Hall’s theorem we can now compute:

$$\mu(a,d) = C_0 -C_1 + C_2 -C_3= 0-1+2-1 =0$$

  • $\begingroup$ So if i had a Poset that looked like a diamond, for instance, then going from the bottom to the top is a chain of length one regardless of whether there is a line connecting them (im coming from graph theory so I think im confusing "paths" and "chains") Thank you very much. $\endgroup$ – Wombles Apr 15 '19 at 5:32
  • $\begingroup$ Yes exactly, chains are different from paths. You may want to compare the definitions. $\endgroup$ – M47145 Apr 15 '19 at 6:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.