Ordnungsdimension

In der Ordnungstheorie, einem der Teilgebiete der Mathematik, versteht man unter der Ordnungsdimension eine bestimmte Kardinalzahl, die jeder teilweise geordneten Menge zugeordnet ist. Grundlage dieser Zuordnung ist ein auf die beiden Mathematiker Ben Dushnik und Edwin W. Miller zurückgehender Lehrsatz, der als Satz von Dushnik-Miller bekannt ist und besagt, dass jede teilweise Ordnung die Schnittmenge von linearen Ordnungen ist. Die Ordnungsdimension einer teilweise geordneten Menge ${\displaystyle (X,\leq )}$ ist dann definiert als die kleinste Mächtigkeit von allen Systemen linearer Ordnungsrelationen auf ${\displaystyle X}$, durch die ${\displaystyle \leq }$ als Durchschnitt gemäß dem Satz von Dushnik–Miller dargestellt werden kann. Sie wird kurz mit ${\displaystyle \operatorname {odim} (X,\leq )}$ oder ${\displaystyle \dim(X,\leq )}$ bezeichnet.

Der Satz von Dushnik-Miller

Er besagt folgendes:

Jede teilweise Ordnung ist der Durchschnitt von linearen Ordnungen.

Das heißt:

Ist ${\displaystyle (X,\leq )}$ eine teilweise geordnete Menge, so existiert auf der Trägermenge ${\displaystyle X}$ ein System ${\displaystyle {\mathfrak {L}}}$ von linearen Ordnungsrelationen mit

${\displaystyle \leq \;=\,\bigcap _{L\in {\mathfrak {L}}}\,L}$.

Anmerkungen, Beispiele, Resultate

• Statt von der Ordnungsdimension sprechen manche Autoren auch von der Dushnik–Miller-Dimension.
• Der Satz von Dushnik-Miller ist eng mit dem Lemma von Szpilrajn verwandt.
• Die Potenzmenge ${\displaystyle {\mathcal {P}}(X)}$ einer nichtleeren Menge ${\displaystyle X}$, versehen mit der Teilmengenrelation, hat die Ordnungsdimension ${\displaystyle \operatorname {odim} ({\mathcal {P}}(X),\subseteq )=|X|}$.
• Ist ${\displaystyle N}$ eine natürliche Zahl, in deren Primfaktorzerlegung genau ${\displaystyle \omega (N)}$[1] Primfaktoren vorkommen, und ist ${\displaystyle (X,\leq )=(T_{N},\mid )}$ deren Teilermenge, versehen mit der Teilerrelation, so gilt ${\displaystyle \operatorname {odim} (T_{N},\mid )=\omega (N)}$. Für ${\displaystyle N=360=2^{3}\cdot 3^{2}\cdot 5}$ etwa ist ${\displaystyle \operatorname {odim} (T_{360},\mid )=\omega (360)=3}$ und für ${\displaystyle N=26411=7^{4}\cdot 11}$ ist ${\displaystyle \operatorname {odim} (T_{26411},\mid )=\omega (26411)=2}$.
• Es liegen – neben vielen anderen – die folgenden Resultate vor:
  • Über die Beziehung zwischen Ordnungsdimension und Spernerzahl: Die Ordnungsdimension einer teilweise geordneten Menge ${\displaystyle (X,\leq )}$ ist höchstens so groß wie deren Spernerzahl ${\displaystyle \operatorname {w} (X,\leq )}$, sofern die Spernerzahl endlich ist.
  • Die (nach dem japanischen Mathematiker Toshio Hiraguchi[2] benannte) Ungleichung von Hiraguchi: Für eine natürliche Zahl ${\displaystyle n\geq 4}$ und eine endliche teilweise geordnete Menge ${\displaystyle (X,\leq )}$ mit ${\displaystyle |X|=n}$ Elementen beträgt die Ordnungsdimension ${\displaystyle \operatorname {odim} (X,\leq )}$ höchstens ${\displaystyle {\frac {n}{2}}}$.
  • Der (nach dem norwegischen Mathematiker Øystein Ore und Toshio Hiraguchi benannte) Satz von Hiraguchi-Ore, welcher einen alternativen Zugang zum Begriff der Ordnungsdimension bietet: Die Ordnungsdimension einer teilweise geordneten Menge ${\displaystyle (X,\leq )}$ ist gleich der kleinsten Anzahl von linear geordneten Mengen, in deren direktes Produkt[3] ${\displaystyle (X,\leq )}$ eingebettet werden kann.
  • Der (nach dem deutschen Mathematiker Egbert Harzheim benannte) Satz von Harzheim: Ist ${\displaystyle N}$ eine natürliche Zahl und ist für jede endliche Teilmenge ${\displaystyle E}$ einer gegebenen teilweise geordneten Menge ${\displaystyle (X,\leq )}$ die Ordnungsdimension ${\displaystyle \operatorname {odim} (E,{{E\times E}\;\cap \leq })}$ der auf ${\displaystyle E}$ eingeschränkten Ordnungsrelation höchstens ${\displaystyle N}$, so ist auch ${\displaystyle \operatorname {odim} (X,\leq )}$ höchstens ${\displaystyle N}$.

Literatur

• Ben Dushnik, E. W. Miller: Partially ordered sets. In: American Journal of Mathematics. Band 63, 1941, S. 600–610, doi:10.2307/2371374, JSTOR:2371374 (ams.org).
• Bernhard Ganter: Diskrete Mathematik: Geordnete Mengen (= Springer-Lehrbuch). Springer Spektrum, Berlin, Heidelberg 2013, ISBN 978-3-642-37499-9, S. 47 ff., doi:10.1007/978-3-642-37500-2.
• Egbert Harzheim: Ordered Sets (= Advances in Mathematics. Band 7). Springer Verlag, New York 2005, ISBN 0-387-24219-8, S. 206 ff. (MR2127991).
• Wacław Sierpiński: Cardinal and Ordinal Numbers. Panstwowe Wydawnictwo Naukowe, Warschau 1958, S. 188 (MR0095787).

Einzelnachweise

1. ${\displaystyle N\mapsto \omega (N)}$ ist eine der Arithmetischen Funktionen.
2. Statt der Transkription „Toshio Hiraguchi“ findet man auch die Transkription „Tosio Hiraguti“
3. Versehen mit der komponentenweise gebildeten teilweisen Ordnung!