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 human spirit is itself the most wonderful fairy tale that can possibly be. What a magnificent world lies enclosed within our bosoms! No solar orbit hems it in, the inexhaustible wealth of the total visible creation is outweighed by its riches!”
—E.T.A.W. (Ernst Theodor Amadeus Wilhelm)
“All things being equal, I would choose a woman over a man in order to even the balance of power, to insinuate a different perspective into the process, to give young women something to shoot for and someone to look up to. But all things are rarely equal.”
—Anna Quindlen (b. 1952)