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.