Inzidenzalgebra

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

Formale Definition

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

<math>\mathcal{I}_M := \{f: M \times M \rightarrow \R \, | \, x \nleq y \Rightarrow f(x,y) = 0\} </math>

Die Addition in <math>\mathcal{I}_M</math> ist punktweise definiert, während die Multiplikation durch eine Faltung gegeben ist:

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

Eigenschaften

Die algebraische Struktur <math> (\mathcal{I}_M,+,*) </math> ist eine assoziative Algebra über dem Körper der reellen Zahlen. Sie besitzt ein Einselement, nämlich

<math> \delta(a,b) := \begin{cases} 1\quad&\mbox{falls }a=b, \\ 0 &\mbox{sonst.}\end{cases}</math>

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

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

sowie die Inzidenzfunktion durch <math> n(a,b) = \zeta(a,b)-\delta(a,b). </math>

Die Zeta-Funktion ist in <math>\mathcal{I}_M</math> invertierbar, ihre Inverse <math>\mu</math> ist induktiv wie folgt definiert:

<math>\begin{alignat}{2} \mu(a,a) &= 1,& &a\in M,\\

\mu(a,b) &= -\sum_{a\leq x<b}\mu(a,x),&\qquad &a < b.\end{alignat}</math>

Diese Funktionen erfüllen die Gleichung <math>\zeta*\mu=\delta</math>.

Nimmt man für <math>M</math> die Menge der natürlichen Zahlen und die sich durch die Teilbarkeitsrelation ergebende Halbordnung, so besteht folgender Zusammenhang zwischen dieser Funktion <math>\mu</math> und der klassischen Möbius-Funktion <math>\mu_0</math>:

<math> \mu_0\left(\frac{m}{n}\right) = \mu(n,m), \quad n,m\in\mathbb{N}, n\mid m.</math>

Offenbar aus diesem Grund nennt Rota diese Funktion <math>\mu</math> die Möbius-Funktion der Halbordnung.

Verallgemeinerte Möbiussche Umkehrformel

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

dann gilt

Weitere Eigenschaften der μ-Funktion

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

Dualität

Ist <math>M^*:=(M,\geq)</math> die zu <math>(M,\leq)</math> duale Halbordnung (sie entsteht durch Umkehrung der Ordnungsrelation), dann gilt

<math>\mu^*(x,y) = \mu(y,x)\quad\mathrm{ f\ddot ur\ alle }\quad x,y\in M.</math>

Segmentbildung

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

Direktes Produkt

Sind <math>(M,\leq_M)</math> und <math>(N,\leq_N)</math> zwei Halbordnungen, so ist ihr direktes Produkt die Menge <math>M\times N</math> mit der Halbordnung

<math> (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.</math>

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

<math> \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</math>

Beziehung zum Prinzip von Inklusion und Exklusion

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

<math> \mu(x,y) = (-1)^{|y-x|}\quad\mathrm{ f\ddot ur\ alle }\quad x,y\subset M \quad\mathrm{mit}\quad x\subset y </math>,

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

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

Literatur

{{#invoke:Vorlage:Literatur|f}}