4 added 802 characters in body; added 3 characters in body; added 44 characters in body

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.

3 added 212 characters in body

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$. 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$). 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.

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 if $(a,2)\le (b,2)$ iff $(a,1)\le (b,1)$. That implies $(a,1)(c,1)\le (ac,2)=(a,1)(c,1)\le (b,1)(c,1)$ 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. 2 fix markup and spelling I am goinng going to show that any characterziation 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. A semigroup is called 3-nilpotent if it has 0 and$xyz=0$. Commutative 3-nilpotent semigroups have very explicite explicit structure. Each such$S$is a disjoint union of three subsets$A\sqcup B\sqcup {0}$\{0\}$ and the operation gives a symmetric function $A\times A\to B\cup {0}$. \{0\}$. Conversely any pair of (non-empty) sets$A,B$and any symmetric function$A\times A\to B\cup{0}$B\cup\{0\}$ defines a 3-nilpotent commutative semigroup (associativity is automatic since $xyz=0$). 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.

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 (explicitely 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}$ \{1,2\}$and${0}$\{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 if $(a,2)\le (b,2)$ iff $(a,1)\le (b,1)$. That implies $(a,1)(c,1)\le (b,1)(c,1)$ 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.

1