HOME

TheInfoList



OR:

In mathematics, a
partial order In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary ...
or
total order In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X: # a \leq a ( reflexiv ...
< on a set X is said to be dense if, for all x and y in X for which x < y, there is a z in X such that 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.


Example

The
rational number In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all ra ...
s as a linearly ordered set are a densely ordered set in this sense, as are the
algebraic number An algebraic number is a number that is a root of a non-zero polynomial in one variable with integer (or, equivalently, rational) coefficients. For example, the golden ratio, (1 + \sqrt)/2, is an algebraic number, because it is a root of the p ...
s, the
real number In mathematics, a real number is a number that can be used to measurement, measure a ''continuous'' one-dimensional quantity such as a distance, time, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small var ...
s, the
dyadic rational In mathematics, a dyadic rational or binary rational is a number that can be expressed as a fraction whose denominator is a power of two. For example, 1/2, 3/2, and 3/8 are dyadic rationals, but 1/3 is not. These numbers are important in compu ...
s and the decimal fractions. In fact, every Archimedean ordered ring extension of the
integers An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
\mathbb /math> is a densely ordered set. On the other hand, the linear ordering on the
integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
s is not dense.


Uniqueness for total dense orders without endpoints

Georg Cantor Georg Ferdinand Ludwig Philipp Cantor ( , ;  – January 6, 1918) was a German mathematician. He played a pivotal role in the creation of set theory, which has become a fundamental theory in mathematics. Cantor established the importance of ...
proved that every two non-empty dense totally ordered
countable set In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural number ...
s without lower or upper bounds are
order-isomorphic In the mathematical field of order theory, an order isomorphism is a special kind of monotone function that constitutes a suitable notion of isomorphism for partially ordered sets (posets). Whenever two posets are order isomorphic, they can be cons ...
. This makes the theory of dense linear orders without bounds an example of an ω- categorical theory where ω is the smallest limit ordinal. For example, there exists an order-isomorphism between the
rational number In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all ra ...
s and other densely ordered countable sets including the
dyadic rational In mathematics, a dyadic rational or binary rational is a number that can be expressed as a fraction whose denominator is a power of two. For example, 1/2, 3/2, and 3/8 are dyadic rationals, but 1/3 is not. These numbers are important in compu ...
s and the
algebraic number An algebraic number is a number that is a root of a non-zero polynomial in one variable with integer (or, equivalently, rational) coefficients. For example, the golden ratio, (1 + \sqrt)/2, is an algebraic number, because it is a root of the p ...
s. The proofs of these results use the back-and-forth method. Minkowski's question mark function can be used to determine the order isomorphisms between the quadratic algebraic numbers and the
rational number In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all ra ...
s, and between the rationals and the
dyadic rational In mathematics, a dyadic rational or binary rational is a number that can be expressed as a fraction whose denominator is a power of two. For example, 1/2, 3/2, and 3/8 are dyadic rationals, but 1/3 is not. These numbers are important in compu ...
s.


Generalizations

Any
binary relation In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over Set (mathematics), sets and is a new set of ordered pairs consisting of ele ...
''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: : \forall x\ \forall y\ xRy\Rightarrow (\exists z\ xRz \land zRy). Alternatively, in terms of composition of ''R'' with itself, the dense condition may be expressed as ''R'' ⊆ ''R'' ; ''R''. Gunter Schmidt (2011) ''Relational Mathematics'', page 212,
Cambridge University Press Cambridge University Press is the university press of the University of Cambridge. Granted letters patent by Henry VIII of England, King Henry VIII in 1534, it is the oldest university press in the world. It is also the King's Printer. Cambr ...
Sufficient condition In logic and mathematics, necessity and sufficiency are terms used to describe a conditional or implicational relationship between two statements. For example, in the conditional statement: "If then ", is necessary for , because the truth of ...
s for a binary relation ''R'' on a set ''X'' to be dense are: * ''R'' is reflexive; * ''R'' is coreflexive; * ''R'' is quasireflexive; * ''R'' is left or right Euclidean; or * ''R'' is
symmetric Symmetry (from grc, συμμετρία "agreement in dimensions, due proportion, arrangement") in everyday language refers to a sense of harmonious and beautiful proportion and balance. In mathematics, "symmetry" has a more precise definit ...
and semi-connex and ''X'' has at least 3 elements. None of them are necessary. For instance, there is a relation R that is not reflexive but dense. A non-empty and dense relation cannot be antitransitive. A strict partial order < is a dense order
if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is bi ...
< is a dense relation. A dense relation that is also transitive is said to be
idempotent Idempotence (, ) is the property of certain operations in mathematics and computer science whereby they can be applied multiple times without changing the result beyond the initial application. The concept of idempotence arises in a number of pl ...
.


See also

*
Dense set In topology and related areas of mathematics, a subset ''A'' of a topological space ''X'' is said to be dense in ''X'' if every point of ''X'' either belongs to ''A'' or else is arbitrarily "close" to a member of ''A'' — for instance, the ...
— a subset of a topological space whose closure is the whole space * Dense-in-itself — a subset A of a topological space such that A does not contain an isolated point * Kripke semantics — a dense accessibility relation corresponds to the axiom \Box\Box A \rightarrow \Box A


References


Further reading

*
David Harel David Harel ( he, דוד הראל; born 12 April 1950) is a computer scientist, currently serving as President of the Israel Academy of Sciences and Humanities. He has been on the faculty of the Weizmann Institute of Science in Israel since 198 ...
, Dexter Kozen, Jerzy Tiuryn, ''Dynamic logic'', MIT Press, 2000, , p. 6ff {{Order theory Binary relations Order theory