linear ordering
   HOME

TheInfoList



OR:

In mathematics, a total or linear order is 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 bina ...
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 ( reflexive). # If a \leq b and b \leq c then a \leq c ( transitive). # If a \leq b and b \leq a then a = b ( antisymmetric). # a \leq b or b \leq a (
strongly connected In the mathematical theory of directed graphs, a graph is said to be strongly connected if every vertex is reachable from every other vertex. The strongly connected components of an arbitrary directed graph form a partition into subgraphs that ...
, formerly called total). Total orders are sometimes also called simple, connex, or full orders. A set equipped with a total order is a totally ordered set; the terms simply ordered set, linearly ordered set, and loset are also used. The term ''chain'' is sometimes defined as a synonym of ''totally ordered set'', but refers generally to some sort of totally ordered subsets of a given partially ordered set. An extension of a given partial order to a total order is called a linear extension of that partial order.


Strict and non-strict total orders

A on a set X is a
strict 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 r ...
on X in which any two distinct elements are comparable. That is, a total order is a binary relation < on some set X, which satisfies the following for all a, b and c in X: # Not a < a (
irreflexive In mathematics, a binary relation ''R'' on a set ''X'' is reflexive if it relates every element of ''X'' to itself. An example of a reflexive relation is the relation " is equal to" on the set of real numbers, since every real number is equal ...
). # If a < b then not b < a ( asymmetric). # If a < b and b < c then a < c ( transitive). # If a \neq b, then a < b or b < a (
connected Connected may refer to: Film and television * ''Connected'' (2008 film), a Hong Kong remake of the American movie ''Cellular'' * '' Connected: An Autoblogography About Love, Death & Technology'', a 2011 documentary film * ''Connected'' (2015 TV ...
). Asymmetry follows from transitivity and irreflexivity; moreover, irreflexivity follows from asymmetry. For each (non-strict) total order \leq there is an associated relation <, called the ''strict total order'' associated with \leq that can be defined in two equivalent ways: * a < b if a \leq b and a \neq b ( reflexive reduction). * a < b if not b \leq a (i.e., < is the
complement A complement is something that completes something else. Complement may refer specifically to: The arts * Complement (music), an interval that, when added to another, spans an octave ** Aggregate complementation, the separation of pitch-clas ...
of the
converse Converse may refer to: Mathematics and logic * Converse (logic), the result of reversing the two parts of a definite or implicational statement ** Converse implication, the converse of a material implication ** Converse nonimplication, a logical c ...
of \leq). Conversely, the
reflexive closure In mathematics, the reflexive closure of a binary relation ''R'' on a set ''X'' is the smallest reflexive relation on ''X'' that contains ''R''. For example, if ''X'' is a set of distinct numbers and ''x R y'' means "''x'' is less than ''y''", the ...
of a strict total order < is a (non-strict) total order.


Examples

