# Dense order

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Dense_order
> Markdown URL: https://mediated.wiki/source/Dense_order.md
> Source: https://en.wikipedia.org/wiki/Dense_order
> Source revision: 1356552700
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

Type of ordering of a set

In [mathematics](/source/Mathematics), a [partial order](/source/Partial_order) or [total order](/source/Total_order) < on a [set](/source/Set_(mathematics)) X {\displaystyle X} is said to be **dense** if, for all x {\displaystyle x} and y {\displaystyle y} in X {\displaystyle X} for which x < y {\displaystyle x<y} , there is a z {\displaystyle z} in X {\displaystyle X} such that x < z < y {\displaystyle x<z<y} . That is, for any two elements, one less than the other, there is another element between them. For total orders this can be simplified to "for any two distinct elements, there is another element between them", since all elements of a total order are [comparable](/source/Comparability).

Equivalently, a partial order is dense precisely if its [covering relation](/source/Covering_relation) is empty.

## Example

The [rational numbers](/source/Rational_number) as a linearly ordered set are a densely ordered set in this sense, as are the [algebraic numbers](/source/Algebraic_number), the [real numbers](/source/Real_number), the [dyadic rationals](/source/Dyadic_rational) and the [decimal fractions](/source/Decimal_fraction). In fact, every [Archimedean](/source/Archimedean_property) ordered [ring extension](/source/Subring#Ring_extensions) of the [integers](/source/Integers) Z [ x ] {\displaystyle \mathbb {Z} [x]} is a densely ordered set.

**Proof**

For the element x ∈ Z [ x ] {\displaystyle x\in \mathbb {Z} [x]} , due to the Archimedean property, if x > 0 {\displaystyle x>0} , there exists a largest integer n < x {\displaystyle n<x} with n < x < n + 1 {\displaystyle n<x<n+1} , and if x < 0 {\displaystyle x<0} , − x > 0 {\displaystyle -x>0} , and there exists a largest integer m = − n − 1 < − x {\displaystyle m=-n-1<-x} with − n − 1 < − x < − n {\displaystyle -n-1<-x<-n} . As a result, 0 < x − n < 1 {\displaystyle 0<x-n<1} . For any two elements y , z ∈ Z [ x ] {\displaystyle y,z\in \mathbb {Z} [x]} with z < y {\displaystyle z<y} , 0 < ( x − n ) ( y − z ) < y − z {\displaystyle 0<(x-n)(y-z)<y-z} and z < ( x − n ) ( y − z ) + z < y {\displaystyle z<(x-n)(y-z)+z<y} . Therefore Z [ x ] {\displaystyle \mathbb {Z} [x]} is dense.

On the other hand, the linear ordering on the [integers](/source/Integer) is not dense.

## Uniqueness for total dense orders without endpoints

Main article: [Cantor's isomorphism theorem](/source/Cantor's_isomorphism_theorem)

[Georg Cantor](/source/Georg_Cantor) proved that every two non-empty dense totally ordered [countable sets](/source/Countable_set) without lower or upper bounds are [order-isomorphic](/source/Order_isomorphism).[1] This makes the theory of dense linear orders without bounds an example of an ω-[categorical theory](/source/Categorical_theory) where ω is the smallest [limit ordinal](/source/Limit_ordinal). For example, there exists an order-isomorphism between the [rational numbers](/source/Rational_number) and other densely ordered countable sets including the [dyadic rationals](/source/Dyadic_rational) and the [algebraic numbers](/source/Algebraic_number). The proofs of these results use the [back-and-forth method](/source/Back-and-forth_method).[2]

[Minkowski's question mark function](/source/Minkowski's_question_mark_function) can be used to determine the order isomorphisms between the [quadratic algebraic numbers](/source/Quadratic_irrational_number) and the [rational numbers](/source/Rational_number), and between the rationals and the [dyadic rationals](/source/Dyadic_rational).

## Generalizations

Any [binary relation](/source/Binary_relation) *R* is said to be *dense* if, for all *R*-related *x* and *y*, there is a *z* such that *x* and *z* and also *z* and *y* are *R*-related. Formally:

- ∀ x ∀ y x R y ⇒ ( ∃ z x R z ∧ z R y ) . {\displaystyle \forall x\ \forall y\ xRy\Rightarrow (\exists z\ xRz\land zRy).} Alternatively, in terms of [composition](/source/Composition_of_relations) of *R* with itself, the dense condition may be expressed as *R* ⊆ (*R* ; *R*).[3]

[Sufficient conditions](/source/Sufficient_condition) for a binary relation *R* on a set *X* to be dense are:

- *R* is [reflexive](/source/Reflexive_relation);

- *R* is [coreflexive](/source/Coreflexive_relation);

- *R* is [quasireflexive](/source/Quasireflexive_relation);

- *R* is left or right [Euclidean](/source/Euclidean_relation); or

- *R* is [symmetric](/source/Symmetric_relation) and [semi-connex](/source/Semi-connex_relation) and *X* has at least 3 elements.

None of them are [necessary](/source/Necessary_condition). For instance, there is a relation R that is not reflexive but dense. A [non-empty](/source/Empty_relation) and dense relation cannot be [antitransitive](/source/Antitransitive).

A strict partial order < is a dense order [if and only if](/source/If_and_only_if) < is a dense relation. A dense relation that is also [transitive](/source/Transitive_relation) is said to be [idempotent](/source/Idempotent_relation).

## See also

- [Dense set](/source/Dense_set) — a subset of a topological space whose closure is the whole space

- [Dense-in-itself](/source/Dense-in-itself) — a subset A {\displaystyle A} of a topological space such that A {\displaystyle A} does not contain an isolated point

- [Kripke semantics](/source/Kripke_semantics) — a dense accessibility relation corresponds to the axiom ◻ ◻ A → ◻ A {\displaystyle \Box \Box A\rightarrow \Box A}

## References

1. **[^](#cite_ref-1)** [Roitman, Judith](/source/Judith_Roitman) (1990), "Theorem 27, p. 123", [*Introduction to Modern Set Theory*](https://books.google.com/books?id=0euMlBhBxjMC&pg=PA123), Pure and Applied Mathematics, vol. 8, John Wiley & Sons, [ISBN](/source/ISBN_(identifier)) [9780471635192](https://en.wikipedia.org/wiki/Special:BookSources/9780471635192).

1. **[^](#cite_ref-2)** Dasgupta, Abhijit (2013), [*Set Theory: With an Introduction to Real Point Sets*](https://books.google.com/books?id=u06-BAAAQBAJ&pg=PA161), Springer-Verlag, p. 161, [ISBN](/source/ISBN_(identifier)) [9781461488545](https://en.wikipedia.org/wiki/Special:BookSources/9781461488545).

1. **[^](#cite_ref-3)** [Gunter Schmidt](/source/Gunter_Schmidt) (2011) *Relational Mathematics*, page 212, [Cambridge University Press](/source/Cambridge_University_Press) [ISBN](/source/ISBN_(identifier)) [978-0-521-76268-7](https://en.wikipedia.org/wiki/Special:BookSources/978-0-521-76268-7)

## Further reading

- [David Harel](/source/David_Harel), [Dexter Kozen](/source/Dexter_Kozen), Jerzy Tiuryn, *Dynamic logic*, MIT Press, 2000, [ISBN](/source/ISBN_(identifier)) [0-262-08289-6](https://en.wikipedia.org/wiki/Special:BookSources/0-262-08289-6), p. 6ff

v t e Order theory Topics Glossary Category Key concepts Binary relation Boolean algebra Cyclic order Lattice Partially ordered set Preorder Total order Weak ordering Results Boolean prime ideal theorem Cantor–Bernstein theorem Cantor's isomorphism theorem Dilworth's theorem Dushnik–Miller theorem Hausdorff maximal principle Knaster–Tarski theorem Kruskal's tree theorem Laver's theorem Mirsky's theorem Szpilrajn extension theorem Zorn's lemma Properties & Types (list) Antisymmetric Asymmetric Boolean algebra topics Completeness Connected Covering Dense Directed (Partial) Equivalence Foundational Heyting algebra Homogeneous Idempotent Lattice Bounded Complemented Complete Distributive Join and meet Partially ordered set Chain-complete Eulerian Graded Locally finite Strict Prefix order Preorder Total Reflexive Semilattice Semiorder Symmetric Tolerance Total Transitive Well-founded Well-quasi-ordering (Better) (Pre) Well-order Constructions Composition Converse/Transpose Lexicographic order Linear extension Product order Reflexive closure Series-parallel partial order Star product Symmetric closure Transitive closure Topology & Orders Alexandrov topology & Specialization preorder Ordered topological vector space Normal cone Order topology Order topology Topological vector lattice Banach Fréchet Locally convex Normed Related Antichain Cofinal Cofinality Comparability Graph Duality Filter Hasse diagram Ideal Net Subnet Order morphism Embedding Isomorphism Order type Ordered field Positive cone of an ordered field Ordered vector space Partially ordered Positive cone of an ordered vector space Riesz space Partially ordered group Positive cone of a partially ordered group Upper set Young's lattice

---
Adapted from the Wikipedia article [Dense order](https://en.wikipedia.org/wiki/Dense_order) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Dense_order?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.