syntactic congruence

Let $S$ be a semigroup and let $X\subseteq S$.The relation

$$s_1{\equiv }_X{s}_2\mathrm{iff}\forall l,r\in S(l{s}_{1}r\in X\mathrm{iff}l{s}_{2}r\in X)$$(1)

is called the syntactic congruence of $X$.The quotient $S/{\equiv }_X$ is called the syntactic semigroup of $X$,and the natural morphism $\varphi :S\to S/{\equiv }_X$is called the syntactic morphism of $X$.If $S$ is a monoid, then $S/{\equiv }_X$ is also a monoid,called the syntactic monoid of $X$.

As an example,if $S=(\mathbb{N},+)$ and$X=\{n\in \mathbb{N}\mid \exists k\in \mathbb{N}\mid n=3k\},$then $m{\equiv }_{X}n$ if $mmod3=nmod3$,and the syntactic monoid is isomorphic to the cyclic group of order three.

It is straightforward that ${\equiv }_X$is an equivalence relation and $X$ is union of classes of ${\equiv }_X$.To prove that it is a congruence, let $s_1,s_2,t_1,t_2\in S$satisfy $s_1{\equiv }_X{s}_2$ and $t_1{\equiv }_X{t}_2$.Let $l,r\in S$ be arbitrary.Then $l{s}_1{t}_{1}r\in X$ iff $l{s}_2{t}_{1}r\in X$ because $s_1{\equiv }_X{s}_2$,and $l{s}_2{t}_{1}r\in X$ iff $l{s}_2{t}_{2}r\in X$ because $t_1{\equiv }_X{t}_2$.Then $s_1{t}_1{\equiv }_X{s}_2{t}_2$ since $l$ and $r$ are arbitrary.

The syntactic congruence is both left- and right-invariant,i.e., if $s_1{\equiv }_X{s}_2$,then $t{s}_1{\equiv }_{X}t{s}_2$ and $s_{1}t{\equiv }_X{s}_{2}t$ for any $t$.

The syntactic congruence is maximal in the following sense:

• if $\chi$ is a congruence over $S$ and $X$ is union of classes of $\chi$,

• then $s\chi t$ implies $s{\equiv }_{X}t$.

In fact, let $l,r\in S$:since $s\chi t$ and $\chi$ is a congruence, $lsr\chi ltr$.However, $X$ is union of classes of $\chi$,therefore $lsr$ and $ltr$are either both in $X$ or both outside $X$.This is true for all $l,r\in S$, thus $s{\equiv }_{X}t$.