Total order
≈ 8 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In mathematics, a total order or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X , which satisfies the following for all a, b and c in X : # a \leq a (reflexive). # If a \leq b and b \leq c then a \leq c (transitive). # If a \leq b and b \leq a then a = b (antisymmetric). # a \leq b or b \leq a (strongly connected, formerly called totality). Requirements 1. to 3. just make up the definition of a partial order.
Reflexivity (1.) already follows from strong connectedness (4.), but is required explicitly by many authors nevertheless, to indicate the kinship to partial orders. Total orders are sometimes also called simple, connex, or full orders. A set equipped with a total order is a totally ordered set; the terms simply ordered set, linearly ordered set, toset and loset are also used. The term chain is sometimes defined as a synonym of totally ordered set, but generally refers to a totally ordered subset of a given partially ordered set.
An extension of a given partial order to a total order is called a linear extension of that partial order.
In mathematics, a total order or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X , which satisfies the following for all a, b and c in X : a \leq a (reflexive). If a \leq b and b \leq c then a \leq c (transitive). If a \leq b and b \leq a then a = b (antisymmetric). a \leq b or b \leq a (strongly connected, formerly called totality). Requirements 1. to 3. just make up the definition of a partial order.
Reflexivity (1.) already follows from strong connectedness (4.), but is required explicitly by many authors nevertheless, to indicate the kinship to partial orders. Total orders are sometimes also called simple, connex, or full orders. A set equipped with a total order is a totally ordered set; the terms simply ordered set, linearly ordered set, toset and loset are also used. The term chain is sometimes defined as a synonym of totally ordered set, but generally refers to a totally ordered subset of a given partially ordered set.
An extension of a given partial order to a total order is called a linear extension of that partial order.
Strict and non-strict total orders
For delimitation purposes, a total order as defined above is sometimes called non-strict order. For each (non-strict) total order \leq there is an associated relation , called the strict total order associated with \leq that can be defined in two equivalent ways: a if a \leq b and a \neq b (reflexive reduction). a if not b \leq a (i.e., is the complement of the converse of \leq ). Conversely, the reflexive closure of a strict total order is a (non-strict) total order.
Thus, a on a set X is a strict partial order on X in which any two distinct elements are comparable. That is, a strict total order is a binary relation on some set X , which satisfies the following for all a, b and c in X : Not a (irreflexive). If a then not b (asymmetric). If a and b then a (transitive). If a \neq b , then a or b (connected). Asymmetry follows from transitivity and irreflexivity; moreover, irreflexivity follows from asymmetry.
Examples
Any subset of a totally ordered set is totally ordered for the restriction of the order on . The unique order on the empty set, , is a total order. Any set of ordinal numbers (more strongly, these are well-orders). If is any set and an injective function from to a totally ordered set then induces a total ordering on by setting if and only if . The lexicographical order on the Cartesian product of a family of totally ordered sets, indexed by a well ordered set, is itself a total order.
The set of real numbers ordered by the usual "less than or equal to" (≤) or "greater than or equal to" (≥) relations is totally ordered. Hence each subset of the real numbers is totally ordered, such as the natural numbers, integers, and rational numbers.
Each of these can be shown to be the unique (up to an order isomorphism) "initial example" of a totally ordered set with a certain property, (here, a total order is initial for a property, if, whenever has the property, there is an order isomorphism from to a subset of ): The natural numbers form an initial non-empty totally ordered set with no upper bound. The integers form an initial non-empty totally ordered set with neither an upper nor a lower bound. The rational numbers form an initial totally ordered set which is dense in the real numbers.
Moreover, the reflexive reduction \{a\vee b, a\wedge b\} = \{a, b\} for all a, b. We then write a ≤ b if and only if a = a\wedge b . Hence a totally ordered set is a distributive lattice.
Finite total orders
A simple counting argument will verify that any non-empty finite totally ordered set (and hence any non-empty subset thereof) has a least element. Thus every finite total order is in fact a well order.
Either by direct proof or by observing that every well order is order isomorphic to an ordinal one may show that every finite total order is order isomorphic to an initial segment of the natural numbers ordered by (A_1,\le_1) and (A_2,\le_2) , there is a natural order \le_+ on the set A_1\cup A_2 , which is called the sum of the two orders or sometimes just A_1+A_2 : For x,y\in A_1\cup A_2 , x\le_+ y holds if and only if one of the following holds: x,y\in A_1 and x\le_1 y x,y\in A_2 and x\le_2 y x\in A_1 and y\in A_2 Intuitively, this means that the elements of the second set are added on top of the elements of the first set.
More generally, if (I,\le) is a totally ordered index set, and for each i\in I the structure (A_i,\le_i) is a linear order, where the sets A_i are pairwise disjoint, then the natural total order on \bigcup_i A_i is defined by For x,y\in \bigcup_{i\in I} A_i , x\le y holds if: Either there is some i\in I with x\le_i y or there are some i in I with x\in A_i , y\in A_j
Orders on the Cartesian product of totally ordered sets
There are several ways to take two totally ordered sets and extend to an order on the Cartesian product, though the resulting order may only be partial. Here are three of these possible orders, listed such that each order is stronger than the next: Lexicographical order: (a,b) ≤ (c,d) if and only if a n , each of these make it an ordered vector space. See also examples of partially ordered sets. A real function of n real variables defined on a subset of R n defines a strict weak order and a corresponding total preorder on that subset.
Related structures
A binary relation that is antisymmetric, transitive, and reflexive (but not necessarily total) is a partial order. A group with a compatible total order is a totally ordered group. There are only a few nontrivial structures that are (interdefinable as) reducts of a total order. Forgetting the orientation results in a betweenness relation. Forgetting the location of the ends results in a cyclic order. Forgetting both data results use of point-pair separation to distinguish, on a circle, the two intervals determined by a point-pair.
See also
– a downward total partial order
Notes
References
Bibliography
George Grätzer (1971). Lattice theory: first concepts and distributive lattices. W. H. Freeman and Co. John G. Hocking and Gail S. Young (1961). Topology. Corrected reprint, Dover, 1988.
External links
Text derived from https://en.wikipedia.org/w/index.php?oldid=1360446695 under CC BY-SA 4.0; modifications have been made.