Incidence algebra

The incidence algebra of a partial order was introduced in 1964 by Gian-Carlo Rota to investigate combinatorial facts.

Formal definition

Let be a partially ordered set (i.e., a set with a partial order ). The incidence algebra is defined as follows: ${\displaystyle (M,\leq )}$ ${\displaystyle {\mathcal {I}}_{M}}$

${\displaystyle {\mathcal {I}}_{M}:=\{f:M\times M\rightarrow \mathbb {R} \,|\,x\nleq y\Rightarrow f(x,y)=0\}}$

The addition in is defined point by point, while the multiplication is given by a convolution : ${\displaystyle {\mathcal {I}}_{M}}$

${\displaystyle (f*g)(a,b)=\sum _{a\leq x\leq b}f(a,x)g(x,b).}$

Since the underlying partially ordered set is locally finite, this sum is finite.

properties

The algebraic structure is an associative algebra over the field of real numbers . It has one element , namely ${\displaystyle ({\mathcal {I}}_{M},+,*)}$

${\displaystyle \delta (a,b):={\begin{cases}1\quad &{\mbox{falls }}a=b,\\0&{\mbox{sonst.}}\end{cases}}}$

Rota also defines the zeta function of the partial order,

${\displaystyle \zeta (a,b):={\begin{cases}1\quad &{\mbox{falls }}a\leq b,\\0&{\mbox{sonst,}}\end{cases}}}$

as well as the incidence function by ${\displaystyle n(a,b)=\zeta (a,b)-\delta (a,b).}$

The zeta function is invertible, its inverse is inductively defined as follows: ${\displaystyle {\mathcal {I}}_{M}}$ ${\displaystyle \mu }$

${\displaystyle {\begin{alignedat}{2}\mu (a,a)&=1,&&a\in M,\\\mu (a,b)&=-\sum _{a\leq x<b}\mu (a,x),&\qquad &a<b.\end{alignedat}}}$

These functions satisfy the equation . ${\displaystyle \zeta *\mu =\delta }$

If one takes the set of natural numbers and the partial order resulting from the divisibility relation, the following relationship exists between this function and the classic Möbius function : ${\displaystyle M}$ ${\displaystyle \mu }$ ${\displaystyle \mu _{0}}$

${\displaystyle \mu _{0}\left({\frac {m}{n}}\right)=\mu (n,m),\quad n,m\in \mathbb {N} ,n\mid m.}$

Apparently for this reason Rota calls this function the Möbius function of the partial order. ${\displaystyle \mu }$

Generalized Möbius inverse formula

The equation leads to the following generalization of Möbius' inverse formula : Let be a locally finite partial order, a real-valued (or complex-valued) function and an element with for . Accepted, ${\displaystyle \zeta *\mu =\delta }$ ${\displaystyle (M,\leq )}$ ${\displaystyle f}$ ${\displaystyle M}$ ${\displaystyle p\in M}$ ${\displaystyle f(x)=0}$ ${\displaystyle x<p}$

${\displaystyle g(x):=\sum _{y\leq x}f(y),}$

then applies

${\displaystyle f(x)=\sum _{y\leq x}g(y)\mu (y,x).}$

Further properties of the μ-function

In the cited work Rota proves a few more properties of its μ-function:

duality

If the partial order is too dual (it is created by reversing the order relation), then applies ${\displaystyle M^{*}:=(M,\geq )}$ ${\displaystyle (M,\leq )}$

${\displaystyle \mu ^{*}(x,y)=\mu (y,x)\quad \mathrm {f{\ddot {u}}r\ alle} \quad x,y\in M.}$

Segmentation

If one regards an interval as a separate partial order, its μ-function is equal to the restriction of the μ-function of to this interval. ${\displaystyle [a,b]\subset M}$ ${\displaystyle M}$

Direct product

If and are two partial orders, their direct product is the set with the partial order ${\displaystyle (M,\leq _{M})}$ ${\displaystyle (N,\leq _{N})}$ ${\displaystyle M\times N}$

${\displaystyle (x,y)\leq _{M\times N}(u,v):\Leftrightarrow x\leq _{M}y{\text{ und }}u\leq _{N}v\quad \mathrm {f{\ddot {u}}r\;alle} \quad x,u\in M,y,v\in N.}$

The μ-function of the direct product results from the individual μ-functions as follows:

${\displaystyle \mu ((x,y),(u,v))=\mu (x,u)\mu (y,v)\quad \mathrm {f{\ddot {u}}r\;alle} \quad x,u\in M,y,v\in N}$

Relationship to the principle of inclusion and exclusion

The power set of a finite set is, with the subset relation as a relation, a partial order. Whose μ-function is ${\displaystyle P(M)}$ ${\displaystyle M}$

${\displaystyle \mu (x,y)=(-1)^{|y-x|}\quad \mathrm {f{\ddot {u}}r\ alle} \quad x,y\subset M\quad \mathrm {mit} \quad x\subset y}$,

where denotes the number of elements of . Otherwise is . ${\displaystyle |z|}$ ${\displaystyle z}$ ${\displaystyle \mu (x,y)=0}$

From this sentence emerges the principle of inclusion and exclusion .

literature

• Gian-Carlo Rota: On the Foundations of Combinatorial Theory I: Theory of Möbius Functions . In: Journal of Probability Theory and Related Areas . Vol. 2, 1964, pp. 340-368 , doi : 10.1007 / BF00531932 .