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

Title	Nerode equivalence
Canonical name	NerodeEquivalence
Date of creation	2013-03-22 18:52:11
Last modified on	2013-03-22 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