Nerode equivalence
Let $S$ be a semigroup^{} and let $X\subseteq S$. The relation^{}
$${s}_{1}{\mathcal{N}}_{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{\mathcal{N}}_{X}n$ iff $mmod3=nmod3$.
The Nerode equivalence is rightinvariant, i.e., if ${s}_{1}{\mathcal{N}}_{X}{s}_{2}$ then ${s}_{1}t{\mathcal{N}}_{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 rightinvariant equivalence over $S$ and $X$ is union of classes of $\eta $,

•
then $s\eta t$ implies $s{\mathcal{N}}_{X}t$.
In fact, let $r\in S$: since $s\eta t$ and $\eta $ is rightinvariant, $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{\mathcal{N}}_{X}t$.
The Nerode equivalence is linked to the syntactic congruence by the following fact, whose proof is straightforward:
$${s}_{1}{\equiv}_{X}{s}_{2}\mathrm{iff}l{s}_{1}{\mathcal{N}}_{X}l{s}_{2}\forall l\in S.$$ 
Title  Nerode equivalence 

Canonical name  NerodeEquivalence 
Date of creation  20130322 18:52:11 
Last modified on  20130322 18:52:11 
Owner  Ziosilvio (18733) 
Last modified by  Ziosilvio (18733) 
Numerical id  4 
Author  Ziosilvio (18733) 
Entry type  Definition 
Classification  msc 68Q70 
Classification  msc 20M35 
Defines  maximality property of Nerode equivalence 