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 ist dann definiert als die kleinste Mächtigkeit von allen Systemen linearer Ordnungsrelationen auf , durch die als Durchschnitt gemäß dem Satz von Dushnik–Miller dargestellt werden kann. Sie wird kurz mit oder bezeichnet.

Der Satz von Dushnik-Miller

Bearbeiten

Er besagt folgendes:

Jede teilweise Ordnung ist der Durchschnitt von linearen Ordnungen.
Das heißt:
Ist   eine teilweise geordnete Menge, so existiert auf der Trägermenge   ein System   von linearen Ordnungsrelationen mit
 .

Anmerkungen, Beispiele, Resultate

Bearbeiten
  • 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   einer nichtleeren Menge  , versehen mit der Teilmengenrelation, hat die Ordnungsdimension  .
  • Ist   eine natürliche Zahl, in deren Primfaktorzerlegung genau  [1] Primfaktoren vorkommen, und ist   deren Teilermenge, versehen mit der Teilerrelation, so gilt  . Für   etwa ist   und für   ist  . Zwei mögliche lineare Ordnungen, deren Durchschnitt die partielle Ordnung des letzten Beispiels ergibt, sind  , .
  • Es liegen – neben vielen anderen – die folgenden Resultate vor:
    • Über die Beziehung zwischen Ordnungsdimension und Spernerzahl: Die Ordnungsdimension einer teilweise geordneten Menge   ist höchstens so groß wie deren Spernerzahl  , sofern die Spernerzahl endlich ist.
    • Die (nach dem japanischen Mathematiker Toshio Hiraguchi[2] benannte) Ungleichung von Hiraguchi: Für eine natürliche Zahl   und eine endliche teilweise geordnete Menge   mit   Elementen beträgt die Ordnungsdimension   höchstens  .
    • 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   ist gleich der kleinsten Anzahl von linear geordneten Mengen, in deren direktes Produkt[3]   eingebettet werden kann.
    • Der (nach dem deutschen Mathematiker Egbert Harzheim benannte) Satz von Harzheim: Ist   eine natürliche Zahl und ist für jede endliche Teilmenge   einer gegebenen teilweise geordneten Menge   die Ordnungsdimension   der auf   eingeschränkten Ordnungsrelation höchstens  , so ist auch   höchstens  .

Literatur

Bearbeiten

Einzelnachweise

Bearbeiten
  1.   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!