# Example of monoid $M$ such that $\operatorname{RAT}(M) \not\subseteq \operatorname{REC}(M)$

Let $M$ be a monoid, the family of rational sets $\operatorname{RAT}(M)$ is defined as the smallest set containing the finite subsets, and closed under union, concatentaion and the star operation. The family of recognizable subsets $\operatorname{REC}(M)$ as the family of subsets $L \subseteq M$ such that $L = \varphi^{-1}(\varphi(L))$ for some monoid morphism $\varphi : M \to N$ with $N$ finite.

Now, a McKnight's Theorem says that $M$ is finitely generated iff $\operatorname{REC}(M) \subseteq \operatorname{RAT}(M)$. And by the famous theorem of Kleene, if $M = \Sigma^{\ast}$ for some finite set $\Sigma$, then $\operatorname{REC}(M) = \operatorname{RAT}(M)$. But what about the inclusion $\operatorname{RAT}(M) \subseteq \operatorname{REC}(M)$?

Do you know any example of a monoid such that $\operatorname{RAT}(M) \not\subseteq \operatorname{REC}(M)$?

• If $M$ is an infinite simple group (or more generally, any monoid without nontrivial finite quotients), the only recognizable subsets of $M$ are $\varnothing$ and $M$. – Emil Jeřábek Jun 5 '18 at 15:09
• @EmilJeřábek Thanks, would you like to make this into a complete answer so I can accept it? Maybe adding some explanations, like this works because semigroup homomorphisms from a group are group homomorphisms... – StefanH Jun 5 '18 at 15:20

If $M$ is an infinite monoid that has no nontrivial finite quotient, then the only recognizable subsets of $M$ are $\varnothing$ and $M$ itself, whereas there are many more rational subsets.
As a special case, this holds if $M$ is any infinite simple group. (Monoid morphisms map inverse elements to inverse elements: $f(x)f(x^{-1})=f(x^{-1})f(x)=f(1)=1$. Thus, surjective monoid morphisms map groups to groups, and are group morphisms.)
A well known and studied example: the monoïde $\mathbb{N}^k$. Indeed, for $k\geq 2$, $\text{Rec}(\mathbb{N}^k)$ are more or less periodic rectangles meanwhile $\text{Rat}(\mathbb{N}^k)$ is the class of semilinear set (it contains for instance the set $\{ (i,i) \mid i\in\mathbb{N}\}$, which is not recognizable).
The simplest example is probably $\mathbb{Z}$. The set $\{0\}$ is rational in $\mathbb{Z}$ but is not recognizable.