(related to Chapter: Order Relations)
We have learned three different possibilities of order relations "$\prec$" on a set $V$, all using the same notation $(V,\prec)$. We now want to recap all definitions again and compare them with each other. The following table summarizes the key differences:
Partial order | Total (Linear) Order | Strict Total Order |
---|---|---|
Poset | Chain | Strictly ordered set. |
=^. $(V,\preceq )$ | $(V,\preceq )$ | $(V,\prec)$ |
For $u,v,w\in V$: | ||
* reflexive: $u\preceq u$ | ||
* antisymmetric: $u\preceq v$ and $v\preceq u$ implies $u=v$ | ||
* transitive: $u\preceq v$ and $v\preceq w$ implies $u\preceq w$ | For $u,v,w\in V$: | |
* reflexive: $u\preceq u$ | ||
* antisymmetric: $u\preceq v$ and $v\preceq u$ implies $u=v$ | ||
* transitive: $u\preceq v$ and $v\preceq w$ implies $u\preceq w$ | ||
* connex: $u\preceq v$ for all $u,v\in V.$ | For $u,v,w\in V$: | |
* irreflexive: $u\not \prec u$ | ||
* asymmetric: $u\prec v$ implies $v\not\prec u$ | ||
* transitive: $u\prec v$ and $v\prec w$ implies $u\prec w$ | ||
Possibilities: | ||
* equal: $u=v$ | ||
* less or equal: $u\preceq v$ | ||
* less: $u\preceq v$ and $u\neq v$ | ||
* greater or equal: $u\succeq v$ | ||
* greater: $u\succeq v$ and $u\neq v$ | ||
* else incomparable | Possibilities: | |
* equal: $u=v$ | ||
* less or equal: $u\preceq v$ | ||
* less: $u\preceq v$ and $u\neq v$ | ||
* greater or equal: $u\succeq v$ | ||
* greater: $u\succeq v$ and $u\neq v$ | Possibilities: | |
* less: $u\prec v$ | ||
* greater: $u\succ v$ | ||
* else equal: $u=v$ | ||
Eg. $(\mathbb N,\le)$ | Eg. $(\mathbb N,<)$ |
Please note that since a total order of a set $V$ is reflexive while a strict total order on it is not, a total order never can be strict total and vice versa. A comparison of both types of order relations leads to the so-called diagonal^{1} $D$ of $V$ defined by $D:=\{(x,x)\in \preceq\}$: * We can transform a given chain $(V,\preceq )$ to a strictly ordered set $(V,\prec)$ by the set difference of the total order "$\preceq$" and $D$, i.e. the strict order is defined by $\prec := \preceq\setminus D.$ * On the other hand, if we change a given strictly ordered set $(V,\prec)$ into a chain $(V,\preceq )$ by the union of its strict order "$\prec$" and $D$, i.e. the total order is defined by $\preceq:=\prec\cup D.$
The word "diagonal" is chosen reflecting that the pairs elements $(x,x)\in \preceq$ are exactly the diagonal elements of the matrix representation of the reflexive relation "$\preceq$". ↩