Inzidenzalgebra

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

Formale Definition

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

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

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

$(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 $({\mathcal {I}}_{M},+,*)$ ist eine assoziative Algebra über dem Körper der reellen Zahlen. Sie besitzt ein Einselement, nämlich

$\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,

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

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

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

${\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 $\zeta *\mu =\delta$.

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

$\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 $\mu$ die Möbius-Funktion der Halbordnung.

Verallgemeinerte Möbiussche Umkehrformel

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

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

dann gilt

$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:

Dualität

Ist $M^{*}:=(M,\geq )$ die zu $(M,\leq )$ duale Halbordnung (sie entsteht durch Umkehrung der Ordnungsrelation), dann gilt

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

Segmentbildung

Betrachtet man ein Intervall $[a,b]\subset M$ als eigene Halbordnung, so ist deren μ-Funktion gleich der Einschränkung der μ-Funktion von $M$ auf dieses Intervall.

Direktes Produkt

Sind $(M,\leq _{M})$ und $(N,\leq _{N})$ zwei Halbordnungen, so ist ihr direktes Produkt die Menge $M\times N$ mit der Halbordnung

$(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.$

Die μ-Funktion des direkten Produkts ergibt sich aus den einzelnen μ-Funktionen wie folgt:

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

Beziehung zum Prinzip von Inklusion und Exklusion

Die Potenzmenge $P(M)$ einer endlichen Menge $M$ ist, mit der Teilmengenbeziehung als Relation, eine Halbordnung. Deren μ-Funktion ist

$\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$,

wobei $|z|$ die Anzahl der Elemente von $z$ bezeichnet. Ansonsten ist $\mu (x,y)=0$.

Aus diesem Satz ergibt sich das Prinzip von Inklusion und Exklusion.

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.