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