Inzidenzalgebra
Die Inzidenzalgebra einer Halbordnung wurde 1964 von Gian-Carlo Rota zur Untersuchung kombinatorischer Sachverhalte eingeführt.
Formale Definition
[Bearbeiten | Quelltext bearbeiten]Sei eine partiell geordnete Menge (d. h., eine Menge mit einer Halbordnung). Die Inzidenzalgebra ist wie folgt definiert:
Die Addition in 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
[Bearbeiten | Quelltext bearbeiten]Die algebraische Struktur ist eine assoziative Algebra über dem Körper der reellen Zahlen. Sie besitzt ein Einselement, nämlich
Rota definiert außerdem die Zeta-Funktion der Halbordnung,
sowie die Inzidenzfunktion durch
Die Zeta-Funktion ist in invertierbar, ihre Inverse ist induktiv wie folgt definiert:
Diese Funktionen erfüllen die Gleichung .
Nimmt man für 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 :
Offenbar aus diesem Grund nennt Rota diese Funktion die Möbius-Funktion der Halbordnung.
Verallgemeinerte Möbiussche Umkehrformel
[Bearbeiten | Quelltext bearbeiten]Die Gleichung führt zu folgender Verallgemeinerung der möbiusschen Umkehrformel: Seien eine lokal endliche Halbordnung, eine reellwertige (oder komplexwertige) Funktion auf und ein Element mit für . Angenommen,
dann gilt
Weitere Eigenschaften der μ-Funktion
[Bearbeiten | Quelltext bearbeiten]Rota beweist in der zitierten Arbeit noch einige weitere Eigenschaften seiner μ-Funktion:
Dualität
[Bearbeiten | Quelltext bearbeiten]Ist die zu duale Halbordnung (sie entsteht durch Umkehrung der Ordnungsrelation), dann gilt
Segmentbildung
[Bearbeiten | Quelltext bearbeiten]Betrachtet man ein Intervall als eigene Halbordnung, so ist deren μ-Funktion gleich der Einschränkung der μ-Funktion von auf dieses Intervall.
Direktes Produkt
[Bearbeiten | Quelltext bearbeiten]Sind und zwei Halbordnungen, so ist ihr direktes Produkt die Menge mit der Halbordnung
Die μ-Funktion des direkten Produkts ergibt sich aus den einzelnen μ-Funktionen wie folgt:
Beziehung zum Prinzip von Inklusion und Exklusion
[Bearbeiten | Quelltext bearbeiten]Die Potenzmenge einer endlichen Menge ist, mit der Teilmengenbeziehung als Relation, eine Halbordnung. Deren μ-Funktion ist
- ,
wobei die Anzahl der Elemente von bezeichnet. Ansonsten ist .
Aus diesem Satz ergibt sich das Prinzip von Inklusion und Exklusion.
Literatur
[Bearbeiten | Quelltext bearbeiten]- 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.