<p>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.</p>

<p>As a special case, this holds if $M$ is any <a href="https://groupprops.subwiki.org/wiki/Infinite_simple_group" rel="nofollow noreferrer">infinite simple group</a>. (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.)</p>

CC BY-SA 4.0
2018-06-05T18:50:54.157Z
2018-06-05T18:50:54.157Z
Emil Jeřábek
<p>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).</p>

<p>For more examples, you can look at the article of Carton, Choffrut and Grigorieff that contains here <a href="https://www.cambridge.org/core/journals/rairo-theoretical-informatics-and-applications/article/div-classtitledecision-problems-among-the-main-subfamilies-of-rational-relationsdiv/26F373562A249E409ACF381E246C6B89" rel="nofollow noreferrer">[1]</a>.</p>

<p>[1] Carton, O., Choffrut, C., &amp; 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</p>

CC BY-SA 4.0
2018-06-06T09:45:17.537Z
2018-06-06T09:45:17.537Z
C.P.
<p>The simplest example is probably $\mathbb{Z}$. The set $\{0\}$ is rational in $\mathbb{Z}$ but is not recognizable.</p>

CC BY-SA 4.0
2018-06-09T18:22:06.973Z
2018-06-09T18:22:06.973Z
J.-E. Pin
<p>Let $M$ be a monoid, the family of <a href="https://en.wikipedia.org/wiki/Rational_set" rel="nofollow noreferrer">rational</a> 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 <a href="https://en.wikipedia.org/wiki/Recognizable_set" rel="nofollow noreferrer">recognizable</a> 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.</p>

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

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

CC BY-SA 4.0
2018-06-05T15:09:36.980Z
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
CC BY-SA 4.0
2018-06-05T15:20:12.023Z
@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
<fl.formal-languages><automata-theory><regular-language><algebra><monoid>
Example of monoid $M$ such that $\operatorname{RAT}(M) \not\subseteq \operatorname{REC}(M)$
StefanH
# Example of monoid $M$ such that $\operatorname{RAT}(M) \not\subseteq \operatorname{REC}(M)$

(Asked by: username_0 on 2018-06-05)

Let $M$ be a monoid, the family of [rational](https://en.wikipedia.org/wiki/Rational_set) 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](https://en.wikipedia.org/wiki/Recognizable_set) 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)$?

**Tags:** fl.formal-languages, automata-theory, regular-language, algebra, monoid
> **Comments:**
> **username_1**: 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$.  
> **username_0**: @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...  

---

## 3 answers

### Answer by username_1 on 2018-06-05. Score: 2 | Accepted answer

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](https://groupprops.subwiki.org/wiki/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 by username_2 on 2018-06-06. Score: 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]](https://www.cambridge.org/core/journals/rairo-theoretical-informatics-and-applications/article/div-classtitledecision-problems-among-the-main-subfamilies-of-rational-relationsdiv/26F373562A249E409ACF381E246C6B89).

[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 by username_3 on 2018-06-09. Score: 1

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


---

