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

Let S be a set of pairs of the form σ=(W σ,f σ) where W σ{X} , f σk{X}.

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

We shall say that a reduction r AσB acts trivially on an element ak{X} if the coefficient of AW σ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 σB. The k-submodule of all irreducible elements of k{X} will be denoted k{X} irr. A finite sequence of reductions r 1,,r n (r i=r A iσ iB i) will be said to be final on ak{X} if r nr 1(a){X} irr.

An element ak{X} will be called reduction-finite if for every infinite sequence r 1,r 2, of reductions, r i acts trivially on r i1r 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 i1r 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 ak{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} irr.

(ii) Suppose a,b,ck{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,bk{X} are reduction-unique, and αk. We know α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 rr(a)=r S(a), and similarly there is a composition of reductions r such that rrr(b)=r S(b). As r(αa+b) is irreducible, we have

(1)r(αa+b)=rrr(αa+b)=αrrr(a)+rrr(b)=αr S(a)+r S(b),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σE. But in that case,

(2)Ar DσE(B)C=r ADσEC(ABC),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.

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

Similarly, a 5-tuple (σ,τ,A,B,C) with στS and A,B,Ck{X} will be called an inclusion ambiguity if W σ=B, W τ=ABC; and such an ambiguity will be called resolvable if Af σC and f τ can be reduced to a common expression.

By a semigroup partial ordering on k{X} we shall mean a partial order such that B<BABC<ABC (A,B,B,C{X}), and it will be called compatible with S if for all σS, f σ is a linear combination of monomials <W σ.

Let I denote the two-sided ideal of k{X} generated by the elements W σf σ (σinS). As a k-module, I is spanned by the products A(W σf σ)B.

If 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 σf σ)C such that BW σC<A. We shall say that an ambiguity (σ,τ,A,B,C) is resolvable relative to if f σCAf τI ABC (or for inclusion ambiguities, if Af σBf τI ABC). Any resolvable ambiguity is resolvable relative to .

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

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

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

If S is a reduction system on k{X} compatible with and having no ambiguities, then the set of k-algebra relations W σ=f σ (σS) is independent.

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

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