Nerode equivalence

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

$$s_1{𝒩}_X{s}_2\iff \forall t\in S(s_{1}t\in X\iff s_{2}t\in X)$$(1)

is an equivalence relation over $S$,called the Nerode equivalence 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{𝒩}_{X}n$ iff $mmod3=nmod3$.

The Nerode equivalence is right-invariant,i.e., if $s_1{𝒩}_X{s}_2$then $s_{1}t{𝒩}_X{s}_{2}t$ for any $t$.However, it is usually not a congruence.

The Nerode equivalence is maximal in the following sense:

• if $\eta$ is a right-invariant equivalence over $S$ and $X$ is union of classes of $\eta$,

• then $s\eta t$ implies $s{𝒩}_{X}t$.

In fact, let $r\in S$:since $s\eta t$ and $\eta$ is right-invariant, $sr\eta tr$.However, $X$ is union of classes of $\eta$,therefore $sr$ and $tr$are either both in $X$ or both outside $X$.This is true for all $r\in S$, thus $s{𝒩}_{X}t$.

The Nerode equivalence is linked to the syntactic congruenceby the following fact, whose proof is straightforward:

$$s_1{\equiv }_X{s}_2\mathrm{iff}l{s}_1{𝒩}_{X}l{s}_2\forall l\in S.$$