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 $AW_\sigma B$, and that sends this basis element to $Af_\sigma B$. We shall call the given set $S$ a **reduction system** and the maps $r_{A\sigma B} : k\{X\} \rightarrow 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 $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 $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, \ldots , 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, \ldots$ 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 $ABC$ is reduction-unique. (In particular this implies that $abc$ is reduction-unique.) Let $r$ be a finite composition of reductions. Then $ar(b)c$ is reduction-unique, and $r_S(ar(b)c) = r_S(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'$ such that $r'r(a) = r_S(a)$, and similarly there is a composition of reductions $r''$ such that $r'' r' r(b) = r_S(b)$. As $r(\alpha a + b)$ is irreducible, we have

(1)$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)$Ar_{D \sigma E}(B)C = r_{AD\sigma E C}(ABC),$

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

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 = AB,$ $W_\tau = 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'$, such that $r(f_\sigma C) = r'(Af_\tau)$ (the confluence condition on the results of the two indicated ways of reducing $ABC$).

Similarly, a 5-tuple $(\sigma,\tau, A,B,C)$ with $\sigma \neq \tau \in S$ and $A,B,C \in k\{X\}$ will be called an **inclusion ambiguity** if $W_\sigma = B,$ $W_\tau = ABC;$ and such an ambiguity will be called resolvable if $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 $''\leq''$ such that $B \lt B' \Rightarrow ABC \lt AB'C$ ($A,B,B',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 $\lt W_\sigma$.

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

If $\leq$ 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 $BW_\sigma C\lt A$. We shall say that an ambiguity $(\sigma, \tau, A,B,C)$ is **resolvable relative to** $\leq$ if $f_\sigma C - Af_\tau \in I_{ABC}$ (or for inclusion ambiguities, if $Af_\sigma B - f_\tau \in I_{ABC}$). Any resolvable ambiguity is resolvable relative to $\leq$.

**Theorem.** Let $S$ be a reduction system for a free associative algebra $k\{X\}$ (a subset of $\{X\} \times
k\{X\}$), and $\leq$ 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 $\leq$.

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

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

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