# Zoran Skoda diamond lemma

Širšov-Bergman diamond lemma in Bergman form

• George M. Bergman, The diamond lemma for ring theory, Adv. in Math. 29 (1978), no. 2, 178–218, MR81b:16001, doi

Suppose we are given the following data

• $k$ – associative ring
• $X$ – any set,
• $\left\{X\right\}$ – free semigroup with $1$ on $X$
• $k\left\{X\right\}$ – semigroup algebra of $\left\{X\right\}$

Let $S$ be a set of pairs of the form $\sigma =\left({W}_{\sigma },{f}_{\sigma }\right)$ where ${W}_{\sigma }\in \left\{X\right\}$ , ${f}_{\sigma }\in k\left\{X\right\}$.

For any $\sigma \in S$ and $A,B\in \left\{X\right\}$, let ${r}_{A\sigma B}$ denote the $k$-module endomorphism of $k\left\{X\right\}$ that fixes all elements of $\left\{X\right\}$ other than ${\mathrm{AW}}_{\sigma }B$, and that sends this basis element to ${\mathrm{Af}}_{\sigma }B$. We shall call the given set $S$ a reduction system and the maps ${r}_{A\sigma B}:k\left\{X\right\}\to k\left\{X\right\}$ reductions.

We shall say that a reduction ${r}_{A\sigma B}$ acts trivially on an element $a\in k\left\{X\right\}$ if the coefficient of ${\mathrm{AW}}_{\sigma }B$ in $a$ is zero, and we shall call $a$ irreducible (under $S$) if every reduction is trivial on $a$, i.e. if $a$ involves none of the monomials ${\mathrm{AW}}_{\sigma }B$. The $k$-submodule of all irreducible elements of $k\left\{X\right\}$ will be denoted $k\left\{X{\right\}}_{\mathrm{irr}}$. A finite sequence of reductions ${r}_{1},\dots ,{r}_{n}$ $\left({r}_{i}={r}_{{A}_{i}{\sigma }_{i}{B}_{i}}\right)$ will be said to be final on $a\in k\left\{X\right\}$ if ${r}_{n}\cdots {r}_{1}\left(a\right)\in \left\{X{\right\}}_{\mathrm{irr}}$.

An element $a\in k\left\{X\right\}$ will be called reduction-finite if for every infinite sequence ${r}_{1},{r}_{2},\dots$ of reductions, ${r}_{i}$ acts trivially on ${r}_{i-1}\cdots {r}_{1}\left(a\right)$ for all sufficiently large $i$. If $a$ is reduction-finite, then any minimal sequence of reductions ${r}_{i}$, such that each ${r}_{i}$ acts nontrivially on ${r}_{i-1}\cdots {r}_{1}\left(a\right)$ will be finite, and hence a final sequence. It follows from their definition that the reduction-finite elements form a $k$-submodule of $k\left\{X\right\}$.

We shall call an element $a\in k\left\{X\right\}$ reduction-unique if it is reduction-finite, and if its image under all final sequences of reductions are the same. This common value will be denoted ${r}_{S}\left(a\right)$.

Lemma. (i) The set of reduction-unique elements of $k\left\{X\right\}$ forms a $k$-submodule, and ${r}_{S}$ is a $k$-linear map of this submodule into $k\left\{X{\right\}}_{\mathrm{irr}}$.

(ii) Suppose $a,b,c\in k\left\{X\right\}$ are such that for all monomials $A,B,C$ occurring with nonzero coefficient in $a,b,c$ respectively, the product $\mathrm{ABC}$ is reduction-unique. (In particular this implies that $\mathrm{abc}$ is reduction-unique.) Let $r$ be a finite composition of reductions. Then $\mathrm{ar}\left(b\right)c$ is reduction-unique, and ${r}_{S}\left(\mathrm{ar}\left(b\right)c\right)={r}_{S}\left(\mathrm{abc}\right)$.

Proof. (i) Say $a,b\in k\left\{X\right\}$ are reduction-unique, and $\alpha \in k$. We know $\alpha a+b$ is reduction-finite. Let $r$ be any composition of reductions final on this element. Since $a$ is reduction-unique, we can find a composition of reductions $r\prime$ such that $r\prime r\left(a\right)={r}_{S}\left(a\right)$, and similarly there is a composition of reductions $r″$ such that $r″r\prime r\left(b\right)={r}_{S}\left(b\right)$. As $r\left(\alpha a+b\right)$ is irreducible, we have

(1)$r\left(\alpha a+b\right)=r″r\prime r\left(\alpha a+b\right)=\alpha r″r\prime r\left(a\right)+r″r\prime r\left(b\right)=\alpha {r}_{S}\left(a\right)+{r}_{S}\left(b\right),$r(\alpha a + b) = r'' r' r(\alpha a + b) = \alpha r'' r' r(a) + r'' r' r(b) = \alpha r_S(a) + r_S(b),

