HOME

TheInfoList




In
mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and their changes (cal ...
, a total or linear order is a
partial order In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
in which any two elements are comparable. That is, a total order is a
binary relation Binary may refer to: Science and technology Mathematics * Binary number In mathematics and digital electronics Digital electronics is a field of electronics The field of electronics is a branch of physics and electrical engineeri ...
\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 Transitivity or transitive may refer to: Grammar * Transitivity (grammar), a property of verbs that relates to whether a verb can take direct objects * Transitive verb, a verb which takes an object * Transitive case, a grammatical case to mark arg ...
) # 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 reachability, reachable from every other vertex. The strongly connected Component (graph theory), components of an arbitrary directed graph ...
, 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 Order theory is a branch of mathematics which investigates the intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". ...
of that partial order.


Strict and non-strict total orders

A on a set X is a
strict partial order In mathematical Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
on X in which any two elements are comparable. That is, a total order is a
binary relation Binary may refer to: Science and technology Mathematics * Binary number In mathematics and digital electronics Digital electronics is a field of electronics The field of electronics is a branch of physics and electrical engineeri ...
< on some set X, which satisfies the following for all a, b and c in X: # Not a < a (
irreflexive In mathematics, a homogeneous binary relation ''R'' over a set (mathematics), set ''X'' is reflexive if it relates every element of ''X'' to itself. An example of a reflexive relation is the relation "equality (mathematics), is equal to" on the se ...
). # If a < b and b < c then a < c (
transitive Transitivity or transitive may refer to: Grammar * Transitivity (grammar), a property of verbs that relates to whether a verb can take direct objects * Transitive verb, a verb which takes an object * Transitive case, a grammatical case to mark arg ...
). # If a \neq b, then a < b or b < a ( connected). 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 often something that completes something else, or at least adds to it in some useful way. Thus it may be: * Complement (linguistics), a word or phrase having a particular syntactic role ** Subject complement, a word or phrase addi ...

complement
of the
converse Converse may refer to: Mathematics and logic * Converse (logic), the result of reversing the two parts of a categorical or implicational statement ** Converse implication, the converse of a material implication ** Converse nonimplication, a logical ...
of \leq). Conversely, the
reflexive closure In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and the ...
of a strict total order < is a (non-strict) total order.


Examples

* Any
subset In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities a ...

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 Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
s or
ordinal number In set theory Set theory is the branch of that studies , which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of , is mostly concerned with those that ...
s (more strongly, these are
well-order In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
s). * If is any set and an
injective function In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...

