# Does a binoid contain an empty word?

$A$ is a finite alphabet. $A^*$ is the set of finite words or the free monoid generated by A.

$A^w$ is the set of infinite words generated by A. Denote $A^\infty=A^*\bigcup A^w$.

$X$ is a set of $A^\infty$. Denote $X_{*}=X\bigcap A^*$, $X_w=X\bigcap A^w$.

A binoid over $A$ is a subset $M$ of $A^\infty$ such that $$M_* M\subseteq M,\quad (M_*)^w\subseteq M.$$ The product of two elements is just using concatenation to put them together.

The notation and definition above quote from Algebraic Combinatorics on Words (2002), which is written by M.Lothaire.

It seems that if M is a binoid, $M_*$ must be a subsemigroup of $A^*$. But the book also mentioned that such $M_*$ is also a submonoid of $A^*$.

My question is how to ensure the empty word or so-called unit belongs to $M_*$, such that $M_*$ is not only a subsemigroup, but also a submonoid of $A^*$.

-
I don't see how it does. If you take $M = A^{\omega}-\{\text{emptyword}\}$, then it would seem to me that $M$ is a binoid. –  Arturo Magidin Mar 2 '12 at 6:04
@ Arturo Magidin :I agree that $M=A^ω−${emptyword}.So I don't konw how $M_*$ comes to be submonoid. –  Andylang Mar 2 '12 at 7:54

Lothaire goes on to define, for $X\subseteq A^\infty$, $X^\infty\triangleq X_*^\infty\cup(X_*)^*X_\omega=X_*\,^*\cup X_*\,^\omega\cup(X_*)^*X_\omega$ and to say that $M\subseteq A^\infty$ is a binoid iff $M^\infty=M$. Clearly $\varepsilon\in X_*\,^*\subseteq X^\infty$ for all $X\subseteq A^\infty$, so he really does expect a binoid to contain $\varepsilon$ (the empty word).
Equally clearly, $M^\infty=M$ does not follow from $M_*M\subseteq M$ and $(M_*)^\omega\subseteq M$: let $M=\{a^\omega\}$ for some $a\in A$, and note that $M_*=\varnothing$, whence $M_*M=(M_*)^\omega=\varnothing\subseteq M$. Indeed, any non-empty $M\subseteq A^\omega$ would work for the same reason, and Arturo’s example, $M=A^+\cup A^\omega$, also works: $M_*M=A^+(A^+\cup A^\omega)=AA^+\cup A^\omega$ and $(M_*)^\omega=(A^+)^\omega=A^\omega$ are plainly subsets of $M$.
It appears to me that the simplest way to salvage the definition is to require that $M_*M=M$ and $(M_*)^\omega\subseteq M$, thereby forcing $\varepsilon$ to belong to $M_*$; the weaker requirement in the book may simply be a typo.
@ Brian M. Scott:As what you explained above,the reason for why $ε$ belongs to M is $M^\infty =M$,which implies $M_* ^*$⊆M.Yes?If I fix the definition as $M_* M=M$,I can just make sure the iff condition does hold.But it seems that I still can't get $ε$ belong to M,if I just follow the definition of binoid which is fixed as above. –  Andylang Mar 2 '12 at 11:22
@ Brian M. Scott:And the book implied that $M_*$ is a submonoid a little earlier than the iff condition appears. –  Andylang Mar 2 '12 at 11:25
@Andylang: I agree: the conditions $M_* M\subseteq M$ and $(M_*)^\omega\subseteq M$ don’t imply that $\varepsilon\in M$. But replacing $M_* M\subseteq M$ with $M_* M=M$ does, and also implies that $M^\infty=M$, which is pretty clearly what he really wants. –  Brian M. Scott Mar 2 '12 at 11:33