Читать книгу Invariants And Pictures: Low-dimensional Topology And Combinatorial Group Theory - Vassily Olegovich Manturov - Страница 18

In the present section we briefly consider a well-known Newman lemma (also known as the Diamond lemma in the literature) [Newman, 1942]. This lemma is a very powerful tool for constructing a minimal form, proving uniqueness theorems and solving word and other problems.

Let A be a set and let → denote a binary relation on the set A.

Definition 1.10. A relation → is called well-founded (or Noetherian) if every non-empty subset X ⊂ A has a minimal element, that is, there exists a ∈ X such that the relation a → b does not hold for any b ∈ X.

Alternatively, one can say that a relation is well-founded if the set A does not contain any infinite decreasing chains in the sense of that relation.

For a relation → let us denote by its reflexive transitive closure.

Definition 1.11. A relation → is called locally confluent if for every three elements a, b, c ∈ A such that

there exists an element d ∈ A such that

This condition is sometimes formulated in the form “every covering is bounded below” in the system (A, →).

Definition 1.12. The relation → is called confluent if for every three elements a, b, c ∈ A such that

there exists an element d ∈ A such that

Lemma 1.5 (The Diamond lemma [Newman, 1942]). If a relation → is well-founded and locally confluent, then the relation → is confluent.

Proof. Let the relation → be well-founded and locally confluent and let a, b, c ∈ A be elements such that a b, a c. We need to prove the existence of an element d ∈ A such that b d, c d.

Let us call two elements y, z ∈ A joinable if there exists an element h ∈ A such that y h and z h. The proof is by the following induction made possible by the well-foundedness of the relation →. Let us say that the property P is satisfied for an element x ∈ A and write P(x) if any elements y, z ∈ A, such that x y and x z, are joinable. Obviously the statement of the lemma is equivalent to P(x) for all x ∈ A.

If we denote by →⁺ the transitive closure of the relation →, the induction is of the form “to show P(x) under the assumption P(t) for all t such that x →⁺ t”. This induction is valid because the relation → is well-founded.

Now let us consider an element x ∈ A and the divergence x y, x z. If x = y or x = z, y and z are joinable immediately. Otherwise, we have x → y₁ y, x → z₁ z. Due to local confluency of the relation →, there exists an element u such that y₁ u, z₁ u. By induction, there exists an element v such that y v, u v. Finally, by induction again, there exists an element w such that v w, z w. Therefore the elements y and z are joinable. This construction is depicted in Fig. 1.4.

This lemma essentially means that, if the conditions of well-foundedness and local confluency hold for a relation →, then every connected component of the graph of the relation → contains a unique minimal element a and for every element b of that connected component the relation b a holds.

Example 1.4. A simple, yet structurally very important example of the use of the diamond lemma is the identity problem and the conjugacy problem in the free group. Given a set of letters (alphabet) a₁, . . . , an, we consider all possible words in this alphabet. Two words w, w′ are in the relation w → w′ if w′ is obtained from w by contraction of two successive letters aa⁻¹ or a⁻¹ a. These transformations are called elementary contractions. The Noetherian property is evident.

Fig. 1.4Proof of the Diamond lemma

How one can check the diamond lemma in this case? Let w be a word which admits two elementary contractions w → w′ and w → w″. If the contracted letters don’t intersect, then we can contract them all in any order and get a word w′″ which is a descendant for w′ and w^″. If the letters intersect then we have a subword aa⁻¹a or a⁻¹aa⁻¹ in w which is contracted by two possible ways. In this case the words w′ and w′ coincide.

Analogously, the conjugacy problem in the free group can be solved. For a word w = w₁ . . . wk of length k, we consider words w_(j) = w_1+jw_2+j . . . w_k+j obtained from w by cyclic permutations 1 → 1 + j, . . . , k → k + j, where the sums are modulo k. It is clear that all these word are conjugate to w. The word w is called cyclically contractible if some of the words wj are contractible. We introduce the following relation on the cyclic words: w → w′ if there exist representatives w and w′ of the words w, w′ such that w → w′.

Evidently, two cyclic words w, w′ are conjugated if and only if there is a sequence of cyclic words w = w₀ → w₁. . . w_p = w′ such that for any successive words either w_j → w_j+1 or w_j+1 → w_j. Thus, the conjugacy is the equivalence generated by the elementary relation →.

For cyclic words of length ≥ 3 the conditions of the diamond lemma can be checked in the same manner as for ordinary words. The verification of the conditions for words of length 2 is obvious.

Remark 1.4. As we could see in the examples considered above, two word contractions a → b, b → c can be independent if the contracted letters of one contraction are not involved in the other, and dependent if the both contractions use common letters. In the first case the commutative diagram of the diamond lemma can be constructed in one step: the word d is obtained from the word c “in the same way” as the word b is obtained from the word a, meanwhile the word d is obtained from the word b “in the same way” as the word c is obtained from the word a. Thus, we have a → b → d and a → c → d.

Such cases of “independent contractions” are connected usually to the phenomenon of “far commutativity”.

As for the case of dependent contractions, in the simplest situation dependence of the contractions a → b and a → c implies b ≡ c where ≡ is the identity relation. In the general case application of the diamond lemma to dependent contractions is much more difficult.