Dichte Ordnung
Dichte Ordnung ist ein mathematischer Begriff aus dem Gebiet der Ordnungstheorie. Eine Ordnung heißt dicht, wenn zwischen je zwei Elementen ein drittes liegt.
Definition
Eine lineare Ordnung < auf einer Menge heißt dicht, falls
- für alle mit gibt es ein mit ,
das heißt, für je zwei verschiedene Elemente von gibt es ein drittes, das zwischen den beiden liegt.[1]
Beispiele
- Die Menge der rationalen Zahlen mit der natürlichen Anordnung < ist dicht, denn sind mit , so ist ebenfalls eine rationale Zahl und diese liegt zwischen und .
- Die Menge der reellen Zahlen mit der natürlichen Anordnung < ist dicht, wobei die Begründung wie für geführt werden kann. liegt ordnungsdicht.
- Die Menge der ganzen Zahlen mit der natürlichen Anordnung < ist nicht dicht, da zwischen zwei aufeinander folgenden ganzen Zahlen keine dritte ganze Zahl liegt.
- Definitionsgemäß ist eine einelementige Menge mit der eindeutig bestimmten linearen Ordnung auf ihr dicht geordnet, da es keine zwei Elemente gibt, für die die definierende Bedingung erfüllt sein müsste. Manche Autoren schließen diesen trivialen Fall aus, indem sie zusätzlich fordern, dass die Menge mindestens zwei Elemente haben muss.
Eigenschaften
Universelle Eigenschaft
Nach einem Satz von Cantor enthalten nichtleere abzählbare, dichte Ordnungen ohne kleinstes und größtes Element alle anderen abzählbaren, linearen Ordnungen, das heißt, sie haben folgende universelle Eigenschaft:[2]
Es sei eine nichtleere abzählbare, dichte, linear geordnete Menge ohne kleinstes und größtes Element und eine beliebige abzählbare, linear geordnete Menge. Dann gibt es eine injektive Abbildung mit
Isomorphieklassen abzählbarer, dichter, linear geordneter Mengen
Nach einem weiteren Satz von Cantor sind je zwei nichtleere, abzählbare, dichte, linear geordnete Mengen ohne kleinstes oder größtes Element ordnungsisomorph.[3][4] Das heißt: Sind und zwei solche Mengen und sind beide Ordnungen mit < bezeichnet, so gibt es eine bijektive Abbildung mit .
Die folgenden Beispiele sind daher alle isomorph:
- mit der natürlichen Ordnung
- mit der natürlichen Ordnung
- mit der natürlichen Ordnung
- mit der natürlichen Ordnung
- mit der natürlichen Ordnung
- mit der lexikographischen Ordnung
Verzichtet man auf die Bedingungen über kleinste und größte Elemente, so erhält man:[5]
Jede abzählbare, dichte, linear geordnete Menge ist isomorph zu einer der folgenden sechs Mengen, jeweils mit ihrer natürlichen Ordnung versehen:
- , , , , ,
Eine Charakterisierung des Kontinuums
Eine Ordnung heißt vollständig, wenn jede nach oben beschränkte Menge ein Supremum hat. Nach einem weiteren Satz von Cantor lässt sich das Kontinuum, das heißt die Menge der reellen Zahlen, ordnungstheoretisch wie folgt charakterisieren: mit der natürlichen Ordnung ist bis auf Ordnungsisomorphie die einzige vollständige, lineare Ordnung, die eine abzählbare, ordnungsdichte und zu ordnungsisomorphe Teilmenge enthält.[6]
Vollständigkeit
Je zwei nichtleere dichte lineare Ordnungen ohne kleinstes und größtes Element sind elementar äquivalent, wie sich aus dem Satz von Fraïssé ergibt (siehe hier für einen Beweis). Die Theorie der dichten linearen Ordnungen ohne Endpunkte ist also vollständig.[7] Insbesondere lassen sich die Ordnungstheorien von und in der Prädikatenlogik erster Stufe nicht unterscheiden, Eigenschaften wie die Vollständigkeit lassen sich in ihr nicht formulieren.
Quantorenelimination
Die Theorie der dichten linearen Ordnungen ohne Endpunkte erlaubt Quantorenelimination. Jede Formel der Prädikatenlogik erster Stufe ist damit äquivalent zu einer booleschen Kombination atomarer Aussagen der Form .[8] Zu jedem Tupel von Elementen einer dichten linearen Ordnung ohne Endpunkte ergibt sich somit der zugehörige Typ allein aus den gültigen und nicht gültigen Vergleichen der Elemente des Tupels. Jede dichte lineare Ordnung ohne Endpunkte ist somit ein atomares Modell.[9]
Allgemeine dichte lineare Ordnungen erlauben Quantorenelimination, wobei zusätzlich Aussagen der Form „es existiert ein kleinstes Element“, „es existiert ein größtes Element“, „ ist das kleinste Element“ und „ ist das größte Element“ in den booleschen Kombinationen zugelassen werden müssen.[8]
Verallgemeinerung: κ-Dichtheit
Sei eine Kardinalzahl. Eine linear geordnete Menge heißt -dicht, wenn für je zwei Mengen mit , sodass alle Elemente in kleiner als alle in sind, ein Element existiert, das größer als alle Elemente in A und kleiner als alle in B ist.[10] -dichte Ordnungen sind gerade die dichten linearen Ordnungen ohne Endpunkte.
Saturiertheit
Eine dichte lineare Ordnung ohne Endpunkte ist genau dann -saturiert, wenn sie -dicht ist.[10] Eine (und damit bis auf Isomorphie genau eine) saturierte dichte lineare Ordnung ohne Endpunkte der Kardinalität (d. h., sie ist -saturiert) existiert genau dann, wenn regulär ist und .[11][12] Die Betrachtung dieser dichten linearen Ordnung und allgemeiner der Saturiertheit geht auf Texte von Felix Hausdorff aus den Jahren 1908[13][14] und 1914[15][16] zurück.
Kategorizität
Für jede überabzählbare Kardinalzahl existieren genau paarweise nicht-isomorphe dichte lineare Ordnungen ohne Endpunkte,[17] während bis auf Isomorphie nur eine einzige abzählbare dichte lineare Ordnung ohne Endpunkte existiert (, welches saturiert ist). Die Theorie der dichten linearen Ordnungen ohne Endpunkte ist damit -kategorisch, doch nicht -kategorisch.
Siehe auch
- Dichte Teilordnung
- Eine zerstreute Ordnung ist eine lineare Ordnung, die keine nicht-triviale dichte Teilordnung enthält
Einzelnachweise
- Thomas Jech: Set Theory. Springer-Verlag, 2003, ISBN 3-540-44085-2, Definition 4.2
- Joseph G. Rosenstein: Linear Orderings. In: Pure & Applied Mathematics, Academic Press, Oktober 1982, Satz 2.5
- Joseph G. Rosenstein: Linear Orderings. In: Pure & Applied Mathematics, Academic Press, Oktober 1982, Satz 2.8
- Ernest Schimmerling: A Course on Set Theory. Cambridge University Press, 2011, ISBN 1-107-00817-4, Theorem 6.5
- Joseph G. Rosenstein: Linear Orderings, Pure & Applied Mathematics, Academic Press Inc (Oktober 1982), Korollar 2.9
- Thomas Jech: Set Theory. Springer-Verlag (2003), ISBN 3-540-44085-2, Satz 4.3
- Heinz-Dieter Ebbinghaus, Jörg Flum, Wolfgang Thomas: Einführung in die mathematische Logik. Spektrum Akademischer Verlag (1996), ISBN 3-8274-0130-5, XII, §2, 2.2
- Wilfrid Hodges: Model theory. Cambridge University Press, 1993, ISBN 0-521-30442-3, S. 67.
- Chen Chung Chang, Howard Jerome Keisler: Model Theory (= Studies in Logic and the Foundations of Mathematics. Band 73). Elsevier, 1990, ISBN 0-444-88054-2, S. 97.
- Gerald E. Sacks: Saturated Model Theory. w. A. Benjamin, 1972, ISBN 0-8053-8380-8, S. 77.
- Andrey I. Bovykin: On order-types of models of arithmetic. 2000, S. 16 (logic.pdmi.ras.ru [PDF]).
- David Marker: Model Theory. An Introduction. Springer, New York 2002, ISBN 0-387-98760-6, S. 142.
- Hodges, S. 485.
- Felix Hausdorff: Grundzüge einer Theorie der geordneten Mengen. In: Mathematische Annalen. Band 65, 1908 (online).
- Chang und Keisler, S. 3, 613.
- Felix Hausdorff: Grundzüge der Mengenlehre. Leipzig 1914.
- Chang und Keisler, S. 179.