# Extension Theorem for Total Orderings

## Theorem

Let the following conditions be fulfilled:

$(1):\quad$ Let $\left({S, \circ, \preceq}\right)$ be a totally ordered commutative semigroup
$(2):\quad$ Let all the elements of $\left({S, \circ, \preceq}\right)$ be cancellable
$(3):\quad$ Let $\left({T, \circ}\right)$ be an inverse completion of $\left({S, \circ}\right)$.

Then:

$(1):\quad$ The relation $\preceq'$ on $T$ satisfying $\forall x_1, x_2, y_1, y_2 \in S: x_1 \circ \left({y_1}\right)^{-1} \preceq' x_2 \circ \left({y_2}\right)^{-1} \iff x_1 \circ y_2 \preceq x_2 \circ y_1$ is a well-defined relation
$(2):\quad$ $\preceq'$ is the only total ordering on $T$ compatible with $\circ$
$(3):\quad$ $\preceq'$ is the only total ordering on $T$ that induces the given ordering $\preceq$ on $S$.

## Proof

every element of $T$ is of the form $x \circ y^{-1}$ where $x, y \in S$.

### Proof that Relation is Well-Defined

First we need to show that $\preceq'$ is well-defined.

So we need to show that if $x_1, x_2, y_1, y_2, z_1, z_2, w_1, w_2 \in S$ satisfy:

 $\displaystyle x_1 \circ \left({y_1}\right)^{-1}$ $=$ $\displaystyle x_2 \circ \left({y_2}\right)^{-1}$ $\displaystyle z_1 \circ \left({w_1}\right)^{-1}$ $=$ $\displaystyle z_2 \circ \left({w_2}\right)^{-1}$ $\displaystyle x_1 \circ w_1$ $\preceq$ $\displaystyle y_1 \circ z_1$

then:

$x_2 \circ \left({w_2}\right)^{-1} = y_2 \circ \left({z_2}\right)^{-1}$

We have:

 $\displaystyle x_1 \circ \left({y_1}\right)^{-1}$ $=$ $\displaystyle x_2 \circ \left({y_2}\right)^{-1}$ $\displaystyle \iff \ \$ $\displaystyle x_1 \circ y_2$ $=$ $\displaystyle x_2 \circ y_1$

and:

 $\displaystyle z_1 \circ \left({w_1}\right)^{-1}$ $=$ $\displaystyle z_2 \circ \left({w_2}\right)^{-1}$ $\displaystyle \iff \ \$ $\displaystyle z_1 \circ w_2$ $=$ $\displaystyle z_2 \circ w_1$

So:

 $\displaystyle x_2 \circ w_2 \circ y_1 \circ z_1$ $=$ $\displaystyle x_1 \circ w_1 \circ y_2 \circ z_2$ $\displaystyle$ $\preceq$ $\displaystyle y_1 \circ z_1 \circ y_2 \circ z_2$ $\displaystyle \implies \ \$ $\displaystyle x_2 \circ w_2$ $\preceq$ $\displaystyle y_2 \circ z_2$ Strict Ordering Preserved under Product with Cancellable Element

Thus $\preceq'$ is a well-defined relation on $T$.

$\Box$

### Proof that Relation is Transitive

To show that $\preceq'$ is transitive:

 $\displaystyle \forall x, y, z, w, u, v \in S: \ \$ $\displaystyle x \circ y^{-1}$ $\preceq'$ $\displaystyle z \circ w^{-1}$ $\displaystyle z \circ w^{-1}$ $\preceq'$ $\displaystyle u \circ v^{-1}$ $\displaystyle \implies \ \$ $\displaystyle x \circ w \circ v$ $\preceq$ $\displaystyle y \circ z \circ v$ $\displaystyle$ $\preceq$ $\displaystyle y \circ w \circ u$ $\displaystyle \implies \ \$ $\displaystyle x \circ v$ $\preceq$ $\displaystyle y \circ u$ Strict Ordering Preserved under Product with Cancellable Element $\displaystyle \implies \ \$ $\displaystyle x \circ y^{-1}$ $\preceq'$ $\displaystyle u \circ v^{-1}$

