An order relation (also called an order or ordering) is a binary relation \(\le\) on a set \(S\) that can be used to order the elements in that set.

An order relation satisfies the following properties:

1. For all \(a \in S\), \(a \le a\). (the reflexive property)

2. For all \(a, b \in S\), if \(a \le b\) and \(b \le a\), then \(a = b\). (the antisymmetric property)

3. For all \(a, b, c \in S\), if \(a \le b\) and \(b \le c\), then \(a \le c\). (the transitive 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:

1. For all \(a, b \in S\), either \(a \le b\) or \(b \le a\) or both. (the total 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.

Well-ordering

A fifth property that extends the idea of a “total order” is that of the well-ordering:

1. 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 perform induction over. (For more on this viewpoint, see the page on structural induction.)

Derived relations

The order relation immediately affords several other relations.

Reverse order

We can define a reverse order \(\ge\) as follows: \(a \ge b\) when \(b \le a\).

Strict order

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\).

Incomparability

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\).

Cover relation

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:

1. \(a < b\).

2. 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\).