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 \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{alignat}{2} \mu(a,a) &= 1,& &a\in M,\\ \mu(a,b) &= -\sum_{a\leq x<b}\mu(a,x),&\qquad &a\leq b.\end{alignat}$

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,\le)$ 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 ur\ 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_Nv\quad\mathrm{ f\ddot ur\; 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 ur\; 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 ur\ alle }\quad x,y\subset M,$

wobei $|x|$ die Anzahl der Elemente von $x$ bezeichnet.

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.