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

Question

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.

Answer 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.

Answer 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.