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:
“Someone once asked me why women don’t gamble as much as men do, and I gave the common-sensical reply that we don’t have as much money. That was a true but incomplete answer. In fact, women’s total instinct for gambling is satisfied by marriage.”
—Gloria Steinem (b. 1934)
“People press toward the light not in order to see better but in order to shine better.—We are happy to regard the one before whom we shine as light.”
—Friedrich Nietzsche (1844–1900)