COHERENCY, FREE INVERSE MONOIDS AND FREE LEFT AMPLE MONOIDS VICTORIA GOULD AND MIKLO´S HARTMANN 5 1 Abstract. AmonoidS isrightcoherentifeveryfinitelygeneratedsubactofeveryfinitely 0 presented right S-act is finitely presented. The corresponding notion for a ring R states 2 that every finitely generated submodule of every finitely presented right R-module is n finitely presented. For monoids (and rings) right coherency is a finitary property which a J determines the existence of a model companion of the class of right S-acts (right R- 2 modules) and hence that the class of existentially closed right S-acts (right R-modules) is axiomatisable. ] Choo, Lam and Luft have shown that free rings are right (and left) coherent; the A authors,togetherwith Ruˇskuc,haveshownthatgroups,andfree monoids,havethe same R properties. We demonstrate that free inverse monoids do not. . h Anyfreeinversemonoidcontainsasasubmonoidthefreeleftamplemonoid,andindeed t the free monoid, on the same set of generators. The main objective of the paper is to a m showthatthefreeleftamplemonoidisrightcoherent. Furthermore,bymakinguseofthe same techniques we show that both free inverse and free left ample monoids satisfy (R), [ (r),(L) and(l),conditions arisingfromthe axiomatisabilityofclassesofrightS-actsand 1 of left S-acts. v 4 0 4 1. Introduction 0 0 Let S be a monoid. A right S-act is a set A together with a map A × S → A where . 1 (a,s) 7→ as, such that for all a ∈ A and s,t ∈ S we have a1 = a and a(st) = (as)t. We 0 5 also have the dual notion of a left S-act: where handedness for S-acts is not specified in 1 this article we will always mean right S-acts. The study of S-acts is, effectively, that of : v representations of the monoid S by mappings of sets. i X Clearly S-acts over a monoid S are the non-additive analogue of R-modules over a (uni- r tal) ring R. Although the study of the two notionsdiverges considerably once technicalities a set in, one can often begin by forming analagous notions and asking analagous questions. In this article we study coherency for monoids. A monoid S is said to be right coherent if every finitely generated subact of every finitely presented right S-act is finitely pre- sented. Left coherency is defined dually; S is coherent if it is both left and right coherent. These notions are analogous to those for a ring R (where, of course, S-acts are replaced by R-modules). Coherency is a finitary condition for rings and monoids, much weaker Date: January 5, 2015. 2010 Mathematics Subject Classification. 20 M 05, 20 M 30. Key words and phrases. free monoids, S-acts, coherency. The authors acknowledge the support of EPSRC grant no. EP/I032312/1. Research also partially supported by the Hungarian Scientific Research Fund (OTKA) grant no. K83219. 1 than, for example, the condition that says all finitely generated R-modules or S-acts be finitely presented. As demonstrated by Eklof and Sabbagh [5], it is intimately related to the model theory of R-modules. The corresponding results for S-acts appear in [9], the latter informed by the more general approach of Wheeler [17]. Chase [1] gave internal conditions on a ring R such that R be right coherent. Corre- spondingly, a monoid S is right coherent if and only if for any finitely generated right congruence ρ on S, and for any a,b ∈ S, the right congruence r(aρ) = {(u,v) ∈ S ×S : auρav} isfinitelygenerated, andthesubact(aρ)S∩(bρ)S oftherightS-actS/ρisfinitelygenerated [11]. Choo, Lam and Luft [2, Corollary 2.2 and remarks] have shown that free rings are coherent. The first author proved that free commutative monoids are coherent [11] and recently theauthors, togetherwithRuˇskuc [12], haveshownthatfreemonoidsarecoherent. The class of coherent inverse monoids contains all semilattices of groups [11] and so, in particular, all groups and all semilattices. Certainly then free groups are coherent. It therefore becomes natural to ask whether free inverse monoids are coherent, since, not only are they free objects in a variety of unary algebras, they are constructed from free groups acting on semilattices. In fact, as we show at the end of this article, coherency fails for free inverse monoids. This negative result motivates us to ask whether free left ample monoids, which may be thought of as the ‘positive’ part of free inverse monoids, being constructed from free monoids rather than free groups, are coherent. We argue that free left ample monoids are right but not left coherent. The proof of right coherency is motivated by the methods in [12], it is, however, rather more delicate. For the convenience of the reader we describe in Section 2 the construction of the free inverse FIM(Ω), free left ample FLA(Ω) and free ample FAM(Ω) monoids on a set Ω from (prefix) closed subsets of the free group FG(Ω). In Section 3 we focus on showing that the finitary properties (R),(r),(L) and (l) (defined therein) hold for FIM(Ω) and FLA(Ω). These properties (which arise fromconsiderations of first order axiomatisability of the class of strongly flat right and left S-acts - see [10]) are similar in flavour, although easier to handle, than coherency. Our main work is in Section 4, where we make a detailed analysis of finitely generated right congruences on FLA(Ω). This hard work is then put to use in Section 5 where we show that FLA(Ω) is right coherent for any set Ω. In Section 6 we argue that the class of right coherent monoids is closed under retract. As a consequence of this, we have an alternative (albeit rather longer) proof that free monoids are coherent. Finally, in Section 7, we show that FIM(Ω), FLA(Ω) and FAM(Ω) are not coherent (for |Ω| ≥ 2). 2. Preliminaries ∗ Let Ω be a non-empty set, let Ω be the free monoid and let FG(Ω) be the free group on Ω, respectively. We follow standard practice and denote by l(a) the length of a reduced ∗ word a ∈ FG(Ω) and so, in particular, of a ∈ Ω . The empty word will be denoted by ǫ. ∗ ∗ Of course, Ω is a submonoid of the free group FG(Ω), and in the sequel, if a ∈ Ω , by 2 a−1 we mean the inverse of a in FG(Ω). For any a ∈ FG(Ω) we denote by a↓ the set of prefixes of the reduced word corresponding to a. Thus, if a is reduced and a = x ...x 1 n where x ∈ Ω∪Ω−1, then i a↓= {ǫ,x ,x x ,...,x x ...x }. 1 1 2 1 2 n The free inverse monoid on Ω is denoted by FIM(Ω). The structure of FIM(Ω) was determined by Munn [15] and Scheiblich [16]; the description we give below follows that of [16], of which further details may be found in [13]. However, we keep the equivalent characterisation via Munn trees constantly in mind. Let Pf(Ω) be the set of finite prefix closed subsets of FG(Ω). If A ∈ Pf(Ω), then - c c regarding elements of A as reduced words - a leaf a of A is a word such that a is not a proper prefix of any other word in A. Note that FG(Ω) acts in the obvious way on its semilattice of subsets under union. Using this action we define FIM(Ω) = {(A,a) : A ∈ Pf(Ω),a ∈ A}. c With binary operation given by (A,a)(B,b) = (A∪aB,ab), FIM(Ω) is the free inverse monoid generated by Ω. The identity is ({ǫ},ǫ), the inverse (A,a)−1 of (A,a) is (a−1A,a−1) and the natural injection of Ω → FIM(Ω) is given by x 7→ ({1,x},x). We will make use of the fact that the free inverse monoid (in fact, every inverse monoid) possesses a left-right duality, by virtue of the anti-isomorphism given by x 7→ x−1. For future purposes we remark that if a ∈ FG(X) is reduced, then a−1 ·a↓ = (a−1)↓. Throughout this article we denote elements of FIM(Ω) by boldface letters, elements of Pf(Ω) by capital letters, and elements of FG(Ω) by lowercase letters. We write a typical c element ofFIM(Ω)asa = (A,a); Aandawillalwaysdenotethefirstandsecondcoordinate of a, respectively. One exception to this convention is that we denote the identity ({ǫ},ǫ) of FIM(Ω) by 1. The free left ample monoid FLA(Ω) on Ω is the submonoid of FIM(Ω) given by ∗ FLA(Ω) = {(A,a) ∈ FIM(Ω) : A ⊆ Ω }, ∗ note that perforce, a ∈ Ω and we assume from the outset, when dealing with an element a = (A,a) ∈ FLA(Ω), that all the words in A are reduced. We remark that FLA(Ω) also possesses a unary operation of (A,a)+ = (A,ǫ) = (A,a)(A,a)−1 and (as a unary semigroup) is the free algebra on Ω in both the variety of left restriction semigroups and the quasi-varieties of (weakly) left ample semigroups [6, 8, 4]. Similarly, the free ample semigroup on Ω is the submonoid of FIM(Ω) given by ∗ FAM(Ω) = {(A,a) ∈ FIM(Ω) : a ∈ Ω }. 3 The free ample monoid possesses another unary operation defined by (A,a)∗ = (A,a)−1(A,a) = (a−1A,1) and (as a biunary semigroup) is the free algebra on Ω in both the variety of restriction semigroups and the quasi-varieties of (weakly) ample semigroups. We remark here that the set of identities and quasi-identities definining the class of ample monoids is left-right dual, so that FAM(Ω) consequently also has a left-right duality. ∗ Note that FLA(Ω) is built from Ω (see [7]),but to simplify notation we make use of the ∗ embedding of Ω into FG(Ω). However, when dealing with FLA(Ω), we will use inverses only when we know that the resulting element lies in Ω∗, for example we will write u−1v only if u is a prefix of v. Let S be a semigroup, let H ⊆ S × S and let us denote by ρ the right congruence generated by H. Then it is well known that s ρ t if and only if there exists a so-called H-sequence s = c t ,d t = c t ,...,d t = t 1 1 1 1 2 2 n n connecting s to t where (c ,d ) ∈ H ∪ H−1 for all 1 ≤ i ≤ n. If n = 0, we interpret this i i sequence as being s = t. 3. FIM(Ω),FAM(Ω) and FLA(Ω) satisfy (R), (r), (L) and (l). The conditions (R) and (r) (cid:0)(L) and (l)(cid:1) are connected to the axiomatisability of certain classes of right (left) acts, and were introduced in [10]. Connected via axiomatisability to coherency, they are somewhat easier to handle. In this section we show that the free inverse, the free ample and the free left ample monoids satisfy these conditions. In doing so we develop some facility for handling products and factorisations in these monoids. Definition 3.1. Let S be a monoid. We say that S satisfies Condition (r) if for every s,t ∈ S the right ideal rS(s,t) = {u ∈ S : su = tu} is finitely generated. The monoid S satisfies Condition (R) if for every s,t ∈ S the S-subact RS(s,t) = {(u,v) : su = tv} of the right S-act S ×S is finitely generated. (Note that we allow ∅ to be an ideal and an S-act.) The conditions (L) and (l) are defined dually. Lemma 3.2. Let A be a prefix closed subset of FG(Ω) and let g,h ∈ A. Then g((g−1h)↓) ⊆ A. Proof. Let x be the longest common prefix of the reduced words g,h ∈ FG(Ω). That is, ′ ′ ′ ′ g = xg and h = xh where g ,h do not have a common nonempty prefix. Then g((g−1h)↓) = xg′(g′−1h′)↓⊆ (xg′)↓ ∪(xh′)↓= g↓ ∪h↓⊆ A. (cid:3) 4 Lemma 3.3. Let S denote either FIM(Ω), FLA(Ω) or FAM(Ω), let au = bv in S and suppose that there exists a leaf x ∈ A ∪ aU = B ∪ bV such that x 6∈ A∪ B. Then there exist u′,v′,z ∈ S such that |A∪aU′| < |A∪aU|, ′ ′ ′ ′ au = bv and (u,v) = (u,v)z. Furthermore, if u = v then u′ = v′. Proof. Clearly u 6= 1. If S = FLA(Ω) then it is easy to see that x = ak where k ∈ Ω∗\{ǫ} is a leaf of U. The statement for S now follows from Lemma 4.3. We therefore consider the case where S = FIM(Ω) of S = FAM(Ω). We can suppose that the words x,a,b,u and v are reduced. Note that x 6∈ A∪B implies that x ∈ aU ∩bV. We have that x 6∈ A so in particular, x is not a prefix of a. In this case the last letter of x does not cancel in the product a−1x. Now if a−1x is not a leaf of U then there exists c ∈ Ω∪Ω−1, different from the last letter of x, such that a−1xc ∈ U. In this case xc ∈ A∪aU, contradicting that x is a leaf of A∪aU. So we have shown that a−1x is a leaf of U. Similarly b−1x is a leaf of V. There are two different cases to consider. Case (i): x 6= au. Let z = (au)−1x. Note that u,a−1x ∈ U, which is prefix closed, and z = (au)−1x = u−1 · a−1x. Lemma 3.2 then gives that u(z↓) ⊆ U. Since uz = a−1x, we have that (U,u) = (U \{a−1x},u)(z↓,1). Furthermore, z = (au)−1x = (bv)−1x, so similarly we have that (V,v) = (V \{b−1x},v)(z↓,1). Also, A∪a(U \{a−1x}) = B ∪b(V \{b−1x}) = (A∪aU)\{x}, so we have that (A,a)(U \{a−1x},u) = (B,b)(V \{b−1x},v). So if we let (U′,u′) = (U \{a−1x},u),(V′,v′) = (V \{b−1x},v) and z = (z↓,z), then (noticing that if (U,u) = (V,v) we must have that a = b), the statements of the lemma are satisfied. Case (ii): x = au = bv. Since x 6∈ A∪B, but a,b ∈ A∪B we have that u,v 6= ǫ. In case S = FAM(Ω), this implies that the last letters of x,u and v are the same which we denote by z ∈ Ω. Note that uz−1,vz−1 ∈ Ω∗ in this case. If S = FIM(Ω) then let z be the last letter of the reduced word x. If z is not the last letter of u then in the product x = au, all letters of u must cancel, so a = xu−1 where xu−1 is reduced. However, this contradicts the fact that x is a leaf, showing that the last letter of the reduced word u is z. Similarly the last letter of the reduced word v is z. In both the cases S = FAM(Ω) and S = FIM(Ω), u 6= uz−1 and u 6= ǫ imply that uz−1 ∈ U \{u}, and similarly vz−1 ∈ V \{v}. Now let u′ = (U \{u},uz−1),v′ = (V \{v},vz−1) and z = ({1,z},z). Then ′ ′ ′ ′ (U,u) = (U ,u)({1,z},z), (V,v) = (V ,v ),({1,z},z) 5 and ′ ′ ′ ′ ′ (A,a)(U ,u) = (cid:0)(A∪aU)\{au},au(cid:1) = (B,b)(V ,v ). Furthermore, if u = v then clearly u′ = v′, which finishes the proof. (cid:3) Proposition 3.4. The monoids FIM(Ω), FAM(Ω) and FLA(Ω) satisfy (R) and (r). Proof. Let S denote FIM(Ω), FAM(Ω) or FLA(Ω) and let a,b ∈ S. We claim that the finite set X = {(u,v) : au = bv, A∪aU = A∪B} generates R(a,b). Let (u,v) ∈ R(a,b). We prove by induction on the size of A ∪ aU that (u,v) ∈ X · S. Note that A ∪ aU = B ∪ bV implies A ∪ B ⊆ A ∪ aU, so that if |A∪aU| ≤ |A∪B|, then necessarily A ∪ aU = B ∪ bV = A ∪ B, which shows that (u,v) ∈ X. Supposenowthatwehavethatthereexistsann ≥ |A∪B|suchthatwhenever|A∪aU| ≤ n and (u,v) ∈ R(a,b), then necessarily (u,v) ∈ X ·S. Now let (u,v) ∈ R(a,b) be such that |A∪aU| = n+ 1. Since (u,v) ∈ R(a,b) we have that A∪B ⊆ A∪aU = B ∪bV, and since n+1 > |A∪B|, there exists x ∈ A∪aU = B ∪bV such that x 6∈ A∪B. This implies that x ∈ aU ∩bV. We can also assume that x is a leaf of A∪aU = B ∪bV. Then Lemma 3.3 implies that there exist elements u′,v′,z ∈ S such that |A∪aU′| < |A∪aU| and ′ ′ ′ ′ (u,v) ∈ R(a,b), (u,v) = (u,v)z. In this case the induction hypothesis implies that (u′,v′) ∈ X ·S, so that (u,v) ∈ X ·S as required. For (r), the proof is entirely similar. We show that the set Y = {u ∈ S : au = bu, A∪aU = A∪B} generates r(s,t), making particular use of the final statement of Lemma 3.3. (cid:3) The free inverse monoid and the free ample monoid are left-right dual, so from the dual of Lemma 3.3 they satisfy (L) and (l). To show that FLA(Ω) satisfies (L) and (l), we first prove a result corresponding to Lemma 3.3. Lemma 3.5. Let ua = vb in FLA(Ω) and suppose that there exists x ∈ U ∪uA = V ∪vB such that x is either a leaf, or x = ǫ and every element of (U ∪uA)\{ǫ} has a common nonempty prefix (this corresponds to a tree having a root with degree 1). Furthermore, suppose that x 6∈ uA ∪ vB. Then there exist u′,v′,z ∈ FLA(Ω) such that |U′ ∪u′A| < |U ∪uA|, ′ ′ ′ ′ ua = vb and (u,v) = z(u,v). Furthermore, if u = v then u′ = v′. Proof. Note that as x ∈/ uA∪vB, x 6= u and x 6= v. If x is a leaf, then let z = (x↓,1),U′ = ′ ′ ′ U \{x},u = u,V = V \{x},v = v. In this case ′ ′ ′ ′ ua = (cid:0)(U ∪uA)\{x},ua(cid:1) = (cid:0)(V ∪vB)\{x},vb(cid:1) = vb,zu = u,zv = v. 6 Furthermore, if u = v then of course u′ = v′. If x = ǫ then x 6∈ uA∪vB implies u,v 6= ǫ. Let z be the common first letter of elements of (U ∪uA)\{ǫ} and let z = ({ǫ,z},z). Then if we set (U′,u′) = (z−1(U \{ǫ}),z−1u) and (V′,v′) = (z−1(V \{ǫ},z−1v) then U′ ∪u′A = z−1(U \{ǫ})∪z−1uA = z−1(cid:0)(U ∪uA)\{ǫ}(cid:1) = ... = V′ ∪v′B, which shows that u′a = v′b. Also we have ′ Z ∪zU = {ǫ,z}∪(U \{ǫ}) = U, because z ∈ U (being the first letter of u). As a consequence zu′ = u and similarly zv′ = v also. Lastly, if u = v then clearly u′ = v′ which finishes the proof. (cid:3) Proposition 3.6. The free inverse monoid FIM(Ω), the free ample monoid FAM(Ω) and the free left ample monoid FLA(Ω) satisfy (L) and (l). Proof. We have already mentioned that FIM(Ω) and FAM(Ω) must satisfy (L) and (l). For FLA(Ω), let a,b ∈ FLA(Ω). Then either L(a,b) is empty or one of a and b is a suffix ∗ of the other. Without loss of generality we can assume that b = ya for some y ∈ Ω . In this case we claim that the finite set X = {(u,v) : ua = vb,U ∪uA = B ∪yA} generates L(a,b). Note that if (u,v) ∈ L(a,b) then necessarily u = vy so from the equation U ∪vyA = V ∪vB we conclude that v(B∪yA) ⊆ U ∪uA. As a consequence we see that if |U ∪uA| ≤ |B ∪yA| then U ∪ uA = v(B ∪ yA), which implies that v = ǫ so that U ∪uA = B ∪yA and (u,v) ∈ X. Suppose now that there exists an n ≥ |B ∪yA| such that whenever |U ∪uA| ≤ n and (u,v) ∈ L(a,b), then necessarily (u,v) ∈ FLA(Ω) ·X. Now let (u,v) ∈ L(a,b) be such that |U ∪uA| = n+1. Note that ua = vya implies that u = vy. Then U ∪vyA = V ∪vB, so v(B ∪ yA) ⊆ U ∪ vyA. However, |v(B ∪yA)| = |B ∪yA| < |U ∪vyA|, so U ∪ uA 6= v(B ∪yA) = uA∪vB. If there exists a leaf of U ∪ uA which is not contained in uA ∪ vB then let x be one such leaf. However, if there is no such leaf then that means that every leaf of U ∪uA is contained in v(B ∪yA). If v = ǫ then as y ∈ B, v(B ∪yA) is prefix closed so U ∪uA = v(B ∪yA) = uA∪vB, which is a contradiction. So v 6= ǫ, and we have that all leaves of U ∪ uA have v as a prefix. This can only happen if U ∪ uA = v↓ ∪vC for some prefix closed set C, which shows that every element of (U ∪uA) \ {ǫ} has the same first letter as v. In this case let x = ǫ. Then Lemma 3.5 implies that there exists u′,v′,z ∈ FLA(Ω) ′ ′ such that |U ∪uA| < |U ∪uA|, ′ ′ ′ ′ (u,v) ∈ L(a,b) and (u,v) = z(u,v). In this case the induction hypothesis implies that (u′,v′) ∈ FLA(Ω) · X and so we have (u,v) ∈ FLA(Ω)·X as required. For (l), the proof is entirely similar, namely the finite set Y = {U ∈ S : ua = ub,U ∪uA = B ∪yA} 7 generates l(a,b) if b = ya. (cid:3) 4. FLA(Ω): analysis of H-sequences In order to show that FLA(Ω) is right coherent, we make a careful examination of H- sequences for finite sets H ⊆ FLA(Ω)×FLA(Ω). Definition 4.1. Let a ∈ FLA(Ω). (i) The weight w(a) of a is defined by w(a) = |A|−1+l(a). (ii) The diameter d(a) of a is defined by d(a) = max {l(u) : u ∈ A}. The following lemma states the most important basic properties of the weight function. Lemma 4.2. Let a,b,c,a ,...,a ∈ FLA(Ω). Then 1 n (W0) w(a) = 0 if and only if a = 1; (W1) w(a),w(b) ≤ w(ab) ≤ w(a)+w(b); (W2) w(ab) = w(a) if and only if ab = a, and this is equivalent to b ∈ E(FLA(Ω)) with a ≤L b. Proof. The proof of (W0) is clear. For (W1), let a = (A,a) and b = (B,b), so that ab = (A∪aB,ab). Then w(ab) = |A∪aB|−1+l(ab) and as |A∪aB| ≥ |A|,|aB| where |aB| = |B| and l(ab) ≥ l(a),l(b), we have w(a),w(b) ≤ w(ab). On the other hand, the second inequality for (W1) follows from the observation that as a ∈ A∩aB we have |A∪aB| = |A|+|aB \A| ≤ |A|+|aB|−1 = |A|+|B|−1. Clearly |A ∪ aB| ≥ |A| and l(ab) ≥ l(a), so that if w(ab) = w(a), we must have |A∪aB| = |A| and l(b) = 0. Hence b = ǫ, aB ⊆ A and so ab = a. If ab = a (equivalently, w(ab) = w(a)), then we have shown that b ∈ E(FLA(Ω)) and clearly a ≤L b. The converse is clear. Thus (W2) holds. (cid:3) The proof of our main result depends heavily on the fact that certain factorisations can be carried through sequences. The following two lemmas constitute the foundations of this process. Lemma 4.3. Let dz = bv, z 6= 1 and let x be a leaf of Z such that dx 6∈ B. Then there exist elements z′,x,v′ ∈ FLA(Ω) such that ′ ′ ′ ′ ′ ′ Z = Z \{x},w(z) < w(z), z = zx, v = vx, dz = bv and (1) if x 6= z and dx 6∈ D then x = (x˜↓ ∪z˜↓,z˜),v′ = (V \{b−1dx},vz˜−1) where x˜,z˜∈ Ω∗ ′ ′ ′ ′ have no common non-empty prefix, x = z x˜,z = z z˜ (so dx = dz x˜ = bv x˜), 8 (2) if x = z (then necessarily x 6= ǫ) and dx 6∈ D then z′ = (Z′,zx′−1),x = ({ǫ,x′},x′) and v′ = (V \{v},vx′−1), where x′ is the last letter of x, (3) if x = z (then necessarily x 6= ǫ) and dx ∈ D then z′ = (Z′,zx′−1),x = ({ǫ,x′},x′) and v′ = (V,vx′−1), where x′ is the last letter of x, (4) if x 6= z and dx ∈ D then z′ = (Z′,z′),x = (x˜↓ ∪z˜↓,z˜),v′ = (V,vz˜−1) where ∗ x˜,z˜∈ Ω have no common non-empty prefix. Furthermore, the following are true: (A) in cases (1) and (2) we have |D ∪dZ′| < |D ∪dZ| and that if z = v then z′ = v′, (B) in cases (1),(2) and (3) we have w(bv′) = w(dz′) < w(dz) = w(bv). Proof. We investigate all 4 cases separately: ′ Case (i): dx 6∈ D and x 6= z. Let z be the greatest common prefix of z and x, that is, ′ ′ there exist z˜and x˜ such that z = z z˜and x = z x˜ and z˜and x˜ have no common non-empty prefix. It is important to note that x˜ 6= ǫ, for x is a leaf different from z. Now let ′ ′ z = (Z \{x},z ),x = (x˜↓ ∪z˜↓,z˜). Then it is easy to check that z′,x ∈ FLA(Ω) and z = z′x. Note that since dx 6∈ B, but ′ ′ dx ∈ B ∪ bV, we have that dx = dz x˜ ∈ bV, and that bv = dz = dz z˜ ∈ bV also. Since ′ z˜ and x˜ have no common non-empty prefix, we conclude that b is a prefix of dz . As a consequence of the fact that bv = dz′z˜, we conclude that z˜ is a suffix of v, so vz˜−1 ∈ V. Furthermore, bv = dz′z˜ implies that vz˜−1 = b−1dz′ 6= b−1dz′x˜ = b−1dx. Now let v′ = (V \{b−1dx},vz˜−1). Note that our assumption that dx 6∈ D implies that dx is a leaf of B ∪ bV. Then, since dx 6∈ B, we have that b−1dx is a leaf of V, so v′ ∈ FLA(Ω). It is then easy to check that v = v′x, since the second coordinates are the same, and b−1dx = b−1dz′x˜ = vz˜−1x˜. Similarly dz′ = bv′, for the second coordinates are bothequal dz′, and the first coordinates both equal (B ∪bV) \ {dx}. Also we have that w(bv′) < w(bv), because dx ∈ B ∪ bV. Furthermore, if z = v then from dz = bv we conclude that d = b which implies that b−1dx = x. Similarly vz˜−1 = b−1dz′ = z′, showing that z′ = v′. Case (ii): dx 6∈ D, and x = z. We have that z 6= ǫ, for otherwise z = 1. So let z = z′x′ ′ where x ∈ Ω, and let ′ ′ ′ ′ z = (Z \{z},z ), x = ({ǫ,x},x). We have that z′,x ∈ FLA(Ω), and that z = z′x. Note that dz 6∈ B, but it is the second coordinate of bv. Thus, v 6= ǫ, and we have that x′ is the last letter of v and as a consequence, dz′ = bv′, where v′ = v(x′)−1. We see that v is a leaf of V and similarly to the previous case it is easy to show that if we define ′ ′ v = (V \{v},v ), then v′ ∈ FLA(Ω),w(bv′) < w(bv),v = v′x and dz′ = bv′ = (cid:0)(D ∪ dZ) \ {dz},dz′(cid:1). Furthermore, if z = v then of course z = v and we conclude that z′ = v′, so the statements of the lemma are true. 9 Case (iii): dx ∈ D, and x = z. This case is similar to Case (ii), the only difference being that we have to define ′ ′ v = (V,v ). Since the second coordinate of bv′ is one letter shorter than bv, we have that w(bv′) < w(bv). Case (iv): dx ∈ D and x 6= z. Put z′ = (Z \{x},z′), x = (x˜↓ ∪z˜↓,z˜) and v′ = (V,vz˜−1) ′ where z ,z˜ and x˜ are defined as in Case (i). It is easy to check (using the same argument as in Case (i)) that b−1dx = vz˜−1x˜ is a leaf in V, z′,x,v′ ∈ FLA(Ω), w(z′) < w(z) and ′ ′ ′ ′ z = zx, v = vx and dz = bv, so that again, the statements of the lemma are true. (cid:3) Lemma 4.4. Let ab = cd such that b = (x↓ ∪b↓,b) for some b,x ∈ Ω∗,x 6= ǫ, having no common non-empty prefix. If ax 6∈ A∪C and A = (A∪aB)\{ax}, then d = d′b for some d′ = (D \{d′x},d′) such that a = cd′. Proof. First remark that our hypotheses guarantee that ax is a leaf of A∪aB = C ∪cD. Since ab = cd, c is a prefix of ab. However, since ax ∈ C∪cD, but ax 6∈ C, we have that c is also a prefix of ax. Since b and x have no common non-empty prefix, this implies that c is a prefix of a. ′ ∗ ′ ′ ′ Let d ∈ Ω be such that a = cd. We have that ax = cdx ∈ cD, so dx ∈ D. From ′ ′ ′ ′ cdb = ab = cd we deduce that db = d ∈ D. From db,dx ∈ D, the prefix closure ′ ′ ′ ′ of D gives that dB ⊆ D. Observe now that dx is a leaf of D and dx 6= d, so that d′ = (D \{d′x},d′) ∈ FLA(Ω) and clearly, cd′x 6∈ C ∪cD′. Moreover, it is easy to check that ′ ′ a = cd and d = db. (cid:3) Let ρ be a finitely generated right congruence on FLA(Ω). Without loss of generality we may suppose that ρ = hHi for some finite H ⊆ FLA(Ω)×FLA(Ω) with H−1 = H. Let us denote by D the maximum of the diameters of the components of the elements of H. In the following definition, we abuse terminology a little. The elements a,u,b and v play a special role, but are not distinguished from the products au and bv. We employ similar conventions in other circumstances. Definition 4.5. Suppose that we have an H-sequence au = c t ,d t = c t ,...,d t = bv 1 1 1 1 2 2 n n connecting au and bv. Then we say that theH-sequence is reducible if there exist elements y,u′,t′,...,t′ ,v′ such that 1 n (Red1) w(au′) < w(au), w(bv′) < w(bv) or w(t′) < w(t ) for some i; i i (Red2) u = u′y,t = t′y,...,t = t′ y,v = v′y; 1 1 n n 10