HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern 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 binary ...
in which any two elements are comparable. That is, a total order is a
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 sets and is a new set of ordered pairs consisting of elements in and in ...
\leq on some
set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...
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, 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 In order theory, a branch of mathematics, a linear extension of a partial order is a total order (or linear order) that is compatible with the partial order. As a classic example, the lexicographic order of totally ordered sets is a linear ext ...
of that partial order.


Strict and non-strict total orders

A on a set X is a strict partial order on X in which any two distinct elements are comparable. That is, a total order is a
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 sets and is a new set of ordered pairs consisting of elements in and in ...
< on some
set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...
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). 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 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 t ...
). * a < b if not b \leq a (i.e., < is the complement of the converse of \leq). Conversely, the reflexive closure of a strict total order < is a (non-strict) total order.


Examples

* Any
subset In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset of ...
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. ...
s or
ordinal number In set theory, an ordinal number, or ordinal, is a generalization of ordinal numerals (first, second, th, etc.) aimed to extend enumeration to infinite sets. A finite set can be enumerated by successively labeling each element with the leas ...
s (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 In mathematics, an injective function (also known as injection, or one-to-one function) is a function that maps distinct elements of its domain to distinct elements; that is, implies . (Equivalently, implies in the equivalent contrapositi ...
from to a totally ordered set then induces a total ordering on by setting if and only if . * The
lexicographical order In mathematics, the lexicographic or lexicographical order (also known as lexical order, or dictionary order) is a generalization of the alphabetical order of the dictionaries to sequences of ordered symbols or, more generally, of elements of ...
on the
Cartesian product In mathematics, specifically set theory, the Cartesian product of two sets ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is : A\t ...
of a family of totally ordered sets, indexed by a well ordered set, is itself a total order. * The set of
real numbers 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 re ...
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 In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called '' cardinal ...
, integers, 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 ra ...
. Each of these can be shown to be the unique (up to an order isomorphism) "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. ** 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 elemen ...
. ** The rational numbers form an initial totally ordered set which is dense in the real numbers. Moreover, the reflexive reduction < is a
dense order In mathematics, a partial order or total order < on a X is said to be dense if, for all x
on the rational numbers. ** The real numbers form an initial unbounded totally ordered set that is connected in the order topology (defined below). * Ordered fields 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'' 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 In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset of ...
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 binary ...
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 ideals. 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 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 c ...
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 is a chain of length zero, and an
ordered pair In mathematics, an ordered pair (''a'', ''b'') is a pair of objects. The order in which the objects appear in the pair is significant: the ordered pair (''a'', ''b'') is different from the ordered pair (''b'', ''a'') unless ''a'' = ''b''. (In con ...
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 coord ...
of a space is often defined or characterized as the maximal length of chains of subspaces. For example, the dimension of a vector space is the maximal length of chains of
linear subspace In mathematics, and more specifically in linear algebra, a linear subspace, also known as a vector subspaceThe term ''linear subspace'' is sometimes used for referring to flats and affine subspaces. In the case of vector spaces over the reals, l ...
s, and the Krull dimension of a
commutative ring In mathematics, a commutative ring is a ring in which the multiplication operation is commutative. The study of commutative rings is called commutative algebra. Complementarily, noncommutative algebra is the study of ring properties that are not ...
is the maximal length of chains of
prime ideal In algebra, a prime ideal is a subset of a ring that shares many important properties of a prime number in the ring of integers. The prime ideals for the integers are the sets that contain all the multiples of a given prime number, together wi ...
s. "Chain" may also be used for some totally ordered subsets of structures that are not partially ordered sets. An example is given by
regular chain In computer algebra, a regular chain is a particular kind of triangular set in a multivariate polynomial ring over a field. It enhances the notion of characteristic set. Introduction Given a linear system, one can convert it to a triangular ...
s 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.


Further concepts


Lattice theory

One may define a totally ordered set as a particular kind of lattice, 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 bic ...
a = a\wedge b. Hence a totally ordered set is a distributive lattice.


Finite total orders

A simple counting 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. Either by direct proof or by observing that every well order is
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 ...
to an ordinal one may show that every finite total order is
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 ...
to an initial segment 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 suc ...
ω 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. Intuitively, ...
of the category 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 binary ...
s, with the
morphism In mathematics, particularly in category theory, a morphism is a structure-preserving map from one mathematical structure to another one of the same type. The notion of morphism recurs in much of contemporary mathematics. In set theory, morphisms ...
s being maps which respect the orders, i.e. maps ''f'' such that if ''a'' ≤ ''b'' then ''f''(''a'') ≤ ''f''(''b''). A bijective map 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 interval In mathematics, a (real) interval is a set of real numbers that contains all real numbers lying between any two numbers of the set. For example, the set of numbers satisfying is an interval which contains , , and all numbers in between. Other ...
s'' (''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. 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.


Completeness

A totally ordered set is said to be
complete Complete may refer to: Logic * Completeness (logic) * Completeness of a theory, the property of a theory that every formula in the theory's language or its negation is provable Mathematics * The completeness of the real numbers, which implies t ...
if every nonempty subset that has an upper bound, has a least upper bound. 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 ra ...
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 R has a least upper bound (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 In mathematics, a complete lattice is a partially ordered set in which ''all'' subsets have both a supremum (join) and an infimum (meet). A lattice which satisfies at least one of these properties is known as a ''conditionally 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 Britis ...
. 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 (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 isom ...
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 In mathematics and other formal sciences, first-order or first order most often means either: * "linear" (a polynomial of degree at most one), as in first-order approximation and other calculus uses, where it is contrasted with "polynomials of hig ...
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 In mathematics, specifically set theory, the Cartesian product of two sets ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is : A\t ...
of two totally ordered sets are: *
Lexicographical order In mathematics, the lexicographic or lexicographical order (also known as lexical order, or dictionary order) is a generalization of the alphabetical order of the dictionaries to sequences of ordered symbols or, more generally, of elements of ...
: (''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). 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 In mathematics, one can often define a direct product of objects already known, giving a new one. This generalizes the Cartesian product of the underlying sets, together with a suitably defined structure on the product set. More abstractly, one t ...
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. 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 binary ...
. A group 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. Forgetting the location of the ends results in a cyclic order. Forgetting both data results in a
separation relation In mathematics, a separation relation is a formal way to arrange a set of objects in an unoriented circle. It is defined as a quaternary relation ' satisfying certain axioms, which is interpreted as asserting that ''a'' and ''c'' separate ''b'' fro ...
.


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