Let $S, T$ be two semigroups. In the following all semigroups are supposed to be finite. We write $S \prec T$ if there exists a surjective semigroup morphism from a subsemigroup of $T$ onto $S$. A class of finite semigroups $\mathcal V$ is defined by a set of equations if exactly the semigroup in $\mathcal V$ fulfill those equations, similar for a class of finite monoids. Let $\mathcal W$ be a class of monoid, we denote by $\mathcal W_S$ the class of semigroups $$ \mathcal W_S = \{ S \mbox{ is a semigroup} \mid S \prec M, M \in \mathcal W \} $$ where the monoid $M$ is considered as a semigroup. Let $R_n$ denote the class of monoid defined by $$ (xy)^n x = (xy)^n. $$ Then the class of semigroup $(R_n)_S$ is defined by the equations $$ x^{n+1} = x^n, \quad (xy)^n x = (xy)^n. $$ Denote by $V_n$ the class of semigroups defined by the single equation $$ (xy)^n x = (xy)^n. $$ Show that $$ (R_n)_S \subseteq V_n \subseteq (R_{n+1})_S. $$ Hint: Utilize the free semigroup over two generators and its subsemigroup of sequenezes of length at least $k$ for suitable $k$.

This is exercise V.3.2 from Samuel Eilenberg, Automata, Machines and Languages, Volume B.

The inclusion $(R_n)_S \subseteq V_n$ is obvious, for properness we can look at the cyclic semigroup $S = \{x,x^2, \ldots, x^{n+1}\}$ with $x^{n+2} = x^{n+1}$. But for the other inclusion I have no idea? I see that if we set $y = x$ we get $V_n \subseteq (R_{2n})_S$, but that is not enough.

  • $\begingroup$ Call your example $S_{n+1}$. Then $S_{2n}$, where $x^{2n+1}=x^{2n}$, seems to be in $V_n$, but it does not satisfy $x^{n+2}=x^{n+1}$ which indeed seems to be implied by being in $(R_{n+1}) _S$. $\endgroup$ – Berci Jun 26 '18 at 13:20
  • $\begingroup$ Yes, so the exercise is wrong? I also could not make much sense out of the hint given... $\endgroup$ – StefanH Jun 26 '18 at 13:22
  • $\begingroup$ Based on our current understanding, I can imagine it's only a typo, meaning $(R_{2n})_S$ on the right hand side. But I'm not sure. $\endgroup$ – Berci Jun 26 '18 at 13:29

It is indeed a typo. The second inclusion fails for $n = 2$. Take the semigroup $\{a, a^2, a^3, a^4\}$ with $a^4 = a^5$. Then it satisfies the equation $(xy)^2x = (xy)^2$ but it does not satisfy the equation $x^4 = x^3$.


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.