Inzidenzalgebra

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

Formale Definition

Sei $(M,\le )$ eine partiell geordnete Menge (d. h., eine Menge mit einer Halbordnung). Die Inzidenzalgebra ${ℐ}_M$ ist wie folgt definiert:

${ℐ}_M:=\{f:M\times M\to ℝ|x\nleqq y\Rightarrow f(x,y)=0\}$

Die Addition in ${ℐ}_M$ ist punktweise definiert, während die Multiplikation durch eine Faltung gegeben ist:

$(f*g)(a,b)=\sum _{a\le x\le b}f(a,x)g(x,b).$

Da die zugrunde liegende partiell geordnete Menge voraussetzungsgemäß lokal endlich ist, ist diese Summe endlich.

Eigenschaften

Die algebraische Struktur $({ℐ}_M,+,*)$ ist eine assoziative Algebra über dem Körper der reellen Zahlen. Sie besitzt ein Einselement, nämlich

$\delta (a,b):=\{\begin{array}{cc}1& \text{falls }a=b,\\ 0& \text{sonst.}\end{array}$

Rota definiert außerdem die Zeta-Funktion der Halbordnung,

$\zeta (a,b):=\{\begin{array}{cc}1& \text{falls }a\le b,\\ 0& \text{sonst,}\end{array}$

sowie die Inzidenzfunktion durch $n(a,b)=\zeta (a,b)-\delta (a,b).$

Die Zeta-Funktion ist in ${ℐ}_M$ invertierbar, ihre Inverse $\mu$ ist induktiv wie folgt definiert:

$\begin{array}{cccc}\mu (a,a)& =1,& & a\in M,\\ \mu (a,b)& =-\sum _{a\le x<b}\mu (a,x),& & a<b.\end{array}$

Diese Funktionen erfüllen die Gleichung $\zeta *\mu =\delta$.

Nimmt man für $M$ die Menge der natürlichen Zahlen und die sich durch die Teilbarkeitsrelation ergebende Halbordnung, so besteht folgender Zusammenhang zwischen dieser Funktion $\mu$ und der klassischen Möbius-Funktion ${\mu }_0$:

${\mu }_0\left(\frac{m}{n}\right)=\mu (n,m),n,m\in \mathbb{N},n\mid m.$

Offenbar aus diesem Grund nennt Rota diese Funktion $\mu$ die Möbius-Funktion der Halbordnung.

Verallgemeinerte Möbiussche Umkehrformel

Die Gleichung $\zeta *\mu =\delta$ führt zu folgender Verallgemeinerung der möbiusschen Umkehrformel: Seien $(M,\le )$ eine lokal endliche Halbordnung, $f$ eine reellwertige (oder komplexwertige) Funktion auf $M$ und $p\in M$ ein Element mit $f(x)=0$ für $x<p$. Angenommen,

$g(x):=\sum _{y\le x}f(y),$

dann gilt

$f(x)=\sum _{y\le x}g(y)\mu (y,x).$

Weitere Eigenschaften der μ-Funktion

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

Dualität

Ist $M^{*}:=(M,\ge )$ die zu $(M,\le )$ duale Halbordnung (sie entsteht durch Umkehrung der Ordnungsrelation), dann gilt

${\mu }^{*}(x,y)=\mu (y,x)\mathrm{f}\ddot{\mathrm{u}}\mathrm{r}\mathrm{a}\mathrm{l}\mathrm{l}\mathrm{e}x,y\in M.$

Segmentbildung

Betrachtet man ein Intervall $[a,b]\subset M$ als eigene Halbordnung, so ist deren μ-Funktion gleich der Einschränkung der μ-Funktion von $M$ auf dieses Intervall.

Direktes Produkt

Sind $(M,{\le }_M)$ und $(N,{\le }_N)$ zwei Halbordnungen, so ist ihr direktes Produkt die Menge $M\times N$ mit der Halbordnung

$(x,y){\le }_{M\times N}(u,v):\iff x{\le }_{M}y\text{ und }u{\le }_{N}v\mathrm{f}\ddot{\mathrm{u}}\mathrm{r}\mathrm{a}\mathrm{l}\mathrm{l}\mathrm{e}x,u\in M,y,v\in N.$

Die μ-Funktion des direkten Produkts ergibt sich aus den einzelnen μ-Funktionen wie folgt:

$\mu ((x,y),(u,v))=\mu (x,u)\mu (y,v)\mathrm{f}\ddot{\mathrm{u}}\mathrm{r}\mathrm{a}\mathrm{l}\mathrm{l}\mathrm{e}x,u\in M,y,v\in N$

Beziehung zum Prinzip von Inklusion und Exklusion

Die Potenzmenge $P(M)$ einer endlichen Menge $M$ ist, mit der Teilmengenbeziehung als Relation, eine Halbordnung. Deren μ-Funktion ist

$\mu (x,y)=(-1{)}^{|y-x|}\mathrm{f}\ddot{\mathrm{u}}\mathrm{r}\mathrm{a}\mathrm{l}\mathrm{l}\mathrm{e}x,y\subset M\mathrm{m}\mathrm{i}\mathrm{t}x\subset y$,

wobei $|z|$ die Anzahl der Elemente von $z$ bezeichnet. Ansonsten ist $\mu (x,y)=0$.

Aus diesem Satz ergibt sich das Prinzip von Inklusion und Exklusion.

Literatur

• Vorlage:Literatur