View source for Total order

{{Short description|Order whose elements are all comparable}}
{{redirect-distinguish|Linear order|Linear order (linguistics)}}
{{More footnotes|date=February 2016}}
{{Use dmy dates|date=August 2021}}

In [[mathematics]], a '''total order''' or '''linear order''' is a [[partial order]] in which any two elements are comparable.  That is, a total order is a [[binary relation]] <math>\leq</math> on some [[Set (mathematics)|set]] <math>X</math>, which satisfies the following for all <math>a, b</math> and <math>c</math> in <math>X</math>:

# <math>a \leq a</math> ([[Reflexive relation|reflexive]]).
# If <math>a \leq b</math> and <math>b \leq c</math> then <math>a \leq c</math> ([[Transitive relation|transitive]]).
# If <math>a \leq b</math> and <math>b \leq a</math> then <math>a = b</math> ([[Antisymmetric relation|antisymmetric]]).
# <math>a \leq b</math> or <math>b \leq a</math> ([[Connected relation|strongly connected]], formerly called total).

Reflexivity (1.) already follows from connectedness (4.), but is required explicitly by many authors nevertheless, to indicate the kinship to partial orders.{{sfn|Halmos|1968|loc=Ch.14}}
Total orders are sometimes also called '''simple''',{{sfn|Birkhoff|1967|p=2}} '''connex''',{{sfn|Schmidt|Ströhlein|1993|p=32}} or '''full orders'''.{{sfn|Fuchs|1963|p=2}}

A set equipped with a total order is a '''totally ordered set''';{{sfn|Davey|Priestley|1990|p=3}} the terms '''simply ordered set''',{{sfn|Birkhoff|1967|p=2}} '''linearly ordered set''',{{sfn|Schmidt|Ströhlein|1993|p=32}}{{sfn|Davey|Priestley|1990|p=3}} and '''loset'''<ref>{{Cite journal|last1=Strohmeier|first1=Alfred|last2=Genillard|first2=Christian|last3=Weber|first3=Mats|date=1990-08-01|title=Ordering of characters and strings|journal=ACM SIGAda Ada Letters|language=EN|issue=7|pages=84|doi=10.1145/101120.101136|s2cid=38115497|doi-access=free}}</ref><ref>{{Cite journal|last=Ganapathy|first=Jayanthi|title=Maximal Elements and Upper Bounds in Posets|date=1992|journal=Pi Mu Epsilon Journal|volume=9|issue=7|pages=462–464|jstor=24340068|issn=0031-952X}}</ref> are also used. The term ''chain'' is sometimes defined as a synonym of ''totally ordered set'',{{sfn|Davey|Priestley|1990|p=3}} 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 '''{{em|strict total order}}''' on a set <math>X</math> is a [[strict partial order]] on <math>X</math> in which any two distinct elements are comparable. That is, a strict total order is a [[binary relation]] <math><</math> on some [[Set (mathematics)|set]] <math>X</math>, which satisfies the following for all <math>a, b</math> and <math>c</math> in <math>X</math>:
# Not <math>a < a</math> ([[Irreflexive relation|irreflexive]]).
# If <math>a < b</math> then not <math> b < a </math> ([[asymmetric relation|asymmetric]]).
# If <math>a < b</math> and <math>b < c</math> then <math>a < c</math> ([[Transitive relation|transitive]]).
# If <math>a \neq b</math>, then <math>a < b</math> or <math>b < a</math> ([[Connected relation|connected]]).

Asymmetry follows from transitivity and irreflexivity;<ref>Let <math>a < b</math>, assume for contradiction that also <math> b < a </math>. Then <math>a < a</math> by transitivity, which contradicts irreflexivity.</ref> moreover, irreflexivity follows from asymmetry.<ref>If <math>a < a</math>, the not <math>a < a</math> by asymmetry.</ref>

