Dichte Ordnungen

Eine wichtige Eigenschaft für unendliche Ordnungen ist:

Definition (dicht)

Eine Ordnung < auf A heißt dicht, falls gilt:

(D) ∀a, b  ∈  A (a < b → ∃c  ∈  A a < c < b).

Dichtheit bedeutet, dass zwischen je zwei vergleichbaren Elementen a und b der Ordnung noch ein weiteres Element c liegt. Weiter liegt dann auch zwischen a und c noch ein Element d usw. Dies zeigt, dass zwischen zwei vergleichbaren Elementen sogar unendlich viele Elemente liegen. Mit Ausnahme der Ordnungen, die nur aus paarweise unvergleichbaren Elementen bestehen, gibt es also keine endliche dichte Ordnung. Die Ordnung auf ℚ ist dicht, denn für alle rationalen Zahlen a < b ist das arithmetische Mittel (a + b)/2 der beiden Zahlen eine rationale Zahle, die zwischen a und b liegt. Aus diesem Blickwinkel ist es bemerkenswert, dass es irrationale Zahlen gibt: Obwohl zwischen zwei rationalen Zahlen immer unendlich viele weitere rationale Zahlen liegen, gibt es immer noch Lücken in ℚ, die beim Übergang von ℚ zu ℝ mit neuen Zahlen gefüllt werden. Dieses Phänomen tritt aber bereits mit einer Teilmenge von ℚ auf:

Beispiel

Sei A = { a/2ⁿ | a  ∈  ℤ, n  ∈  ℕ }. Dann ist A mit der von ℚ ererbten Ordnung dicht (wie erneut die Bildung von arithmetischen Mitteln zeigt). Aber es gilt zum Beispiel 1/3  ∉  A, sodass 1/3 aus der Sicht von A eine Lücke darstellt.

Wir betrachten auch wieder unsere Ordnungen auf den endlichen Folgen.

Beispiele

(1)

Sei A = { 0, 1 }. Die Ordnung <_lex auf Seq_A ist nicht dicht. Denn ist s  ∈  Seq_A und t = s0 die um 0 verlängerte Folge s, so gilt s <_lex t, aber es gibt keine Elemente zwischen s und s0. Analog ist die Ordnung <_KB nicht dicht, wobei nun zwischen s1 und s keine Elemente liegen. Und auch die Ordnung <_shortlex auf Seq_A ist nicht dicht, da sich zum Beispiel zwischen 0 und 1 keine Elemente befinden.

(2)

Sei ℤ versehen mit der üblichen linearen Ordnung. Dann ist die Ordnung <_lex auf Seq_ℤ dicht. Für alle s  ∈  Seq_ℤ und alle a  ∈  ℤ gilt

s <_lex sb <_lex sa für alle b  ∈  ℤ mit b < a,

woraus die Dichtheit folgt (Übung). Analoges gilt für <_KB. Dagegen ist <_shortlex nicht dicht, da für alle Folgen s  ∈  Seq_ℤ und alle a  ∈  ℤ zwischen den Folgen sa und s(a + 1) keine Elemente der Ordnung liegen.