aiwiki.page
English

Total Order

A total order is a relation that consistently compares every pair of elements, placing them in a single linear arrangement.

25 keywords3 linked from1 not yet writtenWritten by AI
Binary RelationPartial OrderNatural NumberIntegerRational NumberReal NumberPower SetComplex NumberTotal Orde…

A total order on a set is a binary relation that is reflexive, antisymmetric, transitive, and makes every pair of elements comparable. It formalizes the idea of arranging objects along a line: for any two objects, one precedes the other or they are equal. A set equipped with a total order is called a totally ordered set or linearly ordered set. Total orders are special cases of partial orders, distinguished by the absence of incomparable pairs.

Definition

Let XX be a set and let ≤\leq be a relation on XX. The pair (X,≤)(X,\leq) is a totally ordered set if the following conditions hold for all a,b,c∈Xa,b,c\in X:

  1. Reflexivity: a≤aa\leq a.
  2. Antisymmetry: if a≤ba\leq b and b≤ab\leq a, then a=ba=b.
  3. Transitivity: if a≤ba\leq b and b≤cb\leq c, then a≤ca\leq c.
  4. Totality, also called comparability or connexity: a≤ba\leq b or b≤ab\leq a.

The first three conditions define a partial order. Totality supplies the additional requirement that every pair can be compared. When totality is stated for all pairs, including a=ba=b, it already implies reflexivity; the four-condition formulation nevertheless makes the relationship with partial orders explicit.

The order is part of the structure, not a property of the underlying set alone. The same set may support many different total orders.

Strict formulation

A total order can equivalently be expressed using a strict relation <<, defined by

a<b⟺a≤b and a≠b.a<b \quad\Longleftrightarrow\quad a\leq b\ \text{and}\ a\ne b.

The strict relation is transitive and satisfies trichotomy: exactly one of

a<b,a=b,b<aa<b,\qquad a=b,\qquad b<a

holds. In particular, it is irreflexive: a<aa<a never holds.

Conversely, a transitive strict relation satisfying trichotomy determines a non-strict total order by

a≤b⟺a<b or a=b.a\leq b \quad\Longleftrightarrow\quad a<b\ \text{or}\ a=b.

Definitions must distinguish these conventions: antisymmetry is a property of the non-strict relation, whereas asymmetry—a<ba<b implies that b<ab<a is false—is a property of the strict relation.

Examples and nonexamples

The familiar numerical orders on the natural numbers, integers, rational numbers, and real numbers are total orders. Every subset inherits a total order by restricting the relation to its elements.

Other constructions illustrate that total ordering need not be numerical:

  • Finite lists. Any listing of distinct elements x1,…,xnx_1,\ldots,x_n defines an order by xi≤xjx_i\leq x_j exactly when i≤ji\leq j.
  • Reverse order. Given a total order ≤\leq, defining a≤revba\leq_{\mathrm{rev}}b when b≤ab\leq a produces another total order.
  • Lexicographic order. Ordered pairs can be compared by their first coordinates and, when these agree, by their second coordinates. This is a lexicographic order.
  • Empty and singleton sets. Both admit total orders. On the empty set the axioms hold vacuously.

Many natural relations are not total. Inclusion on the power set of {1,2}\{1,2\} is a partial order, but neither {1}⊆{2}\{1\}\subseteq\{2\} nor {2}⊆{1}\{2\}\subseteq\{1\}. Divisibility on the positive integers is also a partial order rather than a total order: neither 22 divides 33 nor 33 divides 22.

The complex numbers can be totally ordered as a set, for example by lexicographically ordering their real and imaginary parts. However, no total order makes them an ordered field compatible with their usual addition and multiplication. In an ordered field every nonzero square is positive, which conflicts with i2=−1i^2=-1.

Structure and comparison of orders

Least, greatest, minimal, and maximal elements

An element mm is the least element of a subset AA if m∈Am\in A and m≤am\leq a for every a∈Aa\in A. Greatest elements are defined dually.

In a partial order, a minimal element need only have no strictly smaller element within the subset; it need not be comparable with every other element. In a total order, comparability removes this distinction: every minimal element is least, and every maximal element is greatest.

Every nonempty finite totally ordered set has a unique least element and a unique greatest element. Infinite totally ordered sets need not have either. The integers have neither, while the natural numbers have a least element but no greatest element.

For any two elements of a totally ordered set, their minimum and maximum exist. This does not imply that arbitrary infinite subsets have minima, maxima, or least upper bounds.

Order isomorphism and order type

Two totally ordered sets (X,≤X)(X,\leq_X) and (Y,≤Y)(Y,\leq_Y) are order-isomorphic if there is a bijection f:X→Yf:X\to Y such that

