Total order

From Wikipedia, the free encyclopedia

You have new messages (last change).

In mathematics, a total order, linear order, simple order, or (weak) ordering on a set X is any binary relation on X that is antisymmetric, transitive, and total. This means that if we denote one such relation by ≤ 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 or completeness)

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.

A relation's property of "totality" can be described this way: that any pair of elements in the set are mutually comparable under the relation.

Notice that the totality 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. A total order can also be defined as a partial order that is "total", that is satisfies the "totality" condition.

Alternatively, 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 a ≤ b if and only if a = a\wedge b. It follows that a totally ordered set is a distributive lattice.

If a and b are members of a set that is totally ordered by ≤ then we can define a binary relation a < b as: a ≤ b and a ≠ b. This relation is transitive (a < b and b < c implies a < c) and, unlike ≤, trichotomous (i.e., exactly one of a < b, b < a and a = b is true). We can work the other way and start by choosing < as a transitive trichotomous binary relation; then if we define a ≤ b to mean a < b or a = b then ≤ can be shown to be a total order.

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 a ≤ b then f(a) ≤ f(b).

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

Contents

[edit] Examples

  • The letters of the alphabet ordered by the standard dictionary order, e.g., A < B < C etc.
  • Any subset of a totally ordered set, with the restriction of the order on the whole set.
  • Any partially ordered set X where every two elements are comparable (i.e. if a,b are members of X either a≤b or b≤a or both).
  • If X is any set and f a bijection from any totally ordered set to X then f induces a total ordering on X by setting x1 < x2 if and only if x1 = f(n1) and x2 = f(n2) and n1 < n2.
  • The lexicographical order on the Cartesian product of a set of totally ordered sets indexed by an ordinal, is itself a total order. For example, any set of words ordered alphabetically is a total order, viewed as a subset of a cartesian product of a countable number of copies of a set formed by adding the space symbol to the alphabet (and defining a space to be less than any letter).
  • Natural numbers, integers, rational numbers, and real numbers ordered by the usual less than (<) or greater than (>) relations are all total orders. Each of these can be shown to be the unique (to within isomorphism) smallest example of a totally ordered set with a certain property, (a total order A is the smallest with a certain property if whenever B has the property, there is an order isomorphism from A to a subset of B).:
    • The natural numbers comprise the smallest totally ordered set with no upper bound.
    • The integers comprise the smallest totally ordered set with neither an upper nor a lower bound.
    • The rational numbers comprise the smallest totally ordered set with no upper or lower bound, which is dense in the sense that (a, b) is non-empty for every a < b.
    • The real numbers comprise the smallest unbounded connected totally ordered set. (See below for the definition of the topology.)

[edit] Further concepts

[edit] 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 an 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).

The order topology may be shown to be hereditarily normal.

[edit] Completeness

A totally ordered set is said to be complete if every subset that has an upper bound, has a least upper bound. There are a number of results relating properties of the order topology to the completeness of X:

  • If the order topology on X is connected, X is complete.
  • X is connected under the order topology if and only if it is complete and there is no gap in X (a gap is two points a and b in X with no c satisfying a < c < b.)
  • X is complete if and only if every bounded set that is closed in the order topology is compact.

[edit] 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.

[edit] 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.

[edit] See also

[edit] References

  • George Grätzer (1971). Lattice theory: first concepts and distributive lattices. W. H. Freeman and Co. ISBN 0-7167-0442-0
  • John G. Hocking and Gail S. Young (1961). Topology. Corrected reprint, Dover, 1988. ISBN 0-486-65676-4
Retrieved from "http://en.wikipedia.org../../../t/o/t/Total_order.html"