Thus $\preceq'$ is transitive.

$\Box$

### Proof that Relation is Total Ordering

To show that $\preceq'$ is a total ordering on $T$ compatible with $\circ$:

Let $z_1, z_2 \in T$.

Then:

$\exists x_1, x_2, y_1, y_2 \in S: z_1 = x_1 \circ y_1^{-1}, z_2 = x_2 \circ y_2^{-1}$

Then:

$z_1 \circ y_1 = x_1$
$z_2 \circ y_2 = x_2$

As $\preceq$ is a total ordering on $S$, either:

$z_1 \circ y_1 \circ y_2 \preceq z_2 \circ y_2 \circ y_1$

or:

$z_2 \circ y_2 \circ y_1 \preceq z_1 \circ y_1 \circ y_2$

Suppose WLOG that:

$z_1 \circ y_1 \circ y_2 \preceq z_2 \circ y_2 \circ y_1$

So:

 $\displaystyle z_1 \circ y_1 \circ y_2$ $\preceq$ $\displaystyle z_2 \circ y_2 \circ y_1$ $\displaystyle \implies \ \$ $\displaystyle x_1 \circ y_2$ $\preceq$ $\displaystyle x_2 \circ y_1$ $\displaystyle \implies \ \$ $\displaystyle x_1 \circ y_1^{-1}$ $\preceq'$ $\displaystyle x_2 \circ y_2^{-1}$ $\displaystyle \implies \ \$ $\displaystyle z_1$ $\preceq'$ $\displaystyle z_2$

and it is seen that $\preceq'$ is a total ordering on $T$.

$\Box$

### Proof that Relation is Compatible with Operation

Let $x_1, x_2, y_1, y_2 \in T$ such that $x_1 \preceq' x_2, y_1 \preceq' y_2$.

We need to show that $x_1 \circ y_1 \preceq' x_2 \circ y_2$.

Let:

$x_1 = r_1 \circ s_1^{-1}, x_2 = r_2 \circ s_2^{-1}$
$y_1 = u_1 \circ v_1^{-1}, y_2 = u_2 \circ v_2^{-1}$

We have:

 $\displaystyle x_1$ $\preceq'$ $\displaystyle x_2$ $\displaystyle \implies \ \$ $\displaystyle r_1 \circ s_1^{-1}$ $\preceq'$ $\displaystyle r_2 \circ s_2^{-1}$ $\displaystyle \implies \ \$ $\displaystyle r_1 \circ s_2$ $\preceq$ $\displaystyle r_2 \circ s_1$

and

 $\displaystyle y_1$ $\preceq'$ $\displaystyle y_2$ $\displaystyle \implies \ \$ $\displaystyle u_1 \circ v_1^{-1}$ $\preceq'$ $\displaystyle u_2 \circ v_2^{-1}$ $\displaystyle \implies \ \$ $\displaystyle u_1 \circ v_2$ $\preceq$ $\displaystyle u_2 \circ v_1$

Because of the compatibility of $\preceq$ with $\circ$ on $S$:

 $\displaystyle \left({r_1 \circ s_2}\right) \circ \left({u_1 \circ v_2}\right)$ $\preceq$ $\displaystyle \left({r_2 \circ s_1}\right) \circ \left({u_2 \circ v_1}\right)$ $\displaystyle \implies \ \$ $\displaystyle \left({r_1 \circ u_1}\right) \circ \left({s_2 \circ v_2}\right)$ $\preceq'$ $\displaystyle \left({r_2 \circ u_2}\right) \circ \left({s_1 \circ v_1}\right)$ $\displaystyle \implies \ \$ $\displaystyle \left({r_1 \circ u_1}\right) \circ \left({s_1 \circ v_1}\right)^{-1}$ $\preceq'$ $\displaystyle \left({r_2 \circ u_2}\right) \circ \left({s_2 \circ v_2}\right)^{-1}$ $\displaystyle \implies \ \$ $\displaystyle \left({r_1 \circ s_1^{-1} }\right) \circ \left({u_1 \circ v_1^{-1} }\right)$ $\preceq'$ $\displaystyle \left({r_2 \circ s_2^{-1} }\right) \circ \left({u_2 \circ v_2^{-1} }\right)$ $\displaystyle \implies \ \$ $\displaystyle x_1 \circ y_1$ $\preceq'$ $\displaystyle x_2 \circ y_2$

