# Total order

This article includes a list of general references, but it remains largely unverified because it lacks sufficient corresponding inline citations. (February 2016) (Learn how and when to remove this template message) |

Binary relations | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

A "✓" indicates that the column property is required in the row definition. For example, the definition of an equivalence relation requires it to be symmetric. All definitions tacitly require transitivity and reflexivity. |

In mathematics, a **total order**, **simple order**,^{[1]} **linear order**, **connex order**,^{[2]} or **full order**^{[3]} is a binary relation on some set , which is antisymmetric, transitive, and a connex relation. A set paired with a total order is called a **chain**,^{[4]} a **totally ordered set**,^{[4]} a **simply ordered set**,^{[1]} a **linearly ordered set**,^{[2]}^{[4]} or a **loset**.^{[5]}^{[6]}

Formally, a binary relation is a total order on a set if the following statements hold for all and in :

- Antisymmetry
- If and then ;
- Transitivity
- If and then ;
- Connexity
- or .

Antisymmetry eliminates uncertain cases when both precedes and precedes .^{[7]}^{:325} A relation having the *connex* property means that any pair of elements in the set of the relation are comparable under the relation. This also means that the set can be diagrammed as a line of elements, giving it the name *linear*.^{[7]}^{:330} The *connex* property also implies reflexivity, i.e., *a* ≤ *a*. Therefore, a total order is also a (special case of a) partial order, as, for a partial order, the connex property is replaced by the weaker reflexivity property. An extension of a given partial order to a total order is called a linear extension of that partial order.

## Strict total orderEdit

For each (non-strict) total order ≤ there is an associated asymmetric (hence irreflexive) transitive semiconnex relation <, called a **strict total order** or **strict semiconnex order**,^{[2]} which can be defined in two equivalent ways:

*a*<*b*if*a*≤*b*and*a*≠*b**a*<*b*if not*b*≤*a*(i.e., < is the inverse of the complement of ≤)

Properties:

- The relation is transitive:
*a*<*b*and*b*<*c*implies*a*<*c*. - The relation is trichotomous: exactly one of
*a*<*b*,*b*<*a*and*a*=*b*is true. - The relation is a strict weak order, where the associated equivalence is equality.

We can work the other way and start by choosing < as a transitive trichotomous binary relation; then a total order ≤ can be defined in two equivalent ways:

*a*≤*b*if*a*<*b*or*a*=*b**a*≤*b*if not*b*<*a*

Two more associated orders are the complements ≥ and >, completing the quadruple {<, >, ≤, ≥}.

We can define or explain the way a set is totally ordered by any of these four relations; the notation implies whether we are talking about the non-strict or the strict total order.

## ExamplesEdit

- The letters of the alphabet ordered by the standard dictionary order, e.g.,
*A*<*B*<*C*etc. - Any subset of a totally ordered set
*X*is totally ordered for the restriction of the order on*X*. - The unique order on the empty set, ∅, is a total order.
- Any set of cardinal numbers or ordinal numbers (more strongly, these are well-orders).
- If
*X*is any set and*f*an injective function from*X*to a totally ordered set then*f*induces a total ordering on*X*by setting*x*_{1}<*x*_{2}if and only if*f*(*x*_{1}) <*f*(*x*_{2}). - 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 "greater than" (>) relations is totally ordered, and hence so are the subsets of natural numbers, integers, and rational numbers. Each of these can be shown to be the unique (up to order isomorphism)
*smallest*example of a totally ordered set with a certain property, (a total order*A*is the*smallest*with a certain property if whenever*B*has the property, there is an order isomorphism from*A*to a subset of*B*):- The natural numbers comprise the smallest non-empty totally ordered set with no upper bound.
- The integers comprise the smallest non-empty totally ordered set with neither an upper nor a lower bound.
- The rational numbers comprise the smallest totally ordered set which is
*dense*in the real numbers. The definition of density used here says that for every*a*and*b*in the real numbers such that*a*<*b*, there is a*q*in the rational numbers such that*a*<*q*<*b*. - The real numbers comprise the smallest 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.

## ChainsEdit

- The term
**chain**is a synonym for a totally ordered set, in particular, the term is often used to mean a totally ordered subset of some partially ordered set, for example in Zorn's lemma.^{[8]} - An
**ascending chain**is a totally ordered set having a (unique) minimal element, while a**descending chain**is a totally ordered set having a (unique) maximal element.^{[citation needed]} - Given a set
*S*with a partial order ≤, an**infinite descending chain**is an infinite, strictly decreasing sequence of elements*x*._{1}> x_{2}> ...^{[9]}As an example, in the set of integers, the chain −1, −2, −3, ... is an infinite descending chain, but there exists no infinite descending chain on the natural numbers, as every chain of natural numbers has a minimal element. If a partially ordered set does not possess any infinite descending chains, it is said to satisfy the descending chain condition. Assuming the axiom of choice, the descending chain condition on a partially ordered set is equivalent to requiring that the corresponding strict order is well-founded. A stronger condition, that there be no infinite descending chains and no infinite antichains, defines the well-quasi-orderings. A totally ordered set without infinite descending chains is called well-ordered. - See also Ascending chain condition for this notion.

