Inzidenzalgebra

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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.

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:

Ist die zu duale Halbordnung (sie entsteht durch Umkehrung der Ordnungsrelation), dann gilt

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.

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