FACTOID # 19: Cheap sloppy joes: Looking for reduced-price lunches for schoolchildren? Head for Oklahoma!
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Total order

In mathematics and set theory, a total order, linear order, simple order, or (non-strict) ordering is a binary relation (here denoted by infix ) on some set X. The relation is transitive, antisymmetric, and total. For other meanings of mathematics or uses of math and maths, see Mathematics (disambiguation) and Math (disambiguation). ... Set theory is the mathematical theory of sets, which represent collections of abstract objects. ... In mathematics, a binary relation (or a dyadic relation) is an arbitrary association of elements of one set with elements of another (perhaps the same) set. ... An infix is an affix inserted inside an existing word. ... In mathematics, a set can be thought of as any collection of distinct objects considered as a whole. ... In mathematics, a binary relation R over a set X is transitive if it holds for all a, b, and c in X, that if a is related to b and b is related to c, then a is related to c. ... In mathematics, a binary relation R on a set X is antisymmetric if, for all a and b in X, if a is related to b and b is related to a, then a = b. ... In mathematics, a binary relation R over a set X is total if it holds for all a and b in X that a is related to b or b is related to a (or both). ...


If X is a total order 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 or completeness).

A set paired with a total order is called a totally ordered set, a linearly ordered set, a simply ordered set, or a chain. In mathematics, a binary relation R on a set X is antisymmetric if, for all a and b in X, if a is related to b and b is related to a, then a = b. ... In mathematics, a binary relation R over a set X is transitive if it holds for all a, b, and c in X, that if a is related to b and b is related to c, then a is related to c. ... OR logic gate. ... In mathematics, a binary relation R over a set X is total if it holds for all a and b in X that a is related to b or b is related to a (or both). ...


A relation having the property of "totality" means that any pair of elements in the field of the relation are mutually comparable under the relation. Look up field in Wiktionary, the free dictionary A green field or paddock Field may refer to: A field is an open land area, used for growing agricultural crops. ...


Totality implies reflexivity, that is, aa. Thus a total order is also a partial order, that is, a binary relation which is reflexive, antisymmetric and transitive. Hence a total order is also a partial order satisfying the "totality" condition. In set theory, a binary relation can have, among other properties, reflexivity or irreflexivity. ... In mathematics, a partially ordered set (or poset for short) is a set equipped with a special binary relation which formalizes the intuitive concept of an ordering. ... In mathematics, a binary relation (or a dyadic relation) is an arbitrary association of elements of one set with elements of another (perhaps the same) set. ...

Contents

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: In mathematics, a binary relation R on a set X is antisymmetric if it holds for all a and b in X that if a is related to b and b is related to a then a = b. ...

Properties: In mathematics, a binary relation (or a dyadic relation) is an arbitrary association of elements of one set with elements of another (perhaps the same) set. ... In mathematics, a binary relation (or a dyadic relation) is an arbitrary association of elements of one set with elements of another (perhaps the same) set. ...

  • The relation is transitive: a < b and b < c implies a < c.
  • The relation is trichotomous: exactly one of a < b, b < a and a = b is true.
  • The relation is a strict weak order, where the associated equivalence is equality.

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: For other uses, see trichotomy (disambiguation). ... The 13 possible strict weak orderings on a set of three elements {a, b, c}. The only partially ordered sets are coloured, while totally ordered ones are in black. ...

  • ab if and only if a < b or a = b
  • ab if and only if not b < a

Two more associated orders are the complements ≥ and >, completing the quadruple {<, >, ≤, ≥}. A quadruple is a term from mathematics, depicting an n-tuple with n being 4. ...


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

  • 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 ab or ba or both).
  • If X is any set and f an injective function from X to a totally ordered set then f induces a total ordering on X by setting x1 < x2 if and only if f(x1) < f(x2).
  • 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 totally ordered set, 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).
  • The set of real numbers ordered by the usual less than (<) or greater than (>) relations is totally ordered, hence also the subsets of natural numbers, integers, and rational numbers. 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 for every a and b such that a < b there is a c such that a < c < b.
    • The real numbers comprise the smallest unbounded connected totally ordered set. (See below for the definition of the topology.)

Aleph-0, the smallest infinite cardinal In mathematics, cardinal numbers, or cardinals for short, are a generalized kind of number used to denote the size of a set, known as its cardinality. ... Ordinal numbers, or ordinals for short, are numbers used to denote the position in an ordered sequence: first, second, third, fourth, etc. ... In mathematics, a well-order (or well-ordering) on a set S is a total order on S with the property that every non-empty subset of S has a least element in this ordering. ... An injective function. ... In mathematics, the lexicographic or lexicographical order, (also known as dictionary order, alphabetic order or lexicographic(al) product), is a natural order structure of the Cartesian product of two ordered sets. ... In mathematics, the Cartesian product is a direct product of sets. ... Please refer to Real vs. ... Natural number can mean either a positive integer (1, 2, 3, 4, ...) or a non-negative integer (0, 1, 2, 3, 4, ...). Natural numbers have two main purposes: they can be used for counting (there are 3 apples on the table), or they can be used for ordering (this is... The integers consist of the positive natural numbers (1, 2, 3, &#8230;) the negative natural numbers (&#8722;1, &#8722;2, &#8722;3, ...) and the number zero. ... In mathematics, a rational number (or informally fraction) is a ratio of two integers, usually written as the vulgar fraction a/b, where b is not zero. ... In mathematics, especially in order theory, an upper bound of a subset S of some partially ordered set is an element which is greater than or equal to every element of S. The term lower bound is defined dually. ... In mathematics, especially in order theory, an upper bound of a subset S of some partially ordered set is an element which is greater than or equal to every element of S. The term lower bound is defined dually. ... In mathematics, a partial order ≤ on a set X is said to be dense (or dense-in-itself) if, for all x and y in X for which x < y, there is a z in X such that x < z < y. ... In topology and related branches of mathematics, a topological space X is said to be disconnected if it is the union of two disjoint nonempty open sets. ...

Further concepts

Chains

While chain is often merely a synonym for totally ordered set, chain usually refers to a totally ordered subset of some partially ordered set. The prevalence of the latter definition most likely stems from the crucial role chains so defined play in Zorn's lemma. In mathematics, a total order or linear order on a set X is any binary relation on X that is antisymmetric, transitive, and total. ... “Superset” redirects here. ... In mathematics, especially order theory, a partially ordered set (or poset) is a set equipped with a partial order relation. ... Zorns lemma, also known as the Kuratowski-Zorn lemma, is a proposition of set theory that states: Every non-empty partially ordered set in which every chain (i. ...


Thus the reals R are a totally ordered set. However, if we consider all subsets of the integers partially ordered by inclusion, then the set { In : n is a natural number}, defined in an example above and totally ordered under inclusion, would often be called a chain. In mathematics, the real numbers may be described informally as numbers that can be given by an infinite decimal representation, such as 2. ... The integers are commonly denoted by the above symbol. ... In mathematics, a partially ordered set (or poset for short) is a set equipped with a special binary relation which formalizes the intuitive concept of an ordering. ... In mathematics, inclusion is a partial order on sets. ... In mathematics, a natural number can mean either an element of the set {1, 2, 3, ...} (i. ...


Lattice theory

One may define a totally ordered set as a particular kind of lattice, namely one in which we have The name lattice is suggested by the form of the Hasse diagram depicting it. ...

{avee b, awedge b} = {a, b} for all a, b.

We then write ab if and only if a = awedge b. Hence a totally ordered set is a distributive lattice; here is the proof. ↔ ⇔ ≡ logical symbols representing iff. ... In mathematics, distributive lattices are lattices for which the operations of join and meet distribute over each other. ... // Every totally ordered set is a distributive lattice with max as join and min as meet. ...


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). Counting is the mathematical action of repeatedly adding (or subtracting) one, usually to find out how many objects there are or to set aside a desired number of objects (starting with one for the first object and proceeding with an injective function from the remaining objects to the natural numbers... In mathematics, a well-order (or well-ordering) on a set S is a total order on S with the property that every non-empty subset of S has a least element in this ordering. ... In the mathematical field of order theory an order isomorphism is a special kind of monotone function that constitutes a suitable notion of isomorphism for partially ordered sets. ... Ordinal numbers, or ordinals for short, are numbers used to denote the position in an ordered sequence: first, second, third, fourth, etc. ... In the mathematical field of order theory an order isomorphism is a special kind of monotone function that constitutes a suitable notion of isomorphism for partially ordered sets. ... In mathematics, an upper set, or upward closed set, is a subset Y of a given partially ordered set (X,≤) such that, for all elements x and y, if x is less than or equal to y and x is an element of Y, then y is also in Y... In mathematics, especially in set theory, ordinals may be used to label the elements of any given well-ordered set (the smallest element being labeled 0, the one after that 1, the next one 2, and so on) and to measure the length of the whole set by the least...


Contrast with a partial order, which lacks the third condition. An example of a partial order is the happened-before relation. In mathematics, a partially ordered set (or poset for short) is a set equipped with a special binary relation which formalizes the intuitive concept of an ordering. ... The happened-before relationship is important in figuring out partial ordering of events and in producing and synchronizing logical clocks for asynchronous distributed systems. ...


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). In mathematics, a subcategory S of a category C consists of subsets of the morphisms and of the objects of C, such that the subset X of morphisms is closed under composition in C, and the subset Y of objects contains the source and target of all the f in... In mathematics, categories allow one to formalize notions involving abstract structure and processes that preserve structure. ... In mathematics, a partially ordered set (or poset for short) is a set equipped with a special binary relation which formalizes the intuitive concept of an ordering. ... In mathematics, a morphism is an abstraction of a structure-preserving process between two mathematical structures. ...


A bijective map between two totally ordered sets that respects the two orders is an isomorphism in this category. A bijective function. ... In mathematics and related technical fields, the term map or mapping is often a synonym for function. ... In mathematics, an isomorphism (in Greek isos = equal and morphe = shape) is a kind of mapping between objects, devised by Eilhard Mitscherlich, which shows a relation between two properties or operations. ...


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. In mathematics, interval is a concept relating to the sequence and set-membership of one or more numbers. ... A Möbius strip, an object with only one surface and one edge; such shapes are an object of study in topology. ... In mathematics, the order topology is a topology that can be defined on any totally ordered set. ...


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. In topology and related branches of mathematics, normal spaces, T4 spaces, and T5 spaces are particularly nice kinds of topological spaces. ...


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. In mathematics, especially in order theory, an upper bound of a subset S of some partially ordered set is an element which is greater than or equal to every element of S. The term lower bound is defined dually. ... In mathematics, the supremum of an ordered set S is the least element (not necessarily in S) which is greater than or equal to each element of S. Consequently, it is also referred to as the least upper bound. ... In mathematics, the real numbers may be described informally as numbers that can be given by an infinite decimal representation, such as 2. ... In mathematics, a rational number is a number which can be expressed as a ratio of two integers. ...


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 a < b such that no c satisfies a < c < b.)
  • X is complete if and only if every bounded set that is closed in the order topology is compact.

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. In mathematics, a complete lattice is a partially ordered set in which all subsets have both a supremum (join) and an infimum (meet). ... In mathematics, a subset of Euclidean space Rn is called compact if it is closed and bounded. ... In mathematics, the unit interval is the interval [0,1], that is the set of all real numbers x such that zero is less than or equal to x and x is less than or equal to one. ... In mathematics, the affinely extended real number system is obtained from the real number system R by adding two elements: +∞ and −∞ (pronounced plus infinity and minus infinity). These new elements are not real numbers. ... In the mathematical field of topology a homeomorphism or topological isomorphism (from the Greek words homeos = identical and morphe = shape) is a special isomorphism between topological spaces which respects topological properties. ...


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: In mathematics, the Cartesian product is a direct product of sets. ...

All three can similarly be defined for the Cartesian product of more than two sets. In mathematics, the lexicographic or lexicographical order, (also known as dictionary order, alphabetic order or lexicographic(al) product), is a natural order structure of the Cartesian product of two ordered sets. ... In mathematics, given two ordered sets A and B, one can induce an ordering on the Cartesian product A × B. Given two pairs (a1,b1) and (a2,b2) in A × B, one sets (a1,b1) &#8804; (a2,b2) if and only if a1 &#8804; a2 and b1 &#8804; b2. ... In mathematics, one can often define a direct product of objects already known, giving a new one. ...


Applied to the vector space Rn, each of these make it an ordered vector space. In mathematics, a vector space (or linear space) is a collection of objects (called vectors) that, informally speaking, may be scaled and added. ... A point x in R2 and the set of all y such that x≤y (in red). ...


See also examples of partially ordered setshttp://en.wikipedia.org/wiki/Partially_ordered_set#Examples. In mathematics, especially order theory, a partially ordered set (or poset) is a set equipped with a partial order relation. ...


A real function of n real variables defined on a subset of Rn defines a strict weak order and a corresponding total preorderhttp://en.wikipedia.org/wiki/Strict_weak_ordering#Function on that subset. A strict weak ordering is a binary relation that defines an equivalence relation and has the properties stated below. ...


See also

In mathematics, a partial order ≤* on a set X is an extension of a partial order ≤ on X provided that for any elements x1 and x2 of X with x1 ≤ x2, it is also the case that x1 ≤* x2. ... Order theory is a branch of mathematics that studies various kinds of binary relations that capture the intuitive notion of a mathematical ordering. ... In mathematics, especially order theory, a partially ordered set (or poset) is a set equipped with a partial order relation. ... In mathematics, a well-order (or well-ordering) on a set S is a total order on S with the property that every non-empty subset of S has a least element in this ordering. ... Suslins problem in mathematics is a question about orders posed by M. Suslin in the early 1920s. ... A Countryman line is an uncountable linear ordering whose square is the union of countably many chains. ...

Notes

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

  Results from FactBites:
 
PlanetMath: total order (0 words)
is then called a total order or a linear order (or total ordering or linear ordering).
A totally ordered set is also sometimes called a chain, especially when it is considered as a subset of some other poset.
This is version 16 of total order, born on 2001-10-06, modified 2006-11-25.
Fashion Knockoffs Fax Order Form (86 words)
Please remember to send us a confirming email if ordering by fax to ensure that the appropriate dept. is anticipating your order.
Please call to confirm when ordering by fax.
If you do not feel comfortable ordering over the internet, use this form to
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m