# syntactic congruence

 $s_{1}\equiv_{X}s_{2}\;\;\mathrm{iff}\;\;\forall l,r\in S(ls_{1}r\in X\;\mathrm% {iff}\;ls_{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   $\phi: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 $m\mod 3=n\mod 3$, 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 $ls_{1}t_{1}r\in X$ iff $ls_{2}t_{1}r\in X$ because $s_{1}\equiv_{X}s_{2}$, and $ls_{2}t_{1}r\in X$ iff $ls_{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 $ts_{1}\equiv_{X}ts_{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$.

Title syntactic congruence SyntacticCongruence 2013-03-22 18:52:08 2013-03-22 18:52:08 Ziosilvio (18733) Ziosilvio (18733) 6 Ziosilvio (18733) Definition msc 68Q70 msc 20M35 syntactic semigroup syntactic monoid syntactic morphism maximality property of syntactic congruence