# Total order
A total order is a binary relation on a set that is reflexive, transitive, antisymmetric, and total, meaning that every pair of elements is comparable: for any elements a and b, either a ≤ b or b ≤ a.[1](https://xlinux.nist.gov/dads/HTML/totalorder.html) A total order is also called a linear order, and a set equipped with one is called a totally ordered set, a linearly ordered set, or a chain.[2](https://encyclopediaofmath.org/wiki/Order_%28on_a_set%29) • [3](https://mathworld.wolfram.com/TotallyOrderedSet.html)
| Key fact | Detail |
|---|---|
| Axioms | Reflexivity, antisymmetry, transitivity (the partial order axioms) plus comparability[3](https://mathworld.wolfram.com/TotallyOrderedSet.html) |
| Other names | Linear order; a set with a total order is a chain or totally (linearly) ordered set[2](https://encyclopediaofmath.org/wiki/Order_%28on_a_set%29) |
| Standard examples | The usual order ≤ is total on ℕ, ℤ, ℚ, and ℝ; subset inclusion on a power set is not total unless the underlying set has at most one element[4](https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Elementary_Foundations%3A_An_Introduction_to_Topics_in_Discrete_Mathematics_%28Sylvestre%29/19%3A_Partially_ordered_sets/19.04%3A_Total_Orders) |
| Finite case | A partial order on a finite set is total if and only if its Hasse diagram is a single vertical line[4](https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Elementary_Foundations%3A_An_Introduction_to_Topics_in_Discrete_Mathematics_%28Sylvestre%29/19%3A_Partially_ordered_sets/19.04%3A_Total_Orders) |
| Extension theorem | Every partial order has a linear extension (Szpilrajn's theorem, 1930)[5](https://impan.pl/pl/wydawnictwa/czasopisma-i-serie-wydawnicze/fundamenta-mathematicae/all/16/0/92870/sur-l-extension-de-l-ordre-partiel) • [6](https://encyclopediaofmath.org/wiki/Extension_of_an_order) |
| Counting cost | Counting the linear extensions of a finite poset is #P-complete[7](https://arxiv.org/abs/2506.14725) |
## Definition and strict form
The four defining properties, for a relation ≤ on a set S, are:[3](https://mathworld.wolfram.com/TotallyOrderedSet.html)
1. Reflexivity: a ≤ a for all a in S.
2. Antisymmetry: if a ≤ b and b ≤ a, then a = b.
3. Transitivity: if a ≤ b and b ≤ c, then a ≤ c.
4. Comparability: for any a, b in S, either a ≤ b or b ≤ a.
The first three are exactly the axioms of a partial order; adding comparability yields a total order.[3](https://mathworld.wolfram.com/TotallyOrderedSet.html) From a total order one derives the associated strict order < by setting a < b when a ≤ b and a ≠ b; a strict order is instead characterized by transitivity together with the condition that a < b and b < a cannot both hold.[2](https://encyclopediaofmath.org/wiki/Order_%28on_a_set%29) Weaker structures sit nearby: a relation with only reflexivity and transitivity is a pre-order or quasi-order, and a quasi-order induces an order on the quotient by its associated equivalence relation.[2](https://encyclopediaofmath.org/wiki/Order_%28on_a_set%29)
## Examples and non-examples
The most familiar total orders are the usual orders on the number systems: ≤ is a total order on ℕ, on ℤ, on ℚ, and on ℝ.[4](https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Elementary_Foundations%3A_An_Introduction_to_Topics_in_Discrete_Mathematics_%28Sylvestre%29/19%3A_Partially_ordered_sets/19.04%3A_Total_Orders) On the real numbers the order has the stronger property that for any a and b exactly one of a < b, a = b, or a > b holds, together with transitivity.[8](https://encyclopediaofmath.org/wiki/Real_number)
**Subset inclusion is the standard non-example.** For a universal set U, the inclusion order ⊆ on the power set 𝒫(U) is not total except when |U| ≤ 1: for distinct x, y in U, the singletons {x} and {y} are incomparable, since neither contains the other.[4](https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Elementary_Foundations%3A_An_Introduction_to_Topics_in_Discrete_Mathematics_%28Sylvestre%29/19%3A_Partially_ordered_sets/19.04%3A_Total_Orders) • [1](https://xlinux.nist.gov/dads/HTML/totalorder.html) Incomparability does not require disjointness; two subsets are incomparable under ⊆ as soon as each contains an element the other lacks.[4](https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Elementary_Foundations%3A_An_Introduction_to_Topics_in_Discrete_Mathematics_%28Sylvestre%29/19%3A_Partially_ordered_sets/19.04%3A_Total_Orders)
Total orders also arise by construction. If ⪯ is a total order on an alphabet Σ, the lexicographic order ⪯* is a total order on the set Σ* of all words over that alphabet.[4](https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Elementary_Foundations%3A_An_Introduction_to_Topics_in_Discrete_Mathematics_%28Sylvestre%29/19%3A_Partially_ordered_sets/19.04%3A_Total_Orders) Pulling a total order back through an injection preserves totality: if B is totally ordered and f: A → B is injective, defining a ≤ b by f(a) ≤ f(b) gives a total order on A. Applying this to a bijection ℕ → A shows that every countably infinite set admits a total order, obtained by listing its elements as a sequence a₀ ≤ a₁ ≤ a₂ ≤ ⋯.[4](https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Elementary_Foundations%3A_An_Introduction_to_Topics_in_Discrete_Mathematics_%28Sylvestre%29/19%3A_Partially_ordered_sets/19.04%3A_Total_Orders)
## Finite total orders
On a finite set, a total order is nothing more than a listing of the elements: a list a₀, a₁, …, aₙ becomes the order a₀ ≤ a₁ ≤ ⋯ ≤ aₙ, and conversely.[4](https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Elementary_Foundations%3A_An_Introduction_to_Topics_in_Discrete_Mathematics_%28Sylvestre%29/19%3A_Partially_ordered_sets/19.04%3A_Total_Orders) In diagram form, a partial order on a finite set is total if and only if its [Hasse diagram](https://www.edgepedia.org/hasse-diagram), the graph drawing the order with an edge between elements differing by one step, forms a single vertical line.[4](https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Elementary_Foundations%3A_An_Introduction_to_Topics_in_Discrete_Mathematics_%28Sylvestre%29/19%3A_Partially_ordered_sets/19.04%3A_Total_Orders)
Two structural facts follow. Every finite totally ordered set is well ordered, meaning every nonempty subset has a least element.[3](https://mathworld.wolfram.com/TotallyOrderedSet.html) And any two totally ordered sets with k elements, for k a nonnegative integer, are order isomorphic, so they share a single order type, which is an ordinal number; there is essentially one total order on a finite set of each size.[3](https://mathworld.wolfram.com/TotallyOrderedSet.html)
## Linear extensions of partial orders
A total order L extends a partial order P when a ≤ b in P implies a ≤ b in L; such an L is called a linear extension of P.[6](https://encyclopediaofmath.org/wiki/Extension_of_an_order) Szpilrajn's theorem states that every partial order has a linear extension; the result appeared as Edward Szpilrajn's paper "Sur l'extension de l'ordre partiel" in [Fundamenta Mathematicae](https://www.edgepedia.org/fundamenta-mathematicae) 16 (1930), pages 386–389.[5](https://impan.pl/pl/wydawnictwa/czasopisma-i-serie-wydawnicze/fundamenta-mathematicae/all/16/0/92870/sur-l-extension-de-l-ordre-partiel) • [6](https://encyclopediaofmath.org/wiki/Extension_of_an_order) The theorem is described as a central result in the theory of partial orderings, and it underlies definitions such as the dimension of a partial ordering, the size of the smallest family of linear orders whose intersection recovers the partial order.[9](https://math.uchicago.edu/~drh/Papers/linext.html) • [6](https://encyclopediaofmath.org/wiki/Extension_of_an_order) In the family of all order relations on a set, ordered by extension, the minimal element is the equality relation and the maximal elements are the linear orders.[6](https://encyclopediaofmath.org/wiki/Extension_of_an_order)
Linear extensions have practical readings: a partial order of tasks with precedence constraints can be completed to a consistent total order in which the tasks are performed.[10](https://informatika.stei.itb.ac.id/~rinaldi.munir/Matdis/ln3.pdf) If P is already a total order, it is its own linear extension.[11](https://www.voutsadakis.com/TEACH/LECTURES/DISCRETE/Chapter10.pdf)
## Set-theoretic strength
The order-extension principle, that every partial ordering can be extended to a linear ordering, is weaker than the full axiom of choice. It does not imply the Boolean prime ideal theorem, the statement that every [Boolean algebra](https://www.edgepedia.org/boolean-algebra) has a prime ideal; the independence was proved by showing BPIT does not follow from OE.[12](https://doi.org/10.2307/2586759) At the other extreme, the [well-ordering theorem](https://www.edgepedia.org/well-ordering-theorem), that every set can be well-ordered by a total order in which every nonempty subset has a least element, is equivalent to the axiom of choice; Zermelo proved the theorem from AC in 1904, and the equivalence was quickly recognized.[13](https://plato.stanford.edu/entries/axiom-choice/)
Effective versions behave differently. Several computable analogs of variations of Szpilrajn's theorem fail, and reverse-mathematics analysis uses these failures to locate the theorem's proof-theoretic strength; for example, the maximal linear extension theorem for well partial orders is equivalent over the base system RCA₀ to ATR₀.[9](https://math.uchicago.edu/~drh/Papers/linext.html) • [14](https://arxiv.org/abs/1009.1528)
## Computation
Sorting algorithms presuppose an order on the keys. A [comparison sort](https://www.edgepedia.org/comparison-sort) uses only comparisons between keys to arrange items in a predetermined order.[15](https://xlinux.nist.gov/dads/HTML/comparisnsrt.html) The comparator requirements in practice are weaker than a total order: the C++ standard requires that a comparator induce a strict weak ordering, under which two elements are equivalent when neither compares less than the other, and the induced relation on equivalence classes is a strict total ordering.[16](https://eel.is/c%2B%2Bdraft/alg.sorting.general) A comparator that is cyclic rather than transitive, as can arise from inconsistent comparison logic, produces a nonsensical sort.[1](https://xlinux.nist.gov/dads/HTML/totalorder.html)
For a finite poset, the linear extensions are the total orders compatible with it, and counting them is computationally hard: the counting problem is #P-complete, and remains #P-complete even for restricted classes such as height-2 posets.[7](https://arxiv.org/abs/2506.14725) Generating a uniformly random linear extension is also studied: a 2025 algorithm of Mark Huber, a mathematician working in probability and computational methods, produces a uniform linear extension using on average at most 2.75 n³ ln(n) operations and 1.83 n³ ln(n) independent fair random bits, improving on the previous best method's constant of 16/π ≈ 5.093 operations.[7](https://arxiv.org/abs/2506.14725)
## References
1. [Paul E. Black and Paul J. Tanenbaum, "total order", NIST Dictionary of Algorithms and Data Structures](https://xlinux.nist.gov/dads/HTML/totalorder.html)
2. ["Order (on a set)", Encyclopedia of Mathematics](https://encyclopediaofmath.org/wiki/Order_%28on_a_set%29)
3. [Eric W. Weisstein, "Totally Ordered Set", Wolfram MathWorld](https://mathworld.wolfram.com/TotallyOrderedSet.html)
4. [Jeremy Sylvestre, "19.4: Total Orders", Elementary Foundations, Mathematics LibreTexts](https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Elementary_Foundations%3A_An_Introduction_to_Topics_in_Discrete_Mathematics_%28Sylvestre%29/19%3A_Partially_ordered_sets/19.04%3A_Total_Orders)
5. [Edward Szpilrajn, "Sur l'extension de l'ordre partiel", Fundamenta Mathematicae 16 (1930), 386–389, IMPAN](https://impan.pl/pl/wydawnictwa/czasopisma-i-serie-wydawnicze/fundamenta-mathematicae/all/16/0/92870/sur-l-extension-de-l-ordre-partiel)
6. ["Extension of an order", Encyclopedia of Mathematics](https://encyclopediaofmath.org/wiki/Extension_of_an_order)
7. [Mark Huber, "Generating uniform linear extensions using few random bits", arXiv:2506.14725](https://arxiv.org/abs/2506.14725)
8. ["Real number", Encyclopedia of Mathematics](https://encyclopediaofmath.org/wiki/Real_number)
9. [Rodney G. Downey, Denis R. Hirschfeldt, Steffen Lempp, and Reed Solomon, "Computability-Theoretic and Proof-Theoretic Aspects of Partial and Linear Orderings", Israel Journal of Mathematics 138 (2003), 271–290](https://math.uchicago.edu/~drh/Papers/linext.html)
10. [Rinaldi Munir, "Course Notes 3: Relations"](https://informatika.stei.itb.ac.id/~rinaldi.munir/Matdis/ln3.pdf)
11. ["Linear Extension of a Partial Order on a Finite Set", lecture notes of Costas Voutsadakis](https://www.voutsadakis.com/TEACH/LECTURES/DISCRETE/Chapter10.pdf)
12. ["The independence of the Prime Ideal Theorem from the Order-Extension Principle", Journal of Symbolic Logic](https://doi.org/10.2307/2586759)
13. ["The Axiom of Choice", Stanford Encyclopedia of Philosophy](https://plato.stanford.edu/entries/axiom-choice/)
14. ["The maximal linear extension theorem in second order arithmetic", arXiv:1009.1528](https://arxiv.org/abs/1009.1528)
15. ["comparison sort", NIST Dictionary of Algorithms and Data Structures](https://xlinux.nist.gov/dads/HTML/comparisnsrt.html)
16. ["[alg.sorting.general]", C++ working draft](https://eel.is/c%2B%2Bdraft/alg.sorting.general)
---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Logic and discrete mathematics › General discrete mathematics and discrete structures › Discrete mathematics*
*Initially written Sep 17, 2026 · Reviewed: Sep 30, 2026; Oct 15, 2026 · Edited: Oct 15, 2026 · Last review: Oct 15, 2026*
*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*
License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license