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) = ζ(a,b) − δ(a,b).

Die Zeta-Funktion ist in $\mathcal{I}_M$ invertierbar, ihre Inverse μ 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 ζ * μ = δ.

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 μ und der klassischen Möbius-Funktion μ₀:

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

Verallgemeinerte Möbiussche Umkehrformel

Die Gleichung ζ * μ = δ 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.