Dense order

Dense order is a mathematical term from the field of order theory . An order is called dense if there is a third between every two elements.

definition

A linear order <on a set is called dense , if ${\displaystyle X}$

for everyone with there is one with , ${\displaystyle x,z\in X}$ ${\displaystyle x<z}$ ${\displaystyle y\in X}$ ${\displaystyle x<y<z}$

that is, for every two different elements of there is a third that lies between the two. ${\displaystyle X}$

Examples

• The set of rational numbers with the natural arrangement <is dense, because are with , then is also a rational number and this lies between and . ${\displaystyle \mathbb {Q} }$ ${\displaystyle a,b\in \mathbb {Q} }$ ${\displaystyle a<b}$ ${\displaystyle \textstyle {\frac {a+b}{2}}}$ ${\displaystyle a}$ ${\displaystyle b}$
• The set of real numbers with the natural arrangement <is dense, whereby the justification can be given as for . is tidy. ${\displaystyle \mathbb {R} }$ ${\displaystyle \mathbb {Q} }$ ${\displaystyle \mathbb {Q} \subset \mathbb {R} }$
• The set of integers with the natural order <is not dense because there is no third integer between two consecutive integers. ${\displaystyle \mathbb {Z} }$
• By definition, a one-element set with the uniquely determined linear order is densely ordered on it, since there are no two elements for which the defining condition would have to be fulfilled. Some authors rule out this trivial case by additionally requiring that the set must have at least two elements. ${\displaystyle x<y}$

properties

Universal property

According to Cantor's theorem , non-empty, countable , dense orders without the smallest and largest element contain all other countable, linear orders, i.e. they have the following universal property:

Let it be a non-empty, countable, dense, linearly ordered set without the smallest and largest element and any countable, linearly ordered set. Then there is an injective mapping with ${\displaystyle (X,<)}$ ${\displaystyle (Y,<)}$ ${\displaystyle f\colon Y\rightarrow X}$ ${\displaystyle \forall x,y\in Y:x<y\Leftrightarrow f(x)<f(y)}$

Isomorphism classes of countable, dense, linearly ordered sets

According to another theorem by Cantor, two non-empty, countable, dense, linearly ordered sets without the smallest or largest element are order isomorphic. That means: If and are two such sets and if both orders are denoted by <, then there is a bijective mapping with . ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle f\colon X\rightarrow Y}$ ${\displaystyle \forall x,y\in X:x<y\Leftrightarrow f(x)<f(y)}$

The following examples are therefore all isomorphic:

• ${\displaystyle \mathbb {Q} }$ with the natural order
• ${\displaystyle \mathbb {Q} +{\sqrt {2}}\cdot \mathbb {Q} =\{a+{\sqrt {2}}\cdot b;\,a,b\in \mathbb {Q} \}}$ with the natural order
• ${\displaystyle (0,1)\cap \mathbb {Q} }$ with the natural order
• ${\displaystyle ((-\infty ,0)\cap \mathbb {Q} )\cup ((1,\infty )\cap \mathbb {Q} )}$ with the natural order
• ${\displaystyle ((-\infty ,0]\cap \mathbb {Q} )\cup ((1,\infty )\cap \mathbb {Q} )}$ with the natural order
• ${\displaystyle \mathbb {Q} ^{2}}$with the lexicographical order

If one waives the conditions for the smallest and largest elements, one obtains:

Every countable, dense, linearly ordered set is isomorphic to one of the following six sets, each with its natural order:

${\displaystyle \emptyset }$, , , , , ${\displaystyle \{0\}}$ ${\displaystyle (0,1)\cap \mathbb {Q} }$ ${\displaystyle [0,1)\cap \mathbb {Q} }$ ${\displaystyle (0,1]\cap \mathbb {Q} }$ ${\displaystyle [0,1]\cap \mathbb {Q} }$

A characterization of the continuum

An order is called complete if every set restricted above has a supremum . According to another theorem of Cantor, the continuum, i.e. the set of real numbers, can be characterized in terms of order theory as follows: with the natural order, apart from order isomorphism, the only complete, linear order that contains a countable, order-dense and order-isomorphic subset. ${\displaystyle \mathbb {R} }$ ${\displaystyle \mathbb {R} }$ ${\displaystyle \mathbb {Q} }$

completeness

Any two non-empty dense linear orders without the smallest and largest element are elementarily equivalent , as can be seen from Fraïssé's theorem (see here for a proof). The theory of dense linear orders without end points is thus complete . In particular, the order theories of and in the first-level predicate logic cannot be distinguished; properties such as completeness cannot be formulated in it. ${\displaystyle \mathbb {Q} }$ ${\displaystyle \mathbb {R} }$