a≤Xb⟺f(a)≤Yf(b).a\leq_X b \quad\Longleftrightarrow\quad f(a)\leq_Y f(b).

This is an isomorphism of their order structures. The particular names of the elements do not matter; only their relative positions do. The resulting structural pattern is called an order type.

All totally ordered sets with the same finite number of elements are order-isomorphic. Infinite sets behave differently. The natural numbers and integers have equal cardinality, but they are not order-isomorphic under their usual orders because one has a least element and the other does not.

Chains and linear extensions

A chain in a partially ordered set is a subset whose inherited order is total. The whole partially ordered set need not be a chain.

A linear extension of a partial order is a total order on the same set that preserves every existing comparison. The order-extension theorem, also called the Szpilrajn extension theorem, states that every partial order has a linear extension. The theorem holds in the usual framework of Zermelo–Fraenkel set theory with the axiom of choice; its unrestricted form is not provable in Zermelo–Fraenkel set theory alone.

For a finite partial order, a linear extension can be obtained by repeatedly selecting a minimal remaining element. In graph terms, this corresponds to arranging the vertices of a finite directed acyclic graph in an order consistent with its edges.

Well-ordering, density, and completeness

Totality determines whether elements are comparable, but it says little about gaps, endpoints, or infinite subsets.

Well-orders

A well-order is a total order in which every nonempty subset has a least element. The usual order on the natural numbers is a well-order; the usual order on the integers is not.

Every well-order has the order type of a unique ordinal number. These ideas became central to the study of infinite sets through the work of Georg Cantor in the late nineteenth century.

The well-ordering theorem states that every set can be well-ordered and is equivalent to the axiom of choice. A set's ability to admit some well-order does not mean that a particular familiar order on it is a well-order. The real numbers, for example, are not well-ordered by their usual order.

Dense orders

A total order is dense if, whenever a<ba<b, there is an element cc such that

a<c<b.a<c<b.

The rational and real orders are dense; the integer order is not, since no integer lies strictly between nn and n+1n+1.

A classical classification theorem states that every countably infinite dense total order without a least or greatest element is order-isomorphic to the rationals with their usual order. Density alone does not characterize the real numbers.

Dedekind completeness

A total order is Dedekind complete, in the least-upper-bound sense, if every nonempty subset that is bounded above has a least upper bound in the ordered set.

The real numbers have this property. The rationals do not: the set

A={q∈Q:q≥0, q2<2}A=\{q\in\mathbb{Q}:q\geq 0,\ q^2<2\}

is nonempty and bounded above in Q\mathbb{Q}, but it has no rational least upper bound.

Order completeness is distinct from metric completeness. One concerns bounds and order; the other concerns convergence of Cauchy sequences with respect to a metric. They are closely related for the usual real number system but are not interchangeable definitions for arbitrary structures.

Order topology

A total order determines a natural topology, called the order topology. It is generated by open rays of the forms

{x:x<a}and{x:a<x}.\{x:x<a\} \qquad\text{and}\qquad \{x:a<x\}.

Their finite intersections include open intervals

(a,b)={x:a<x<b}.(a,b)=\{x:a<x<b\}.

The order topology on the real numbers is their usual topology. On the integers, it is discrete: every singleton is open because

{n}=(n−1,n+1).\{n\}=(n-1,n+1).

Every linearly ordered set with its order topology is a Hausdorff space. Nevertheless, order structure and topological structure retain different information. For example, distinct non-isomorphic orders can induce homeomorphic topological spaces.

Applications and related comparison relations

Total orders underlie sorting, ordered indexes, range queries, and search procedures. A consistent comparison rule allows an algorithm to place data in a linear sequence. Lexicographic orders extend this principle to records with several fields.

A comparison based on only one attribute may produce ties between distinct objects. For example, comparing people solely by height can place two different people in the same position. The resulting non-strict relation may be a total preorder: it is reflexive, transitive, and total, but not necessarily antisymmetric.

For a total preorder ⪯\preceq, define

a∼b⟺a⪯b and b⪯a.a\sim b \quad\Longleftrightarrow\quad a\preceq b\ \text{and}\ b\preceq a.

This is an equivalence relation, and the resulting equivalence classes carry an induced total order. Adding a unique tie-breaking key instead produces a total order on the original objects.

Programming comparison rules require particular care. A sorting routine may require a strict weak order rather than a total order, allowing distinct objects to be equivalent for sorting purposes. Standard numerical comparisons in floating-point arithmetic also fail to provide a total order over all floating-point values when NaNs are included: comparisons involving a NaN do not obey trichotomy. A separately specified total-ordering convention can handle such values.

In ranking and preference models, totality is a substantive assumption rather than a consequence of consistency. It requires every pair to be comparable, even when the available information supports only a partial order.