* Any subset of a totally ordered set is totally ordered for the restriction of the order on . * The unique order on the empty set, , is a total order. * Any set of
cardinal number In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality (size) of sets. The cardinality of a finite set is a natural number: the number of elements in the set. T ...
s or ordinal numbers (more strongly, these are
well-order In mathematics, a well-order (or well-ordering or well-order relation) on a set ''S'' is a total order on ''S'' with the property that every non-empty subset of ''S'' has a least element in this ordering. The set ''S'' together with the well-or ...
s). * If is any set and an injective function from to a totally ordered set then induces a total ordering on by setting if and only if . * The lexicographical order on the Cartesian product of a family of totally ordered sets, indexed by a well ordered set, is itself a total order. * The set of real numbers ordered by the usual "less than or equal to" (≤) or "greater than or equal to" (≥) relations is totally ordered. Hence each subset of the real numbers is totally ordered, such as the natural numbers,
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 ...
, and
rational numbers 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 rat ...
. Each of these can be shown to be the unique (up to an
order isomorphism 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 ...
) "initial example" of a totally ordered set with a certain property, (here, a total order is ''initial'' for a property, if, whenever has the property, there is an order isomorphism from to a subset of ): ** The natural numbers form an initial non-empty totally ordered set with no
upper bound In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is greater than or equal to every element of . Dually, a lower bound or minorant of is defined to be an eleme ...
. ** The integers form an initial non-empty totally ordered set with neither an upper nor a
lower bound In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is greater than or equal to every element of . Dually, a lower bound or minorant of is defined to be an eleme ...
. ** The rational numbers form an initial totally ordered set which is
dense Density (volumetric mass density or specific mass) is the substance's mass per unit of volume. The symbol most often used for density is ''ρ'' (the lower case Greek letter rho), although the Latin letter ''D'' can also be used. Mathematically ...
in the real numbers. Moreover, the reflexive reduction < is a dense order on the rational numbers. ** The real numbers form an initial unbounded totally ordered set that is
connected Connected may refer to: Film and television * ''Connected'' (2008 film), a Hong Kong remake of the American movie ''Cellular'' * '' Connected: An Autoblogography About Love, Death & Technology'', a 2011 documentary film * ''Connected'' (2015 TV ...
in the
order topology In mathematics, an order topology is a certain topology that can be defined on any totally ordered set. It is a natural generalization of the topology of the real numbers to arbitrary totally ordered sets. If ''X'' is a totally ordered set, th ...
(defined below). *
Ordered field In mathematics, an ordered field is a field together with a total ordering of its elements that is compatible with the field operations. The basic example of an ordered field is the field of real numbers, and every Dedekind-complete ordered fiel ...
s are totally ordered by definition. They include the rational numbers and the real numbers. Every ordered field contains an ordered subfield that is isomorphic to the rational numbers. Any ''
Dedekind-complete In mathematics, the least-upper-bound property (sometimes called completeness or supremum property or l.u.b. property) is a fundamental property of the real numbers. More generally, a partially ordered set has the least-upper-bound property if eve ...
'' ordered field is isomorphic to the real numbers. * The letters of the alphabet ordered by the standard dictionary order, e.g., etc., is a strict total order.


Chains

The term chain is sometimes defined as a synonym for a totally ordered set, but it is generally used for referring to a subset of a
partially ordered set 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 bina ...
that is totally ordered for the induced order. Typically, the partially ordered set is a set of subsets of a given set that is ordered by inclusion, and the term is used for stating properties of the set of the chains. This high number of nested levels of sets explains the usefulness of the term. A common example of the use of ''chain'' for referring to totally ordered subsets is Zorn's lemma which asserts that, if every chain in a partially ordered set has an upper bound in , then contains at least one maximal element. Zorn's lemma is commonly used with being a set of subsets; in this case, the upperbound is obtained by proving that the union of the elements of a chain in is in . This is the way that is generally used to prove that a
vector space In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called '' vectors'', may be added together and multiplied ("scaled") by numbers called ''scalars''. Scalars are often real numbers, but can ...
has Hamel bases and that a ring has
maximal ideal In mathematics, more specifically in ring theory, a maximal ideal is an ideal that is maximal (with respect to set inclusion) amongst all ''proper'' ideals. In other words, ''I'' is a maximal ideal of a ring ''R'' if there are no other ideals c ...
s. In some contexts, the chains that are considered are order isomorphic to the natural numbers with their usual order or its opposite order. In this case, a chain can be identified with a monotone sequence, and is called an ascending chain or a descending chain, depending whether the sequence is increasing or decreasing. A partially ordered set has the
descending chain condition In mathematics, the ascending chain condition (ACC) and descending chain condition (DCC) are finiteness properties satisfied by some algebraic structures, most importantly ideals in certain commutative rings.Jacobson (2009), p. 142 and 147 These con ...
if every descending chain eventually stabilizes. For example, an order is well founded if it has the descending chain condition. Similarly, the
ascending chain condition In mathematics, the ascending chain condition (ACC) and descending chain condition (DCC) are finiteness properties satisfied by some algebraic structures, most importantly ideals in certain commutative rings.Jacobson (2009), p. 142 and 147 These con ...
means that every ascending chain eventually stabilizes. For example, a
Noetherian ring In mathematics, a Noetherian ring is a ring that satisfies the ascending chain condition on left and right ideals; if the chain condition is satisfied only for left ideals or for right ideals, then the ring is said left-Noetherian or right-Noethe ...
is a ring whose ideals satisfy the ascending chain condition. In other contexts, only chains that are
finite set In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example, :\ is a finite set with five elements. T ...
s are considered. In this case, one talks of a ''finite chain'', often shortened as a ''chain''. In this case, the length of a chain is the number of inequalities (or set inclusions) between consecutive elements of the chain; that is, the number minus one of elements in the chain. Thus a
singleton set In mathematics, a singleton, also known as a unit set or one-point set, is a set with exactly one element. For example, the set \ is a singleton whose single element is 0. Properties Within the framework of Zermelo–Fraenkel set theory, the ...
is a chain of length zero, and an ordered pair is a chain of length one. The
dimension In physics and mathematics, the dimension of a mathematical space (or object) is informally defined as the minimum number of coordinates needed to specify any point within it. Thus, a line has a dimension of one (1D) because only one coor ...
of a space is often defined or characterized as the maximal length of chains of subspaces. For example, the
dimension of a vector space In mathematics, the dimension of a vector space ''V'' is the cardinality (i.e., the number of vectors) of a basis of ''V'' over its base field. p. 44, §2.36 It is sometimes called Hamel dimension (after Georg Hamel) or algebraic dimension to di ...
is the maximal length of chains of linear subspaces, and the
Krull dimension In commutative algebra, the Krull dimension of a commutative ring ''R'', named after Wolfgang Krull, is the supremum of the lengths of all chains of prime ideals. The Krull dimension need not be finite even for a Noetherian ring. More generally th ...
of a commutative ring is the maximal length of chains of prime ideals. "Chain" may also be used for some totally ordered subsets of
structures A structure is an arrangement and organization of interrelated elements in a material object or system, or the object or system so organized. Material structures include man-made objects such as buildings and machines and natural objects such as ...
that are not partially ordered sets. An example is given by regular chains of polynomials. Another example is the use of "chain" as a synonym for a
walk Walking (also known as ambulation) is one of the main gaits of terrestrial locomotion among legged animals. Walking is typically slower than running and other gaits. Walking is defined by an ' inverted pendulum' gait in which the body vaults ...
in a
graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...
.


Further concepts


Lattice theory

One may define a totally ordered set as a particular kind of
lattice Lattice may refer to: Arts and design * Latticework, an ornamental criss-crossed framework, an arrangement of crossing laths or other thin strips of material * Lattice (music), an organized grid model of pitch ratios * Lattice (pastry), an orna ...
, namely one in which we have : \ = \ for all ''a'', ''b''. We then write ''a'' ≤ ''b''
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 b ...
a = a\wedge b. Hence a totally ordered set is a
distributive lattice In mathematics, a distributive lattice is a lattice in which the operations of join and meet distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set ...
.


Finite total orders

A simple
counting Counting is the process of determining the number of elements of a finite set of objects, i.e., determining the size of a set. The traditional way of counting consists of continually increasing a (mental or spoken) counter by a unit for every ele ...
argument will verify that any non-empty finite totally ordered set (and hence any non-empty subset thereof) has a least element. Thus every finite total order is in fact a
well order In mathematics, a well-order (or well-ordering or well-order relation) on a set ''S'' is a total order on ''S'' with the property that every non-empty subset of ''S'' has a least element in this ordering. The set ''S'' together with the well-ord ...
. Either by direct proof or by observing that every well order is order isomorphic to an ordinal one may show that every finite total order is order isomorphic to an
initial segment In mathematics, an upper set (also called an upward closed set, an upset, or an isotone set in ''X'') of a partially ordered set (X, \leq) is a subset S \subseteq X with the following property: if ''s'' is in ''S'' and if ''x'' in ''X'' is larger ...
of the natural numbers ordered by <. In other words, a total order on a set with ''k'' elements induces a bijection with the first ''k'' natural numbers. Hence it is common to index finite total orders or well orders with
order type In mathematics, especially in set theory, two ordered sets and are said to have the same order type if they are order isomorphic, that is, if there exists a bijection (each element pairs with exactly one in the other set) f\colon X \to Y such ...
ω by natural numbers in a fashion which respects the ordering (either starting with zero or with one).


Category theory

Totally ordered sets form a
full subcategory In mathematics, specifically category theory, a subcategory of a category ''C'' is a category ''S'' whose objects are objects in ''C'' and whose morphisms are morphisms in ''C'' with the same identities and composition of morphisms. Intuitive ...
of the
category Category, plural categories, may refer to: Philosophy and general uses *Categorization, categories in cognitive science, information science and generally * Category of being * ''Categories'' (Aristotle) * Category (Kant) * Categories (Peirce) ...
of
partially ordered set 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 bina ...
s, with the morphisms being maps which respect the orders, i.e. maps ''f'' such that if ''a'' ≤ ''b'' then ''f''(''a'') ≤ ''f''(''b''). A
bijective In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other ...
map A map is a symbolic depiction emphasizing relationships between elements of some space, such as objects, regions, or themes. Many maps are static, fixed to paper or some other durable medium, while others are dynamic or interactive. Although ...
between two totally ordered sets that respects the two orders is an
isomorphism In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word i ...
in this category.


Order topology

For any totally ordered set ''X'' we can define the '' open intervals'' (''a'', ''b'') = , (−∞, ''b'') = , (''a'', ∞) = and (−∞, ∞) = ''X''. We can use these open intervals to define a
topology In mathematics, topology (from the Greek words , and ) is concerned with the properties of a geometric object that are preserved under continuous deformations, such as stretching, twisting, crumpling, and bending; that is, without closing ...
on any ordered set, the
order topology In mathematics, an order topology is a certain topology that can be defined on any totally ordered set. It is a natural generalization of the topology of the real numbers to arbitrary totally ordered sets. If ''X'' is a totally ordered set, th ...
. When more than one order is being used on a set one talks about the order topology induced by a particular order. For instance if N is the natural numbers, < is less than and > greater than we might refer to the order topology on N induced by < and the order topology on N induced by > (in this case they happen to be identical but will not in general). The order topology induced by a total order may be shown to be hereditarily
normal Normal(s) or The Normal(s) may refer to: Film and television * ''Normal'' (2003 film), starring Jessica Lange and Tom Wilkinson * ''Normal'' (2007 film), starring Carrie-Anne Moss, Kevin Zegers, Callum Keith Rennie, and Andrew Airlie * ''Norma ...
.


Completeness

A totally ordered set is said to be complete if every nonempty subset that has an
upper bound In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is greater than or equal to every element of . Dually, a lower bound or minorant of is defined to be an eleme ...
, has a
least upper bound In mathematics, the infimum (abbreviated inf; plural infima) of a subset S of a partially ordered set P is a greatest element in P that is less than or equal to each element of S, if such an element exists. Consequently, the term ''greatest lo ...
. For example, the set of
real number In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every ...
s R is complete but the set of
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 rat ...
s Q is not. In other words, the various concepts of completeness (not to be confused with being "total") do not carry over to restrictions. For example, over the
real number In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every ...
s a property of the relation ≤ is that every non-empty subset ''S'' of R with an
upper bound In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is greater than or equal to every element of . Dually, a lower bound or minorant of is defined to be an eleme ...
in R has a
least upper bound In mathematics, the infimum (abbreviated inf; plural infima) of a subset S of a partially ordered set P is a greatest element in P that is less than or equal to each element of S, if such an element exists. Consequently, the term ''greatest lo ...
(also called supremum) in R. However, for the rational numbers this supremum is not necessarily rational, so the same property does not hold on the restriction of the relation ≤ to the rational numbers. There are a number of results relating properties of the order topology to the completeness of X: * If the order topology on ''X'' is connected, ''X'' is complete. * ''X'' is connected under the order topology if and only if it is complete and there is no ''gap'' in ''X'' (a gap is two points ''a'' and ''b'' in ''X'' with ''a'' < ''b'' such that no ''c'' satisfies ''a'' < ''c'' < ''b''.) * ''X'' is complete if and only if every bounded set that is closed in the order topology is compact. A totally ordered set (with its order topology) which is a complete lattice is
compact Compact as used in politics may refer broadly to a pact or treaty; in more specific cases it may refer to: * Interstate compact * Blood compact, an ancient ritual of the Philippines * Compact government, a type of colonial rule utilized in British ...
. Examples are the closed intervals of real numbers, e.g. the
unit interval In mathematics, the unit interval is the closed interval , that is, the set of all real numbers that are greater than or equal to 0 and less than or equal to 1. It is often denoted ' (capital letter ). In addition to its role in real analysis ...
,1 and the
affinely extended real number system In mathematics, the affinely extended real number system is obtained from the real number system \R by adding two infinity elements: +\infty and -\infty, where the infinities are treated as actual numbers. It is useful in describing the algebra on ...
(extended real number line). There are order-preserving
homeomorphism In the mathematical field of topology, a homeomorphism, topological isomorphism, or bicontinuous function is a bijective and continuous function between topological spaces that has a continuous inverse function. Homeomorphisms are the isomor ...
s between these examples.


Sums of orders

For any two disjoint total orders (A_1,\le_1) and (A_2,\le_2), there is a natural order \le_+ on the set A_1\cup A_2, which is called the sum of the two orders or sometimes just A_1+A_2: : For x,y\in A_1\cup A_2, x\le_+ y holds if and only if one of the following holds: :# x,y\in A_1 and x\le_1 y :# x,y\in A_2 and x\le_2 y :# x\in A_1 and y\in A_2 Intuitively, this means that the elements of the second set are added on top of the elements of the first set. More generally, if (I,\le) is a totally ordered index set, and for each i\in I the structure (A_i,\le_i) is a linear order, where the sets A_i are pairwise disjoint, then the natural total order on \bigcup_i A_i is defined by : For x,y\in \bigcup_ A_i, x\le y holds if: :# Either there is some i\in I with x\le_i y :# or there are some i in I with x\in A_i, y\in A_j


Decidability

The first-order theory of total orders is decidable, i.e. there is an algorithm for deciding which first-order statements hold for all total orders. Using interpretability in S2S, the monadic second-order theory of
countable 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 numbers ...
total orders is also decidable.


Orders on the Cartesian product of totally ordered sets

In order of increasing strength, i.e., decreasing sets of pairs, three of the possible orders on the Cartesian product of two totally ordered sets are: * Lexicographical order: (''a'',''b'') ≤ (''c'',''d'') if and only if ''a'' < ''c'' or (''a'' = ''c'' and ''b'' ≤ ''d''). This is a total order. * (''a'',''b'') ≤ (''c'',''d'') if and only if ''a'' ≤ ''c'' and ''b'' ≤ ''d'' (the
product order In mathematics, given two preordered sets A and B, the product order (also called the coordinatewise orderDavey & Priestley, ''Introduction to Lattices and Order'' (Second Edition), 2002, p. 18 or componentwise order) is a partial ordering o ...
). This is a partial order. * (''a'',''b'') ≤ (''c'',''d'') if and only if (''a'' < ''c'' and ''b'' < ''d'') or (''a'' = ''c'' and ''b'' = ''d'') (the reflexive closure of the direct product of the corresponding strict total orders). This is also a partial order. All three can similarly be defined for the Cartesian product of more than two sets. Applied to the
vector space In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called '' vectors'', may be added together and multiplied ("scaled") by numbers called ''scalars''. Scalars are often real numbers, but can ...
R''n'', each of these make it an
ordered vector space In mathematics, an ordered vector space or partially ordered vector space is a vector space equipped with a partial order that is compatible with the vector space operations. Definition Given a vector space ''X'' over the real numbers R and a pr ...
. See also examples of partially ordered sets. A real function of ''n'' real variables defined on a subset of R''n'' defines a strict weak order and a corresponding total preorder on that subset.


Related structures

A binary relation that is antisymmetric, transitive, and reflexive (but not necessarily total) is 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 bina ...
. A
group A group is a number of persons or things that are located, gathered, or classed together. Groups of people * Cultural group, a group whose members share the same cultural identity * Ethnic group, a group whose members share the same ethnic ide ...
with a compatible total order is a totally ordered group. There are only a few nontrivial structures that are (interdefinable as) reducts of a total order. Forgetting the orientation results in a
betweenness relation Ordered geometry is a form of geometry featuring the concept of intermediacy (or "betweenness") but, like projective geometry, omitting the basic notion of measurement. Ordered geometry is a fundamental geometry forming a common framework for aff ...
. Forgetting the location of the ends results in a
cyclic order In mathematics, a cyclic order is a way to arrange a set of objects in a circle. Unlike most structures in order theory, a cyclic order is not modeled as a binary relation, such as "". One does not say that east is "more clockwise" than west. Ins ...
. Forgetting both data results in a separation relation.


See also

* * * * * – a downward total partial order * *


Notes


References

* * * * George Grätzer (1971). ''Lattice theory: first concepts and distributive lattices.'' W. H. Freeman and Co. * John G. Hocking and Gail S. Young (1961). ''Topology.'' Corrected reprint, Dover, 1988. * *


External links

* {{Order theory Binary relations Order theory Set theory