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 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\le 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\ne 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\ne 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\le b$ nor $b\le a$ then we say that $a$ and $b$ are incomparable, and write $a\parallel b$.

Cover relation

From any poset $(S,\le )$, 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\le 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$.