Inzidenzalgebra

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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

Formale Definition[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

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

Dualität[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]