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:
“It seems certain, that though a man, in a flush of humour, after intense reflection on the many contradictions and imperfections of human reason, may entirely renounce all belief and opinion, it is impossible for him to persevere in this total scepticism, or make it appear in his conduct for a few hours.”
—David Hume (1711–1776)
“In order to acquire a growing and lasting respect in society, it is a good thing, if you possess great talent, to give, early in your youth, a very hard kick to the right shin of the society that you love. After that, be a snob.”
—Salvador Dali (1904–1989)