1

Let $M = \{a,b,c\}^*$ be a free monoid. Let consider $M' = \{abc, abcba, baabc, baba\}^*$ Check, if $M'$ is a free submonoid of $M$

The solution is:

$M'$ is not a free submonoid of $M$ beacuse: $abcbabaabc = abc \cdot baba \cdot abc = abcba \cdot baabc.$

I don't understand why this fact deny that $M'$ is a free submonoid. I know that fact:

If $T \subset S $ and S is a free monoid and $T^2 \subset T$ and $e \in T$ then $T$ is submonoid of S

user180834
  • 1,453

1 Answers1

2

Just give the elements of $M'$ different names to see why:

Define $A=abc$, $B=abcba$, $C=baabc$ and $D=baba$.

Now you can easily check that any set of generators of $M'$ has to include $A$, $B$, $C$ and $D$.

Thus in a free monoid, every different product of those would be a different element. In particular, in a free monoid, you'd have $ADA \ne BC$.

However using the definitions, you get $ADA = abc \cdot baba \cdot abc = abcba \cdot baabc = BC$ (you'll recognize in the middle the equation you gave). Therefore, $M'$ cannot be a free monoid.

Since $M'$ is not a free monoid, it cannot be a free submonoid of $M$. It is, of course, still a submonoid of $M$, it's just not free.

celtschk
  • 43,384
  • You also need to argue that $M'$ is not a free monoid on some other set of generators. (But it is fairly easy to see that any set of generators for $M'$ must include $A$, $B$, $C$ and $D$, so this isn't a big problem.) – Rob Arthan Apr 11 '15 at 14:42
  • @RobArthan: Good point, thank you; I'll modify my post accordingly. – celtschk Apr 11 '15 at 14:53
  • "Now you can easily check that any set of generators of M′ has to include A, B, C and D." Please check my train of thought A must be one of generators because product of {B,C,D} can't give A, and so on? – user180834 Apr 11 '15 at 15:49
  • @user180834: You cannot in general exclude $A$ from those products. For example, if in a monoid generated by $u$, $v$ and $w$ you'd have $uvwuvw=u$, $vwuvwu=v$ and $wuvwuv=w=c$ (note: I didn't check if such a monoid exists), then you could use $x=uvw$, $y=vwu$ and $z=wuv$ as set of generators containing none of $a$, $b$, $c$ despite each one needing all three to be written in the original generators. You see that $x$, $y$, $z$ generate the monoid because $x^2=a$, $y^2=b$ and $z^2=c$, so you can get the original generators back. However you can easily check that in $M'$ that cannot work … – celtschk Apr 11 '15 at 18:03
  • … because $M$ is a free monoid, and thus the number of $a$, $b$, $c$-faactors needed to write elements in $M$ add up on multiplication. Now by adding up positive numbers, you cannot ever get back to the positive numbers you've just added up, and the smallest $M$-length for a product in $M'$ you get is for $AD$ (length $7$), which already is longer than the largest length of single elements ($B$ and $C$ with length $5$ each). – celtschk Apr 11 '15 at 18:07