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 $X$ heißt dicht, falls

für alle

x,z\in X

mit

x<z

gibt es ein

y\in X

mit

x<y<z

,

das heißt, für je zwei verschiedene Elemente von $X$ gibt es ein drittes, das zwischen den beiden liegt.^[1]

Beispiele

Die Menge $\mathbb {Q}$ der rationalen Zahlen mit der natürlichen Anordnung < ist dicht, denn sind $a,b\in \mathbb {Q}$ mit $a<b$ , so ist $\textstyle {\frac {a+b}{2}}$ ebenfalls eine rationale Zahl und diese liegt zwischen $a$ und $b$ .
Die Menge $\mathbb {R}$ der reellen Zahlen mit der natürlichen Anordnung < ist dicht, wobei die Begründung wie für $\mathbb {Q}$ geführt werden kann. $\mathbb {Q} \subset \mathbb {R}$ liegt ordnungsdicht.
Die Menge $\mathbb {Z}$ 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 $x<y$ 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 $(X,<)$ eine nichtleere abzählbare, dichte, linear geordnete Menge ohne kleinstes und größtes Element und $(Y,<)$ eine beliebige abzählbare, linear geordnete Menge. Dann gibt es eine injektive Abbildung $f\colon Y\rightarrow X$ mit $\forall x,y\in Y:x<y\Leftrightarrow f(x)<f(y)$

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 $X$ und $Y$ zwei solche Mengen und sind beide Ordnungen mit < bezeichnet, so gibt es eine bijektive Abbildung $f\colon X\rightarrow Y$ mit $\forall x,y\in X:x<y\Leftrightarrow f(x)<f(y)$ .

Die folgenden Beispiele sind daher alle isomorph:

$\mathbb {Q}$ mit der natürlichen Ordnung
$\mathbb {Q} +{\sqrt {2}}\cdot \mathbb {Q} =\{a+{\sqrt {2}}\cdot b;\,a,b\in \mathbb {Q} \}$ mit der natürlichen Ordnung
$(0,1)\cap \mathbb {Q}$ mit der natürlichen Ordnung
$((-\infty ,0)\cap \mathbb {Q} )\cup ((1,\infty )\cap \mathbb {Q} )$ mit der natürlichen Ordnung
$((-\infty ,0]\cap \mathbb {Q} )\cup ((1,\infty )\cap \mathbb {Q} )$ mit der natürlichen Ordnung
$\mathbb {Q} ^{2}$ 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:

\emptyset

,

\{0\}

,

(0,1)\cap \mathbb {Q}

,

[0,1)\cap \mathbb {Q}

,

(0,1]\cap \mathbb {Q}

,

[0,1]\cap \mathbb {Q}

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 $\mathbb {R}$ der reellen Zahlen, ordnungstheoretisch wie folgt charakterisieren: $\mathbb {R}$ mit der natürlichen Ordnung ist bis auf Ordnungsisomorphie die einzige vollständige, lineare Ordnung, die eine abzählbare, ordnungsdichte und zu $\mathbb {Q}$ 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 $\mathbb {Q}$ und $\mathbb {R}$ 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 $x<y$ .^[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“, „ $x$ ist das kleinste Element“ und „ $x$ ist das größte Element“ in den booleschen Kombinationen zugelassen werden müssen.^[8]

Verallgemeinerung: κ-Dichtheit

Sei $\kappa$ eine Kardinalzahl. Eine linear geordnete Menge $(X,<)$ heißt $\kappa$ -dicht, wenn für je zwei Mengen $A,B\subset X$ mit $\left|A\right|,\left|B\right|<\kappa$ , sodass alle Elemente in $A$ kleiner als alle in $B$ sind, ein Element $x\in X$ existiert, das größer als alle Elemente in A und kleiner als alle in B ist.^[10] $\aleph _{0}$ -dichte Ordnungen sind gerade die dichten linearen Ordnungen ohne Endpunkte.

Saturiertheit

Eine dichte lineare Ordnung ohne Endpunkte ist genau dann $\kappa$ -saturiert, wenn sie $\kappa$ -dicht ist.^[10] Eine (und damit bis auf Isomorphie genau eine) saturierte dichte lineare Ordnung ohne Endpunkte der Kardinalität $\kappa$ (d. h., sie ist $\kappa$ -saturiert) existiert genau dann, wenn $\kappa$ regulär ist und $\kappa ^{<\kappa }=\kappa$ .^[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 $\kappa$ existieren genau $2^{\kappa }$ 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 ( $\mathbb {Q}$ , welches saturiert ist). Die Theorie der dichten linearen Ordnungen ohne Endpunkte ist damit $\aleph _{0}$ -kategorisch, doch nicht $\aleph _{1}$ -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
↑ ^a ^b 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.
↑ ^a ^b 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.

[1] Thomas Jech: Set Theory. Springer-Verlag, 2003, ISBN 3-540-44085-2, Definition 4.2

[2] Joseph G. Rosenstein: Linear Orderings. In: Pure & Applied Mathematics, Academic Press, Oktober 1982, Satz 2.5

[3] Joseph G. Rosenstein: Linear Orderings. In: Pure & Applied Mathematics, Academic Press, Oktober 1982, Satz 2.8

[4] Ernest Schimmerling: A Course on Set Theory. Cambridge University Press, 2011, ISBN 1-107-00817-4, Theorem 6.5

[5] Joseph G. Rosenstein: Linear Orderings, Pure & Applied Mathematics, Academic Press Inc (Oktober 1982), Korollar 2.9

[6] Thomas Jech: Set Theory. Springer-Verlag (2003), ISBN 3-540-44085-2, Satz 4.3

[7] 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

[hodgesquantelim-8] Wilfrid Hodges: Model theory. Cambridge University Press, 1993, ISBN 0-521-30442-3, S. 67.

[9] 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.

[smt-10] Gerald E. Sacks: Saturated Model Theory. w. A. Benjamin, 1972, ISBN 0-8053-8380-8, S. 77.

[11] Andrey I. Bovykin: On order-types of models of arithmetic. 2000, S. 16 (logic.pdmi.ras.ru [PDF]).

[12] David Marker: Model Theory. An Introduction. Springer, New York 2002, ISBN 0-387-98760-6, S. 142.

[13] Hodges, S. 485.

[14] Felix Hausdorff: Grundzüge einer Theorie der geordneten Mengen. In: Mathematische Annalen. Band 65, 1908 (online).

[15] Chang und Keisler, S. 3, 613.

[16] Felix Hausdorff: Grundzüge der Mengenlehre. Leipzig 1914.

[17] Chang und Keisler, S. 179.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]