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

An order relation satisfies the following properties:

For all $a \in S$ , $a \leq a$ . (the reflexive property)
For all $a, b \in S$ , if $a \leq b$ and $b \leq a$ , then $a = b$ . (the antisymmetric property)
For all $a, b, c \in S$ , if $a \leq b$ and $b \leq c$ , then $a \leq c$ . (the transitive property)

A set that has an order relation is called a partially ordered set (or "poset"), and $\leq$ 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 \leq b$ or $b \leq 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 $\leq$ is its total order.

Well-ordering

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 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 $\geq$ as follows: $a \geq b$ when $b \leq a$ .

Strict order

From any poset $(S, \leq)$ , we can derive a strict order $<$ , which disallows equality. For $a, b \in S$ , $a < b$ when $a \leq 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 \leq 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 ∥ b$ .

Cover relation

From any poset $(S, \leq)$ , we can derive an underlying cover relation $≺$ , defined such that for $a, b \in S$ , $a ≺ 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 ≺ b$ means that $b$ is the smallest element of $S$ which is strictly greater than $a$ . $a ≺ b$ is pronounced " $a$ is covered by $b$ ", or " $b$ covers $a$ ", and $b$ is said to be a cover of $a$ .

Order relation