In set theory, a total order, linear order, simple order, or (non-strict) ordering is a binary relation (here denoted by infix ≤) on some set X. The relation is transitive, antisymmetric, and total. A set paired with a total order is called a totally ordered set, a linearly ordered set, a simply ordered set, or a chain.
If X is totally ordered under ≤, then the following statements hold for all a, b and c in X:
- If a ≤ b and b ≤ a then a = b (antisymmetry);
- If a ≤ b and b ≤ c then a ≤ c (transitivity);
- a ≤ b or b ≤ a (totality).
Contrast with a partial order, which has a weaker form of the third condition (it only requires reflexivity, not totality). A relation having the property of "totality" means that any pair of elements in the set of the relation are mutually comparable under the relation. Totality implies reflexivity, that is, a ≤ a, thus a total order is also a partial order. An extension of a given partial order to a total order is called a linear extension of that partial order.
Read more about Total Order: Strict Total Order, Examples, Orders On The Cartesian Product of Totally Ordered Sets, Related Structures
Famous quotes containing the words total and/or order:
“The effectiveness of our memory banks is determined not by the total number of facts we take in, but the number we wish to reject.”
—Jon Wynne-Tyson (b. 1924)
“In Russia there is an emigration of intelligence: émigrés cross the frontier in order to read and to write good books. But in doing so they contribute to making their fatherland, abandoned by spirit, into the gaping jaws of Asia that would like to swallow our little Europe.”
—Friedrich Nietzsche (1844–1900)