Total order
From Exampleproblems
In mathematics, a total order, linear order or simple order on a set X is any binary relation on X that is antisymmetric, transitive, and total. This means that, if we denote the relation by ≤, 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 (totalness)
A set paired with an associated total order on it is called a totally ordered set, a linearly ordered set, a simply ordered set, or a chain. The totalness property can be stated thus: that any pair of elements in the chain are mutually comparable.
Notice that the totalness condition implies reflexivity, that is a ≤ a. Thus a total order is also a partial order, that is, a binary relation which is reflexive, antisymmetric and transitive. It follows that a total order can also be defined as a partial order that is total.
Alternatively, one may define a totally ordered set as a particular kind of lattice, namely one in which we have 
for all a, b. We then write a ≤ b if and only if 
.
If a and b are members of a totally ordered set, we may write a < b if a ≤ b and a ≠ b. The binary relation < is then transitive (a < b and b < c implies a < c) and trichotomous (one and only one of a < b, b < a and a = b is true). In fact, we can define a total order to be a transitive trichotomous binary relation <, and then define a ≤ b to mean a < b or a = b, and this definition can be shown to be equivalent to the one given at the beginning of this article.
Contents |
Examples
- Natural numbers, integers, rational numbers, and real numbers ordered by the standard less than (<) or greater than (>) relations are all total orders.
- Any subset of a totally ordered set.
- Any set of cardinal numbers or ordinal numbers is totally ordered (in fact, even well-ordered).
- The letters of the alphabet ordered by the standard dictionary order, e.g., A < B < C etc..
- The lexicographical order on any Cartesian product of total orders. Combined with the fact that the alphabet is totally ordered as well as any subset of a totally ordered set this entails that any set of words ordered alphabetically is a total order.
- Sets ordered by inclusion (A < B iff A is a subset of B) are in general not totally ordered (neither {1} < {2} nor {2} < {1} ) However, frequently special collections of sets turn out to be totally ordered by inclusion. For example if for every natural number n In={1..n} (the set of the first n natural numbers) then {In} (the set of all the In) is totally ordered by inclusion. Note that it is only the latter set (a set of sets of natural numbers) which is totally ordered by inclusion. The Ins may be compared to each other in this order but are not themselves necesserily totally ordered by inclusion (depending on how you define the natural numbers).
- If X is any set and f a bijection from an initial segment of the natural numbers totally ordered by < to X then f induces a total ordering on X by setting x1 < x2 iff x1=f(n1) and x2=f(n2) and n1 < n2. In fact more generally any bijection from a totally ordered set induces a total order on its range.
Mathematical Errata
Order Topology
For any totally ordered set X we can define the open intervals (a, b) = {x : a < x and x < b}, (−∞, b) = {x : x < b}, (a, ∞) = {x : a < x} and (−∞, ∞) = X. We can use open intervals to define a topology on any ordered set, the order topology.
Note that the formal definition of a ordered set as a set paired with an ordering guarantees that there is a unique order topology on any ordered set. However, in practice the distinction between a set which has an order defined on it and the pair of the set and associated order is usually ignored. Hence to avoid confusion when more than one order is being used in conjunction with a set it is common to talk about the order topology induced by a particular order. For instance if N is the natural numbers, < is less than and > greater than we might refer to the order topology on N induced by < and the order topology on N induced by > (in this case they happen to be identical but will not in general).
Chains
While from a definition point of view, chain is merely a synonym for totally ordered set the term is usually used to describe a totally ordered subset of some partial order. Thus the reals would probably be described as a totally ordered set. However, if we were to consider all subsets of the integers partially ordered by inclusion then the totally ordered set under inclusion { In :n is a natural number} defined in an above example would frequently be called a chain.
The preferential use of chain to refer to a totally ordered subset of a partial order likely stems from the important role such totally ordered subsets play in Zorn's Lemma.
Finite Total Orders
A simple counting argument will verify that any finite total order (and hence any 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 <. In other words a total order with k elements is induced by a bijection with the first k natural numbers. Hence it is common to index finite total orders or countable well orders by natural numbers in a fashion which respects the ordering.
Contrast with a partial order, which lacks the third condition. An example of a partial order is the happened-before relation.es:Orden total pl:Porządek liniowy ru:Вполне упорядоченное множество zh:全序关系
