imported>Aka: Abkürzung korrigiert, Links optimiert, Links normiert

2018-04-10T21:24:16Z

Abkürzung korrigiert, Links optimiert, Links normiert

Neue Seite

Die '''Inzidenzalgebra''' einer [[Halbordnung]] wurde 1964 von [[Gian-Carlo Rota]] zur Untersuchung [[Kombinatorik|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 (Mathematik)|Faltung]] gegeben ist:
:<math> (f*g)(a,b) = \sum_{a \leq x \leq b}f(a,x)g(x,b).</math>
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 [[Assoziativgesetz|assoziative]] [[Algebra über einem Körper|Algebra]] über dem [[Körper (Algebra)|Körper]] der [[Reelle Zahlen|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ürliche Zahl|natürlichen Zahlen]] und die sich durch die [[Teilbarkeit]]srelation 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öbiussche Umkehrformel|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,
:<math> g(x) := \sum_{y\leq x}f(y), </math>
dann gilt
:<math> f(x) = \sum_{y\leq x}g(y)\mu(y,x).</math>

== 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 ==

*{{Literatur| Autor = Gian-Carlo Rota | Titel = On the Foundations of Combinatorial Theory I: Theory of Möbius Functions| Sammelwerk = Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete| Band= Vol. 2| Seiten =340–368 | Jahr = 1964 | DOI=10.1007/BF00531932}}

[[Kategorie:Algebraische Struktur]]
[[Kategorie:Kombinatorik]]

Inzidenzalgebra - Versionsgeschichte

imported>Aka: Abkürzung korrigiert, Links optimiert, Links normiert