imported>Hayek2020: /* growthexperiments-addlink-summary-summary:6|0|0 */

2021-10-23T09:47:45Z

growthexperiments-addlink-summary-summary:6|0|0

Neue Seite

'''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 [[Ordnungsrelation|lineare Ordnung]] < auf einer Menge <math>X</math> heißt '''dicht''', falls
: für alle <math>x,z\in X</math> mit <math>x<z</math> gibt es ein <math>y\in X</math> mit <math>x<y<z</math>,
das heißt, für je zwei verschiedene Elemente von <math>X</math> gibt es ein drittes, das zwischen den beiden liegt.<ref>[[Thomas Jech]]: ''Set Theory''. Springer-Verlag, 2003, ISBN 3-540-44085-2, Definition 4.2</ref>

== Beispiele ==
* Die Menge <math>\Q</math> der [[Rationale Zahl|rationalen Zahlen]] mit der natürlichen Anordnung < ist dicht, denn sind <math>a,b\in \Q</math> mit <math>a<b</math>, so ist <math>\textstyle \frac{a+b}{2}</math> ebenfalls eine rationale Zahl und diese liegt zwischen <math>a</math> und <math>b</math>.
* Die Menge <math>\R</math> der [[Reelle Zahl|reellen Zahlen]] mit der natürlichen Anordnung < ist dicht, wobei die Begründung wie für <math>\Q</math> geführt werden kann. <math>\Q\subset \R</math> liegt ordnungsdicht.
* Die Menge <math>\Z</math> der [[Ganze Zahl|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 <math>x<y</math> 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 [[Georg Cantor|Cantor]] enthalten nichtleere [[Abzählbarkeit|abzählbare]], dichte Ordnungen ohne [[Größtes und kleinstes Element|kleinstes und größtes Element]] alle anderen abzählbaren, linearen Ordnungen, das heißt, sie haben folgende [[universelle Eigenschaft]]:<ref>Joseph G. Rosenstein: ''Linear Orderings''. In: ''Pure & Applied Mathematics'', Academic Press, Oktober 1982, Satz 2.5</ref>

Es sei <math>(X,<)</math> eine nichtleere abzählbare, dichte, linear geordnete Menge ohne kleinstes und größtes Element und <math>(Y,<)</math> eine beliebige abzählbare, linear geordnete Menge. Dann gibt es eine injektive Abbildung <math>f\colon Y\rightarrow X</math> mit <math>\forall x,y\in Y: x<y \Leftrightarrow f(x) < f(y)</math>

=== 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.<ref>Joseph G. Rosenstein: ''Linear Orderings''. In: ''Pure & Applied Mathematics'', Academic Press, Oktober 1982, Satz 2.8</ref><ref>Ernest Schimmerling: ''A Course on Set Theory''. Cambridge University Press, 2011, ISBN 1-107-00817-4, Theorem 6.5</ref>
Das heißt: Sind <math>X</math> und <math>Y</math> zwei solche Mengen und sind beide Ordnungen mit < bezeichnet, so gibt es eine [[Bijektive Funktion|bijektive]] Abbildung <math>f\colon X\rightarrow Y</math> mit <math>\forall x,y\in X: x<y \Leftrightarrow f(x) < f(y)</math>.

Die folgenden Beispiele sind daher alle isomorph:
* <math>\Q</math> mit der natürlichen Ordnung
* <math>\Q+\sqrt{2}\cdot \Q = \{a+\sqrt{2}\cdot b;\, a,b\in \Q\} </math> mit der natürlichen Ordnung
* <math>(0,1)\cap \Q</math> mit der natürlichen Ordnung
* <math>((-\infty,0)\cap\Q) \cup ((1,\infty)\cap\Q)</math> mit der natürlichen Ordnung
* <math>((-\infty,0]\cap\Q) \cup ((1,\infty)\cap\Q)</math> mit der natürlichen Ordnung
* <math>\Q^2</math> mit der [[Lexikographische Ordnung|lexikographischen Ordnung]]

Verzichtet man auf die Bedingungen über kleinste und größte Elemente, so erhält man:<ref>Joseph G. Rosenstein: ''Linear Orderings'', Pure & Applied Mathematics, Academic Press Inc (Oktober 1982), Korollar 2.9</ref>

Jede abzählbare, dichte, linear geordnete Menge ist isomorph zu einer der folgenden sechs Mengen, jeweils mit ihrer natürlichen Ordnung versehen:
: <math>\emptyset</math>, <math>\{0\}</math>, <math>(0,1)\cap \Q</math>, <math>[0,1)\cap \Q</math>, <math>(0,1]\cap \Q</math>, <math>[0,1]\cap \Q</math>

=== 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 <math>\R</math> der reellen Zahlen, ordnungstheoretisch wie folgt charakterisieren:
<math>\R</math> mit der natürlichen Ordnung ist bis auf Ordnungsisomorphie die einzige vollständige, lineare Ordnung, die eine abzählbare, ordnungsdichte und zu <math>\Q</math> ordnungsisomorphe [[Teilmenge]] enthält.<ref>[[Thomas Jech]]: ''Set Theory''. Springer-Verlag (2003), ISBN 3-540-44085-2, Satz 4.3</ref>

=== Vollständigkeit ===
Je zwei nichtleere dichte lineare Ordnungen ohne kleinstes und größtes Element sind [[Elementare Äquivalenz|elementar äquivalent]], wie sich aus dem [[Satz von Fraïssé]] ergibt (siehe [[Satz von Fraïssé#Anwendung|hier]] für einen Beweis). Die Theorie der dichten linearen Ordnungen ohne Endpunkte ist also [[Vollständigkeit (Logik)|vollständig]].<ref>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</ref> Insbesondere lassen sich die Ordnungstheorien von <math>\Q</math> und <math>\R</math> 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 <math>x<y</math>.<ref name="hodgesquantelim">{{Literatur |Autor=[[Wilfrid Hodges]] |Titel=Model theory |Verlag=Cambridge University Press |Datum=1993 |ISBN=0-521-30442-3 |Seiten=67}}</ref> Zu jedem [[Tupel]] von Elementen einer dichten linearen Ordnung ohne Endpunkte ergibt sich somit der zugehörige [[Typ (Modelltheorie)|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]].<ref>{{Literatur |Autor=Chen Chung Chang, [[Howard Jerome Keisler]] |Titel=Model Theory |Reihe=Studies in Logic and the Foundations of Mathematics |BandReihe=73 |Verlag=Elsevier |Datum=1990 |ISBN=0-444-88054-2 |Seiten=97}}</ref>

Allgemeine dichte lineare Ordnungen erlauben Quantorenelimination, wobei zusätzlich Aussagen der Form „es existiert ein kleinstes Element“, „es existiert ein größtes Element“, „<math>x</math> ist das kleinste Element“ und „<math>x</math> ist das größte Element“ in den booleschen Kombinationen zugelassen werden müssen.<ref name="hodgesquantelim" />

== Verallgemeinerung: κ-Dichtheit ==
Sei <math>\kappa</math> eine [[Kardinalzahl (Mathematik)|Kardinalzahl]]. Eine linear geordnete Menge <math>(X,<)</math> heißt <math>\kappa</math>-dicht, wenn für je zwei Mengen <math>A,B\subset X</math> mit <math>\left|A\right|,\left|B\right|<\kappa</math>, sodass alle Elemente in <math>A</math> kleiner als alle in <math>B</math> sind, ein Element <math>x\in X</math> existiert, das größer als alle Elemente in A und kleiner als alle in B ist.<ref name="smt">{{Literatur |Autor=[[Gerald E. Sacks]] |Titel=Saturated Model Theory |Verlag=w. A. Benjamin |Datum=1972 |ISBN=0-8053-8380-8 |Seiten=77}}</ref> <math>\aleph_0</math>-dichte Ordnungen sind gerade die dichten linearen Ordnungen ohne Endpunkte.

== Saturiertheit ==
Eine dichte lineare Ordnung ohne Endpunkte ist genau dann <math>\kappa</math>-[[Saturiertheit (Modelltheorie)|saturiert]], wenn sie <math>\kappa</math>-dicht ist.<ref name="smt" /> Eine (und damit bis auf Isomorphie genau eine) saturierte dichte lineare Ordnung ohne Endpunkte der Kardinalität <math>\kappa</math> (d. h., sie ist <math>\kappa</math>-saturiert) existiert genau dann, wenn <math>\kappa</math> [[Reguläre Kardinalzahl|regulär]] ist und <math>\kappa^{<\kappa}=\kappa</math>.<ref>{{Literatur |Autor=Andrey I. Bovykin |Titel=On order-types of models of arithmetic |Datum=2000 |Seiten=16 |Online=[https://logic.pdmi.ras.ru/~andrey/phd.pdf logic.pdmi.ras.ru] |Format=PDF |KBytes=}}</ref><ref>{{Literatur |Autor=David Marker |Titel=Model Theory |TitelErg=An Introduction |Verlag=Springer |Ort=New York |Datum=2002 |ISBN=0-387-98760-6 |Seiten=142}}</ref> Die Betrachtung dieser dichten linearen Ordnung und allgemeiner der Saturiertheit geht auf Texte von [[Felix Hausdorff]] aus den Jahren 1908<ref>Hodges, S. 485.</ref><ref>{{Literatur |Autor=[[Felix Hausdorff]] |Titel=Grundzüge einer Theorie der geordneten Mengen |Sammelwerk=[[Mathematische Annalen]] |Band=65 |Datum=1908 |Online=[https://gdz.sub.uni-goettingen.de/id/PPN235181684_0065 online]}}</ref> und 1914<ref>Chang und Keisler, S. 3, 613.</ref><ref>{{Literatur |Autor=[[Felix Hausdorff]] |Titel=Grundzüge der Mengenlehre |Ort=Leipzig |Datum=1914}}</ref> zurück.

== Kategorizität ==
Für jede überabzählbare Kardinalzahl <math>\kappa</math> existieren genau <math>2^\kappa</math> paarweise nicht-isomorphe dichte lineare Ordnungen ohne Endpunkte,<ref>Chang und Keisler, S. 179.</ref> während bis auf Isomorphie nur eine einzige abzählbare dichte lineare Ordnung ohne Endpunkte existiert (<math>\Q</math>, welches saturiert ist). Die Theorie der dichten linearen Ordnungen ohne Endpunkte ist damit <math>\aleph_0</math>-[[Kategorizität|kategorisch]], doch nicht <math>\aleph_1</math>-kategorisch.

== Siehe auch ==
* [[Dichte Teilordnung]]
* Eine [[zerstreute Ordnung]] ist eine lineare Ordnung, die keine nicht-triviale dichte Teilordnung enthält

== Einzelnachweise ==
<references />

[[Kategorie:Ordnungsstruktur]]
[[Kategorie:Ordnungstheorie]]

Dichte Ordnung - Versionsgeschichte

imported>Hayek2020: /* growthexperiments-addlink-summary-summary:6|0|0 */