fullorder

Full order, or total order, is a concept in order theory describing a way to arrange elements so that every pair of elements is comparable. Formally, a set X equipped with a binary relation ≤ is a total order if ≤ is reflexive, antisymmetric, and transitive, and for all a, b in X, either a ≤ b or b ≤ a. In contrast to partial orders, a total order requires no incomparabilities between elements.

A related notion is a strict total order, denoted <, which is irreflexive and transitive, and such that for any distinct a and b, exactly one of a < b or b < a holds. Every total order induces a strict total order by defining a < b if and only if a ≤ b and a ≠ b.

Examples of total orders include the standard order on the natural numbers, integers, and real numbers, as well as the lexicographic order on strings. In these systems, any two elements can be compared, and there is a well-defined notion of minimum and maximum for finite subsets.

Total orders are a special case of partial orders; in a total order, every pair of elements is comparable, whereas in a partial order some pairs may be incomparable. In a total order, any two elements have a greatest lower bound (minimum) and least upper bound (maximum), so such sets form a lattice under the order.

Many total orders can be well-orders, where every nonempty subset has a least element; however, not all total orders are well-orders (for example, the integers under ≤ are not well-ordered).

Applications of full orders include sorting in computer science, mathematical proofs, and the definition of rankings and prioritization in various disciplines. The term is often used interchangeably with total order or linear order.