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,
- $\{X\}$ – free semigroup with $1$ on $X$
- $k\{X\}$ – semigroup algebra of $\{X\}$

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

For any $\sigma \in S$ and $A,B\in \{X\}$, let ${r}_{A\sigma B}$ denote the *$k$-module* endomorphism of $k\{X\}$ that fixes all elements of $\{X\}$ 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\{X\}\to k\{X\}$ **reductions**.

We shall say that a reduction ${r}_{A\sigma B}$ **acts trivially** on an element $a\in k\{X\}$ 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\{X\}$ will be denoted $k\{X{\}}_{\mathrm{irr}}$. A finite sequence of reductions ${r}_{1},\dots ,{r}_{n}$ $({r}_{i}={r}_{{A}_{i}{\sigma}_{i}{B}_{i}})$ will be said to be *final* on $a\in k\{X\}$ if ${r}_{n}\cdots {r}_{1}(a)\in \{X{\}}_{\mathrm{irr}}$.

An element $a\in k\{X\}$ 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}(a)$ 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}(a)$ will be finite, and hence a final sequence. It follows from their definition that the reduction-finite elements form a $k$-submodule of $k\{X\}$.

We shall call an element $a\in k\{X\}$ *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}(a)$.

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

(ii) Suppose $a,b,c\in k\{X\}$ 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}(b)c$ is reduction-unique, and ${r}_{S}(\mathrm{ar}(b)c)={r}_{S}(\mathrm{abc})$.

*Proof.* (i) Say $a,b\in k\{X\}$ 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(a)={r}_{S}(a)$, and similarly there is a composition of reductions $r\u2033$ such that $r\u2033r\prime r(b)={r}_{S}(b)$. As $r(\alpha a+b)$ is irreducible, we have

(1)$$r(\alpha a+b)=r\u2033r\prime r(\alpha a+b)=\alpha r\u2033r\prime r(a)+r\u2033r\prime 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}(B)C={r}_{\mathrm{AD}\sigma EC}(\mathrm{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 $(\sigma ,\tau ,A,B,C)$ with $\sigma ,\tau \in S$ and $A,B,C\in \{X\}-\{1\},$ such that ${W}_{\sigma}=\mathrm{AB},$ ${W}_{\tau}=\mathrm{BC},$ an **overlap ambiguity** of $S$. We shall say the overlap ambiguity $(\sigma ,\tau ,A,B,C)$ is **resolvable** if there exist compositions of reductions, $r$ and $r\prime $, such that $r({f}_{\sigma}C)=r\prime ({\mathrm{Af}}_{\tau})$ (the confluence condition on the results of the two indicated ways of reducing $\mathrm{ABC}$).

Similarly, a 5-tuple $(\sigma ,\tau ,A,B,C)$ with $\sigma \ne \tau \in S$ and $A,B,C\in k\{X\}$ 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\{X\}$ we shall mean a partial order $\u2033\le \u2033$ such that $B<B\prime \Rightarrow \mathrm{ABC}<\mathrm{AB}\prime C$ ($A,B,B\prime ,C\in \{X\}$), 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\{X\}$ generated by the elements ${W}_{\sigma}-{f}_{\sigma}$ ($\sigma \mathrm{in}S$). As a $k$-module, $I$ is spanned by the products $A({W}_{\sigma}-{f}_{\sigma})B$.

If $\le $ is a partial order on $k\{X\}$ compatible with the reduction system $S$, and $A$ is any element of $\{X\}$, let ${I}_{A}$ denote the submodule of $k\{X\}$ spanned by all elements $B({W}_{\sigma}-{f}_{\sigma})C$ such that ${\mathrm{BW}}_{\sigma}C<A$. We shall say that an ambiguity $(\sigma ,\tau ,A,B,C)$ 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\{X\}$ (a subset of $\{X\}\times k\{X\}$), and $\le $ a semigroup ordering on $\{X\}$, 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\{X\}$ are reduction-unique under $S$.

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

If $S$ is a reduction system on $k\{X\}$ 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)