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

Formale Definition

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

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

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

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

Dualität

Bearbeiten

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

 

Segmentbildung

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

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

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