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$. Viewing relations as subsets of $A \times A$, this states that the relation ${\le}$ contains the relation ${\sqsubseteq}$ as a subset.

A family of order relations ${\le}_i$, $i \in I$, realises an order ${\sqsubseteq}$ on a set $A$ if each ${\le}_i$ extends ${\sqsubseteq}$ and $a \sqsubseteq b$ if and only if $a\,{\le}_i\,b$ for all $i \in I$. Viewing relations as subsets of $A \times A$, this states that the relation ${\sqsubseteq}$ is the intersection of the relations ${\le}_i$, $i \in I$. If $\mathcal{C}$ is a class of order relations and all the ${\le}_i$ are in $\mathcal{C}$ then they form a $\mathcal{C}$-realisation of ${\sqsubseteq}$. For example, the dimension of a partially ordered set $(A,{\sqsubseteq})$ is the size of the smallest realisation of ${\sqsubseteq}$ from the class of linear orders on $A$; while the interval dimension is the size of the smallest realisation from the class of interval orders.

The family of all order relations on a set is itself partially ordered by extension. The minimal element is the equality relation (distinct elements are incomparable), and the maximal elements are linear orders. Every order has a linear extension: this is Szpilrajn's theorem [a1].

References

[a1]	E. Szpilrajn, "Sur l'extension de l'ordre partiel" Fund. Math. , 16 (1930) pp. 386–389 Zbl 56.0843.02