- The
**height**of a poset denotes the cardinality of its largest chain in this sense.^{[citation needed]} - For example, consider the set of all subsets of the integers, partially ordered by inclusion. Then the set {
*I*_{n}:*n*is a natural number}, where*I*_{n}is the set of natural numbers below*n*, is a chain in this ordering, as it is totally ordered under inclusion: If*n*≤*k*, then*I*_{n}is a subset of*I*_{k}.

## Further conceptsEdit

### Lattice theoryEdit

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 . Hence a totally ordered set is a distributive lattice.

### Finite total ordersEdit

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 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 theoryEdit

Totally ordered sets form a full subcategory of the category of partially ordered sets, 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 map between two totally ordered sets that respects the two orders is an isomorphism in this category.

### Order topologyEdit

For any totally ordered set *X* we can define the **open intervals** (*a*, *b*) = {*x* : *a* < *x* and *x* < *b*}, (−∞, *b*) = {*x* : *x* < *b*}, (*a*, ∞) = {*x* : *a* < *x*} and (−∞, ∞) = *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, < 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.

### CompletenessEdit

A totally ordered set is said to be **complete** if every nonempty subset that has an upper bound, has a least upper bound. For example, the set of real numbers **R** is complete but the set of rational numbers **Q** is not.

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. 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 ordersEdit

For any two disjoint total orders and , there is a natural order on the set , which is called the sum of the two orders or sometimes just :

- For , holds if and only if one of the following holds:
- and
- and
- and

Intuitively, this means that the elements of the second set are added on top of the elements of the first set.

More generally, if is a totally ordered index set, and for each the structure is a linear order, where the sets are pairwise disjoint, then the natural total order on is defined by

- For , holds if:
- Either there is some with
- or there are some in with ,

## Orders on the Cartesian product of totally ordered setsEdit

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 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**^{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 structuresEdit

A binary relation that is antisymmetric, transitive, and reflexive (but not necessarily total) is a partial order.

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.^{[10]}

## See alsoEdit

- Artinian ring
- Order theory
- Well-order
- Suslin's problem
- Countryman line
- Prefix order – a downward total partial order

## NotesEdit

- ^
^{a}^{b}Birkhoff 1967, p. 2. - ^
^{a}^{b}^{c}Schmidt & Ströhlein 1993, p. 32. **^**Fuchs 1963, p. 2.- ^
^{a}^{b}^{c}Davey & Priestley 1990, p. 3. **^**Strohmeier, Alfred; Genillard, Christian; Weber, Mats (1 August 1990). "Ordering of characters and strings".*ACM SIGAda Ada Letters*(7): 84. doi:10.1145/101120.101136.**^**Ganapathy, Jayanthi (1992). "Maximal Elements and Upper Bounds in Posets".*Pi Mu Epsilon Journal*.**9**(7): 462–464. ISSN 0031-952X. JSTOR 24340068.- ^
^{a}^{b}Nederpelt, Rob (2004).*Logical Reasoning: A First Course*. Texts in Computing.**3**(3rd, Revised ed.). King's College Publications. ISBN 0-9543006-7-X. **^**Paul R. Halmos (1968).*Naive Set Theory*. Princeton: Nostrand. Here: Chapter 14**^**Yiannis N. Moschovakis (2006)*Notes on set theory*, Undergraduate Texts in Mathematics (Birkhäuser) ISBN 0-387-28723-X, p. 116**^**Macpherson, H. Dugald (2011), "A survey of homogeneous structures",*Discrete Mathematics*,**311**(15): 1599–1634, doi:10.1016/j.disc.2011.01.024

## ReferencesEdit

- Garrett Birkhoff (1967).
*Lattice Theory*. Colloquium Publications.**25**. Providence: Am. Math. Soc. - Brian A. Davey; Hilary Ann Priestley (1990).
*Introduction to Lattices and Order*. Cambridge Mathematical Textbooks. Cambridge University Press. ISBN 0-521-36766-2. LCCN 89009753. - Fuchs, L (1963).
*Partially Ordered Algebraic Systems*. Pergamon Press. - George Grätzer (1971).
*Lattice theory: first concepts and distributive lattices.*W. H. Freeman and Co. ISBN 0-7167-0442-0 - John G. Hocking and Gail S. Young (1961).
*Topology.*Corrected reprint, Dover, 1988. ISBN 0-486-65676-4 - Schmidt, Gunther; Ströhlein, Thomas (1993).
*Relations and Graphs: Discrete Mathematics for Computer Scientists*. Berlin: Springer-Verlag. ISBN 978-3-642-77970-1.

## External linksEdit

- "Totally ordered set",
*Encyclopedia of Mathematics*, EMS Press, 2001 [1994]