Möbius inversion （1）Ring on locally finite partial order set

I learn this from 《代数学方法-基础架构》李文威

You can download this book from his page 书籍 (wwli.asia)

Locally finite partial order set

Definition: Consider a no empty partial order set $(P,\le )$$(P,\le)$, $\mathrm{\forall }x\le y,[x,y]:=\{z\in P,x\le z\le y\}$$\forall x\le y,[x,y]:=\{z\in P,x\le z\le y\}$ is finite, then we call it a locally finite partial order set.

Example 1.1

$(\mathbb{N},\le ),(\mathbb{N},|)$$(\mathbb N,\le),(\mathbb N,|)$ are the classic example, easy to see that is locally finite. But $(\mathbb{Q},\le )$$(\mathbb Q,\le)$ is not

Ring on the locally finite partial order set

We can define a ring $(I,(P,\le ),+,\star )$$(I,(P,\le),+,\star)$on locally finite $(P,\le )$$(P,\le)$

$\mathrm{♢}$$\diamondsuit$ The element of this ring is all the functions $f:\{(x,y)\in P^2:x\le y\}\to \mathbb{Q}$$f:\{(x,y)\in P^2:x\le y\}\to\mathbb Q$

$\mathrm{♢}$$\diamondsuit$ Define $(f+g)(x,y)=f(x,y)+g(x,y)$$(f+g)(x,y)=f(x,y)+g(x,y)$

$\mathrm{♢}$$\diamondsuit$ Define $(f\star g)(x,y)=\sum _{z:x\le z\le y}f(x,z)g(z,y)$$(f\star g)(x,y)=\sum_{z:x\le z\le y} f(x,z)g(z,y)$

