Order (on a set)

order relation

A binary relation on some set $A$, usually denoted by the symbol $\leq$ and having the following properties: 1) $a\leq a$ (reflexivity); 2) if $a\leq b$ and $b\leq c$, then $a\leq c$ (transitivity); 3) if $a\leq b$ and $b\leq a$, then $a=b$ (anti-symmetry). If $\leq$ is an order, then the relation $<$ defined by $a<b$ when $a\leq b$ and $a\neq b$ is called a strict order. A strict order can be defined as a relation having the properties 2) and 3'): $a<b$ and $b<a$ cannot occur simultaneously. The expression $a\leq b$ is usually read as "a is less than or equal to b" or "b is greater than or equal to a", and $a<b$ is read as "a is less than b" or "b is greater than a". The order is called total if for any $a,b\in A$ either $a\leq b$ or $b\leq a$. A relation which has the properties 1) and 2) is called a pre-order or a quasi-order. If $\triangleleft$ is a quasi-order, then the relation $a\approx b$ defined by the conditions $a\triangleleft b$ and $b\triangleleft a$ is an equivalence. On the quotient set by this equivalence one can define an order by setting $[a]\leq[b]$, where $[a]$ is the class containing the element $a$, if $a\triangleleft b$. 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 $a||b$ to indicate that neither $a\leq b$ nor $b\leq a$ holds.

If ${\le}$ and ${\sqsubseteq}$ are order relations on a set $A$, then ${\le}$ extends ${\sqsubseteq}$ if $a \le b$ whenever $a \sqsubseteq b$.