total order


Definition: An order defined for all pairs of items of a set. For instance, ≤ (less than or equal to) is a total order on integers, that is, for any two integers, one of them is less than or equal to the other.

Formal Definition: A total order is a relation that is reflexive, transitive, antisymmetric, and total.

Also known as linear order.

See also partial order, chain.

Note: Subset (⊆) is partial not total, since {a} is not a subset of {b}, nor is {b} a subset of {a}. The sets {a} and {b} are incomparable.

How could an order be total, but not transitive? If it is cyclic, like in the game Paper, Scissors, Rock.

Authors: PEB,PJT

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 11 February 2019.
HTML page formatted Wed Mar 13 12:42:46 2019.

Cite this as:
Paul E. Black and Paul J. Tanenbaum, "total order", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 11 February 2019. (accessed TODAY) Available from: