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:

- For all $~$a \in S$~$, $~$a \le a$~$. (the reflexive property)
- For all $~$a, b \in S$~$, if $~$a \le b$~$ and $~$b \le a$~$, then $~$a = b$~$. (the antisymmetric property)
- 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:

- 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:

- 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:

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

## Comments

Dylan Hendrickson

Any relation satisfying 1-3 is a partial order, and the corresponding set is a poset. A total order is a special kind of partial order defined by also satisfying 4.