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 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
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
- 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
.
- Über die Beziehung zwischen Ordnungsdimension und Spernerzahl: Die Ordnungsdimension einer teilweise geordneten Menge
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
🔥 Top keywords: Wikipedia:HauptseiteSpezial:SucheFußball-Europameisterschaft 2024Sabine DöringKylian MbappéSpecial:MyPage/toolserverhelferleinconfig.jsAntoine GriezmannRalf RangnickFußball-EuropameisterschaftDomenico TedescoJodie DevosFußball-Europameisterschaft 2021Marko ArnautovićBastian SchweinsteigerDavid AlabaRomelu LukakuListe der größten AuslegerbrückenFußball-Weltmeisterschaft 2022SlowakeiMatija ŠarkićChristoph KramerStraßenbahnunfall in der Grüne (Iserlohn)Fußball-WeltmeisterschaftN’Golo KantéÖsterreichische BundeshymneFußball-Weltmeisterschaft 2026Aufstand vom 17. Juni 1953Der Garten der Finzi ContiniAlmuth SchultMarcel Sabitzer17. JuniDidier DeschampsHauptseiteChatGPTWikipedia:Wiki Loves Earth 2024/DeutschlandUrsula von der LeyenSchmökerJosef FritzlBettina Stark-Watzinger