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 rightinvariant, 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$.
Title  syntactic congruence 

Canonical name  SyntacticCongruence 
Date of creation  20130322 18:52:08 
Last modified on  20130322 18:52:08 
Owner  Ziosilvio (18733) 
Last modified by  Ziosilvio (18733) 
Numerical id  6 
Author  Ziosilvio (18733) 
Entry type  Definition 
Classification  msc 68Q70 
Classification  msc 20M35 
Defines  syntactic semigroup 
Defines  syntactic monoid 
Defines  syntactic morphism 
Defines  maximality property of syntactic congruence 