from which our assertions follow.

(ii) By (i) and the way (ii) is formulated, it clearly suffices to prove (ii) in the case where $a,b,c$ are monomials $A,B,C,$ and $r$ is a single reduction ${r}_{D\sigma E}$. But in that case,

(2)${\mathrm{Ar}}_{D\sigma E}\left(B\right)C={r}_{\mathrm{AD}\sigma EC}\left(\mathrm{ABC}\right),$Ar_{D \sigma E}(B)C = r_{AD\sigma E C}(ABC),

which is the image of $\mathrm{ABC}$ under a reduction, hence is reduction-unique if $\mathrm{ABC}$ is, with the same reduced form. $\square$

Let us call a $5$-tuple $\left(\sigma ,\tau ,A,B,C\right)$ with $\sigma ,\tau \in S$ and $A,B,C\in \left\{X\right\}-\left\{1\right\},$ such that ${W}_{\sigma }=\mathrm{AB},$ ${W}_{\tau }=\mathrm{BC},$ an overlap ambiguity of $S$. We shall say the overlap ambiguity $\left(\sigma ,\tau ,A,B,C\right)$ is resolvable if there exist compositions of reductions, $r$ and $r\prime$, such that $r\left({f}_{\sigma }C\right)=r\prime \left({\mathrm{Af}}_{\tau }\right)$ (the confluence condition on the results of the two indicated ways of reducing $\mathrm{ABC}$).

Similarly, a 5-tuple $\left(\sigma ,\tau ,A,B,C\right)$ with $\sigma \ne \tau \in S$ and $A,B,C\in k\left\{X\right\}$ will be called an inclusion ambiguity if ${W}_{\sigma }=B,$ ${W}_{\tau }=\mathrm{ABC};$ and such an ambiguity will be called resolvable if ${\mathrm{Af}}_{\sigma }C$ and ${f}_{\tau }$ can be reduced to a common expression.

By a semigroup partial ordering on $k\left\{X\right\}$ we shall mean a partial order $″\le ″$ such that $B ($A,B,B\prime ,C\in \left\{X\right\}$), and it will be called compatible with $S$ if for all $\sigma \in S$, ${f}_{\sigma }$ is a linear combination of monomials $<{W}_{\sigma }$.

Let $I$ denote the two-sided ideal of $k\left\{X\right\}$ generated by the elements ${W}_{\sigma }-{f}_{\sigma }$ ($\sigma \mathrm{in}S$). As a $k$-module, $I$ is spanned by the products $A\left({W}_{\sigma }-{f}_{\sigma }\right)B$.

If $\le$ is a partial order on $k\left\{X\right\}$ compatible with the reduction system $S$, and $A$ is any element of $\left\{X\right\}$, let ${I}_{A}$ denote the submodule of $k\left\{X\right\}$ spanned by all elements $B\left({W}_{\sigma }-{f}_{\sigma }\right)C$ such that ${\mathrm{BW}}_{\sigma }C. We shall say that an ambiguity $\left(\sigma ,\tau ,A,B,C\right)$ is resolvable relative to $\le$ if ${f}_{\sigma }C-{\mathrm{Af}}_{\tau }\in {I}_{\mathrm{ABC}}$ (or for inclusion ambiguities, if ${\mathrm{Af}}_{\sigma }B-{f}_{\tau }\in {I}_{\mathrm{ABC}}$). Any resolvable ambiguity is resolvable relative to $\le$.

Theorem. Let $S$ be a reduction system for a free associative algebra $k\left\{X\right\}$ (a subset of $\left\{X\right\}×k\left\{X\right\}$), and $\le$ a semigroup ordering on $\left\{X\right\}$, compatible with $S$, and having descending chain condition. Then the following conditions are equivalent:

(a) All ambiguities of $S$ are resolvable.

(b) All ambiguities of $S$ are resolvable relative to $\le$.

(c) All elements of $k\left\{X\right\}$ are reduction-unique under $S$.

Corollary. Let $k\left\{X\right\}$ be a free associative algebra, and $″\le ″$ a semigroup partial ordering of $\left\{X\right\}$ with descending chain condition.

If $S$ is a reduction system on $k\left\{X\right\}$ compatible with $\le$ and having no ambiguities, then the set of $k$-algebra relations ${W}_{\sigma }={f}_{\sigma }$ ($\sigma \in S$) is independent.

More generally, if ${S}_{1}\subset {S}_{2}$ are reduction systems, such that ${S}_{1}$ is compatible with $\le$ and all its ambiguities are resolvable, and if ${S}_{2}$ contains some $\sigma$ such that ${W}_{\sigma }$ is irreducible with respect to ${S}_{1}$, then the inclusion of ideals associated with these systems, ${I}_{1}\subset {I}_{2}$, is strict.

Revised on February 6, 2013 06:50:53 by Todd Trimble? (67.81.93.26)