Extension Theorem for Total Orderings
From ProofWiki
Contents |
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 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 \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle x_1 \circ \left({y_1}\right)^{-1}\) | \(=\) | \(\displaystyle x_2 \circ \left({y_2}\right)^{-1}\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle z_1 \circ \left({w_1}\right)^{-1}\) | \(=\) | \(\displaystyle z_2 \circ \left({w_2}\right)^{-1}\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle x_1 \circ w_1\) | \(\preceq\) | \(\displaystyle y_1 \circ z_1\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) |
... then $x_2 \circ \left({w_2}\right)^{-1} = y_2 \circ \left({z_2}\right)^{-1}$.
We have:
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle x_1 \circ \left({y_1}\right)^{-1}\) | \(=\) | \(\displaystyle x_2 \circ \left({y_2}\right)^{-1}\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \iff\) | \(\displaystyle \) | \(\displaystyle x_1 \circ y_2\) | \(=\) | \(\displaystyle x_2 \circ y_1\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) |
and:
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle z_1 \circ \left({w_1}\right)^{-1}\) | \(=\) | \(\displaystyle z_2 \circ \left({w_2}\right)^{-1}\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \iff\) | \(\displaystyle \) | \(\displaystyle z_1 \circ w_2\) | \(=\) | \(\displaystyle z_2 \circ w_1\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) |
So:
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\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 \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\preceq\) | \(\displaystyle y_1 \circ z_1 \circ y_2 \circ z_2\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \implies\) | \(\displaystyle \) | \(\displaystyle x_2 \circ w_2\) | \(\preceq\) | \(\displaystyle y_2 \circ z_2\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | Cancellability in Ordered Semigroup |
Thus $\preceq'$ is a well-defined relation on $T$.
$\blacksquare$
Proof that Relation is Transitive
To show that $\preceq'$ is transitive:
| \(\displaystyle \) | \(\displaystyle \forall x, y, z, w, u, v \in S:\) | \(\displaystyle \) | \(\displaystyle x \circ y^{-1}\) | \(\preceq'\) | \(\displaystyle z \circ w^{-1}\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle z \circ w^{-1}\) | \(\preceq'\) | \(\displaystyle u \circ v^{-1}\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \implies\) | \(\displaystyle \) | \(\displaystyle x \circ w \circ v\) | \(\preceq\) | \(\displaystyle y \circ z \circ v\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\preceq\) | \(\displaystyle y \circ w \circ u\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \implies\) | \(\displaystyle \) | \(\displaystyle x \circ v\) | \(\preceq\) | \(\displaystyle y \circ u\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | Cancellability in Ordered Semigroup | ||
| \(\displaystyle \) | \(\displaystyle \implies\) | \(\displaystyle \) | \(\displaystyle x \circ y^{-1}\) | \(\preceq'\) | \(\displaystyle u \circ v^{-1}\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) |
Thus $\preceq'$ is transitive.
$\blacksquare$
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$.
Suppose that WLOG that $z_1 \circ y_1 \circ y_2 \preceq z_2 \circ y_2 \circ y_1$.
As $\preceq$ is a total ordering on $S$, it's either that or $z_2 \circ y_2 \circ y_1 \preceq z_1 \circ y_1 \circ y_2 $.
So:
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle z_1 \circ y_1 \circ y_2\) | \(\preceq\) | \(\displaystyle z_2 \circ y_2 \circ y_1\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \implies\) | \(\displaystyle \) | \(\displaystyle x_1 \circ y_2\) | \(\preceq\) | \(\displaystyle x_2 \circ y_1\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \implies\) | \(\displaystyle \) | \(\displaystyle x_1 \circ y_1^{-1}\) | \(\preceq'\) | \(\displaystyle x_2 \circ y_2^{-1}\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \implies\) | \(\displaystyle \) | \(\displaystyle z_1\) | \(\preceq'\) | \(\displaystyle z_2\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) |
and we see that $\preceq'$ is a total ordering on $T$.
$\blacksquare$
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 \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle x_1\) | \(\preceq'\) | \(\displaystyle x_2\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \implies\) | \(\displaystyle \) | \(\displaystyle r_1 \circ s_1^{-1}\) | \(\preceq'\) | \(\displaystyle r_2 \circ s_2^{-1}\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \implies\) | \(\displaystyle \) | \(\displaystyle r_1 \circ s_2\) | \(\preceq\) | \(\displaystyle r_2 \circ s_1\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) |
and
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle y_1\) | \(\preceq'\) | \(\displaystyle y_2\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \implies\) | \(\displaystyle \) | \(\displaystyle u_1 \circ v_1^{-1}\) | \(\preceq'\) | \(\displaystyle u_2 \circ v_2^{-1}\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \implies\) | \(\displaystyle \) | \(\displaystyle u_1 \circ v_2\) | \(\preceq\) | \(\displaystyle u_2 \circ v_1\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) |
Because of the compatibility of $\preceq$ with $\circ$ on $S$, we have:
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\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 \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \implies\) | \(\displaystyle \) | \(\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 \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \implies\) | \(\displaystyle \) | \(\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 \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \implies\) | \(\displaystyle \) | \(\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 \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \implies\) | \(\displaystyle \) | \(\displaystyle x_1 \circ y_1\) | \(\preceq'\) | \(\displaystyle x_2 \circ y_2\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) |
Thus compatibility is proved.
$\blacksquare$
Proof about Restriction of Relation
To show that the restriction of $\preceq'$ to $S$ is $\preceq$:
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \forall x, y \in S: x\) | \(\preceq\) | \(\displaystyle y\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \implies\) | \(\displaystyle \) | \(\displaystyle \forall a \in S: \left({x \circ a}\right) \circ a\) | \(\preceq\) | \(\displaystyle \left({y \circ a}\right) \circ a\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \implies\) | \(\displaystyle \) | \(\displaystyle x\) | \(=\) | \(\displaystyle \left({x \circ a}\right) \circ a^{-1}\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\preceq\) | \(\displaystyle \left({y \circ a}\right) \circ a^{-1}\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle y\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) |
Conversely:
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \forall x, y \in S: x\) | \(\preceq'\) | \(\displaystyle y\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \implies\) | \(\displaystyle \) | \(\displaystyle \exists u, v, z, w \in S: x\) | \(=\) | \(\displaystyle u \circ v^{-1}\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle y\) | \(=\) | \(\displaystyle z \circ w^{-1}\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle u \circ w\) | \(\preceq\) | \(\displaystyle z \circ v\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \implies\) | \(\displaystyle \) | \(\displaystyle x \circ v \circ w\) | \(=\) | \(\displaystyle u \circ w\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\preceq\) | \(\displaystyle z \circ v\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle y \circ v \circ w\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \implies\) | \(\displaystyle \) | \(\displaystyle x\) | \(\preceq\) | \(\displaystyle y\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | Cancellability in Ordered Semigroup |
$\blacksquare$
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 \) | \(\displaystyle \forall x, y, z, w \in S:\) | \(\displaystyle \) | \(\displaystyle x \circ y^{-1}\) | \(\preceq^*\) | \(\displaystyle z \circ w^{-1}\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \iff\) | \(\displaystyle \) | \(\displaystyle x \circ w\) | \(\preceq\) | \(\displaystyle y \circ z\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) |
Then:
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle x \circ y^{-1}\) | \(\preceq^*\) | \(\displaystyle z \circ w^{-1}\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \implies\) | \(\displaystyle \) | \(\displaystyle x \circ w\) | \(=\) | \(\displaystyle \left({x \circ y^{-1} }\right) \circ \left({y \circ w}\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\preceq\) | \(\displaystyle \left({z \circ w^{-1} }\right) \circ \left({y \circ w}\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle y \circ z\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) |
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle x \circ w\) | \(\preceq\) | \(\displaystyle y \circ z\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \implies\) | \(\displaystyle \) | \(\displaystyle x \circ y^{-1}\) | \(=\) | \(\displaystyle \left({x \circ w}\right) \circ w^{-1} \circ y^{-1}\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\preceq^*\) | \(\displaystyle \left({y \circ z}\right) \circ w^{-1} \circ y^{-1}\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle z \circ w^{-1}\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) |
So:
| \(\displaystyle \) | \(\displaystyle \forall x, y, z, w \in S:\) | \(\displaystyle \) | \(\displaystyle x \circ y^{-1}\) | \(\preceq^*\) | \(\displaystyle z \circ w^{-1}\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \iff\) | \(\displaystyle \) | \(\displaystyle x \circ w\) | \(\preceq\) | \(\displaystyle y \circ z\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) |
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
- Seth Warner: Modern Algebra (1965)... (previous)... (next): $\S 20$: Theorem $20.6$
