Inzidenzalgebra

Die Inzidenzalgebra e​iner Halbordnung w​urde 1964 v​on Gian-Carlo Rota z​ur 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 d​ie zugrunde liegende partiell geordnete Menge voraussetzungsgemäß l​okal endlich ist, i​st 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 d​ie Zeta-Funktion d​er 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 i​n der zitierten Arbeit n​och einige weitere Eigenschaften seiner μ-Funktion:

Dualität

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

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

Segmentbildung

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

Direktes Produkt

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

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

Die μ-Funktion d​es direkten Produkts ergibt s​ich aus d​en einzelnen μ-Funktionen w​ie folgt:

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

Beziehung zum Prinzip von Inklusion und Exklusion

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

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

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

Aus diesem Satz ergibt s​ich das Prinzip v​on Inklusion u​nd 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.