# Order relation

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:

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

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

Parents:

• 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.

• So effectively all order relations are partial order relations?