Thus compatibility is proved.

$\Box$

### Proof about Restriction of Relation

To show that the restriction of $\preceq'$ to $S$ is $\preceq$:

 $\displaystyle \forall x, y \in S: x$ $\preceq$ $\displaystyle y$ $\displaystyle \implies \ \$ $\displaystyle \forall a \in S: \left({x \circ a}\right) \circ a$ $\preceq$ $\displaystyle \left({y \circ a}\right) \circ a$ $\displaystyle \implies \ \$ $\displaystyle x$ $=$ $\displaystyle \left({x \circ a}\right) \circ a^{-1}$ $\displaystyle$ $\preceq$ $\displaystyle \left({y \circ a}\right) \circ a^{-1}$ $\displaystyle$ $=$ $\displaystyle y$

Conversely:

 $\displaystyle \forall x, y \in S: x$ $\preceq'$ $\displaystyle y$ $\displaystyle \implies \ \$ $\displaystyle \exists u, v, z, w \in S: x$ $=$ $\displaystyle u \circ v^{-1}$ $\displaystyle y$ $=$ $\displaystyle z \circ w^{-1}$ $\displaystyle u \circ w$ $\preceq$ $\displaystyle z \circ v$ $\displaystyle \implies \ \$ $\displaystyle x \circ v \circ w$ $=$ $\displaystyle u \circ w$ $\displaystyle$ $\preceq$ $\displaystyle z \circ v$ $\displaystyle$ $=$ $\displaystyle y \circ v \circ w$ $\displaystyle \implies \ \$ $\displaystyle x$ $\preceq$ $\displaystyle y$ Strict Ordering Preserved under Product with Cancellable Element

$\Box$

### Proof that Relation is Unique

To show that $\preceq'$ is unique:

Let $\preceq^*$ be any ordering on $T$ compatible with $\circ$ that induces $\preceq$ on $S$.

Then:

 $\displaystyle \forall x, y, z, w \in S: \ \$ $\displaystyle x \circ y^{-1}$ $\preceq^*$ $\displaystyle z \circ w^{-1}$ $\displaystyle \iff \ \$ $\displaystyle x \circ w$ $\preceq$ $\displaystyle y \circ z$

Then:

 $\displaystyle x \circ y^{-1}$ $\preceq^*$ $\displaystyle z \circ w^{-1}$ $\displaystyle \implies \ \$ $\displaystyle x \circ w$ $=$ $\displaystyle \left({x \circ y^{-1} }\right) \circ \left({y \circ w}\right)$ $\displaystyle$ $\preceq$ $\displaystyle \left({z \circ w^{-1} }\right) \circ \left({y \circ w}\right)$ $\displaystyle$ $=$ $\displaystyle y \circ z$

 $\displaystyle x \circ w$ $\preceq$ $\displaystyle y \circ z$ $\displaystyle \implies \ \$ $\displaystyle x \circ y^{-1}$ $=$ $\displaystyle \left({x \circ w}\right) \circ w^{-1} \circ y^{-1}$ $\displaystyle$ $\preceq^*$ $\displaystyle \left({y \circ z}\right) \circ w^{-1} \circ y^{-1}$ $\displaystyle$ $=$ $\displaystyle z \circ w^{-1}$

So:

 $\displaystyle \forall x, y, z, w \in S: \ \$ $\displaystyle x \circ y^{-1}$ $\preceq^*$ $\displaystyle z \circ w^{-1}$ $\displaystyle \iff \ \$ $\displaystyle x \circ w$ $\preceq$ $\displaystyle y \circ z$

Hence as every element of $T$ is of the form $x \circ y^{-1}$ where $x, y \in S$, the orderings $\preceq^*$ and $\preceq'$ are identical.

$\blacksquare$