| Total Order |
Article Index for Total |
Website Links For Total |
Information AboutTotal Order |
| CATEGORIES ABOUT TOTAL ORDER | |
| order theory | |
| set theory | |
|
: 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 : for all ''a'', ''b''. We then write ''a'' ≤ ''b'' If And Only If . It follows that a totally ordered set is a Distributive Lattice . Totally ordered sets form a Full Subcategory of the Category of Partially Ordered Sets , with the Morphism s 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. 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 Order topology For any totally ordered set ''X'' we can define the '''open 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 Number s is complete but the set of Rational Number s 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 {Link without Title} , and the Affinely Extended Real Number System (extended real number line). There are order-preserving Homeomorphism s between these examples. 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 { ''I''''n'' : ''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 totally-ordered set (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 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). Contrast with a Partial Order , which lacks the third condition. An example of a partial order is the Happened-before relation. 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 R''n'', each of these make it an Ordered Vector Space . See also . A real function of ''n'' real variables defined on a subset of R''n'' on that subset. SEE ALSO REFERENCES
|
|
|