Order (on a set)

From Encyclopedia of Mathematics
Revision as of 17:19, 7 February 2011 by (talk) (Importing text file)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

order relation

A binary relation on some set , usually denoted by the symbol and having the following properties: 1) (reflexivity); 2) if and , then (transitivity); 3) if and , then (anti-symmetry). If is an order, then the relation defined by when and is called a strict order. A strict order can be defined as a relation having the properties 2) and 3'): and cannot occur simultaneously. The expression is usually read as "a is less than or equal to b" or "b is greater than or equal to a" , and is read as "a is less than b" or "b is greater than a" . The order is called total if for any either or . A relation which has the properties 1) and 2) is called a pre-order or a quasi-order. If is a quasi-order, then the relation defined by the conditions and is an equivalence. On the quotient set by this equivalence one can define an order by setting , where is the class containing the element , if . For examples and references see Partially ordered set.


A total order is also called a linear order, and a set equipped with a total order is sometimes called a chain or totally ordered set. For emphasis, an order which is not (necessarily) total is often called a partial order; some writers use the notation to indicate that neither nor holds.

How to Cite This Entry:
Order (on a set). Encyclopedia of Mathematics. URL:
This article was adapted from an original article by L.A. Skornyakov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article