For delimitation purposes, a total order as defined in the [[#Top|lead]] is sometimes called ''non-strict'' order.
For each (non-strict) total order <math>\leq</math> there is an associated relation <math><</math>, called the ''strict total order'' associated with <math>\leq</math> that can be defined in two equivalent ways:
* <math>a < b</math> if <math>a \leq b</math> and <math>a \neq b</math> ([[reflexive reduction]]).
* <math>a < b</math> if not <math>b \leq a</math> (i.e., <math><</math> is the [[Binary relation#Complement|complement]] of the [[converse relation|converse]] of <math>\leq</math>).

Conversely, the [[reflexive closure]] of a strict total order <math><</math> is a (non-strict) total order.

==Examples==

* Any [[subset]] of a totally ordered set {{math|''X''}} is totally ordered for the restriction of the order on {{math|''X''}}. 
* The unique order on the empty set, {{math|∅}}, is a total order.
* Any set of [[cardinal number]]s or [[ordinal number]]s (more strongly, these are [[well-order]]s).
* If {{math|''X''}} is any set and {{math|''f''}}{{math|}} an [[injective function]] from {{math|''X''}} to a totally ordered set then {{math|''f''}} induces a total ordering on {{math|''X''}} by setting {{math|''x''<sub>1</sub> ≤ ''x''<sub>2</sub>}} if and only if {{math|''f''(''x''<sub>1</sub>) ≤ ''f''(''x''<sub>2</sub>)}}.
* The [[lexicographical order]] on the [[Cartesian product]] of a family of totally ordered sets, [[Index set|indexed]] by a [[well-order|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]], and [[rational numbers]]. 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 {{math|''A''}} is ''initial'' for a property, if, whenever {{math|''B''}} has the property, there is an order isomorphism from {{math|''A''}} to a subset of {{math|''B''}}):<ref>This definition resembles that of an [[initial object]] of a [[category (mathematics)|category]], but is weaker.</ref>{{citation needed|reason=such non-evident properties must be sourced; see talk page|date=March 2021}}
** 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]].
** The rational numbers form an initial totally ordered set which is [[dense set|dense]] 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 [[connectedness|connected]] in the [[order topology]] (defined below).
* [[Ordered field]]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]]'' ordered field is isomorphic to the real numbers.
* The letters of the alphabet ordered by the standard [[Alphabetical order|dictionary order]], e.g., {{math|''A'' < ''B'' < ''C''}} 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]] that is totally ordered for the induced order.{{sfn|Halmos|1968|loc=Ch.14}}<ref>{{cite book | url=https://www.elsevier.com/books/theory-of-relations/fraisse/978-0-444-50542-2 | isbn=978-0-444-50542-2 | author=Roland Fraïssé | author-link=Roland Fraïssé| title=Theory of Relations | publisher=Elsevier | series=Studies in Logic and the Foundations of Mathematics | volume=145 | edition=1st | date=Dec 2000 }} Here: p. 35</ref> 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 {{mvar|X}} has an upper bound in {{mvar|X}}, then {{mvar|X}} contains at least one maximal element.<ref>{{cite book | lccn=89009753 | isbn=0-521-36766-2 | author=Brian A. Davey and Hilary Ann Priestley | title=Introduction to Lattices and Order | publisher=Cambridge University Press | series=Cambridge Mathematical Textbooks | year=1990 }} Here: p. 100</ref> Zorn's lemma is commonly used with {{mvar|X}} being a set of subsets; in this case, the upperbound is obtained by proving that the union of the elements of a chain in {{mvar|X}} is in {{mvar|X}}. This is the way that is generally used to prove that a [[vector space]] has [[Hamel bases]] and that a [[ring (mathematics)|ring]] has [[maximal ideal]]s.

In some contexts, the chains that are considered are order isomorphic to the natural numbers with their usual order or its [[converse relation|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.<ref>[[Yiannis N. Moschovakis]] (2006) ''Notes on set theory'', [[Undergraduate Texts in Mathematics]] (Birkhäuser) {{ISBN|0-387-28723-X}}, p.&nbsp;116</ref>

A partially ordered set has the [[descending chain condition]] if every descending chain eventually stabilizes.<ref>that is, beyond some index, all further sequence members are equal</ref> For example, an order is [[well-founded order|well founded]] if it has the descending chain condition. Similarly, the [[ascending chain condition]] means that every ascending chain eventually stabilizes. For example, a [[Noetherian ring]] is a ring whose [[ideal (ring theory)|ideals]] satisfy the ascending chain condition.

In other contexts, only chains that are [[finite set]]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.<ref>Davey and Priestly 1990, Def.2.24, p. 37</ref> Thus a [[singleton set]] is a chain of length zero, and an [[ordered pair]] is a chain of length one. The [[dimension theory|dimension]] 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]]s, and the [[Krull dimension]] of a [[commutative ring]] is the maximal length of chains of [[prime ideal]]s.

"Chain" may also be used for some totally ordered subsets of [[mathematical structure|structures]] that are not partially ordered sets. An example is given by [[regular chain]]s of polynomials. Another example is the use of "chain" as a synonym for a [[walk (graph theory)|walk]] in a [[graph (discrete mathematics)|graph]].

==Further concepts==

===Lattice theory===

One may define a totally ordered set as a particular kind of [[Lattice (order)|lattice]], namely one in which we have
: <math>\{a\vee b, a\wedge b\} = \{a, b\}</math> for all ''a'', ''b''.

We then write ''a'' ≤ ''b'' [[if and only if]] <math>a = a\wedge b</math>. 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]] &omega; 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]]s, with the [[morphism]]s 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 {{mvar|X}} we can define the ''[[interval (mathematics)|open interval]]s'' 
* {{math|1=(''a'', ''b'') = {{mset|''x'' | ''a'' < ''x'' and ''x'' < ''b''}}}}, 
* {{math|1=(−∞, ''b'') = {{mset|''x'' | ''x'' < ''b''}}}}, 
* {{math|1=(''a'', ∞) = {{mset|''x'' | ''a'' < ''x''}}}}, and 
* {{math|1=(−∞, ∞) = ''X''}}.  
We can use these open intervals to define a [[topology]] 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, {{char|<}} is less than and {{char|>}} greater than we might refer to the order topology on '''N''' induced by {{char|<}} and the order topology on '''N''' induced by {{char|>}} (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===<!-- This section is linked from [[Completely distributive lattice]]. See [[WP:MOS#Section management]] -->

A totally ordered set is said to be '''[[Completeness (order theory)|complete]]''' if every nonempty subset that has an [[upper bound]], has a [[least upper bound]]. For example, the set of [[real number]]s '''R''' is complete but the set of [[rational number]]s '''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 number]]s a property of the relation {{char|≤}} is that every [[Empty set|non-empty]] subset ''S'' of '''R''' with an [[upper bound]] 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 {{char|≤}} 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 [[homeomorphism]]s between these examples.

===Sums of orders===<!-- This section is linked from [[Scattered_order]]. See [[WP:MOS#Section management]] -->

For any two disjoint total orders <math>(A_1,\le_1)</math>  and <math>(A_2,\le_2)</math>, there is a natural order <math>\le_+</math> on the set <math>A_1\cup A_2</math>, which is called the sum of the two orders or sometimes just <math>A_1+A_2</math>: 
: For <math>x,y\in A_1\cup A_2</math>, <math>x\le_+ y</math> holds if and only if one of the following holds:
:# <math>x,y\in A_1</math> and <math>x\le_1 y</math>
:# <math>x,y\in A_2</math> and <math>x\le_2 y</math>
:# <math>x\in A_1</math> and <math>y\in A_2</math>
Intuitively, this means that the elements of the second set are added on top of the elements of the first set.

More generally, if <math>(I,\le)</math> is a totally ordered index set, and for each <math>i\in I</math> the structure <math>(A_i,\le_i)</math> is a linear order, where the sets <math>A_i</math> are pairwise disjoint, then the natural total order on <math>\bigcup_i A_i</math> is defined by 
: For <math>x,y\in \bigcup_{i\in I} A_i</math>, <math>x\le y</math> holds if: 
:# Either there is some <math>i\in I</math> with <math> x\le_i y </math>
:# or there are some <math>i<j</math> in <math>I</math>  with <math> x\in A_i</math>,  <math> y\in A_j</math>

=== Decidability ===
The [[first-order logic|first-order]] theory of total orders is [[decidability (logic) | decidable]], i.e. there is an algorithm for deciding which first-order statements hold for all total orders.  Using interpretability in [[S2S (mathematics)|S2S]], the [[monadic second-order logic|monadic second-order]] theory of [[countable set|countable]] total orders is also decidable.<ref>{{Cite book | last=Weyer | first=Mark | date=2002 | title=Automata, Logics, and Infinite Games |chapter=Decidability of S1S and S2S | series=Lecture Notes in Computer Science | volume=2500 | pages=207–230 |chapter-url=https://link.springer.com/chapter/10.1007/3-540-36387-4_12 | doi=10.1007/3-540-36387-4_12 | publisher=Springer| isbn=978-3-540-00388-5 }}</ref>

==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]]). 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]] '''R'''<sup>''n''</sup>, 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'''<sup>''n''</sup> [[Strict weak ordering#Function|defines a strict weak order and a corresponding total preorder]] on that subset.

==Related structures==
{{stack|{{Binary relations}}}}
A binary relation that is antisymmetric, transitive, and reflexive (but not necessarily total) is a [[partial order]].

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]].<ref>{{Citation |last=Macpherson |first=H. Dugald |year=2011 |title=A survey of homogeneous structures |journal=Discrete Mathematics |volume=311 |issue=15 |pages=1599–1634 |doi=10.1016/j.disc.2011.01.024|doi-access=free }}</ref>

==See also==
{{cols}}
* {{annotated link|Artinian ring}}
* {{annotated link|Countryman line}}
* {{annotated link|Order theory}}
* {{annotated link|Permutation}}
* {{annotated link|Prefix order}} – a downward total partial order
* {{annotated link|Suslin's problem}}
* {{annotated link|Well-order}}
{{colend}}

==Notes==

{{reflist}}

==References==

* {{cite book | author=Garrett Birkhoff | author-link=Garrett Birkhoff | title=Lattice Theory | location=Providence | publisher=Am. Math. Soc. | series=Colloquium Publications | volume=25 | year=1967 }}
* {{cite book | author1=Brian A. Davey | author2=Hilary Ann Priestley | author2-link=Hilary Priestley | title=Introduction to Lattices and Order|title-link= Introduction to Lattices and Order | publisher=Cambridge University Press | series=Cambridge Mathematical Textbooks | isbn=0-521-36766-2 | lccn=89009753 | year=1990 }}
* {{cite book |last=Fuchs |first=L  |title=Partially Ordered Algebraic Systems |publisher=Pergamon Press|year=1963}}
* George Grätzer (1971). ''Lattice theory: first concepts and distributive lattices.'' W. H. Freeman and Co. {{isbn|0-7167-0442-0}}
* {{cite book | first=Paul R. |last=Halmos | author-link=Paul R. Halmos | title=Naive Set Theory | location=Princeton | publisher=Nostrand | year=1968 }}
* John G. Hocking and Gail S. Young (1961). ''Topology.'' Corrected reprint, Dover, 1988.  {{isbn|0-486-65676-4}}
* {{Cite book| publisher = Academic Press| last = Rosenstein| first = Joseph G.| title = Linear orderings| location = New York| date = 1982}}
* {{cite book |last1=Schmidt |first1=Gunther |last2=Ströhlein |first2=Thomas |date=1993 |title=Relations and Graphs: Discrete Mathematics for Computer Scientists |url=https://books.google.com/books?id=ZgarCAAAQBAJ |location=Berlin |publisher=Springer-Verlag |isbn=978-3-642-77970-1 |author-link=Gunther Schmidt }}

==External links==

* {{SpringerEOM
 |title=Totally ordered set
 |id=Total_order&oldid=35332
}}

{{Order theory}}

[[Category:Binary relations]]
[[Category:Order theory]]
[[Category:Set theory]]