View source for Order (on a set)

{{TEX|done}}
''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$ ([[Transitive relation|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 order]]s on $A$; while the [[Interval dimension of a partially ordered set|interval dimension]] is the size of the smallest realisation from the class of [[interval order]]s.  

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 [[#References|[a1]]].

====References====
<table>
<TR><TD valign="top">[a1]</TD> <TD valign="top">  E. Szpilrajn,   "Sur l'extension de l'ordre partiel"  ''Fund. Math.'' , '''16'''  (1930)  pp. 386–389 {{ZBL|56.0843.02}}</TD></TR>
</table>

[[Category:Order, lattices, ordered algebraic structures]]