Naturally Ordered Semigroup is Unique

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\struct {S, \circ, \preceq}$ and $\struct {S', \circ', \preceq'}$ be naturally ordered semigroups.


Let:

$0'$ be the smallest element of $S'$
$1'$ be the smallest element of $S' \setminus \set {0'} = S'^*$.

Then the mapping $g: S \to S'$ defined as:

$\forall a \in S: \map g a = \circ'^a 1'$

is an isomorphism from $\struct {S, \circ, \preceq}$ to $\struct {S', \circ', \preceq'}$.

This isomorphism is unique.


Thus, up to isomorphism, there is only one naturally ordered semigroup.


Proof

Proof that Mapping is Isomorphism

Let $T' = \Cdm g$, that is, the codomain of $g$.

By Zero is Identity in Naturally Ordered Semigroup, $0'$ is the identity for $\circ'$.

Thus:

$\map g 0 = \circ'^0 1' = 0'$

and so $0' \in T'$


Suppose $x' \in T'$.

Then:

$\map g n = x'$

and so:

\(\displaystyle x' \circ' 1'\) \(=\) \(\displaystyle \circ'^n 1' \circ' 1'\)
\(\displaystyle \) \(=\) \(\displaystyle \paren {\circ'^n 1'} \circ' \paren {\circ'^1 1'}\)
\(\displaystyle \) \(=\) \(\displaystyle \circ'^{\paren {n \circ 1} } 1'\)
\(\displaystyle \) \(=\) \(\displaystyle \map g {n \circ 1}\)


So:

$x' \in T' \implies x' \circ' 1' \in T'$

Thus, by the Principle of Mathematical Induction applied to $S'$:

$T' = S'$

So:

$\forall a' \in S': \exists a \in S: \map g a = a'$

and so $g$ is surjective by definition.


From Index Laws for Semigroup: Sum of Indices:

$\map g {a \circ b} = \map g a \circ' \map g b$

and therefore $g$ is a homomorphism from $\struct {S, \circ}$ to $\struct {S', \circ'}$.

Now:

\(\displaystyle \forall p \in S: \ \ \) \(\displaystyle \circ'^p 1'\) \(\prec'\) \(\displaystyle \circ'^p 1' \circ' 1'\) Sum with One is Immediate Successor in Naturally Ordered Semigroup
\(\displaystyle \) \(=\) \(\displaystyle \paren {\circ'^p 1'} \circ' \paren {\circ'^1 1'}\)
\(\displaystyle \) \(=\) \(\displaystyle \circ'^{\paren {p \circ 1} } 1'\) Index Laws for Semigroup: Sum of Indices
\(\displaystyle \leadsto \ \ \) \(\displaystyle \circ'^p 1'\) \(\prec'\) \(\displaystyle \circ'^{\paren {p \circ 1} } 1'\)


For $p \in S$, let $S_p$ be the initial segment of $S$:

$S_p = \set {x \in S: x \prec p}$

Let:

$T = \set {p \in S: \forall a \in S_p: \circ'^a 1' \prec' \circ'^p 1'}$

Now $S_0 = \O \implies 0 \in T$.


Suppose $p \in T$.

Then:

$a \prec p \circ 1 \implies a \preceq p$

By Strict Lower Closure of Sum with One, either of these is the case:

$(1): \quad a \prec p: p \in T \implies \circ'^a 1' \prec' \circ'^p 1' \prec' \circ'^{\paren {p \circ 1} } 1'$
$(2): \quad a = p: \circ'^a 1' = \circ'^p 1' \prec' \circ'^{\paren {p \circ 1} } 1'$

In either case, we have:

$p \in T \implies p \circ 1 \in T$, and by thePrinciple of Mathematical Induction:
$T = S$


So $n \prec p \implies \circ'^n 1' \prec' \circ'^p 1'$.

Thus $g$ is a surjective monomorphism and therefore is an isomorphism from $\struct {S, \circ, \preceq}$ to $\struct {S', \circ', \preceq'}$.

$\blacksquare$


Proof that Isomorphism is Unique

Now we need to show that the isomorphism $g$ is unique.

Let $f: S \to S'$ be another isomorphism different from $g$.

Aiming for a contradiction, suppose $\map f 1 \ne 1'$.

We show by induction that $1' \notin \Cdm f$.



... Thus $1' \notin \Cdm f$ which is a contradiction.


Thus $\map f 1 = 1$ and it follows



that $f = g$.

Thus the isomorphism $g$ is unique.

$\blacksquare$


Sources