$\mathrm{♢}$$\diamondsuit$ Define $1$$1$ in this ring as $\begin{array}{c}\delta (x,y)=\{\begin{array}{l}1,x=y\\ 0,x\ne y\end{array}\end{array}$$\delta(x,y)=\begin{cases}1,x=y\\0,x\ne y\end{cases}$

$\mathrm{♢}$$\diamondsuit$Easy to check that $(I,+)$$(I,+)$ is an Abelian Group

To see $(I,(P,\le ),+,\star )$$(I,(P,\le),+,\star)$ is a ring

According to $P$$P$ is locally finite, $\star$$\star$ is well-defined

$\mathrm{♢}$$\diamondsuit$ $\star$$\star$ is associative

View $(f\star g)(x,y)$$(f\star g)(x,y)$ as $c_{ij}$$c_{ij}$ in Matrix, $\begin{array}{c}{c}_{ij}=\sum _{k=1}^n{a}_{ik}{b}_{kj}\end{array}$$c_{ij}=\sum_{k=1}^n a_{ik}b_{kj}\\$

That is, $\begin{array}{c}(f\star g)(x,y)=c_{xy}=\sum _{z=1}^n{a}_{xz}{b}_{zy}\end{array}$$(f\star g)(x,y)=c_{xy}=\sum_{z=1}^n a_{xz}b_{zy}\\$

We know that $(M_1{M}_2)M_3=M_1(M_2{M}_3)$$(M_1M_2)M_3=M_1(M_2M_3)$

Thus $(f\star g)\star h=f\star (g\star h)$$(f\star g)\star h=f\star(g\star h)$

$\mathrm{♢}$$\diamondsuit$ $\delta \star f=f\star \delta =f$$\delta \star f=f\star\delta=f$

$\delta \star f=\sum _{z\in [x,y]}\delta (x,z)f(z,y)=\delta (x,x)f(x,y)=f(x,y)$$\delta\star f=\sum_{z\in [x,y]} \delta(x,z)f(z,y)=\delta(x,x)f(x,y)=f(x,y)$

$f\star \delta =\sum _{z\in [x,y]}f(x,z)\delta (z,y)=f(x,y)\delta (y,y)=f(x,y)$$f\star\delta=\sum_{z\in [x,y]}f(x,z)\delta(z,y)=f(x,y)\delta(y,y)=f(x,y)$

$\mathrm{♢}$$\diamondsuit$ $f\star (g+h)=f\star g+f\star h,(g+h)\star f=g\star f+h\star f$$f\star (g+h)=f\star g+f\star h,(g+h)\star f=g\star f+h\star f$

Similarly, consider the distributive law for matrix.

The dual partial order and the opposite ring

We know that $(P,\le )$$(P,\le)$ is a locally finite partial order set if and only if $(P,\ge )$$(P,\ge)$ is locally finite.

And we have $(I,(P,\ge ),+,\ast )=(I,(P,\le ),+,\star {)}^{op}$$(I,(P,\ge),+,*)=(I,(P,\le),+,\star)^{op}$

$x\le y\iff y\ge x$$x\le y\Leftrightarrow y\ge x$

Thus in $(I,(P,\ge )),(g\ast f)(y,x)=\sum _{z:y\ge z\ge x}g(y,z)f(z,x)=(f\star g)(x,y)$$(I,(P,\ge)), (g*f)(y,x)=\sum_{z:y\ge z\ge x}g(y,z)f(z,x)=(f\star g)(x,y)$

Lemma 1

For locally finite $(P,\le )$$(P,\le)$, $\mathrm{\forall }f\in (I,(P,\le ))$$\forall f\in (I,(P,\le))$, those statements are equivalent

$\mathrm{♢}$$\diamondsuit$ $f$$f$ have a left inverse

$\mathrm{♢}$$\diamondsuit$ $\mathrm{\forall }x\in P,f(x,x)\ne 0$$\forall x\in P, f(x,x)\ne 0$

$\mathrm{♢}$$\diamondsuit$ $f$$f$ have a right inverse

$\mathrm{Proof}.$$\mathrm{Proof.}$

$1\Rightarrow 2$$1\Rightarrow 2$

Let $g\star f=\delta$$g\star f=\delta$

$(g\star f)(x,y)=\sum _{z\in [x,y]}g(x,z)f(z,y)=\delta (x,y)$$(g\star f)(x,y)=\sum_{z\in[x,y]} g(x,z)f(z,y)=\delta(x,y)$

Thus $g(x,x)f(x,x)=1$$g(x,x)f(x,x)=1$

Therefore $\mathrm{\forall }x,f(x,x)\ne 0$$\forall x, f(x,x)\ne 0$

$2\Rightarrow 1$$2\Rightarrow 1$

Expand $g\star f=\delta$$g\star f=\delta$

$g(x,y)f(y,y)=-\sum _{x\le z<y}g(x,z)f(z,y)$$g(x,y)f(y,y)=-\sum_{x\le z<y} g(x,z)f(z,y)$ $x,y\in P,x<y$$x,y\in P,x<y$

Since $\mathrm{\forall }x\in P,f(x,x)\ne 0$$\forall x\in P,f(x,x)\ne 0$, $g(x,y)$$g(x,y)$ is defined uniquely

$\begin{array}{c}g(y,y)=\frac{1}{f(y,y)},g(x,y)=-\frac{\sum _{x\le z<y}g(x,z)f(z,y)}{f(y,y)}\end{array}$$g(y,y)=\frac{1}{f(y,y)},g(x,y)= -\frac{\sum_{x\le z<y}g(x,z)f(z,y)}{f(y,y)}\\$

$1\iff 3$$1\Leftrightarrow 3$

$f$$f$ have right inverse in $(I,(P,\le ))$$(I,(P,\le))$ if and only if $f$$f$ have left inverse in $(I,(P,\ge ))$$(I,(P,\ge))$

For locally finite Poset, define $\zeta ={\zeta }_p\in (I,(P,\le ),+,\star ),\mathrm{\forall }x\le y,\zeta (x,y)=1$$\zeta=\zeta_p\in (I,(P,\le),+,\star),\forall x\le y,\zeta(x,y)=1$

Then define Möbius function $\mu :={\zeta }^{-1}$$\mu:=\zeta^{-1}$

If we expand $\mu \star \zeta =\delta =\zeta \star \mu$$\mu\star\zeta=\delta=\zeta\star\mu$, then we will get $\sum _{z\in [x,y]}\mu (x,z)=\delta =\sum _{z\in [x,y]}\mu (z,y)$$\sum_{z\in[x,y]}\mu(x,z)=\delta=\sum_{z\in[x,y]}\mu(z,y)$

Proposition. Möbius inversion

Lemma 2.

Define $g\in (I,(P,\le ),+,\star ):=f\star \zeta$$g\in(I,(P,\le),+,\star):= f\star\zeta$

Thus $g\star \mu =(f\star \zeta )\star \mu =f\star (\zeta \star \mu )=f\star \delta =f$$g\star\mu=(f\star\zeta)\star\mu=f\star(\zeta\star\mu)=f\star\delta=f$

Consider Abelian Group $(A,+)$$(A,+)$, Let $(P,\le )$$(P,\le)$ satisfied with $\mathrm{\forall }x,\{y\in P:y\le x\}$$\forall x,\{y\in P:y\le x\}$ is finite.

And denote the least element as $0,\mathrm{\forall }x\in P,0\le x$$0,\forall x\in P,0\le x$, if $(P,\le )$$(P,\le)$ have no least element, then add $0$$0$

Denote $\mathrm{\forall }f\in I,f(0,x):=f(x)$$\forall f\in I,f(0,x):=f(x)$

Then define $g(x)=f\star \zeta =\sum _{z\le x}f(z)$$g(x)=f\star\zeta=\sum_{z\le x} f(z)$

According to Lemma 2

$f=g\star \mu =\sum _{z\le x}g(z)\mu (z,x)$$f= g\star\mu=\sum_{z\le x}g(z)\mu(z,x)$