Order relation

An order relation (or a partial order relation) on a set $S$ is a binary relation $\le$ on $S$ which satisfies the following axioms:

  • For all $a \in S$, $a \le a$. (Reflexivity)
  • For all $a,b \in S$, if $a\leq b$ and $b \leq a$, then $a=b$. (Anti-symmetry)
  • For all $a,b,c \in S$, if $a\leq b$ and $b \leq c$, then $a\leq c$. (Transitivity)

We use $b \ge a$ to denote $a\le b$.

One example of an ordering is the relation $\le$ on the natural numbers.

A set $S$ with a partial order relation on $S$ is also called a partially ordered set (or poset). Note that it under some partial orderings, there can exist elements $a,b$ in $S$, such that $a \neq b$, $a \nleq b$, and $a \ngeq b$. For instance, we could define $a\leq b$ to mean $a=b$, in which case we can only write $a \leq b$ or $a \geq b$ if $a=b$. For a more substantial example, we can let $S$ be the power set of another set $A$, and define $a \leq b$ to mean "$a$ is a subset of $b$." In this case, $a$ and $b$ are not related in either direction in many cases (e.g., when $a$ and $b$ are disjoint).

We say that a partial order on a set $S$ which also satisfies the axiom

  • For all $a,b \in S$, $a\le b$ or $b \le a$ (Comparability, or trichotomy)

is a total order. For instance, our first example, the relation $\le$ on the natural numbers, is a total order. A set with a total order is called a totally ordered set.

See Also

This article is a stub. Help us out by expanding it.