Requirement of a smallest element for Möbius inversion on a finite poset

166 Views Asked by At

Here is the Möbius Inversion Formula on a finite poset $(X, \le)$ :

Suppose $(X, \le)$ has a smallest element--that is, an element $0$ such that $0 \le x$ for all $x \in X$. Let $\mu$ be its Möbius function and let $F : X \rightarrow \Re$ be a real-valued function defined on $X$. Let the function $G : X \rightarrow \Re$ be defined by $$G(x) = \sum_{z:z \le x} F(z),\ \ (x \in X).$$ Then $$F(x) = \sum_{y:y \le x} G(y) \mu(y,x),\ \ (x \in X).$$

The proof in Introductory Combinatorics by Richard A. Brualdi reads:

Let $\zeta$ be the zeta function of $(X, \le )$. Using the properties of $\zeta$ and $\mu$, we calculate as follows for $x$ an arbitrary element in $X$:
$$ \begin{align*} \sum_{y:y \le x} G(y)\mu(y,x) &= \sum_{y:y \le x} \mu(y,x) \sum_{z:z \le y} F(z) \\ &= \sum_{y:y \le x} \mu(y,x) \sum_{z:z \in X} \zeta(z,y)F(z) \\ &= \sum_{z:z \in X} F(z) \sum_{y:z \le y \le x} \zeta(y,x) \mu(y,x) \\ &= \sum_{z:z \in X} F(z) \delta(z,x) \\ &= F(x) \end{align*} $$

From my perspective, the condition "$(X, \le )$ has a smallest element" seems unused. So can anyone tell me how this proof use this condition implicitly?

1

There are 1 best solutions below

0
On

The Möbius function - that you didn't define - is the one defining $T^{-1}$ where $T$ is the linear operator defined by $T[F](x)= \sum_{z \in X, z\le x} F(z)$.

$T$ is well-defined if you assume $\{ z\in X,z\le x\}$ is always a finite set and there is an element $x_0$ such that $\{ z \in X, z\le x_0\}= \{x_0\}$ and $\forall x, x_0 \le x$,

in which case $F(x_0) = T[F](x_0)$ and once you know $F(z)$ for $z < x$ then $F(x) = T[F](x)-\sum_{z < x} F(z)$. This is the implicit definition of the linear operator $T^{-1}$ such that $T^{-1}TF = TT^{-1} F=F$.

Finally the Möbius function is $\mu(z,a) = T^{-1}[1_{x = a}](z)$ and $T^{-1}[F](x) = \sum_{z \le x} \mu(z,x) F(z)$