# examples of finitely generated semigroups that are not residually finite

Does anybody know of any finitely generated semigroups that are not residually finite and whose group of units (if there is an identity) is trivial? Basically, I'm looking for finitely generated semigroups that are not residually finite, but I don't just want to punt and look at groups (like Thompson's groups or something). Thanks!

-

Take $S=\langle a, b, c \mid ab^na=0 \hbox{ for all prime } n, ab^ma=c \hbox{ for all composite } m\rangle$. If there exists a homomorphism of that semigroup onto a finite semigroup $F$, and $\bar x$ is the image of $x$ ($x=a,b,c$), then $\bar b^n=\bar b^{n+m}$ for some $n,m$. Therefore for every prime $p>n$, and every $k$, $\bar b^p=\bar b^{p+mk}$. For some $k$, say, $k=p$, $p+km$ is not prime. Hence $\bar c= \bar a\bar b^{p+mk}\bar a=\bar a \bar b^p\bar a=0$. So $c$ and $a$ cannot be separated by a homomorphism to a finite semigroup. So $S$ is not residually finite. The semigroup $S$ does not have a unit.

That was just the simplest example.

There are also many finitely presented examples. For example, take a deterministic Turing machine $T$ with one tape and undecidable halting problem, tape alphabet $X$, state alphabet $Q$, commands $[U_i\to V_i]$, $i=1,...,n$ (where $U_i, V_i$ are words containing one occurrence of $Q$-letter each). For simplicity assume that the letters on the tape to the right of the state letter and to the left of the state letter are from disjoint parts of $X$. Consider the semigroup $\langle X\cup Q | U_i=V_i, i=1,...,n\rangle$. If the input and the terminal states cannot occur in the middle of computation and the terminal state can occur only when the tape is empty, it is easy to see that the semigroup will have undecidable word problem. So by McKinsey it is not residually finite. The group of units of this semigroup is also empty.

All the statements about semigroups in these two examples follow from the fact that the presentations are confluent and terminating (there are no overlaps at all), see any book on rewriting systems.

-
Thanks for the examples! –  dan Dec 7 '10 at 22:53
McKinsey? or McKenzie? Gerhard "Ask Me About System Design" Paseman, 2010.12.08 –  Gerhard Paseman Dec 9 '10 at 4:22
$\,\,\,\,\,\,$McKinsey –  Mark Sapir Dec 9 '10 at 4:58

I think the easiest answer is the bicyclic monoid $B$ given by the presentation $\langle a,b\mid ab=1\rangle$. Considering a unilateral shift on Hilbert space and its adjoint show that $ba\ne 1$. But of course $ab=1\implies ba=1$ in a finite monoid so $ba$ and $1$ are inseparable in a finite monoid. Actually, it is known that any proper image of $B$ is a cyclic group. There are no invertible elements in $B$ since using the relation, it is easy to see that every element is of the form $b^ma^k$ with $m,k$ nonnegative integers. If the element is invertible and not the identity, then either $a$ would have a left inverse or $b$ would have a right inverse, which would make $B$ a group.

Actually, it is known that $B$ cannot be embedded in any compact Hausdorff topological monoid. In particular, it cannot embed in it's profinite completion.

If one takes the monoid with presentation $\langle a,b,c,d\mid ab=1=cd, cb=0=ad\rangle$, where 0 is a multiplicative zero, then one gets a monoid with no nontrivial proper images and trivial group of units, but this is a little harder to prove.

-