Quantifier elimination

The theory of dense linear orders without endpoints allows quantifier elimination . Every formula of the first-order predicate logic is therefore equivalent to a Boolean combination of atomic statements of the form . For each tuple of elements of a dense linear order without end points, the associated type thus results solely from the valid and invalid comparisons of the elements of the tuple. Every dense linear order without end points is thus an atomic model . ${\displaystyle x<y}$

General dense linear orders allow quantifier elimination, whereby statements of the form “there is a smallest element”, “there is a largest element”, “ is the smallest element” and “ is the largest element” must be allowed in the Boolean combinations. ${\displaystyle x}$ ${\displaystyle x}$

Generalization: κ-tightness

Be a cardinal number . A linearly ordered set is called -dense if for every two sets with such that all elements in are smaller than all in , there exists an element that is larger than all elements in A and smaller than all in B. -dense orders are just the dense linear orders without end points. ${\displaystyle \kappa }$ ${\displaystyle (X,<)}$ ${\displaystyle \kappa }$ ${\displaystyle A,B\subset X}$ ${\displaystyle \left|A\right|,\left|B\right|<\kappa }$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle x\in X}$ ${\displaystyle \aleph _{0}}$

Saturation

A dense linear order without end points is - saturated if and only if it is - dense . A (and thus exactly one, except for isomorphism) saturated, dense linear order without endpoints of cardinality (i.e., it is -saturated) exists if and only if is regular and . The consideration of this dense linear order and, more generally, of the saturation goes back to texts by Felix Hausdorff from the years 1908 and 1914. ${\displaystyle \kappa }$ ${\displaystyle \kappa }$ ${\displaystyle \kappa }$ ${\displaystyle \kappa }$ ${\displaystyle \kappa }$ ${\displaystyle \kappa ^{<\kappa }=\kappa }$

Categoricity

For every uncountable cardinal number there are exactly paired non-isomorphic dense linear orders without end points, while apart from isomorphism there is only one single countable dense linear order without end points ( which is saturated). The theory of dense linear orders without endpoints is thus - categorical , but not -categorical. ${\displaystyle \kappa }$ ${\displaystyle 2^{\kappa }}$ ${\displaystyle \mathbb {Q} }$ ${\displaystyle \aleph _{0}}$ ${\displaystyle \aleph _{1}}$

See also

• Dense partial order
• A scattered order is a linear order that does not contain a non-trivial dense suborder

Individual evidence

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, October 1982, sentence 2.5
3. ^ Joseph G. Rosenstein: Linear Orderings . In: Pure & Applied Mathematics , Academic Press, October 1982, sentence 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 (October 1982), Corollary 2.9
6. ^ Thomas Jech : Set Theory . Springer-Verlag (2003), ISBN 3-540-44085-2 , sentence 4.3
7. ^ Heinz-Dieter Ebbinghaus, Jörg Flum, Wolfgang Thomas: Introduction to mathematical logic. Spektrum Akademischer Verlag (1996), ISBN 3-8274-0130-5 , XII, §2, 2.2
8. ^ ^{A b} Wilfrid Hodges : Model theory . Cambridge University Press, 1993, ISBN 0-521-30442-3 , pp. 67 .
9. ↑ Chen Chung Chang, Howard Jerome Keisler : Model Theory (=  Studies in Logic and the Foundations of Mathematics . Volume 73 ). Elsevier, 1990, ISBN 0-444-88054-2 , pp. 97 .
10. ^ ^{A b} Gerald E. Sacks : Saturated Model Theory . w. A. Benjamin, 1972, ISBN 0-8053-8380-8 , pp. 77 .
11. ↑ Andrey I. Bovykin: On order-types of models of arithmetic . 2000, p. 16 ( logic.pdmi.ras.ru [PDF]).
12. ^ David Marker: Model Theory . An Introduction. Springer, New York 2002, ISBN 0-387-98760-6 , pp. 142 .
13. ↑ Hodges, p. 485.
14. ↑ Felix Hausdorff : Fundamentals of a theory of ordered sets . In: Mathematical Annals . tape 65 , 1908 ( online ).
15. ↑ Chang and Keisler, pp. 3, 613.
16. ↑ Felix Hausdorff : Fundamentals of set theory . Leipzig 1914.
17. ↑ Chang and Keisler, p. 179.