Order relations, total and partial

The other great family of useful relations is that of order: it lets us say ”$a$ comes before $b$”. The key property is antisymmetry: if $a\le b$ and $b\le a$ then $a=b$ (in place of the symmetry of equivalences).

Definition — Total and partial order

A relation $R$ on $A$ is an (partial) order relation if it is reflexive, antisymmetric and transitive. It is called a total order if, in addition, for every $a,b\in A$, either $a\mathbin{R} b$ or $b\mathbin{R} a$ holds (every pair is comparable). Otherwise the order is called partial.

Example — Total order on $\mathbb{R}$

The relation $\le$ on $\mathbb{R}$ is a total order: given two reals, you always know which is the smaller. The line is a physical picture of the total order, in which every point is comparable with every other.

Example — Partial order: "divides" on $\mathbb{N}$

On $\mathbb{N}=\{1,2,3,\ldots\}$ we set $a\preceq b$ if $a$ divides $b$ (that is, $b=ka$ for some $k\in\mathbb{N}$).

• Reflexive: $a$ divides $a$.
• Antisymmetric: if $a\mid b$ and $b\mid a$ (with $a,b>0$) then $a=b$.
• Transitive: if $a\mid b$ and $b\mid c$ then $a\mid c$.

However $2$ does not divide $3$ and $3$ does not divide $2$: pairs of “distinct primes” are not comparable. It is a partial order.

Example — Partial order: inclusion $\subseteq$ between sets

The relation "$A\subseteq B$" on the power set $\mathcal{P}(X)$ is a partial order. For instance $\{1\}\subseteq\{1,2\}$, but $\{1\}$ and $\{2\}$ are not comparable.

Links

Topics: Set theory
Concepts: Inclusion · Partial order · Total order · Order relation