How to ensure the syntactic semigroup of $X$ is the smallest semigroup recognizing $X$

Show that the syntactic semigroup of $X$ is the smallest semigroup recognizing $X$ in the sense that, for every semigroup $S$ recognizing $X$, there exists a morphism from $S$ onto the syntactic semigroup of $X$.

Some background knowledge:

1. A semigroup $S$ is said to recognize a set $X$ if there exists a morphism $f:A^*\to S$ such that $X=f^{-1}(f(X))$.

2. (1) Let $X$ be a set of words. The set of contexts of a word $w$ is the set $$C(w)=\{(x,y)\in A^*\times A^*| xwy\in X\}\;.$$ (2) The syntactic equivalence of $X$ is defined by $u\equiv v$ if and only if $C(u)=C(v)$.
(3) The syntactic equivalence $\equiv$ is a congruence with concatenation of words and the quotient $A^*/\equiv$ is called the syntactic semigroup of $X$.

Actually I have known there exists a surjective map from $S$ to $A^*/\equiv$, since $\ker f\subset \equiv$. But I can't make sure the surjective map is a morphism.

Define $g:f(A^*) \rightarrow A^*/\equiv$ by:

$g(s)=[\text{ any }u \in A^*:f(u)= s]_\equiv = [\text{ any }u \in A^*: u \in f^{-1}(s)]_\equiv$

This works because you've established that $\ker f\subset \equiv$, so: $f(u)=f(v) \Rightarrow u \equiv v$. We know $g$ is surjective because $f$, being a morphism, is total, that is, defined on every $u \in A^*$, so $g(S)$ contains every $[u]_\equiv$. Note that if $s=f(x)$ then $g(s)=[x]_\equiv$.

To show $g$ a morphism, consider $s, t \in f(A^*), s=f(x), t=f(y)$. We then get

$g(st) = g(f(x)f(y))=g(f(xy))=[xy]_\equiv=[x]_\equiv[y]_\equiv=g(s)g(t)$

That finishes the proof you requested. But to be complete, let's show the part you said you did, that $ker(f) \subset\equiv$, that is $f(u)=f(v)\Rightarrow u\equiv v$. This is really the crux of the proof.

Take $f(u) = f(v)$ and any $\langle x,y\rangle \in C(u)$ and show $\langle x,y\rangle \in C(v)$. If we do that in one direction, it will work symmetrically in the other direction too, showing that $C(u)=C(v)$ and $u\equiv v$. We have:

$\langle x,y \rangle\in C(u)$, so $xuy \in X$ which implies $f^{-1}(f(xuy)) \subseteq f^{-1}(f(X))$ which $=X$.

But because $f$ is a morphism and $f(u)=f(v)$ we have $f(xuy)=f(xvy)$, so $f^{-1}(f(xvy)) \subseteq X$. Finally, since $xvy \in f^{-1}(f(xvy))$, we get $xvy\in X$ and $\langle x,y\rangle\in C(v)$, which was our goal.

• @ David Lewis：First,thanks for your help.And I think I understand what you mean.Actually I know the $g$ in your proof is a surjective morphism.But in my opinion,the problem I showed above seems to ask us to prove there exists a surjective morphism $f:S\to A^*/\equiv$.And in your proof,it just finished that there exists a surjective morphism $g:f(A^*)\to A^*/\equiv$.And does $f(A^*)$ equal to $S$? This is my main question. – Andylang Apr 10 '12 at 15:41
• $g$ has to be defined on $f(A^*)$ because you did not say that $f$ was surjective, so S could be a lot bigger than $f(A^*)$. Or you could fix it by declaring $f$ to be surjective. But don't get hung up on this -- it's a minor point and does not injure the cardinality argument. I think the crux for the question you asked is that $f$ is total, so the "reverse" morphism $g$ is surjective, which establishes that $\equiv$ is the smallest equivalence relation recognizing X. Do I have that right? Sounds like you did the hard parts on your own. – David Lewis Apr 10 '12 at 16:06
• Yes.I can figure out $g$ is surjective morphism. I just get confused that since $f$ is not known to be surjective or not,then how to get a surjective morphism from $S \to A^*/\equiv$ instead of from $f(A^*)\to A^*/\equiv$.If $f$ is surjective,I have no problem indeed. – Andylang Apr 10 '12 at 16:22
• @Andylang -- Ah, are you saying your inability to verify that the mapping ($g$ for me) is a morphism because you cannot verify that it is defined everywhere on S, that is, it is a total function, which is required for a morphism unless it is qualified by "partial"? But you were able to prove that the hoped-for morphism respects multiplication? If so, then looks like you hit on a glitch in the problem statement, which you need to fix one way or the other. That, of course, makes my whole proof beside the point. Well it was fun trying to streamline it down to essentials. – David Lewis Apr 10 '12 at 16:31
• @ David Lewis:Yes.I am confused with what you mentioned that "you cannot verify that it is defined everywhere on S".I don't know how can $g(s_1 s_2)=g(s_1)g(s_2)$ if $s_1 \in f(A^*)$ and $s_2 \in S$\ $A^*$. – Andylang Apr 10 '12 at 16:51

