examples of finitely generated semigroups that are not residually finite

Question

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!

Answer 1

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.

Answer 2

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 its profinite completion.

If one takes the monoid (with zero) with presentation $\langle a,b,c,d\mid ab=1=cd, cb=0=ad\rangle$ in that category, 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.

Answer 3

To generalise @BenjaminSteinberg's (by now rather old) answer, Lallement showed in 1971 that a one-relation monoid $M = \text{Mon}\langle A \mid w= w'\rangle$ where $w$ is a left and right factor of $w'$ (that is, there exist $w_1, w_2 \in A^\ast$ with $w' \equiv ww_1 \equiv w_2 w$, where $\equiv$ denotes graphical equality of words) is not residually finite if the presentation relation of the left special monoid $L(M)$ associated to $M$ is not the presentation relation of a group. In this case, it cannot be embedded into a compact semigroup, just as the bicyclic monoid.

The left special monoid comes about through so-called compression, which is a little too long to get into here, but one particular corollary is that if one takes $w \equiv \varepsilon$, then $L(M) = M$. Hence $\text{Mon}\langle A \mid w' = 1\rangle$ is not residually finite if it is not the free product of a free monoid by a group. So this includes the bicyclic monoid $\text{Mon}\langle b,c \mid bc = 1\rangle$, but also more general examples such as $\text{Mon}\langle a,b \mid ababb = 1\rangle$ and $\text{Mon}\langle a,b,c \mid abacac = 1\rangle$, both of which have trivial group of units.

One can easily check whether or not a one-relation special monoid $\text{Mon}\langle A \mid w' = 1\rangle$ is the free product of a free monoid by a group by Adian's algorithm.