Endliche Posets

Matrixdarstellung

Sei P={a1,…,an}P=\{a_1,\dots,a_n\} ein endliches Poset. Dann kann man dieses als 0-1-Matrix M=(m11…m1n⋮⋮mn1…mnn)M=\begin{pmatrix}m_{11} &\dots & m_{1n} \\ \vdots& &\vdots \\ m_{n1} &\dots & m_{nn} \end{pmatrix} darstellen, wobei mkl=1m_{kl}=1 falls ak≤ala_k\le a_l, sonst mkl=0m_{kl}=0.
Wir nennen MM die Ordnungsmatrix.
Wegen der Reflexivität ist die Hauptdiagonale von MM mit Einsen belegt (mkk=1m_kk=1). Die Antisymmetrie bedeutet, dass für k≠lk\ne l niemals mkl=mlk=1m_{kl}=m_{lk}=1 gelten kann. Und wegen der Transitivität muss für MM gelten: ist akl=alm=1a_{kl}=a_{lm}=1, so auch ist auch akm=1a_{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 akl=0a_{kl}=0 für k>lk>l.

Insotone Abbildungen in die ganzen Zahlen

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

Satz A9TA

Sei μ,ν:P→Z\my, \ny: P\to \Z mit μ(a)=∣Mi⁡(a)∣\my(a)=|\Mi(a)| und ν(a)=∣Ma⁡(a)∣\ny(a)=|\Ma(a)| für a∈Pa\in P. Dann sind μ\my und −ν-\ny isoton.

Beweis

Sei a≤ba\le b. x∈Mi⁡(a)  ⟹  x≤a≤bx\in\Mi(a)\implies x\le a\le b, also x∈Mi⁡(b)x\in\Mi(b), daher Mi⁡(a)⊆Mi⁡(b)\Mi(a)\subseteq \Mi(b)   ⟹  \implies μ(a)=∣Mi⁡(a)∣≤∣Mi⁡(b)∣=μ(b)\my(a)=|\Mi(a)|\le |\Mi(b)|=\my(b).
x∈Ma⁡(b)  ⟹  x≥b≥ax\in\Ma(b)\implies x\ge b\ge a, also x∈Ma⁡(a)x\in\Ma(a), daher Ma⁡(a)⊇Ma⁡(b)\Ma(a)\supseteq \Ma(b)   ⟹  \implies ν(a)=∣Ma⁡(a)∣≥∣Ma⁡(b)∣=ν(b)\ny(a)=|\Ma(a)|\ge |\Ma(b)|=\ny(b). □\qed

Bemerkungen

In einer Ordnungsmatrix MM sind μ\my-Werte genau die Spaltensummen und die ν\ny-Werte die Zeilensummen.
Sei PP ein nn-elemetiges Poset, dann gilt für p∈Pp\in P 1≤μ(p),ν(p)≤n1\le \my(p),\ny(p)\le n. (wegen a∈Mi⁡(a)a\in\Mi(a) bzw. a∈Ma⁡(a)a\in\Ma(a) und die Minoranten und Majoranten können maximal nn Elemente enthalten.)
Sei nun P={p1,…,pn}P=\{p_1,\dots,p_n\}, dann gilt ∑k=1nμ(pk)=∑k=1nν(pk)\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.
 
 

Die Furcht vor der Mathematik steht der Angst erheblich näher als der Ehrfurcht.

Felix Auerbach

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е
Datenschutzerklärung

 

Algebra