Naturally Ordered Semigroup: Why does axioms imply order of group is infinite countable ? Why are every group equal up to isomorphism?

Question

Naturally Ordered Semigroup:

http://www.proofwiki.org/wiki/Definition:Naturally_Ordered_Semigroup

I know $\mathbb N$ is a naturally ordered semigroup by definition. Also I know that the naturally ordered semigroup is unique up to isomorphism:

http://www.proofwiki.org/wiki/Natural_Numbers_form_Naturally_Ordered_Semigroup

Questions:

Why does the axioms of the naturally ordered semigroup imply that the order of the group is infinite countable (isomorphic to $\mathbb N$) ?

Why can't a uncountable set be a naturally ordered semigroup ?

Could someone explain why every naturally ordered semigroup is equal up to isomorphism (the proof is quite tricky and the notation is hard to understand)

Thanks everyone.

Answer 1

Informally speaking, the well-ordering combined with ability to go "exactly one step backwards" (i.e. "subtract one") implies that the countability of the structure; and the properties of naturally ordered semigroup imply this.

In a more formal setting (and possibly not in the most efficient demonstration), let $(S,\circ,\preceq)$ be a naturally ordered semigroup. Then:

1. We can make a simple observation which is not valid for general ordered semigroups, but which becomes true once we have the cancellation property of naturally ordered ones: If $a\prec b$, then $(a\circ c)\prec (b\circ c)$ for any $a,b,c\in S$, where $x \prec y$ means $x \preceq y \wedge x\not=y$ (i.e. being strictly smaller).

2. The well-ordering property tells us that there is some element $\bar{0} \in S$ which is smaller than all the other elements. As the label suggests, it behaves just like zero in natural numbers; $\bar{0}\circ x=x$ for any $x$ in the semigroup.

   In order to see why, consider the "subtraction" property of naturally ordered semigroups: It tells us that since $\bar{0}\preceq\bar{0}$, we have $\bar{0}=\bar{0}+z$ for some $z\in S$. By the definition of $\bar{0}$, we have $\bar{0}\preceq z$. If the inequality was strict; i.e. if we had $\bar{0}\prec z$, we'd also have $\bar{0}+\bar{0} \prec \bar{0}+z = \bar{0}$, an impossibility. Thus, $\bar{0}+\bar{0}=\bar{0}$.

   Finally, for any $x\in S$, we have $\bar{0}+x = \bar{0}+\bar{0}+x$ and cancellation simplifies this to $x = \bar{0}+x$.

3. Since $S$ has at least two different elements, the set of elements differing from $\bar{0}$ is non-empty and the well-ordering gives us its smallest element, $\bar{1}$, which is strictly greater than $\bar{0}$, but smaller than all the other elements. Not very surprisingly, it behaves similarly to number one among naturals; being the building block to build (all) the remaining ones.

4. Let's define $p_0=\bar{0}$ and $p_{i+1}=p_i\circ\bar{1}$; so that $p_1=\bar{1}$, $p_2=(\bar{1}\circ\bar{1})$ and so on. Since $\bar{0}\prec \bar{1}$, easy induction can be used to prove that $p_i\prec p_j$ whenever $i<j$. Thus, the mapping $i\mapsto p_i$ is actually an isomorphism between the ordered semigroups $(\mathbb{N},+,\leq)$ and $(\{p_0,p_1,\ldots\},\circ,\preceq)$.

5. So far so good; but what about elements of $S$ which are not of the form $p_i$ for any natural number $i$? Well, if there are any, the set of all such strange elements is non-empty and thus, using the well-ordering property one more time, it has the smallest element which we will call $s$.

   We have $\bar{1}\preceq s$, so according to the naturally ordered semigroup properties, $s$ can be expressed as $s=1\circ t$ for some $t$. Since $\bar{0}\prec \bar{1}$, we have $t=\bar{0}\circ t\prec \bar{1}\circ t=s$. But this means that $t$ must be equal to $p_i$ for some $i$, since $s$ was the smallest non-expressible element. But then, $s=1\circ p_i=p_{i+1}$ and $s$ would be expressible too, contradicting its choice as a non-expressible!

6. All in all, we've shown that the mapping $i\mapsto p_i$ is an isomorphism between $(\mathbb{N},+,\leq)$ and $(S,\circ,\preceq)$. Since being an isomorphism is both symmetric and transitive, it implies that all naturally ordered semigroups are isomorphic to $(\mathbb{N},+,\leq)$ and thus they all must be countably infinite too.