injective function
from to a totally ordered set then induces a total ordering on by setting if and only if . * The
lexicographical order In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
on the
Cartesian product In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
of a family of totally ordered sets,
indexed Index may refer to: Arts, entertainment, and media Fictional entities * Index (A Certain Magical Index), Index (''A Certain Magical Index''), a character in the light novel series ''A Certain Magical Index'' * The Index, an item on a Halo (megastr ...
by a well ordered set, is itself a total order. * The set of
real numbers In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities an ...

real numbers
ordered by the usual "less than or equal to" (≤) or "greater than or equal to" (≥) relations is totally ordered, and hence so are the subsets of
natural numbers In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and total order, ordering (as in "this is the ''third'' largest city in the country"). In common mathematical terminology, w ...

natural numbers
,
integers An integer (from the Latin Latin (, or , ) is a classical language belonging to the Italic languages, Italic branch of the Indo-European languages. Latin was originally spoken in the area around Rome, known as Latium. Through the power ...

integers
, and
rational numbers In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities a ...
. Each of these can be shown to be the unique (up to an
order isomorphism In the mathematical Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities an ...
) "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 Order theory is a branch of mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), sh ...
. ** The integers form an initial non-empty totally ordered set with neither an upper nor a
lower bound In mathematics, particularly in order theory Order theory is a branch of mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), sh ...
. ** The rational numbers form an initial totally ordered set which is
dense The density (more precisely, the volumetric mass density; also known as specific mass), of a substance is its mass Mass is both a property Property (''latin: Res Privata'') in the Abstract and concrete, abstract is what belongs to or ...
in the real numbers. Moreover, the reflexive reduction < is a
dense order In mathematics, a partial order or total order < on a Set (mathematics), 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 ...
on the rational numbers. ** The real numbers form an initial unbounded totally ordered set that is connected 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, the ...
(defined below). *
Ordered field In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and the ...
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 Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and th ...
'' 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 Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities a ...

subset
of a
partially ordered set In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
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 Zorn's lemma, also known as the Kuratowski–Zorn lemma, after mathematicians Max August Zorn, Max Zorn and Kazimierz Kuratowski, is a proposition of set theory. It states that a partially ordered set containing upper bounds for every chain (or ...
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 Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities a ...
has
Hamel bases In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
and that a ring has
maximal ideal In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and th ...
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 conditionIn mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ha ...
if every descending chain eventually stabilizes. For example, an order is well founded if it has the descending chain condition. Similarly, the
ascending chain conditionIn mathematics, the ascending chain condition (ACC) and descending chain condition (DCC) are finiteness properties satisfied by some algebraic structures, most importantly Ideal (ring theory), ideals in certain commutative rings.Jacobson (2009), p. 1 ...
means that every ascending chain eventually stabilizes. For example, a
Noetherian ring In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and th ...
is a ring whose
ideals Ideal may refer to: Philosophy * Ideal (ethics), values that one actively pursues as goals * Platonic ideal, a philosophical idea of trueness of form, associated with Plato Mathematics * Ideal (ring theory), special subsets of a ring considered ...
satisfy the ascending chain condition. In other contexts, only chains that are
finite set In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and 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 Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
is a chain of length zero, and an
ordered pair In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and th ...

ordered pair
is a chain of length one. The
dimension In physics Physics is the that studies , its , its and behavior through , and the related entities of and . "Physical science is that department of knowledge which relates to the order of nature, or, in other words, to the regular s ...
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 Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and th ...
is the maximal length of chains of
linear subspace In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and t ...
s, and the
Krull dimension In commutative algebra Commutative algebra is the branch of algebra Algebra (from ar, الجبر, lit=reunion of broken parts, bonesetting, translit=al-jabr) is one of the areas of mathematics, broad areas of mathematics, together with ...
of a
commutative ring In ring theory In algebra Algebra (from ar, الجبر, lit=reunion of broken parts, bonesetting, translit=al-jabr) is one of the areas of mathematics, broad areas of mathematics, together with number theory, geometry and mathematical ana ...
is the maximal length of chains of
prime ideal In algebra Algebra (from ar, الجبر, lit=reunion of broken parts, bonesetting, translit=al-jabr) is one of the areas of mathematics, broad areas of mathematics, together with number theory, geometry and mathematical analysis, analysis. ...
s. "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 A system is a group of Interaction, interacting or interrelated elements that act according to a set of rules to form a unified whole. ...
that are not partially ordered sets. An example is given by
regular chain In computer algebra In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry) ...
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 gait Gait is the pattern of movement Movement may refer to: Common uses * Movement (clockwork), the internal mechanism of a timepiece * Motion (physics), commonly referred to as move ...
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 discret ...
.


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 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 to an Ordinal number, ordinal one may show that every finite total order is order isomorphic 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 ω by natural numbers in a fashion which respects the ordering (either starting with zero or with one).


Category theory

Totally ordered sets form a subcategory, full subcategory of the category (mathematics), category of
partially ordered set In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
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 bijection, bijective map (mathematics), map between two totally ordered sets that respects the two orders is an isomorphism in this category.


Order topology

For any totally ordered set ''X'' we can define the ''interval (mathematics), open intervals'' (''a'', ''b'') = , (−∞, ''b'') = , (''a'', ∞) = and (−∞, ∞) = ''X''. We can use these open intervals to define a topology 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, the ...
. 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 space, normal.


Completeness

A totally ordered set is said to be Completeness (order theory), complete if every nonempty subset that has an
upper bound In mathematics, particularly in order theory Order theory is a branch of mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), sh ...
, has a least upper bound. For example, the set of real numbers R is complete but the set of rational numbers Q is not. In other words, the various concepts of Completeness (order theory), completeness (not to be confused with being "total") do not carry over to Binary relation, restrictions. For example, over the real numbers a property of the relation ≤ is that every Empty set, non-empty subset ''S'' of R with an
upper bound In mathematics, particularly in order theory Order theory is a branch of mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), sh ...
in R has a Supremum, 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 is Compact space, compact. Examples are the closed intervals of real numbers, e.g. the unit interval [0,1], and the affinely extended real number system (extended real number line). There are order-preserving homeomorphisms 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


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 Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
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). 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#Direct product of binary relations, 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 Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities a ...
R''n'', each of these make it an ordered vector space. See also Partially ordered set#Examples, examples of partially ordered sets. A real function of ''n'' real variables defined on a subset of R''n'' Strict weak ordering#Function, 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 Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
. A group (mathematics), 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.


See also

* Artinian ring * Order theory * Well-order * Suslin's problem * Countryman line * Permutation * Prefix order – 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

* {{SpringerEOM , title=Totally ordered set , id=Total_order&oldid=35332 Binary relations Order theory Set theory