An order relation satisfies the following properties:
For all \(a \in S\), \(a \le a\). (the property)
For all \(a, b \in S\), if \(a \le b\) and \(b \le a\), then \(a = b\). (the property)
For all \(a, b, c \in S\), if \(a \le b\) and \(b \le c\), then \(a \le c\). (the property)
A set that has an order relation is called a partially ordered set (or “poset”), and \(\le\) is its partial order.
Totality of an order
There is also a fourth property that distinguishes between two different types of orders:
For all \(a, b \in S\), either \(a \le b\) or \(b \le a\) or both. (the property)
The total property implies the reflexive property, by setting \(a = b\).
If the order relation satisfies the total property, then \(S\) is called a totally ordered set, and \(\le\) is its total order.
A fifth property that extends the idea of a “total order” is that of the well-ordering:
For every subset \(X\) of \(S\), \(X\) has a least element: an element \(x\) such that for all \(y \in X\), we have \(x \leq y\).
Well-orderings are very useful: they are the orderings we can performover. (For more on this viewpoint, see the page on .)
The order relation immediately affords several other relations.
We can define a reverse order \(\ge\) as follows: \(a \ge b\) when \(b \le a\).
From any poset \((S, \le)\), we can derive a strict order \(<), which disallows equality. For \(a, b \in S\), \(a < b\) when \(a \le b\) and \(a \neq b\). This strict order is still antisymmetric and transitive, but it is no longer reflexive.
We can then also define a reverse strict order \(>\) as follows: \(a > b\) when \(b \le a\) and \(a \neq b\).
In a poset that is not totally ordered, there exist elements \(a\) and \(b\) where the order relation is undefined. If neither \(a \leq b\) nor \(b \leq a\) then we say that \(a\) and \(b\) are incomparable, and write \(a \parallel b\).
From any poset \((S, \leq)\), we can derive an underlying cover relation \(\prec\), defined such that for \(a, b \in S\), \(a \prec b\) whenever the following two conditions are satisfied:
\(a < b\).
For all \(s \in S\), \(a \leq s < b\) implies that \(a = s\).
Simply put, \(a \prec b\) means that \(b\) is the smallest element of \(S\) which is strictly greater than \(a\). \(a \prec b\) is pronounced ”\(a\) is covered by \(b\)”, or ”\(b\) covers \(a\)”, and \(b\) is said to be a cover of \(a\).