Complement of Strict Total Ordering

Theorem

Let $\left({S, \prec}\right)$ be a relational structure such that $\prec$ is a strict total ordering.

Then the complement of $\prec$ is a weak total ordering.

Proof

We need to show that $\not \prec$ is a weak total ordering.

First we check in turn each of the criteria for an ordering:

Reflexivity

By Complement of Reflexive Relation, it follows directly that $\not \prec$ is reflexive.

Transitivity

Let $a \not \prec b$ and $b \not \prec c$.

Now, suppose that $a \prec c$.

As $b \not \prec c$, from the Trichotomy Law, one of the following is the case:

• $b = c$ and so $a \prec b$;

• $c \prec b$ and $a \prec b$ from transitivity of $\prec$.

Both are an immediate contradiction.

So $a \not \prec c$ and so $\not \prec$ is transitive.

Antisymmetry

Suppose $a \not \prec b$.

Then from the Trichotomy Law, either $a = b$ or $b \prec a$.

Similarly, if $b \not \prec a$ we have that either $a = b$ or $a \prec b$.

As $\prec$ is asymmetric, $b \prec a \iff \neg a \prec b$.

So if $a \not \prec b$ and $b \not \prec a$, it follows that $a = b$.

So $\not \prec$ is antisymmetric.

The fact that $\not \prec$ is connected follows directly from the Trichotomy Law.

$\blacksquare$