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

Question

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

Answer 1

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

Answer 2

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

For more examples, you can look at the article of Carton, Choffrut and Grigorieff that contains here [1].

[1] Carton, O., Choffrut, C., & Grigorieff, S. (2006). Decision problems among the main subfamilies of rational relations. RAIRO - Theoretical Informatics and Applications, 40(2), 255-275. doi:10.1051/ita:2006005

Answer 3

The simplest example is probably $\mathbb{Z}$. The set $\{0\}$ is rational in $\mathbb{Z}$ but is not recognizable.