Which semigroups can be linearly ordered?

2012-04-01T15:36:07Z

As usual I consider a semigroup to be a structure $(A, +)$ such that $+$ is an associative binary function over the set $A$. The notion of linearly-ordered semigroup corresponds to structures of the form $(A, + , \leq)$ such that $(A,+)$ is a semigroup, $\leq$ is a linear order on $A$, and this order $\leq$ is compatible with the binary operation $+$ (i.e., if $a \leq b$ and $a' \leq b'$, then $a + a' \leq b + b'$).

I am interested on known answers to the following questions (they follow the same pattern):

Is there some "useful" characterization of semigroups which can be linearly ordered? To be more precise, for which semigroups $(A, +)$ there is a linear order $\leq$ such that $(A, +, \leq)$ is a linearly ordered semigroup?
Is there some "useful" characterization of commutative semigroups which can be linearly ordered?

Perhaps it is worth pointing out that for the case of commutative groups it is well known that the criteria for admitting a linear order coincides with being torsion-free.

Answer by Benjamin Steinberg for Which semigroups can be linearly ordered?

2012-04-01T18:55:54Z

You might want to look at Clifford's survey http://www.ams.org/journals/bull/1958-64-06/S0002-9904-1958-10221-9/S0002-9904-1958-10221-9.pdf for the commutative case. Although it is old, I doubt much new is known. Basically the cancelative case works like for groups. The general case can be more complicated because any totally ordered set is a semigroup with respect to max.

Answer by Mark Sapir for Which semigroups can be linearly ordered?

2012-04-05T16:28:44Z

I am going to show that any characterization of (linearly) orderable commutative semigroups should be as hard (or as easy, depending on your taste) as the characterization of orderable 3-nilpotent commutative semigroups and as hard as characterization of orderable commutative magmas.

A semigroup is called 3-nilpotent if it has 0 and $xyz=0$ for every $x,y,z$. Commutative 3-nilpotent semigroups have very explicit structure. Each such $S$ is a disjoint union of three subsets $A\sqcup B\sqcup \{0\}$ and the operation gives a symmetric function $A\times A\to B\cup \{0\}$. Conversely any pair of (non-empty) sets $A,B$ and any symmetric function $A\times A\to B\cup\{0\}$ defines a 3-nilpotent commutative semigroup (the product of elements from $A$ is defined using the function, all other products are 0; the associativity is automatic since $xyz=0$ for every $x,y,z$).

I will use my old idea of $\Theta$-indicator functions (see, say, Sapir, Mark V. Residually finite semigroups in varieties. Monash Conference on Semigroup Theory (Melbourne, 1990), 258–268, World Sci. Publ., River Edge, NJ, 1991.) If $\Theta$ is a property of countable semigroups and ${\mathcal A}, {\mathcal B}$ are two classes of semigroups (for simplicity we can assume that all countable semigroups have natural numbers as the underlying set). Then a $\Theta$-indicator is a map $\Phi$ from ${\mathcal A}$ to $\mathcal B$ such that

(*) for every $S\in \mathcal A$, the operation in $\Phi(S)$ is computable given the oracle computing the operation in $S$, satisfying the following property

(**) $S$ satisfies $\Theta$ iff $\Phi(S)$ satisfies $\Theta$.

The point is that if a $\Theta$-indicator exists, then the problem of describing semigroups from $\mathcal A$ satisfying $\Theta$ is as hard (or as easy) as the problem of describing semigroups from $\mathcal B$ with that property.

Edit. We can view the set $\mathcal F$ of all functions $\mathbb{N}\times\mathbb{N}\to \mathbb{N}$ as subsets of $\mathbb{N}^3$. They form a compact subset with the natural product topology. The set of all semigroup operations is a closed subset. So we can view $\Phi$ as a function from a closed subset of $\mathcal F$ to itself. As I learned from Simon Thomas, $\Phi$ satisfies (* ) if and only if it is continuous. See Dave Marker's text, Lemma 3.11. Dave Marker told me that the result probably goes back to Kleene and Turing. So $\Phi$ is a $\Theta$-indicator if and only if it is a continuous map satisfying (**). I did not know it when I introduced these in 1974 (I was a second year undergraduate student then), in fact I did not know it till a few days ago.

I used $\Theta$-indicators mostly to study residually finite semigroups. But one can use it for other properties including the orderability.

Theorem. Let $\Theta$ be the property of being linearly orderable. Then there exists an (explicitly constructed) $\Theta$-indicator map from the class of commutative monoids to the class of 3-nilpotent commutative semigroups.

Proof. Let $S$ be a commutative monoid. Consider the semigroup $T(S)$ which is a union of three sets $A\times \{1,2\}$ and $\{0\}$ with operation $(a,1)(b,1)=(ab,2)$, all other products are 0.

It is easy to see that (*) is satisfied. To show (**), assume that $S$ is orderable, then order $T(S)$ by $(a,i)\le (b,i)$ iff $a\le b$, $(a,2) \lt (b,1)$, $0\le x$ for every $a,b\in S$ and any $x$. Clearly it is a linear order on $T(S)$.

Conversely, if $T(S)$ is linearly orderable, define an order on $S$ by $a\le b$ iff $(a,2)\le (b,2)$. Note that $a\le b$ iff $(a,2)\le (b,2)$ iff $(a,1)(e,1)\le (b,1)(e,1)$ where $e$ is the identity element of $S$. Hence $(a,2)\le (b,2)$ iff $(a,1)\le (b,1)$. That implies $(ac,2)=(a,1)(c,1)\le (b,1)(c,1)=(bc,2)$ in $T(S)$ hence $ac\le bc$ in $S$. Q.E.D.

Thus one can say that orderable commutative monoids are described modulo 3-nilpotent commutative semigroups.

On the other hand if $S$ is only a commutative magma (not necessarily associative groupoid) with unit, then $T(S)$ is still a 3-nilpotent commutative semigroup and $S$ is orderable iff $T(S)$ is orderable. Hence describing orderable commutative (3-nilpotent) semigroups is as hard as describing all orderable unitary commutative magmas.

Which semigroups can be linearly ordered? - MathOverflow

Which semigroups can be linearly ordered?

Answer by Benjamin Steinberg for Which semigroups can be linearly ordered?

Answer by Mark Sapir for Which semigroups can be linearly ordered?