Ordnungsdimension

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Satz von Dushnik-Miller)
Zur Navigation springen Zur Suche springen

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 | Quelltext 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 | Quelltext 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 .

Einzelnachweise

[Bearbeiten | Quelltext 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!