<p>Yes, these monoids have received attention in the research literature and actually lead to difficult questions.</p>

<p><strong>Definition</strong>. A monoid $N$ is called <em>projective</em> if the following property holds: if $f:N \to R$ is a monoid morphism and $h:T \to R$ is a surjective morphism, then there exists a morphism $g:N \to T$ such that $f = h \circ g$.</p>

<p>You can find a long discussion on projective monoids in [1], right after Definition 4.1.33. It is shown in particular that every projective finite semigroup is a band (a semigroup in which every element is idempotent). But the converse is not true and it is actually an open problem to decide whether a finite semigroup is projective.</p>

<p>[1] J. Rhodes and B. Steinberg, <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.115.5826&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">The $q$-theory of finite semigroups</a>. Springer Monographs in Mathematics. Springer, New York, 2009. xxii+666 pp. ISBN: 978-0-387-09780-0</p>

CC BY-SA 4.0
2018-06-06T12:57:39.683Z
Thanks for your answer! But is this property really necessary, I mean it is sufficient, but does the "division property" of the syntactic monoid really fails in general, and if so do you have an example (or counter-example that if the syntactic monoid divides another monoid, then the other monoid also recognizes the subset from which the syntactic monoid is built)?
StefanH
CC BY-SA 4.0
2018-06-06T12:47:46.373Z
2018-06-08T00:23:25.283Z
2018-06-08T00:23:25.283Z
J.-E. Pin
<p>Let $A$ be a finite alphabet. For a given language $L \subseteq A^{\ast}$ the <a href="https://en.wikipedia.org/wiki/Syntactic_monoid" rel="nofollow noreferrer">syntactic monoid</a> $M(L)$ is a well-known notion in formal language theory. Furthermore, a monoid $M$ recognizes a language $L$ iff there exists a morphism $\varphi : A^{\ast} \to M$ such that $L = \varphi^{-1}(\varphi(L)))$.</p>

<p>Then we have the nice result:</p>

<p>A monoid $M$ recognizes $L \subseteq A^{\ast}$ if $M(L)$ is a homomorphic image of a submonoid of $M$ (writen as $M(L) \prec M$).</p>

<p>The above is usually states in the context of regular languages, and then the above monoids are all finite.</p>

<p>Now suppose we substitute $A^{\ast}$ with an arbitrary monoid $N$, and we say that a subset $L \subseteq N$ is recognized by $M$ if there exists a morphism $\varphi : N \to M$ such that $L = \varphi^{-1}(\varphi(L))$. Then we still have that if $M$ recognizes $L$, then $M(L) \prec M$ (see S. Eilenberg,  Automata, Machines and Languages, Volume B), but does the converse hold?</p>

<p>In the proof for $A^{\ast}$ the converse is proven by exploiting the property that if $N = \varphi(M)$ for some morphism $\varphi : M \to N$ and $\psi : A^{\ast} \to N$ is also a morphism, then we can find $\rho : A^{\ast} \to M$ such that $\varphi(\rho(u)) = \psi(u)$ holds, simply by choosing some $\rho(x) \in \varphi^{-1}(\psi(x))$ for each $x \in A$ and extending this to a morphism from $A^{\ast}$ to $M$. But this does not work for arbitrary monoids $N$ so I expect the above converse to be false then. And if it is false, for what kind of monoid beside $A^{\ast}$ is it still true, and did those monoids have received any attention in the research literature?</p>

CC BY-SA 4.0
2018-06-06T21:36:20.277Z
End of first paragraph: wouldn't be L instead of A?
Mateus de Oliveira Oliveira
CC BY-SA 4.0
2018-06-07T09:06:23.823Z
@MateusdeOliveiraOliveira Yes, thank for noticing!
StefanH
<fl.formal-languages><automata-theory><regular-language><algebra><monoid>
Generalisation of the statement that a monoid recognizes language iff syntactic monoid divides monoid
StefanH
# Generalisation of the statement that a monoid recognizes language iff syntactic monoid divides monoid

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

Let $A$ be a finite alphabet. For a given language $L \subseteq A^{\ast}$ the [syntactic monoid](https://en.wikipedia.org/wiki/Syntactic_monoid) $M(L)$ is a well-known notion in formal language theory. Furthermore, a monoid $M$ recognizes a language $L$ iff there exists a morphism $\varphi : A^{\ast} \to M$ such that $L = \varphi^{-1}(\varphi(L)))$.

Then we have the nice result:

A monoid $M$ recognizes $L \subseteq A^{\ast}$ if $M(L)$ is a homomorphic image of a submonoid of $M$ (writen as $M(L) \prec M$).

The above is usually states in the context of regular languages, and then the above monoids are all finite.

Now suppose we substitute $A^{\ast}$ with an arbitrary monoid $N$, and we say that a subset $L \subseteq N$ is recognized by $M$ if there exists a morphism $\varphi : N \to M$ such that $L = \varphi^{-1}(\varphi(L))$. Then we still have that if $M$ recognizes $L$, then $M(L) \prec M$ (see S. Eilenberg, Automata, Machines and Languages, Volume B), but does the converse hold?

In the proof for $A^{\ast}$ the converse is proven by exploiting the property that if $N = \varphi(M)$ for some morphism $\varphi : M \to N$ and $\psi : A^{\ast} \to N$ is also a morphism, then we can find $\rho : A^{\ast} \to M$ such that $\varphi(\rho(u)) = \psi(u)$ holds, simply by choosing some $\rho(x) \in \varphi^{-1}(\psi(x))$ for each $x \in A$ and extending this to a morphism from $A^{\ast}$ to $M$. But this does not work for arbitrary monoids $N$ so I expect the above converse to be false then. And if it is false, for what kind of monoid beside $A^{\ast}$ is it still true, and did those monoids have received any attention in the research literature?

**Tags:** fl.formal-languages, automata-theory, regular-language, algebra, monoid

> **Comments:**
> **username_1**: End of first paragraph: wouldn't be L instead of A?  
> **username_0**: @MateusdeOliveiraOliveira Yes, thank for noticing!  

---

## 1 answers

### Answer by username_2 on 2018-06-06. Score: 5 | Accepted answer

Yes, these monoids have received attention in the research literature and actually lead to difficult questions.

**Definition**. A monoid $N$ is called *projective* if the following property holds: if $f:N \to R$ is a monoid morphism and $h:T \to R$ is a surjective morphism, then there exists a morphism $g:N \to T$ such that $f = h \circ g$.

You can find a long discussion on projective monoids in [1], right after Definition 4.1.33. It is shown in particular that every projective finite semigroup is a band (a semigroup in which every element is idempotent). But the converse is not true and it is actually an open problem to decide whether a finite semigroup is projective.

[1] J. Rhodes and B. Steinberg, [The $q$-theory of finite semigroups](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.115.5826&rep=rep1&type=pdf). Springer Monographs in Mathematics. Springer, New York, 2009. xxii+666 pp. ISBN: 978-0-387-09780-0

> **Comments:**
> **username_0**: Thanks for your answer! But is this property really necessary, I mean it is sufficient, but does the "division property" of the syntactic monoid really fails in general, and if so do you have an example (or counter-example that if the syntactic monoid divides another monoid, then the other monoid also recognizes the subset from which the syntactic monoid is built)?  

---

