Endliche Posets

Matrixdarstellung

Sei \(\displaystyle P=\{a_1,\dots,a_n\}\) ein endliches Poset. Dann kann man dieses als 0-1-Matrix \(\displaystyle M=\begin{pmatrix}m_{11} &\dots & m_{1n} \\ \vdots& &\vdots \\ m_{n1} &\dots & m_{nn} \end{pmatrix}\) darstellen, wobei \(\displaystyle m_{kl}=1\) falls \(\displaystyle a_k\le a_l\), sonst \(\displaystyle m_{kl}=0\).
Wir nennen \(\displaystyle M\) die Ordnungsmatrix.
Wegen der Reflexivität ist die Hauptdiagonale von \(\displaystyle M\) mit Einsen belegt (\(\displaystyle m_kk=1\)). Die Antisymmetrie bedeutet, dass für \(\displaystyle k\ne l\) niemals \(\displaystyle m_{kl}=m_{lk}=1\) gelten kann. Und wegen der Transitivität muss für \(\displaystyle M\) gelten: ist \(\displaystyle a_{kl}=a_{lm}=1\), so auch ist auch \(\displaystyle a_{km}=1\).
Im weiteren Verlauf werden wir sehen, dass man jede Ordnungsmatrix durch Umordnung der Elemente in eine obere Diagonalform bringen kann, wo unter der Hauptdiagonalen nur Nullen stehen, also \(\displaystyle a_{kl}=0\) für \(\displaystyle k>l\).
 
 

Insotone Abbildungen in die ganzen Zahlen

Für \(\displaystyle a\in P\) bezeichnen wir mit \(\displaystyle \Mi(a):=\Mi(\{a\})\) die Minorante von \(\displaystyle a\) und mit \(\displaystyle \Ma(a):=\Ma(\{a\})\) die Majorante von \(\displaystyle a\).

Satz A9TA

Sei \(\displaystyle \my, \ny: P\to \Z\) mit \(\displaystyle \my(a)=|\Mi(a)|\) und \(\displaystyle \ny(a)=|\Ma(a)|\) für \(\displaystyle a\in P\). Dann sind \(\displaystyle \my\) und \(\displaystyle -\ny\) isoton.

Beweis

Sei \(\displaystyle a\le b\). \(\displaystyle x\in\Mi(a)\implies x\le a\le b\), also \(\displaystyle x\in\Mi(b)\), daher \(\displaystyle \Mi(a)\subseteq \Mi(b)\) \(\displaystyle \implies\) \(\displaystyle \my(a)=|\Mi(a)|\le |\Mi(b)|=\my(b)\).
\(\displaystyle x\in\Ma(b)\implies x\ge b\ge a\), also \(\displaystyle x\in\Ma(a)\), daher \(\displaystyle \Ma(a)\supseteq \Ma(b)\) \(\displaystyle \implies\) \(\displaystyle \ny(a)=|\Ma(a)|\ge |\Ma(b)|=\ny(b)\). \(\displaystyle \qed\)

Bemerkungen

In einer Ordnungsmatrix \(\displaystyle M\) sind \(\displaystyle \my\)-Werte genau die Spaltensummen und die \(\displaystyle \ny\)-Werte die Zeilensummen.
Sei \(\displaystyle P\) ein \(\displaystyle n\)-elemetiges Poset, dann gilt für \(\displaystyle p\in P\) \(\displaystyle 1\le \my(p),\ny(p)\le n\). (wegen \(\displaystyle a\in\Mi(a)\) bzw. \(\displaystyle a\in\Ma(a)\) und die Minoranten und Majoranten können maximal \(\displaystyle n\) Elemente enthalten.)
Sei nun \(\displaystyle P=\{p_1,\dots,p_n\}\), dann gilt \(\displaystyle \sum\limits_{k=1}^n \my(p_k)=\sum\limits_{k=1}^n \ny(p_k)\), denn beide Summen entsprechen in der Ordnungsmatrix der Anzahl der Einsen.

Jede Wissenschaft bedarf der Mathematik, die Mathematik bedarf keiner.

Jakob I. Bernoulli

Copyright- und Lizenzinformationen: Diese Seite ist urheberrechtlich geschützt und darf ohne Genehmigung des Autors nicht weiterverwendet werden.
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе