FACTOID # 10: The total number of state executions in 2005 was 60: 19 in Texas and 41 elsewhere. The racial split was 19 Black and 41 White.
 
 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 > Totally ordered set

In mathematics, a total order or linear 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 ab and ba then a = b (antisymmetry)
if ab and bc then ac (transitivity)
ab or ba (totalness)

A set with a total order on it is called a totally ordered set, a linearly 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 aa. 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 ab if and only if .


If a and b are members of a totally ordered set, we may write a < b if ab and ab. 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 ab 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.


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.


Examples

The following is valid up to order isomorphism:


The set of natural numbers is the unique smallest totally ordered set with no upper bound. Similarly, the unique smallest totally ordered set with neither an upper nor a lower bound is the integers. The unique smallest unbounded totally ordered set which also happens to be dense in the sense that (a, b) is non-empty for every a < b, is the rational numbers. The unique smallest unbounded connected totally ordered set is the real numbers.


Note that subsets are possible, which in a way are smaller, but that they are order isomorphic and therefore not counting as smaller. For example, instead of natural numbers and integers we can take the even ones, and instead of all rational numbers we can take those with a finite decimal expansion.


Any set of cardinal numbers or ordinal numbers is totally ordered (in fact, even well-ordered).



See also: happened-before


  Results from FactBites:
 
Total order - Wikipedia, the free encyclopedia (1046 words)
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.
Thus a total order is also a partial order, that is, a binary relation which is reflexive, antisymmetric and transitive.
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.
Station Information - Total order (347 words)
In mathematics, a total order or linear order on a set X is a binary relation that is reflexive, antisymmetric, transitive and total.
Alternatively, one may define a totally ordered set as a particular kind of lattice, namely one in which we have {a v b, a ^ b} = {a, b} for all a, b.
Similarly, the unique smallest totally ordered set with neither an upper nor a lower bound is the integers.
  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