For $u\in A^*$ let $[u]$ be the $\equiv$-equivalence class of $u$.

Suppose that $S$ recognizes $X$ via the surjective homomorphism $f:A^*\to S$. Suppose further that $u,v\in A^*$ and $u\not\equiv v$. Without loss of generality there is $\langle x,y\rangle\in C(u)\setminus C(v)$. Then $xuy\in X$, so $f(xuy)\in f[X]$, but $xvy\notin X=f^{-1}[f[X]]$, so $f(xvy)\notin f[X]$, and $f(xuy)\ne f(xvy)$. But then $f(x)f(u)f(y)\ne f(x)f(v)f(y)$, and therefore $f(u)\ne f(v)$. In other words, if $u,v\in A^*$ and $f(u)=f(v)$, then $u\equiv v$.

For each $u\in A^*$ let $[u]_f=\{v\in A^*:f(v)=f(u)\}$, the equivalence class of $u$ with respect to the congruence induced by $f$. We’ve just shown that for every $u\in A^*$, $[u]_f\subseteq [u]$. In other words, the partition induced by $f$ refines the partition induced by $\equiv$, and it follows at once that $A^*/\equiv$ is a homomorphic image of $S$. Specifically, define $h:S\to A^*/\equiv$ as follows: for $s\in S$ fix $u\in f^{-1}[\{s\}]$ arbitrarily, and let $h(s)=[u]$. It’s straightforward to check that $h$ is a homomorphism.

Added: Here’s a counterexample if $f$ is not surjective.

Let $A=\{a\}$, and let $X=\{x\in A^*:|x|\text{ is odd}\}$. The two $\equiv$-classes are $[a]$ and $[aa]$, and the syntactic semigroup $S_0$ is isomorphic to $\Bbb Z_2=\Bbb Z/2\Bbb Z$ under addition via the isomorphism $[a]\mapsto 1$ and $[aa]\mapsto 0$. Extend $S_0$ to a new semigroup $S=\{[a],[aa],z\}$, where $z$ is a zero element: $z[a]=[a]z=z[aa]=[aa]z=z^2=z$. The map $f:A^*\to S:u\mapsto[u]$ shows that $S$ recognizes $X$, but there is no homomorphism $h$ of $S$ onto $S_0$: if $h$ were such a homomorphism, for each $s\in S_0$ there would be $t\in S$ such that $h(t)=s$, but then $$h(z)=h(zt)=h(z)h(t)=h(z)s\;,$$ contradicting the fact that $S_0$ has no zero element.

• @ Brian M. Scott：Actually if $f$ is surjective,I know how to prove it.But it seems that there is no clue that $f$ is surjective. – Andylang Apr 10 '12 at 14:29
• @Andylang -- I think you mean that you want to show $h$ in Brian's proof is surjective. But that's true because $c$ is a total function, being a morphism: $A^* \text{to} S$. I have done a complete proof below which incorporates that as well as the parts you have said you've done, not only for completeness, but I also tried for a clear, streamlined proof. – David Lewis Apr 10 '12 at 15:16
• @Andylang: Since the result as stated appears to require that $f$ be surjective, I assumed that this was part of your definition of morphism in this context. The definition of S recognizes X used by Jean-Eric Pin in his survey Syntactic semigroups cited here requires that $f$ be surjective. – Brian M. Scott Apr 10 '12 at 23:41
• @ Brian M. Scott:I agree with you.But in the book $Algebraic$ $Combinatorics$ $on$ $Words$,a semigroup $S$ recognizes $X$ if there exists a morphism(seems to be not necessary surjective) from $A^* \to S$ and $X=f^{-1} (f(X))$. So if I follow the author,it seems that I can't figure out the problem. Do you think so? – Andylang Apr 11 '12 at 4:31
• Is this Exercise 1.3.2 of Lothaire’s book? I just found the PDF. There appears to be a genuine error: see the counterexample that I just added to my answer. – Brian M. Scott Apr 11 '12 at 8:46