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:

4. For all $a, b \in S$, either $a \le b$ or $b \le a$ or both. (the [total_relation 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:

5. 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$.