Die Inzidenzalgebra einer Halbordnung wurde 1964 von Gian-Carlo Rota zur Untersuchung kombinatorischer Sachverhalte eingeführt.

Formale Definition

Sei ${\displaystyle (M,\leq )}$ eine partiell geordnete Menge (d. h., eine Menge mit einer Halbordnung). Die Inzidenzalgebra ${\displaystyle {\mathcal {I}}_{M}}$ ist wie folgt definiert:

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

Die Addition in ${\displaystyle {\mathcal {I}}_{M}}$ ist punktweise definiert, während die Multiplikation durch eine Faltung gegeben ist:

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

Da die zugrunde liegende partiell geordnete Menge voraussetzungsgemäß lokal endlich ist, ist diese Summe endlich.

Eigenschaften

Die algebraische Struktur ${\displaystyle ({\mathcal {I}}_{M},+,*)}$ ist eine assoziative Algebra über dem Körper der reellen Zahlen. Sie besitzt ein Einselement, nämlich

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

Rota definiert außerdem die Zeta-Funktion der Halbordnung,

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

sowie die Inzidenzfunktion durch ${\displaystyle n(a,b)=\zeta (a,b)-\delta (a,b).}$

Die Zeta-Funktion ist in ${\displaystyle {\mathcal {I}}_{M}}$ invertierbar, ihre Inverse ${\displaystyle \mu }$ ist induktiv wie folgt definiert:

${\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}}}$

Diese Funktionen erfüllen die Gleichung ${\displaystyle \zeta *\mu =\delta }$.

Nimmt man für ${\displaystyle M}$ die Menge der natürlichen Zahlen und die sich durch die Teilbarkeitsrelation ergebende Halbordnung, so besteht folgender Zusammenhang zwischen dieser Funktion ${\displaystyle \mu }$ und der klassischen Möbius-Funktion ${\displaystyle \mu _{0}}$:

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

Offenbar aus diesem Grund nennt Rota diese Funktion ${\displaystyle \mu }$ die Möbius-Funktion der Halbordnung.

Verallgemeinerte Möbiussche Umkehrformel

Die Gleichung ${\displaystyle \zeta *\mu =\delta }$ führt zu folgender Verallgemeinerung der möbiusschen Umkehrformel: Seien ${\displaystyle (M,\leq )}$ eine lokal endliche Halbordnung, ${\displaystyle f}$ eine reellwertige (oder komplexwertige) Funktion auf ${\displaystyle M}$ und ${\displaystyle p\in M}$ ein Element mit ${\displaystyle f(x)=0}$ für ${\displaystyle x<p}$. Angenommen,

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

dann gilt

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

Weitere Eigenschaften der μ-Funktion

Rota beweist in der zitierten Arbeit noch einige weitere Eigenschaften seiner μ-Funktion:

Literatur

• Gian-Carlo Rota: On the Foundations of Combinatorial Theory I: Theory of Möbius Functions. In: Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete. Vol. 2, 1964, S. 340–368, doi:10.1007/BF00531932.