Suppose $\mathcal{M}$ is a commutative monoid and $E$ is any equivalence relation on $\mathcal{M}$. Define $\widehat{E}$ to be the "shift-invariant" part of $E$, that is, $$a\widehat{E}b\quad\iff\quad\forall c(acEbc).$$
Say that $\mathcal{M}$ is scorable if every such $\widehat{E}$ is a congruence on $\mathcal{M}$, regardless of possible algebraic nastinesses of $E$.
My interest in scorability, and the name, comes from one way of looking at the construction of surreal numbers; see the first part of this MO question of mine.
Question: When is a monoid scorable (and for that matter, what is scorability actually called)?
For example, any abelian group (or even cancellative commutative monoid, via an appropriate embedding into a group) is scorable. This is basically trivial but a bit tedious. We reason as follows:
-
Let $(E)$ be the $\widehat{E}$-class of the additive identity $0$. We have $(E)=\{z: \forall w(z+wEw)\}$, which quickly leads to $(E)$ being a subgroup of $\mathcal{M}$. Since $\mathcal{M}$ is by assumption an abelian group, $(E)$ is normal and we just need to show that mod-$(E)$ equivalence coincides with $\widehat{E}$.
-
In one direction, if $x\widehat{E} y$ then letting $z=y-x$ we get $x+z\widehat{E}x$. Now for any $w$, the definition of $\widehat{E}$ means that $x+z+w-xEx+w-x$, and so $z\in (E)$.
-
In the other direction, assuming $x-y:=z\in(E)$ we get that for any $w$ we have $x+wEx+w+z$. But rearranging, this is equivalent to $x+wEx+z+w$ which is just $x+wEy+w$, and so $x\widehat{E}y$ as desired.
Note that scorability can be generalized to arbitrary algebraic structures – $\mathcal{A}$ is scorable iff for any equivalence relation $E$ on $\mathcal{A}$, the corresponding $\widehat{E}$ defined by $$a\widehat{E}b\quad\iff\quad\forall f\in\mathsf{Cl}(\mathcal{A}),\overline{c}\in\mathcal{A}(f(a,\overline{c})Ef(b,\overline{c}))$$ where $\mathsf{Cl}(\mathcal{A})$ is the clone of term operations on $\mathcal{A}$ – but it's not clear to me that this added generality is very interesting.
Best Answer
Question: When is a monoid scorable?
Any algebra is scorable. In fact, the relation $\widehat{E}$ defined in the problem is the largest congruence on $\mathbb A$ contained in $E$.
To see this one may use Maltsev's Congruence Generation Theorem, which asserts that a relation $\theta$ is a congruence of an algebra $\mathbb A$ if and only if it is an equivalence relation on $\mathbb A$ that is closed under all unary polynomials of $\mathbb A$. A unary polynomial is a function of the form $f(x,\bar{c})$ for some term $f(x,\bar{y})$ and some tuple $\bar{c}$ from $\mathbb A$. An equivalence relation $\theta$ is closed under $f(x,\bar{c})$ if $(a,b)\in\theta$ implies $(f(a,\bar{c}),f(b,\bar{c}))\in \theta$.
$\widehat{E}$ is a congruence contained in $E$.
(i) Choose $(a,b)\in\widehat{E}$ arbitrarily. Now choose $f(x,\bar{y}):=x$. For any $\bar{c}$ we have $(a,b)=(f(a,\bar{c}),f(b,\bar{c}))\in E$, showing that $\widehat{E}\subseteq E$.
(ii) It is easy to see that $\widehat{E}$ is an equivalence relation.
(iii) By the definition of $\widehat{E}$, for any $(a,b)\in\widehat{E}$ and $f(x,\bar{c})$ we have $(a',b'):=(f(a,\bar{c}),f(b,\bar{c})\in E$. To show that $\widehat{E}$ is closed under unary polynomials, I must argue that, in fact, $(a',b')\in\widehat{E}$. If this is not the case, then there must exist $g(x,\bar{d})$ such that $(g(a',\bar{d}),g(b',\bar{d}))\notin E$. But now, using the term $h(x,\overline{yz})=g(f(x,\bar{y}),\bar{z})$ and the tuple $\overline{cd}$ we get that $(h(a,\overline{cd}),h(b,\overline{cd}))\notin E$. This contradicts the fact that $(a,b)\in\widehat{E}$. \\\
$\widehat{E}$ is, in fact, the largest congruence contained in $E$.
Suppose that $\theta$ is any congruence contained in $E$. For any $(a,b)\in \theta$ and any $f(x,\bar{c})$ we have $(f(a,\bar{c}),f(b,\bar{c})\in \theta\subseteq E$. This establishes that $(a,b)\in \widehat{E}$. This shows that $\theta\subseteq \widehat{E}$ for any congruence $\theta$ contained in $E$. \\\