3
$\begingroup$

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.

2 Answers 2

2

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.

  • 0
    @ 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.2012-04-10
  • 0
    $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.2012-04-10
  • 0
    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.2012-04-10
  • 0
    @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.2012-04-10
  • 0
    @ 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^*$.2012-04-10
  • 0
    @Andylang -- reread my proof. All you need is $s_1, s_2 \in f(A^*)$. I don't understand your last point about $s_2 \in S \backslash A^*$. $S$ and $A^*$ aren't even in the same base set. Did you mean $s_2 \in S \backslash f(A^*)$? But working with $f(A^*)$ rather than $S$ eliminates that case, yet does not injure the cardinality argument. (PS -- I prefer $X-Y$ to $X \backslash Y$)2012-04-10
  • 0
    @ David Lewis:I agree that doesn't injure the cardinality.But a morphism $f:S \to A^*/\equiv$ should satisfy:for any $s_1,s_2\in S$,$f(s_1 s_2)=f(s_1)f(s_2)$.So I will consider all the elements in $S$ not just $f(A^*)$ that whether $f(s_1 s_2)=f(s_1)f(s_2)$.And when I do this,the case I mentioned above will appear normally.2012-04-11
  • 0
    @ David Lewis:After reading your comment on Brian and my own thinking about the $smallest$.I finally agree with you.And I think we just need to know the syntactic is the smallest with respect to the cardinality.And it is not necessary to find a morphism from $S \to A^*/\equiv$,while it is good enough from $f(A^*) \to A^*/\equiv$.2012-04-12
  • 0
    @ David Lewis:Ignoring this problem,I want to ask you 2 questions for help. (1)What is the definition for a semigroup(or monoid) recognizing a set of words(or language)?(2)Are $recognizable$,$rational$ and $regular$ equivalent to each other?2012-04-13
  • 0
    @Andylang -- why not post those as questions? I think we've exceeded the design specs of comments ;-))2012-04-13
  • 0
    @ David Lewis:Yes.I have posted it as the title of "Two elementary question on automaton and language".And if possible,please have a look.Thanks in advance.2012-04-13
1

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.

  • 0
    @ 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.2012-04-10
  • 0
    @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.2012-04-10
  • 0
    @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](http://en.wikipedia.org/wiki/Syntactic_monoid) requires that $f$ be surjective.2012-04-10
  • 0
    @ 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?2012-04-11
  • 1
    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.2012-04-11
  • 0
    Last comment from me. @Brian -- nice counterexample. But what it shows is that we should work with $f(A^*)$ instead of $S$ as the domain of the "reverse" function -- rather than requiring $f$ surjective onto $S$. Why? We are proving that the syntactic semigroup is the smallest (coarsest) semigroup recognizing X, and making $S$ larger (if $f$ not surjective) does not interfere with that. So that allows for a slightly more general notion of a semigroup recognizing a language.2012-04-11
  • 0
    @ Brian M. Scott:Yes,exactly from there!And thanks a lot for your counterexample!I think that has helped me understand deeply about the problem.One more question,if $f$ is assumed to be surjective,the definition about a semigroup recognizing a set of words will be modified,since it just requires $f$ is a morphism so far.And if we just consider the $smallest$ with respect to the cardinality,then surjective has been proved and we just forget the requirement of morphism.So maybe we just need to modify the statement in the exercise from a $morphism$ to a $map$.How do you feel about that?2012-04-12
  • 0
    @Andylang: Judging from the little that I’ve read on the subject, I think that it would be better either to modify Lothaire definition to require that the morphism showing recognizability is surjective, or, as David Lewis suggests, to modify the problem to say that there is a morphism from $f[A^*]$ onto $S$.2012-04-12
  • 0
    @Andylang -- I think we are prolonging discussion of what is really a simple -- if important -- theorem. I doubt that a map $f$ that is not a morphism will of any value. We won't get the notion of recognition which is, after all, related to the notion of an automaton that recognizes a language. Classes of $\equiv$ become the states of an automaton, and if $f$ is not a morphism, that won't work, and neither will most of the other beautiful properties of recognition. So, instead of cardinality, we really mean refinement of an equivalence relation.2012-04-12
  • 0
    @ Brian M. Scott & David Lewis:Thanks you two for your best comment for the problem.I will think deeply and try to uniform the statement and make the problem easily understood by my friends.2012-04-13