Extension Theorem for Total Orderings

From ProofWiki
Jump to navigation Jump to search

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

By Inverse Completion is Commutative Semigroup:

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$


Sources