Definition:Total Ordering

From ProofWiki

Jump to: navigation, search

Definition

Let $\left({S, \preceq}\right)$ be a poset.

Then the ordering $\preceq$ is a total ordering on $S$ iff $\left({S, \preceq}\right)$ has no non-comparable pairs:

$\forall x, y \in S: x \preceq y \lor y \preceq x$

That is, iff $\preceq$ is connected.

If this is the case, then $\left({S, \preceq}\right)$ is referred to as a totally ordered set or toset.

Some sources call this a linear ordering, or a simple ordering.

If it is necessary to emphasise that a total ordering $\preceq$ is not strict, then the term weak total ordering may be used.