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 E. Black.

Entry modified 30 March 2006.
HTML page formatted Tue Dec 6 16:16:33 2011.

Cite this as:
Paul E. Black and Paul J. Tanenbaum, "total order", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 30 March 2006. (accessed TODAY) Available from:

to NIST home page