Order (on a set)
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.
Comments
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.
Order (on a set). Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Order_(on_a_set)&oldid=33634