Which semigroups can be linearly ordered? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T12:37:25Z http://mathoverflow.net/feeds/question/92818 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/92818/which-semigroups-can-be-linearly-ordered Which semigroups can be linearly ordered? boumol 2012-04-01T15:36:07Z 2012-04-07T21:53:23Z <p>As usual I consider a <em>semigroup</em> to be a structure $(A, +)$ such that $+$ is an associative binary function over the set $A$. The notion of <em>linearly-ordered semigroup</em> 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'$).</p> <p>I am interested on known answers to the following questions (they follow the same pattern):</p> <ol> <li><p>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?</p></li> <li><p>Is there some "useful" characterization of commutative semigroups which can be linearly ordered?</p></li> </ol> <p>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.</p> http://mathoverflow.net/questions/92818/which-semigroups-can-be-linearly-ordered/92836#92836 Answer by Benjamin Steinberg for Which semigroups can be linearly ordered? Benjamin Steinberg 2012-04-01T18:55:54Z 2012-04-01T18:55:54Z <p>You might want to look at Clifford's survey <a href="http://www.ams.org/journals/bull/1958-64-06/S0002-9904-1958-10221-9/S0002-9904-1958-10221-9.pdf" rel="nofollow">http://www.ams.org/journals/bull/1958-64-06/S0002-9904-1958-10221-9/S0002-9904-1958-10221-9.pdf</a> 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. </p> http://mathoverflow.net/questions/92818/which-semigroups-can-be-linearly-ordered/93230#93230 Answer by Mark Sapir for Which semigroups can be linearly ordered? Mark Sapir 2012-04-05T16:28:44Z 2012-04-07T21:53:23Z <p>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.</p> <p>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$). </p> <p>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 </p> <p>(*) 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 </p> <p>(**) $S$ satisfies $\Theta$ iff $\Phi(S)$ satisfies $\Theta$.</p> <p>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.</p> <p><b> Edit. </b> 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 <a href="http://homepages.math.uic.edu/~marker/math512/dst.pdf" rel="nofollow"> Dave Marker's text</a>, 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. </p> <p>I used $\Theta$-indicators mostly to study residually finite semigroups. But one can use it for other properties including the orderability. </p> <p><b> Theorem.</b> 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. </p> <p><b> Proof. </b> 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. </p> <p>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)$. </p> <p>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.</p> <p>Thus one can say that orderable commutative monoids are described modulo 3-nilpotent commutative semigroups. </p> <p>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. </p>