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:
“I have often thought that if photography were difficult in the true sense of the term—meaning that the creation of a simple photograph would entail as much time and effort as the production of a good watercolor or etching—there would be a vast improvement in total output. The sheer ease with which we can produce a superficial image often leads to creative disaster.”
—Ansel Adams (1902–1984)
“I write poetry in order to live more fully.”
—Judith Rodriguez (b. 1936)