(definition)
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.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 30 March 2006.
HTML page formatted Mon Feb 2 13:10:40 2015.
Cite this as:
Paul E. Black and Paul J. Tanenbaum, "total order", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 30 March 2006. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/totalorder.html