Širšov-Bergman diamond lemma in Bergman form
Suppose we are given the following data
Let be a set of pairs of the form where , .
For any and , let denote the -module endomorphism of that fixes all elements of other than , and that sends this basis element to . We shall call the given set a reduction system and the maps reductions.
We shall say that a reduction acts trivially on an element if the coefficient of in is zero, and we shall call irreducible (under ) if every reduction is trivial on , i.e. if involves none of the monomials . The -submodule of all irreducible elements of will be denoted . A finite sequence of reductions will be said to be final on if .
An element will be called reduction-finite if for every infinite sequence of reductions, acts trivially on for all sufficiently large . If is reduction-finite, then any minimal sequence of reductions , such that each acts nontrivially on will be finite, and hence a final sequence. It follows from their definition that the reduction-finite elements form a -submodule of .
We shall call an element 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 .
Lemma. (i) The set of reduction-unique elements of forms a -submodule, and is a -linear map of this submodule into .
(ii) Suppose are such that for all monomials occurring with nonzero coefficient in respectively, the product is reduction-unique. (In particular this implies that is reduction-unique.) Let be a finite composition of reductions. Then is reduction-unique, and .
Proof. (i) Say are reduction-unique, and . We know is reduction-finite. Let be any composition of reductions final on this element. Since is reduction-unique, we can find a composition of reductions such that , and similarly there is a composition of reductions such that . As is irreducible, we have
from which our assertions follow.
(ii) By (i) and the way (ii) is formulated, it clearly suffices to prove (ii) in the case where are monomials and is a single reduction . But in that case,
which is the image of under a reduction, hence is reduction-unique if is, with the same reduced form.
Let us call a -tuple with and such that an overlap ambiguity of . We shall say the overlap ambiguity is resolvable if there exist compositions of reductions, and , such that (the confluence condition on the results of the two indicated ways of reducing ).
Similarly, a 5-tuple with and will be called an inclusion ambiguity if and such an ambiguity will be called resolvable if and can be reduced to a common expression.
By a semigroup partial ordering on we shall mean a partial order such that (), and it will be called compatible with if for all , is a linear combination of monomials .
Let denote the two-sided ideal of generated by the elements (). As a -module, is spanned by the products .
If is a partial order on compatible with the reduction system , and is any element of , let denote the submodule of spanned by all elements such that . We shall say that an ambiguity is resolvable relative to if (or for inclusion ambiguities, if ). Any resolvable ambiguity is resolvable relative to .
Theorem. Let be a reduction system for a free associative algebra (a subset of ), and a semigroup ordering on , compatible with , and having descending chain condition. Then the following conditions are equivalent:
(a) All ambiguities of are resolvable.
(b) All ambiguities of are resolvable relative to .
(c) All elements of are reduction-unique under .
Corollary. Let be a free associative algebra, and a semigroup partial ordering of with descending chain condition.
If is a reduction system on compatible with and having no ambiguities, then the set of -algebra relations () is independent.
More generally, if are reduction systems, such that is compatible with and all its ambiguities are resolvable, and if contains some such that is irreducible with respect to , then the inclusion of ideals associated with these systems, , is strict.