Total order

In mathematics, a linear order, total order, simple order, or (non-strict) ordering is a binary relation on some set X, which is transitive, antisymmetric, and total (this relation is denoted here by infix ≤). 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 ab and ba then a = b (antisymmetry);
If ab and bc then ac (transitivity);
ab or ba (totality).

Antisymmetry eliminates uncertain cases when both a precedes b and b precedes a.[1] A relation having the property of "totality" means that any pair of elements in the set of the relation are comparable under the relation. This also means that the set can be diagrammed as a line of elements, giving it the name linear.[2] Totality also implies reflexivity, i.e., aa. Therefore, a total order is also a partial order. The partial order has a weaker form of the third condition. (It requires only reflexivity, not totality.) An extension of a given partial order to a total order is called a linear extension of that partial order.

Strict total order

For each (non-strict) total order ≤ there is an associated asymmetric (hence irreflexive) relation <, called a strict total order, which can equivalently be defined in two ways:

Properties:

We can work the other way and start by choosing < as a transitive trichotomous binary relation; then a total order ≤ can equivalently be defined in two ways:

Two more associated orders are the complements ≥ and >, completing the quadruple {<, >, ≤, ≥}.

We can define or explain the way a set is totally ordered by any of these four relations; the notation implies whether we are talking about the non-strict or the strict total order.

Examples

Further concepts

Chains

While chain is sometimes merely a synonym for totally ordered set, it can also refer to a totally ordered subset of some partially ordered set. The latter definition has a crucial role in Zorn's lemma. The height of a poset denotes the cardinality of its largest chain in this sense.

For example, consider the set of all subsets of the integers partially ordered by inclusion. Then the set { In : n is a natural number}, where In is the set of natural numbers below n, is a chain in this ordering, as it is totally ordered under inclusion: If nk, then In is a subset of Ik.

Lattice theory

One may define a totally ordered set as a particular kind of lattice, namely one in which we have

\{a\vee b, a\wedge b\} = \{a, b\} for all a, b.

We then write ab 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 <. In other words, a total order on a set with k elements induces a bijection with the first k natural numbers. Hence it is common to index finite total orders or well orders with order type ω by natural numbers in a fashion which respects the ordering (either starting with zero or with one).

Category theory

Totally ordered sets form a full subcategory of the category of partially ordered sets, with the morphisms being maps which respect the orders, i.e. maps f such that if ab then f(a)f(b).

A bijective map between two totally ordered sets that respects the two orders is an isomorphism in this category.

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 these open intervals to define a topology on any ordered set, the order topology.

When more than one order is being used on a set one talks 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).

The order topology induced by a total order may be shown to be hereditarily normal.

Completeness

A totally ordered set is said to be complete if every nonempty subset that has an upper bound, has a least upper bound. For example, the set of real numbers R is complete but the set of rational numbers Q is not.

There are a number of results relating properties of the order topology to the completeness of X:

A totally ordered set (with its order topology) which is a complete lattice is compact. Examples are the closed intervals of real numbers, e.g. the unit interval [0,1], and the affinely extended real number system (extended real number line). There are order-preserving homeomorphisms between these examples.

Sums of orders

For any two disjoint total orders (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:
  1. x,y\in A_1 and x\le_1 y
  2. x,y\in A_2 and x\le_2 y
  3. x\in A_1 and y\in A_2

Intutitively, 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:
  1. Either there is some i\in I with  x\le_i y
  2. or there are some i<j in I with  x\in A_i,  y\in A_j

Orders on the Cartesian product of totally ordered sets

In order of increasing strength, i.e., decreasing sets of pairs, three of the possible orders on the Cartesian product of two totally ordered sets are:

All three can similarly be defined for the Cartesian product of more than two sets.

Applied to the vector space Rn, 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 Rn 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 in a separation relation.[3]

See also

Notes

  1. Nederpelt, Rob (2004). "Chapter 20.2: Ordered Sets. Orderings". Logical Reasoning: A First Course. Texts in Computing 3 (3rd, Revised ed.). King's College Publications. p. 325. ISBN 0-9543006-7-X.
  2. Nederpelt, Rob (2004). "Chapter 20.3: Ordered Sets. Linear orderings". Logical Reasoning: A First Course. Texts in Computing 3 (3rd, Revisied ed.). King's College Publications. p. 330. ISBN 0-9543006-7-X.
  3. Macpherson, H. Dugald (2011), "A survey of homogeneous structures" (PDF), Discrete Mathematics, doi:10.1016/j.disc.2011.01.024, retrieved 28 April 2011

References

This article is issued from Wikipedia - version of the Thursday, February 11, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.