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