3
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – Emil Jeřábek supports Monica Jun 5 '18 at 15:09
  • $\begingroup$ @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... $\endgroup$ – StefanH Jun 5 '18 at 15:20
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.