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

Title	syntactic congruence
Canonical name	SyntacticCongruence
Date of creation	2013-03-22 18:52:08
Last modified on	2013-03-22 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