Identities of Finite Semigroups and

Related Questions

by Olga B. Sapir

A DISSERTATION

Presented to the Faculty of

The Graduate College at the University of Nebraska In partial Fulfillment of Requirements For the Degree of Doctor of Philosophy

Major: Mathematics and Statistics

Under the Supervision of

Professor Stuart W. Margolis and Professor John C. Meakin

Lincoln, Nebraska

December, 1997

IDENTITIES OF FINITE SEMIGROUPS

AND RELATED QUESTIONS

Olga B. Sapir, Ph.D University of Nebraska, 1997

Advisors: Stuart W. Margolis and John C. Meakin

The theory of semigroup varieties is one of the most important parts of the theory of semigroups. Many important results in this theory have been obtained in the last 15 - 20 years. This theory is well represented in the recent books on the theory of semigroups by Almeida and Pin.

Two of the most important classes of semigroup varieties are the class of finitely based varieties (that is varieties given by finitely many identities) and the class of finitely generated varieties (that is varieties generated by finite semigroups). There are two main questions concerning these classes:

• When does a finite semigroup generate a finitely based variety?

• When is a finitely based variety finitely generated?

Both of these questions go back to the original work by Oates, Powell, Tarski and others on varieties of groups and universal algebras in general. In this thesis, we study both of these questions.

We give an algorithmic description of varieties of commutative semigroups generated by finite semigroups. As an application of our method, we describe all axiomatic and basis ladders of commutative semigroup varieties, answering a question by Jonsson, McNulty and Quackenbush. We also prove that the variety of idempotent semigroups is a minimal example of an inherently non-finitely generated variety of semigroups. This is the first example of this kind. We prove several results about the finite basis property of finite semigroups. With every finite language W we associate a finite monoid S(W) which is the syntactic monoid of the completion of W under taking subwords. We prove that the set of finite finitely based (infinitely based) monoids of the form S(W) is not closed either under direct products or under taking homomorphisms, or under taking subsemigroups. We also construct the first example of an infinite chain of finitely generated semigroup varieties where finitely based and infinitely based varieties alternate. Finally we give a complete description of all words w in a two-letter alphabet such that S({w}) is finitely based.

Acknowledgements

I would like to express deep gratitude to my advisors, Professor Stuart W. Margolis and Professor John C. Meakin for their valuable advice and encouragement. I am grateful to the members of my supervisory committee, Professors Jean-Camille Birget, Jamie Radcliffe and Roger Wiegand. My special thanks to Professor Mark Sapir (who also happens to be my husband) for all of his support.

Contents

1 Introduction 1 1.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Survey . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3 Outline of the results . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2 Commutative Semigroups 15 2.1 Finite Commutative Semigroups . . . . . . . . . . . . . . . . . . . . . 15 2.2 Axiomatic and Basis Chains for Varieties of Commutative Semigroups 24

3 Idempotent Semigroups 34

4 The Finite Basis Problem 43 4.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 4.2 Main Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

Chapter 1

Introduction

1.1 Preliminaries

For general background on semigroups and varieties we refer the reader to [4] and [18].

A semigroup is a universal algebra with one binary associative operation.

A monoid is a semigroup with an identity element 1 (such that 1 ∗ a = a ∗ 1 = a for every element a of the semigroup).

Homomorphisms, direct products of semigroups and subsemigroups are defined in the usual universal algebraic way.

A monogenic (cyclic) monoid is a monoid generated by one element. It is known [4] that a monogenic monoid is isomorphic to either the additive semigroup of nonnegative integers or to a finite monoid with a single defining relation of the form x^{m} = x^{m+k} where m, k ≥ 1. The latter monoid will be denoted by C_{m,k}.

The free monoid (resp. semigroup) generated by a set X consists of all (nonempty) words over X with operation concatenation. It is denoted X^{∗} (resp. X^{+}). A language is any subset of a free monoid.

An element e of a semigroup is called idempotent if e = e^{2}. The identity element and the zero element (if they exist) are examples of idempotents.

An ideal of a semigroup S is a subset I such that xs, sx ∈ I for every x ∈ I and s ∈ S.

If I is an ideal of a semigroup S then the Rees factor semigroup S/I consists of all elements S\I and 0. The operation in S/I is defined as follows: for every two elements x, y ∈ S\I if xy ∉ I then the product of x and y in S/I coincides with their product in S; all other products are equal to 0.

An identity is a pair of words u, v denoted by u = v. An identity u = v is said to be true in a semigroup S if for every substitution of elements from S for letters in u and v the products corresponding to u and v (that is the corresponding values of u and v) are equal in S. The pair of identities uz = u, zu = u means that all values of the word u are equal to 0. We shall replace this pair by u = 0 and call this also an identity (although formally speaking it is not an identity).

A substitution is any homomorphism of a free semigroup X^{+} into itself. Any such homomorphism is defined by a map from the set X into X^{+}. If u is a word in X^{+} and ϕ is a substitution then ϕ(u) is called the value of the word u under this substitution.

To deduce an identity u = v from a set of identities Σ means to present a sequence of words u = w_{1}, w_{2}, ..., w_{n} = v such that the transition from w_{i} to w_{i+1} (i = 1, ..., n − 1) is obtained by replacing a subword of w_{i} which is a value of one of the sides of one of the identities from Σ by the corresponding value of the other side of this identity: w_{i} = p_{i}ϕ(U)q_{i}, w_{i+1} = p_{i}ϕ(V)q_{i} for some (possibly empty) words p_{i}, q_{i}, a substitution ϕ and an identity U = V ∈ Σ.

A variety is a class of semigroups defined by identities. The variety of commutative semigroups is defined by the identity xy = yx. The variety of nilpotent semigroups of class k is defined by the identity x_{1}x_{2}...x_{k} = 0. The variety of idempotent semigroups is defined by the identity x = x^{2}.

A variety V is called finitely based if it can be defined by a finite set of identities Σ. In this case we shall write V = varΣ.

We say that a class of semigroups C generates a variety V if V is the smallest variety containing C. In this case we shall write V = varC. By Birkhoff’s theorem, V = varC if and only if every semigroup in V is a homomorphic image of a subsemigroup of a direct product of members from C.

A variety is called finitely generated if it is generated by a finite semigroup. A variety of groups V is said to be a just-non-Cross variety if every subvariety

of V is generated by a finite group.

A variety is called locally finite if every finitely generated semigroup in this variety is finite. Every periodic variety of commutative semigroups is locally finite [23]. A description (modulo groups) of all locally finite varieties of semigroups is obtained by M. Sapir in [20].

The union of two varieties is the smallest variety containing them. The operation of union and intersection define the structure of a lattice on the set of varieties. The union of two varieties generated by semigroups S and T respectively, is equal to the variety generated by the direct product S × T.

1.2 Survey

The theory of semigroup varieties as a part of the general theory of varieties of universal algebras has its origin in classical work by G. Birkhoff [3]. The first papers dealing systematically with semigroup varieties appeared in the 50s. These were papers by Green and Rees [7] Malcev [11] and others. During the last twenty years this became one of the central directions of the theory of semigroups. There are two big survey articles devoted to varieties of semigroups, one by Shevrin and Volkov [24] and one by Shevrin and Sukhanov [23].

Two classes of varieties attract the most attention. These are the class of finitely based varieties (i.e. varieties defined by finitely many identities) and the class of finitely generated varieties (i.e. varieties generated by finite semigroups). There are two major questions concerning these classes:

• When does a finite semigroup generate a finitely based variety?

• When is a finitely based variety finitely generated?

Both these questions go back to the original work by Oates, Powell, Tarski and others on varieties of groups and universal algebras in general. In particular the algorithmic version of the first question is the specification of the famous Tarski problem in the case of semigroups.

The celebrated theorem of Oates and Powell says that every finite group is finitely based. Thus the first question has an “easy” solution in the class of groups. In the case of semigroups the situation is much harder. In 1969, Perkins [16] constructed first two examples of non-finitely based finite semigroups. One of these examples was the 6-element semigroup B_{2}^{1} consisting of the four 2 × 2-matrix units, the identity matrix and the zero matrix. The second semigroup was the syntactic monoid of the language consisting of all subwords of the following words: {abcba, acbab, abab, aac}. This semigroup contains 25 elements. In [13] McNulty constructed an increasing infinite chain of infinitely based finitely generated semigroup varieties. M. Sapir [24], [21] showed that there exists a finite semigroup which does not even have an independent basis of identities (that is a basis where none of the identities follows from the other identities). He also showed that the set of finitely based (resp. infinitely based) finitely generated semigroup varieties is not closed under taking covers and unions. Therefore the direct product of two finitely based (resp. infinitely based) finite semigroups can be infinitely based (resp. finitely based). This answered questions by Gratzer. Other examples of pairs of finitely based finite semigroups whose direct product is not finitely based were constructed by Volkov [24]. All these examples involve finite groups in a very significant way. So M. Sapir asked if there are aperiodic examples (i.e. examples with no non-trivial subgroups.

There are several important classes of semigroups (other than the class of all groups) where one can describe all finitely based finite semigroups. The first of this is the class of all commutative semigroups: Perkins [16] showed that every variety of commutative semigroups is finitely based (this is a simple consequence of the Hilbert basis theorem). The second is the class of orthodox completely regular semigroups: a non-trivial result of Rasin [19] proved that every finite semigroup in this class is finitely based. Another class is the class of all inverse semigroups: from results of M. Sapir [20] and Volkov [25], it follows that a finite inverse semigroup is finitely based (as a semigroup) if and only if B_{2}^{1} is not a homomorphic image of a subsemigroup of this semigroup.

Nevertheless the problem of describing all finite finitely based semigroups is still open. This problem became even more interesting after the recent paper by McKenzie [12] where McKenzie proved that the set of finitely based finite universal algebras is not recursive. This solved the original Tarski problem. Although the class of finite finitely based semigroups has some “bad” properties (mentioned above), the situation in the class of semigroups is certainly better than in the class of general universal algebras. For example, McKenzie [12] proved that the set of inherently non-finitely based finite algebras is not recursive. But the set of inherently nonfinitely based finite semigroups is recursive (Sapir, [20]). Recall that a finite algebra is called inherently non-finitely based if it does not belong to any finitely based locally finite variety.

The second of the two questions mentioned above was originally formulated by M. Sapir. Using results by Oates and Powell [14] and Olshanskii [15] one can describe finitely based finitely generated varieties of solvable groups. These are precisely the varieties which do not contain the just-non-Cross varieties of solvable groups described in [15]. The reason why the second question has a nice solution in the class of groups is the following: every subvariety of a finitely generated (in other words Cross) variety is finitely generated [14]. Therefore every just-non-Cross variety of groups is inherently non-finitely generated, that is it cannot be contained in any finitely generated variety of groups.

The situation in the case of semigroups is more complicated. A subvariety of a finitely generated variety need not be finitely generated. The possibly simplest example is the following. Let V be the variety generated by the monogenic monoid C_{2,1} =< a | a^{2} = a^{3} >. It is easy to see that it is given by the following identities: {x^{2} = x^{3}, xy = yx}. The subvariety V′ of this variety given by identities {x^{2} = 0, xy = yx} cannot be finitely generated because every finite nil-semigroup is nilpotent [4] and the variety V′ is not nilpotent (one cannot deduce any identity of the form x_{1}...x_{n} = 0 from the identities of V′). Thus even in the case of varieties of commutative semigroups the description of finitely generated varieties cannot be trivial. It is known that although the lattice of varieties of commutative semigroups is countable and every variety of commutative semigroups is finitely based [16], this lattice is very complicated: for example, it contains a copy of every finite lattice [10].

A partial result for commutative varieties was obtained by Aizenstat [1]. She described all varieties of commutative semigroups with finite lattice of subvarieties: a variety of commutative semigroups contains finitely many subvarieties if and only if its basis of identities contains an identity of the form x_{1}...x_{n} = u where u is not a permutation of the word x_{1}...x_{n}. It is well known and easy to prove that every locally finite variety with finitely many subvarieties is finitely generated. As the above example of the variety V shows, the converse is not true for varieties of commutative semigroups: the variety V from the previous paragraph contains infinitely many subvarieties (otherwise V_{1} would be finitely generated).

If V is a variety, then the free semigroup in V with the set of free generators X is by definition a semigroup F from V generated by the set X such that every map from X to a semigroup S in V can be extended to a (unique) homomorphism from F to S. Elements of F are called V-words. For example the free commutative semigroup with the set of generators X consists of all products x_{1}^{n_{1}}x_{2}^{n_{2}}...x_{m}^{n_{m}} where x_{i} ∈ X and n_{i} are natural numbers. Two words in X define the same commutative word if they are permutations of each other.

1.3 Outline of the results

This thesis consists of three chapters. The first chapter is devoted to commutative semigroups. The following Theorem answers the second question (which finitely based varieties are finitely generated?) in the case of commutative semigroups. We say that a set of identities Σ contains an identity u = v modulo commutativity if Σ contains an identity u′ = v′ and u is a permutation of u′, v is a permutation of v′. For simplicity we shall consider only symmetric sets of identities Σ: if u = v ∈ Σ then v = u ∈ Σ.

Theorem 1.1 A variety of commutative semigroups V given by a finite set of identities Σ is generated by a finite semigroup if and only if one of the following conditions holds.

(A) Modulo commutativity, Σ contains an identity of the form x_{1}x_{2}...x_{n} = u for some natural number n and a word u which is not a permutation of x_{1}x_{2}...x_{n}.

(B) Modulo commutativity, Σ contains the following identity (for some natural

numbers k, m, h):

x_{1}^{m}x_{2}...x_{h} = x_{1}^{m+k}x_{2}...x_{h}

and varΣ contains the cyclic monoid C_{m,1}.

This theorem implies the following surprising corollary.

Corollary 1.1 The finitely generated varieties of commutative semigroups form a sublattice of the lattice of varieties of commutative semigroups.

As another corollary of this result, we can deduce that all finitely generated varieties of semigroups do not form a lattice: moreover the intersection of a finitely generated variety of semigroups and a finitely generated commutative variety may not be finitely generated.

Using methods developed in proving Theorem 1.1, we study axiomatic and basis ladders of commutative varieties. With every variety V of universal algebras one can associate two chains of varieties. In the basis chain,

V_{1} ⊆ V_{2} ⊆ ...,

each variety V_{n} is generated by all ≤ n-generated algebras in V, n = 1, 2...,. In the axiomatic chain

V^{1} ⊇ V^{2} ⊇ ...

each variety V^{n} is given by all identities in ≤ n variables satisfied by V. It is easy to see that a locally finite variety V is finitely generated if and only if V = V_{n} for some n, and a variety is finitely based if and only if V = V^{n} for some n.

Some of the members of the basis (axiomatic) chain of a variety V may coincide. Since if two members coincide then all varieties between them also coincide, each variety V induces two partitions of the set of natural numbers into intervals. These partitions will be called the basis ladder and the axiomatic ladder. Two numbers m, n belong to one class of the basic (axiomatic) ladder of V if V_{m} = V_{n} (resp. V^{m} = V^{n}). Jonsson, McNulty and Quackenbush [8] proved that every ladder where 1, 2, 3 belong to different classes is an axiomatic ladder of some semigroup variety. Petrov [17] showed that every ladder where 1 and 2 belong to different classes is the basis ladder of some semigroup variety. If V_{1} = V_{2} then a variety V is commutative. So in order to complete Petrov’s description of basis ladders it remained to describe all basis ladders of commutative semigroups.

The next two theorems describe all basis and axiomatic ladders of commutative semigroup varieties.

Theorem 1.2 A ladder is a basis ladder of a commutative variety of semigroups if and only if it contains only finitely many non-singleton intervals.

Theorem 1.3 A ladder is an axiomatic ladder of a commutative variety of semigroups if and only if it contains only finitely many intervals.

From Theorem 1.2 and the result by Petrov we can deduce.

Corollary 1.2 A ladder is the basis ladder of a variety of semigroups if and only if either 1 and 2 belong to different classes or this ladder contains only finitely many non-singleton intervals.

From Theorem 1.3, one can deduce a description of axiomatic ladders of all finitely based semigroup varieties.

Corollary 1.3 A ladder is the axiomatic ladder of a finitely based variety of semigroups if and only if it contains finitely many classes.

The “only if” part in this corollary follows from the fact that a variety is finitely based. The “if” part follows from Theorem 1.3.

In the second chapter we prove that the variety of all idempotent semigroups is inherently non-finitely generated. This means that it cannot be inside any finitely generated variety. The variety of all idempotent semigroups is very well studied. Several authors, Fennemore [5], Gerhard [6] and Birjukov [2] independently described the lattice of subvarieties of idempotent semigroups. By a theorem of Green and Rees [7], this variety is locally finite. The description of its lattice of subvarieties implies that every proper subvariety of this variety contains only finitely many subvarieties. Thus every proper subvariety of the variety of idempotent semigroups is finitely generated. This implies the following

Theorem 1.4 The variety of all idempotent semigroups is a minimal example of an inherently non-finitely generated variety.

Notice that this is the only known non-group example of this kind. Minimal inherently non-finitely generated varieties of groups are just-non-Cross varieties (as we mentioned above).

In the last chapter of the thesis we study finitely based syntactic monoids of finite complete languages^{1}. These monoids are Rees quotients of the finitely generated free monoids. From the semigroup theory point of view these semigroups are very simple: they are nilpotent semigroups with identity element adjoined. These monoids appear frequently in the theory of semigroups (these are all finite monoids with defining relations of the form u = 0 where u is a word). Another reason for this choice was that the identities of any particular monoid in this class are easy to describe (see Lemma 4.1 below). Recall that the first example of an infinitely based syntactic monoid of a finite language was constructed by Perkins [16] (see the 25-element example above).

1Subsequent to obtaining results in this chapter the author received a preprint of Marcel Jackson “Notes on the finite basis problem for finite Rees quotients of free monoids” where he proved independently some of these results.

In general, the syntactic monoids we are dealing with are constructed as follows. Let A be an alphabet. Let W be a finite set of words in the free monoid A^{∗}. Let W^{c} mean the closure of W under taking subwords. Then I = A^{∗}\W^{c} is an ideal of A^{∗}. Then S(W) = A^{∗}/I is the syntactic monoid of the set W^{c}. Let S be the class of all syntactic monoids of finite complete (i.e. closed under taking subwords) languages.

M. Sapir asked a question [24] of whether the set of finitely based monoids in S is recursive.

In Chapter 4, we show that the subclass of finitely based monoids in S is very complicated. In particular, we show that there exists an infinite increasing chain of varieties each generated by a monoid from S where finitely based and infinitely based varieties alternate. We also show (Theorem 4.5) that there exist two finite infinitely (finitely) based semigroups S(U) and S(V) such that S(U) × S(V) is finitely (nonfinitely) based. These are the first examples of pairs of aperiodic semigroups with these properties.

On the other hand we describe all words U in a two-letter alphabet such that S({U}) is finitely based. The set of such monoids turned out to be recursive. The description is contained in the following Theorem. Theorem 1.5 Let U be a word in {a, b}^{∗}. Then S({U}) is finitely based if and only if for some m, n ≥ 0 U is equal to one of the following words: a^{m}b^{n}, b^{m}a^{n}, a^{m}ba^{n}, b^{m}ab^{n}.

We also found some necessary and some sufficient conditions for a finite semigroup S(W) to be finitely based (see Theorems 4.1, 4.2, 4.32). Notice that the first such condition can be found in [16]. But we still do not know if the set of all finitely based semigroups of the form S(W) is recursive even if the alphabet consists of two letters.

Commutative Semigroups

2.1 Finite Commutative Semigroups

In this Section, we shall prove the following theorem.

Theorem 2.1 A variety of commutative semigroups V given by a finite set of identities Σ is generated by a finite semigroup if and only if one of the following conditions holds.

(A) Modulo commutativity, Σ contains an identity of the form x_{1}x_{2}...x_{n} = u for some natural number n and a word u which is not a permutation of x_{1}x_{2}...x_{n}.

(B) Modulo commutativity, Σ contains the following identity (for some natural

numbers k, m, h):

x_{1}^{m}x_{2}...x_{h} = x_{1}^{m+k}x_{2}...x_{h}  (2.1)

and varΣ contains the cyclic monoid C_{m,1}.

Recall that an identity is called regular if its left and right sides contain the same letters, otherwise the identity is called irregular.

We say that an identity u′ = v′ is obtained from u = v by equalizing pairs of letters if we obtain u′ = v′ from u = v by a sequence of substitutions each of which makes two letters equal and is identical on the other letters. For any word u, the set of letters of u is denoted by c(u). If α is an identity u = v then c(α) = c(u) ∪ c(v).

Lemma 2.1 A locally finite variety V is generated by a finite semigroup if and only if there exists a natural number p such that for any identity α which is false in V one can apply a sequence of equalizing pairs of letters and get an identity α′ of ≤ p variables which is also false in V.

Proof. If V is generated by a finite semigroup S then one can take p equal to the order of this semigroup. Indeed if there exists a homomorphism from a free semigroup generated by c(α) to S which disproves α then this endomorphism must equalize enough pairs of letters in c(α) so that the number of different images of letters from c(α) does not exceed p = |S|. We can get the same result by first equalizing these pairs of letters in α and then mapping the content of a new identity α′ to S. This α′ is also false on S and has ≤ p letters.

Now suppose that there exists a number p as in the formulation of the lemma. Then the basis rank of V does not exceed p. Since V is locally finite, it is finitely generated. The lemma is proved.

We shall also need the following three lemmas. Notice that two words in the free commutative semigroup are equal if and only if they are permutations of each other. We shall call elements of the free commutative semigroup commutative words. The following lemma is obvious.

Lemma 2.2 Let V = varΣ. Suppose that u = v is an identity in V. Then there exists a sequence of commutative words u = w_{1}, w_{2}, ..., w_{n} = v such that the transition from w_{i} to w_{i+1} (i = 1, ..., n − 1) is obtained by replacing a (commutative) subword of w_{i} which is a value of one of the sides of one of the identities from Σ by the corresponding value of the other side of this identity: w_{i} = p_{i}ϕ(U)q_{i}, w_{i+1} = p_{i}ϕ(V)q_{i} for some (possibly empty) words p_{i}, q_{i}, a substitution ϕ and an identity U = V ∈ Σ.

Lemma 2.3 Let V = varΣ be a variety of commutative semigroups. Then V satisfies an identity of the form x_{1}...x_{n} = u where u is not a permutation of x_{1}...x_{n} if and only if Σ contains such an identity.

Proof. The “if” part is obvious. In order to prove the “only if” part, recall that if an identity u′ = u is true in the variety varΣ and not true in the variety of all commutative semigroups, then u′ = u can be deduced from the identities in Σ. In particular, there should exist an identity U = V ∈ Σ, a substitution ϕ and a pair of commutative words p, q such that x_{1}x_{2}...x_{n} = pϕ(U)q in the free commutative semigroup and ϕ(U) ≠ ϕ(V) in the free commutative semigroup. This immediately implies that U must have the form x_{1}...x_{s} (for some s ≤ n) and that V is not a permutation of U. The lemma is proved.

Lemma 2.4 Suppose that a variety of commutative semigroups V = varΣ does not satisfy condition (A) of Theorem 2.1 but is finitely generated, satisfies the equation (2.1) and contains the monogenic monoid C_{m,1}. Then it satisfies condition (B) of Theorem 2.1

Proof. Suppose first that Σ contains an irregular identity. Then it is well known (see [23]) that V consists of ideal extensions of groups by nil-semigroups. Since V is finitely generated it is generated by an ideal extension S of a finite group by a finite nil-semigroup. Every finite nil-semigroup is nilpotent. Therefore S satisfies an identity x_{1}...x_{n} = (x_{1}...x_{n})^{m} for some n, m > 1. By Lemma 2.2 Σ must contain an identity of the form x_{1}...x_{n} = u where u is not a permutation of x_{1}...x_{n}. This contradicts the assumption that Σ does not satisfy condition (A).

Now suppose that all identities in Σ are regular. Since Σ satisfies the identity (2.1), there exists an identity U = V in Σ, a substitution ϕ and a pair of commutative words p, q such that x_{1}^{m}x_{1}...x_{n} = pϕ(U)q in the free commutative semigroup and ϕ(U) ≠ ϕ(V) in the free commutative semigroup.

Therefore modulo commutativity, U has the form

x_{1}^{α_{1}}x_{2}^{α_{2}}...x_{s}^{α_{s}}x_{s+1}...x_{t}

and V has the form

x_{1}^{β_{1}}x_{2}^{β_{2}}...x_{s}^{β_{s}}x_{s+1}^{γ_{1}}...x_{s+t}^{γ_{t}}

where α_{1} + ... + α_{s} ≤ m, α_{i} ≥ 1, and either γ_{i} > 1 for some i or α_{i} ≠ β_{i} for some i.

Suppose first that γ_{i} > 1. Since U = V must be true on C_{m,1} we can substitute 1 for all letters in U = V except x_{s+i} and deduce that C_{m,1} satisfies the equation x_{s+i} = x_{s+i}^{γ_{i}}. This immediately implies that m = 1 and Σ satisfies condition (A).

Suppose now that all α_{i} ≠ β_{i}. We can substitute the identity element of C_{m,1} for all letters in U = V except x_{i}. This will give us an identity x_{i}^{α_{i}} = x_{i}^{β_{i}}. This identity cannot hold in C_{m,1}. Thus α_{i} = m. But then s = 1 (because the sum of α’s is m and each of these numbers is greater than 0). Similarly we can prove that β_{i} > m. Since we already know that γ_{j} = 1 for all j, we can deduce that U = V has the following form (modulo commutativity and renaming letters):

x_{1}^{m}x_{2}...x_{t+1} = x_{1}^{m+r}x_{2}...x_{t+1}

for some m, r, t. Therefore Σ satisfies condition (B). The lemma is proved.

Proof of Theorem 2.1. The fact that condition (A) implies that V is finitely generated follows from the results of [1]. Indeed, in this paper, Aizenshtat proved that varieties of commutative semigroups satisfying condition (A) are exactly the varieties which contain finitely many subvarieties. Every variety with finitely many subvarieties is generated by its free semigroup of some finite rank. So a locally finite variety with this property is finitely generated.

Let us prove that varieties satisfying condition (B) are also finitely generated. Take any identity ϕ which is false in varΣ. First let us suppose that this identity is irregular. Then as in the proof of Lemma 2.4 we can prove that V consists of ideal extensions of groups by nil-semigroups. In particular every semigroup in V contains only one idempotent. Since C_{m,1} contains two idempotents (the zero and the identity element), it cannot belong to V, a contradiction.

Now suppose that ϕ is regular. Without loss of generality we can assume that ϕ has more than n variables. Every identity in Σ can be transformed with the help of the identity xy = yx to the following form:

\begin{matrix}x_{1}^{α_{1}}x_{2}^{α_{2}}...x_{q}^{α_{q}}x_{q+1}^{τ_{1}}...x_{q+k}^{τ_{k}} = \\ x_{1}^{β_{1}}x_{2}^{β_{2}}...x_{q}^{β_{q}}x_{q+1}^{τ_{1}}...x_{q+k}^{τ_{k}} \end{matrix}  (2.2)

where α_{i} ≠ β_{i} (i = 1, ..., q). Let d be the greatest common divisor of all numbers α_{i} − β_{i}, i = 1, ..., q. Then Σ implies

x^{t} = x^{t+d}.  (2.3)

for some t. From identities (2.1) and (2.3), we can deduce the following identity

x_{1}^{m}x_{2}...x_{n} = x_{1}^{m+d}x_{2}...x_{n}.  (2.4)

Now since C_{m,1} is contained in varΣ, m does not exceed all α_{i} and β_{i} for all identities in Σ and all i. Now let W be a word containing > n−1 letters. Then any application to W of any identity from Σ is equivalent to several applications of the identity (2.4). Therefore every identity in ≥ n variables which follows from Σ also follows from (2.4). Let us return to the identity ϕ. Since it is false in varΣ, it does not follow from (2.4). Therefore the identity ϕ has the form x^{α}u = x^{β}v where x^{α} = x^{β} does not follow from x^{m} = x^{m+d} and u, v do not contain x. Equalizing some pairs of variables in ϕ we get an identity in n variables which is false in varΣ (because it will not follow from (2.4). It remains to apply Lemma 2.1.

Now let us prove that every variety which does not satisfy condition (A) or condition (B) is not finitely generated. Consider two cases.

Case 1. Suppose that Σ contains an irregular identity. Then as in the proof of Lemma 2.4, if varΣ is finitely generated, it must satisfy condition (A), a contradiction.

Case 2. Suppose now that all identities in Σ are regular. As we have mentioned above every identity from Σ can be transformed (using the commutativity identity) into the form (2.2). Let m be the minimal number among all α_{i} and β_{i} for all identities in Σ and all i. It is clear that C_{m,1} belongs to varΣ. Since the condition B is false, Σ does not contain an identity of the form

x^{m}x_{1}...x_{n} = x^{m+k}x_{1}...x_{n}

for any k, n. Furthermore, by equalizing some pairs of letters in one of the identities in Σ one can get an identity of the form

x^{m}y^{p} = x^{m+c}y^{q}

This identity implies

x^{m}y^{p+m} = x^{m+c}y^{q}y^{m+c} = x^{m+c}y^{m+p}.

Therefore varΣ satisfies the identity

x^{m}y^{n} = x^{m+c}y^{n}, n > 1.

Take any natural number k and consider the identity

x^{m}x_{1}...x_{kn} = x^{m+c}x_{1}...x_{kn}.  (2.5)

By Lemma 2.4, this identity cannot follow from Σ because Σ does not satisfy condition (B).

On the other hand, every identity in k variables obtained from (2.5) by equalizing pairs of variables follows from x^{m}y^{n} = x^{m+c}y^{n}, and so is true in varΣ. Since k is an arbitrary natural number, by Lemma 2.1 varΣ is not finitely generated.

The theorem is proved.

As we mentioned in the Introduction, Theorem 2.1 implies the following corollary.

Corollary 2.1 Finitely generated varieties of commutative semigroups form a sublattice of the lattice of varieties of commutative semigroups.

Proof. Since the join of two finitely generated varieties is always finitely generated, it is enough to show that the intersection of two finitely generated varieties of commutative semigroups is also finitely generated. Let V_{1} and V_{2} be two finitely generated varieties of commutative semigroups. If V_{1} or V_{2} satisfies condition (A) of Theorem 2.1 then V_{1} ∩ V_{2} contains finitely many subvarieties by a result of Aizenshtat [1]. As we have mentioned before this implies that the intersection is finitely generated.

Suppose that V_{1} and V_{2} satisfy condition (B). Let

x_{1}^{g}x_{2}...x_{t} = x_{1}^{g+h}x_{2}...x_{t}

and

x_{1}^{p}x_{2}...x_{s} = x_{1}^{p+q}x_{2}...x_{s}

be the identities of the form (2.4) from condition (B) which belong to the sets of identities defining V_{1} and V_{2} respectively. Then V_{1} ∩ V_{2} satisfies the identity

x_{1}^{min(g,p)}x_{2}...x_{max(t,s)} = x_{1}^{min(g,p)+GCD(h,q)}x_{2}...x_{max(t,s)}

and the monogenic monoid C_{min(g,p),1} is contained in the intersection V_{1}∩V_{2} because it is a submonoid of both C_{g,1} and C_{p,1}. Therefore V_{1} ∩ V_{2} satisfies condition (B). The corollary is proved.

The following corollary shows that the situation is worse in the lattice of all semigroup varieties.

Corollary 2.2 The set of all finitely generated varieties of semigroups is not a sublattice of the lattice of all varieties.

Proof. Indeed, let V_{1} be the variety generated by the Brandt semigroup B_{2} (the Brandt monoid B_{2}^{1} without the identity element). Let V_{2} be the variety of commutative semigroups given by the identities {xy = yx, x^{2} = x^{3}}. By Theorem 1.1 V_{2} is generated by a finite semigroup. By a result of Trahtman, V_{1} has the following basis of identities: x^{2} = x^{3}, xyx = xyxyx, x^{2}y^{2} = y^{2}x^{2}. Therefore V_{1} ∩ V_{2} has the following basis of identities x^{2} = x^{3}, xy = yx, x^{2}y = x^{3}y^{2}. Therefore the maximal monogenic monoid C_{m,1} in V_{1} ∩ V_{2} is C_{1,1}. If V_{1} ∩ V_{2} was finitely generated then by Theorem 1.1 it would satisfy an identity of the form x_{1}...x_{n} = u where u is not a permutation of x_{1}...x_{n} (in this case m = 1). But it is easy to see that this identity is impossible to deduce from the basis of V_{1} ∩ V_{2}. The corollary is proved.

2.2 Axiomatic and Basis Chains for Varieties of

Commutative Semigroups

Recall that every partition of the set of natural numbers into intervals is called a ladder. With every variety V we associate the axiomatic ladder and the basic ladder. Two numbers m, n belong to one class of the axiomatic ladder of V if the identities in m variables of V define the same variety as the identities in n variables of V. Two numbers m, n belong to the same class of the basis ladder if all m-generated semigroups from V generate the same subvariety of V as all n-generated semigroups from V.

Here we shall prove the following results.

Theorem 2.2 A ladder is a basis ladder for some variety of commutative semigroups if and only if it contains only finitely many non-singleton intervals.

Theorem 2.3 A ladder is an axiomatic ladder for some variety of commutative semigroups if and only if it contains only finitely many classes.

We shall use the following notation. Let u be a word. We shall denote the length of u by |u|, the number of variables in u by p(u) and the difference between |u| and p(u) by r(u). We say that a word u is applicable to a word v if v = w_{1}τ(u)w_{2} for some words w_{1}, w_{2} and a substitution τ. We shall say that a substitution τ depends on n variables if the image of τ is contained in an n-generated free semigroup.

Recall also that if V is a variety of semigroups then V_{n} denotes the variety generated by all n-generated semigroups of V and V^{n} is the variety defined by identities of V with at most n variables.

Proof of Theorem 2.2.

We shall use Theorem 2.1 from Section 2.1. For convenience let us formulate it here again as the first lemma.

Lemma 2.5 A variety of commutative semigroups V is generated by a finite semigroup if and only if one of the following conditions holds.

(A) V satisfies the identity of the form x_{1}x_{2}...x_{n} = u for some number n and a word u which is not a permutation of x_{1}x_{2}...x_{n}.

(B) For some natural numbers k, m, h the variety V satisfies the identity

x_{1}^{m}x_{2}...x_{h} = x_{1}^{m+k}x_{2}...x_{h}  (2.6)

and V contains the cyclic monoid C_{m,1}.

The following lemma is obvious.

Lemma 2.6 Let V be a variety of semigroups and n be a natural number. Then an identity α holds in V_{n} if and only if for every substitution τ which depends on n letters τ(α) holds in V.

Lemma 2.7 Let n < k be natural numbers. Then the varieties V_{n} and V_{k} coincide if and only if the following condition holds:

* For every identity α in k variables which is false in V there exists a substitution τ depending on n variables such that τ(α) is also false in V.

Proof. The “only if” part follows immediately from Lemma 2.6. Let us prove the “if” part.

Suppose that the condition (*) is satisfied. Consider any identity α of the variety V_{n}. We need to show that α holds in V_{k}, that is (by Lemma 2.6) for every substitution τ depending on k variables, τ(α) holds in V. By contradiction suppose that for some substitution α depending on k variables the identity α(τ) is false in V. Then by condition (*) there exists a substitution μ depending on n variables such that μτ(α) is false in V. Notice that μτ is a substitution depending on n variables. By Lemma 2.6 this contradicts the fact that α holds in V_{n}.

Lemma 2.8 Let V be a variety of commutative semigroups which is not generated by a finite semigroup but satisfies the identity (2.6). Then V satisfies the identity x^{c}y^{p} = x^{c+k}y^{p} for some c and p such that c < m.

Proof. By Lemma 2.5 V does not contain the cyclic monoid C_{m,1}. Therefore V satisfies an identity of the form x^{c}u = x^{c+k′}v where c < m and u and v do not contain x. Let us replace all letters in u and v by a power y^{p} of a letter y such that y^{p} is an idempotent in the free semigroup of the variety V. Then V satisfies the identity x^{c}y^{p} = x^{c+k′}y^{p}. It is clear that in this identity, one can replace k′ by any multiple tk′, t ≥ 1. The identity (2.6) implies an identity of the form x^{t} = x^{t+k} for some t. Therefore

x^{c}y^{p} = x^{c+k′t+k}y^{p} = x^{c+k′t}y^{p}x^{k} = x^{c}y^{p}x^{k} = x^{c+k}y^{p}.

The lemma is proved.

If α is an identity then the length of α is the maximum of the lengths of the left and right parts of α.

The following lemma implies the “if” part of Theorem 2.2. Lemma 2.9 Let V be a proper subvariety of the variety of all commutative semigroups, which is not generated by a finite semigroup. Then there exists a natural number N such that for every n > N we have V_{n} ≠ V_{n+1}.

Proof. Since V is a periodic variety, it satisfies the identity (2.6) for some m, k, h. Choose such an identity with the smallest possible triple (m, k, h) (in the lexicographic order). Let us denote this identity by α_{1}. Notice that m > 1, otherwise by Lemma 2.5 V would be finitely generated. By Lemma 2.8 V satisfies the identity α_{2}: x^{m−1}y^{d} = x^{m−1+k}y^{d} for some d.

By Lemma 2.7 we need to find a natural number N such that for every n > N there exists an identity in n+1 variables which is false in V but such that substitution depending on n variables makes it an identity in V. We shall find this identity among the identities of the form

x^{m−1}y_{1}^{d−1}...y_{t_{d−1}}^{d−1}z_{1}^{d−2}z_{2}^{d−2}...z_{t_{d−2}}^{d−2}...w_{1}...w_{t_{1}} = x^{m−1+k}y_{1}^{d−1}...y_{t_{d−1}}^{d−1}z_{1}^{d−2}z_{2}^{d−2}...z_{t_{d−2}}^{d−2}..w_{1}...w_{t_{1}} where y, z, ..., w are d − 1 different letters.

For convenience we shall denote this identity by a vector with d − 1 coordinates: (t_{d−1}, ..., t_{1}).

Suppose that i ≥ 2, and that starting with the identities α_{1} and α_{2} we have constructed i identities of V:

α_{3} = (g_{3}, 0, ..., 0, h_{1})

α_{4} = (g_{3} − 1, g_{4}, 0, ..., h_{2})
..............
α_{i} = (g_{3} − 1, g_{4} − 1, ..., g_{i}, 0, ..., h_{i})

Let ℓ_{i} be the length of the i-th identity α_{i}. Consider the set of identities

T = {(g_{3} − 1, ..., g_{i} − 1, g, 0..., 0, h′) | g, h′ ≥ 0}.

Case 1. None of the identities from T hold in V. In this case we let N = max{ℓ_{1}, ..., ℓ_{i}}. Take any n > N and choose g such that the identity

β = (g_{3} − 1, ..., g_{i} − 1, g, 0, ..., 0)

depends on n + 1 variables. Since β ∈ T, it is false in V. At the same time it is easy to check that every identity in n variables obtained from β by a substitution is a corollary from one of the identities α_{1}, ..., α_{i}.

Case 2. Suppose that some identities of T hold in V. Then choose the one for which the pair (g, h′) is the smallest in the lexicographic order. Denote this identity by α_{i+1}. Since i cannot exceed the number d, sooner or later Case 1 will occur and we shall find a number N as required. The lemma is proved.

Lemma 2.10 If a word u is applicable to a word v then r(u) ≤ r(v).

Proof. Suppose first that v = v_{1}uv_{2} or v = τ(u) for some words v_{1}, v_{2} and a substitution τ. Then p(v) ≤ p(u) + |v| − |u|. Therefore r(u) = |u| − p(u) ≤ |v| − p(v) = r(v).

Now consider the general case: v = v_{1}τ(u)v_{2} for some words v_{1}, v_{2} and a substitution τ. Then by what has been proved in the previous paragraph r(u) ≤ r(τ(u)) ≤ r(v). The lemma is proved.

Now let us prove the only if part of Theorem 2.2. Consider any ladder with finitely many non-singleton classes.

Case 1. Suppose that our ladder does not contain infinite classes, that is it has the form

{1, ..., i_{1}}, {i_{1} + 1, ..., i_{2}}, ..., {i_{n−1} + 1, ..., i_{n}}, {i_{n} + 1}, {i_{n} + 2}...  (2.7)

Consider the subvariety of the variety of commutative semigroups V given by identities {v = 0 | v ∈ V } where V = V_{1} ∪ V_{2} ∪ ... ∪ V_{n} and the set V_{k} consists of all words of length i_{n} + k − n + 1 in i_{n} variables.

Let us prove that the ladder (2.7) is the ladder of V.

Lemma 2.11 V_{i_{k}} ≠ V_{i_{k}+1}.

Proof. Consider an identity u = 0 where p(u) = i_{k} + 1, |u| = i_{n} + k − n + 1. Suppose that one of the identities v = 0, v ∈ V is applicable to u = 0. For every k let r_{k} be the difference between the length and the number of variables in any word in V_{k}, that is r_{k} = k − n + 1. Every word from V_{k+1}, ..., V_{n} is longer than u, so it cannot be applicable to u. Let v ∈ V_{k}. Then |u| = |v| but p(v) = p(u)−1. Therefore r(u) < r(v), so v is not applicable to u by Lemma 2.10. Now suppose that v ∈ V_{p} where p < k. Since i_{p} < i_{p+1} we have that r_{p} ≥ r_{p+1}. Therefore r(v) ≥ r_{k} > r(u). Again by Lemma 2.10 v is not applicable to u. Thus v = 0 is not an identity of V.

Now let τ be any substitution depending on i_{k} variables. Then the identity τ(u) = 0 contains ≤ i_{k} variables and has length ≥ i_{n} + k − n + 1. Then τ(u) contains one of the words from V_{k} as a (commutative) subword. Therefore the identity τ(u) = 0 can be deduced from one of the identities v = 0 where v ∈ V_{k}. Thus τ(u) = 0 holds in V. By Lemma 2.6, we get V_{i_{k}} ≠ V_{i_{k}+1}. The lemma is proved.

Lemma 2.12 V_{j} = V_{j+1} if i_{k} < j < i_{k+1} for some k.

Proof. Let u = v be an identity in j + 1 variables which is false in V. Then either u = 0 or v = 0 does not hold in V. Without loss of generality assume that u = 0 does not hold in V.

By Lemma 2.7 we need to find a substitution τ such that the identity τ(u) = τ(v) is false in V and depends on ≤ j variables.

If u contains ≤ j variables then we can take τ which fixes letters from u and maps all other letters to a letter from u. Indeed, if τ(u) = τ(v) holds in V then it is deducible from the identities w = 0 where w ∈ V. But then one of the words w ∈ V is applicable to u. Therefore the identity u = 0 follows from w = 0, so u = 0 holds in V, a contradiction.

Therefore we can assume that u contains j + 1 variables. Let u′ = v′ be an identity in j variables obtained from u = v by equalizing two letters. Suppose u′ = v′ holds in V. Then as in the previous paragraph u′ = 0 holds in V. Therefore one of the words w ∈ V_{1} ∪ V_{2} ∪ ... ∪ V_{n} is applicable to u′. Since words from V_{k+1} are not applicable to u we have |u| ≤ i_{n}+k−n+2. Therefore |u′| ≤ i_{n}+k−n+2. Hence r(u′) ≤ i_{n}+k−n+2−j. On the other hand r(w) ≥ i_{n}+k−n+1−i_{k} > i_{n}+k−n+1−j. Therefore by Lemma 2.10 v cannot be applicable to u. The lemma is proved.

From Lemmas 2.11 and 2.12 it follows immediately that the ladder (2.7) is the basis ladder for V.

Case 2. Suppose now that our ladder contains an infinite class, that is it has the form

{1, ..., i_{1}}, {i_{1} + 1, ..., i_{2}}, ..., {i_{n−1} + 1, ..., i_{n}}, {i_{n} + 1, i_{n} + 2...}

Consider the ladder (2.7) and the variety V corresponding to this ladder. Let V′ be the subvariety of V generated by the free semigroup in V′ with i_{n} + 1 generators. It is clear that our ladder in the basis ladder of V′.

The theorem is proved.

Proof of Theorem 2.3. The “only if” part follows from the fact that every variety of commutative semigroups is finitely based [24]. Let us prove the “if” part. The following lemma is obvious.

Lemma 2.13 Let V be a variety of universal algebras. Then V^{n} and V^{n+1} coincide if and only if every identity in n + 1 variables which is true on V follows from identities of V in n variables.

Now consider the variety of commutative semigroups given by the set of identities V = {v_{i} = 0 | i = 0, 1, ..., n} where the words v_{i} are defined as follows:

v_{0} = x_{1}^{2n}

............
v_{n−k} = x_{1}^{n+k}x_{2}^{n}...x_{i_{n−k}}^{n}
............
v_{n} = x_{1}^{n}x_{2}^{n}...x_{i_{n}}^{n}

where i_{1} < i_{2} < ... < i_{n} are fixed natural numbers.

Notice that the identities of the variety varV satisfy the following properties:

1. The i-th identity in V does not follow from any identity in V with smaller index since the highest exponent of a letter in v_{i} (the exponent of x_{1}) decreases when i increases.

2. If an identity in j variables (j < i_{k}) follows from v_{k} then it also follows from v_{0} because if we equalize any two variables in v_{k}, the 2n-th power of a letter appears as a subword (modulo commutativity).

Properties 1 and 2 together with Lemma 2.13 imply that the axiomatic ladder of the variety var(V) is

{1, ..., i_{1} − 1}, {i_{1}, ..., i_{2} − 1}, ..., {i_{n−1}, ..., i_{n} − 1}, {i_{n}, i_{n} + 1, ...}.

Since the increasing sequence i_{1} < i_{2} < ... < i_{n} was chosen arbitrarily, we can conclude that every ladder with finite number of classes is the axiomatic ladder of some variety of commutative semigroups.

The theorem is proved.

Idempotent Semigroups

Recall that a variety V is said to be inherently not finitely generated if it is not contained in any finitely generated variety.

Theorem 3.1 The variety of all idempotent semigroups is a minimal example of an inherently not finitely generated variety.

It is well known that each proper subvariety of idempotent semigroups is finitely generated [5], [6], [2]. Thus it is enough to show that the variety of all idempotent semigroups cannot be contained in any finitely generated variety. We shall prove the following stronger result.

Proposition 3.1 Let S be a semigroup satisfying an identity of the form x^{k} = x^{k+m}, k, m > 0, such that all chains of idempotents of S are uniformly bounded. Then varS does not contain the variety of all idempotent semigroups.

We shall need the following definition. Let {S_{α} | α ∈ A} be a collection of semigroups with common zero 0. Suppose also that S_{α}\{0} are disjoint sets. Let U be the union ⋃_{α∈A}. Then one can define an operation on U by keeping the operations of each S_{α} and making all other products 0. The resulting groupoid is a semigroup which is called the zero-direct union of semigroups {S_{α} | α ∈ A}.

The following lemma may be found in [22].

Lemma 3.1 Let S be a periodic semigroup with zero where all chains of idempotents have bounded lengths. Then the semigroup S contains a chain of ideals:

I_{0} = {0} < I_{1} < I_{2} < ... < I_{n} = S, such that each factor I_{k}/I_{k−1}, k = 1, ..., n, is a nil-semigroup or a zero-direct union of completely 0-simple semigroups (here we let I_{0} = {0}).

Let us fix the notations of lemma 3.1. Let x be an element of a periodic semigroup T. By x^{0} we denote the idempotent of the cyclic semigroup generated by x in T.

Lemma 3.2 Let e and f be idempotents of the semigroup I_{k}/I_{k−1}. Then either (ef)^{0} = 0 or f(ef)^{0} = f.

Proof. If I_{k}/I_{k+1} does not contain a non-zero idempotent, then it is a nilsemigroup, and the lemma is trivial. If I_{k}/I_{k+1} contains a nontrivial idempotent, then it is a zero-direct union of completely 0-simple semigroups. If e and f are contained in different components of the union, then ef = 0 by definition of zerodirect union, and the lemma is trivial. Therefore, we can assume that e and f belong to the same completely 0-simple semigroup M.

By Rees’s theorem [4], M is isomorphic to the Rees matrix semigroup M^{0}(G, I, J, P), where G is a group, I and J are index sets, P is an I × J matrix over G ∪ 0. The semigroup M consists of triples (i, g, j) with the multiplication (i, g, j)(i′, g′, j′) = (i, gp_{i′,j}g′, j′), where p_{i′,j} is the (i′, j)-entry of the matrix P. The idempotents of M have the form (i, p_{i,j}^{−1}, j), where i ∈ I, j ∈ J, and p_{i,j} ≠ 0. Suppose that e = (i, p_{i,j}^{−1}, j), f = (i′, p_{i′,j′}^{−1}, j′). If p_{i′,j} = 0 then ef = 0. So suppose that p_{i′,j} ≠ 0. Then ef = (i, g, j′) for some g ∈ G. If p_{i,j′} = 0 then (ef)^{0} = 0. So let p_{i,j′} ≠ 0. Then (ef)^{0} is the only idempotent in the subgroup {i} × G × {j}, so it is equal to (i, p_{i,j′}^{−1}, j′). Hence

f(ef)^{0} = (i′, p_{i′,j′}^{−1}, j′)(i, p_{i,j′}^{−1}, j′) = (i′, p_{i′,j′}^{−1}p_{i,j′}p_{i,j′}^{−1}, j′) = (i′, p_{i′,j′}^{−1}, j′) = f

as desired. The lemma is proved.

Proof of Proposition 3.1. Let S be a periodic semigroup satisfying an identity of the form x^{k} = x^{k+m}, k, m > 0, where the chains of idempotents are uniformly bounded. Without loss of generality we can assume that S contains 0. The free monogenic semigroup in the variety generated by S is finite, so it satisfies an identity x^{n} = x^{2n} for some n > 0. Therefore for every element a ∈ S, a^{n} is the only idempotent in < a >. As before we shall denote this idempotent by a^{0}. If u is a word, it will be convenient to use the notation u^{0} instead of u^{n}.

We need to construct an identity which is true in S and false in var{x = x^{2}}. Let us start with the following identity which we shall denote u = v:

\begin{matrix}(yt)^{0}((zp)^{0}(yt)^{0})^{0}((yp)^{0}(yt)^{0})^{0}x((zp)^{0}(yt)^{0})^{0} = \\ (yt)^{0}((yp)^{0}(yt)^{0})^{0}x((zp)^{0}(yt)^{0})^{0}. \end{matrix}

We need infinitely many copies of the identity u = v, so let us assign an index i to each variable in u = v. The resulting identity will be denoted by u_{i} = v_{i}. We shall assume that all variables we are going to use here are generators of the free semigroup F_{∞}.

We define a substitution τ as follows:

τ(y) = v_{1}, τ(y_{i}) = v_{i+1}, τ(z) = u_{1}, τ(z_{i}) = u_{i+1};

τ fixes all other letters.

If w is a word, then by ℓ(w) (resp. r(w)) we denote the minimal left (resp. right) part of the word w containing all but one of the letters of w. The following statement was proved, say, in [2].

Lemma 3.3 An identity w = w′ holds in the variety of all idempotent semigroups if and only if the contents of w and w′ are the same and the identities ℓ(w) = ℓ(w′), r(w) = r(w′) hold in the variety of all idempotent semigroups.

Lemma 3.4 For every substitution α which is identical on every letter except y and z and such that the contents of α(y) and α(z) are the same and do not contain the letters p, t, x, the identities α(u) = α(v) and α(y) = α(z) are either both true or both false in the variety of all idempotent semigroups.

Proof. Since in every idempotent semigroup x^{0} = x, we can turn the identity α(u) = α(v) into the following identity ū = v̄:

\begin{matrix}ū = α(y)tα(z)pα(y)tα(y)pα(y)txα(z)pα(y)t \\ v̄ = α(y)tα(y)pα(y)txα(z)pα(y)t. \end{matrix}

Since α(y), α(z) do not contain the letters p, t, x and have the same contents we have

ℓ(ū) = α(y)tα(z)pα(y)tα(y)pα(y)t, ℓ(v̄) = α(y)tα(y)pα(y)t,
ℓ(ℓ(ū)) = α(y)tα(z), ℓ(ℓ(v̄)) = α(y)tα(y),
r(ℓ(ℓ(ū))) = α(z), r(ℓ(ℓ(v̄))) = α(y).

This and Lemma 3.3 imply that if α(u) = α(v) holds in the variety of idempotent semigroups then the identity α(y) = α(z) also holds there. Conversely, if we equalize y and z in the identity u = v then this left part of this identity will contain a square of ((yp)^{0}(yt)^{0})^{0} which is an idempotent. Replacing this square by ((yp)^{0}(yt)^{0})^{0}, we obtain a trivial identity. Therefore if we equalize y and z in the identity u = v, the resulting identity will hold in every periodic semigroup. Thus the identity α(u) = α(v) follows from the identities α(y) = α(z) and x = x^{2}. The lemma is proved.

Lemma 3.5 For every k ≥ 1 the identity τ^{k}(u) = τ^{k}(v) is false in the variety of all idempotent semigroups.

Proof. It is easy to see that r(ℓ(ℓ(u))) = tz modulo the identity x = x^{2} and r(ℓ(ℓ(v))) = y modulo x = x^{2}. Since the identity tz = y does not hold in the variety of idempotent semigroups, by Lemma 3.3 the identity u = v does not follow from x = x^{2}. This gives the base of an induction.

Suppose that for some k ≥ 0 the identity τ^{k}(u) = τ^{k}(v) is false in the variety of idempotent semigroups. The identity τ^{k+1}(u) = τ^{k+1}(v) can be obtained from u = v by substituting τ^{k}(v) for y and τ^{k}(u) for z. By Lemma 3.4 the identities τ^{k+1}(u) = τ^{k+1}(v) and τ^{k}(u) = τ^{k}(v) are either both true or both false in the variety of all idempotent semigroups. Since the second identity is false by the inductive assumption, the first identity is also false. This gives us the inductive step. The lemma is proved.

Now we are going to prove that for some n the identity τ^{n}(u) = τ^{n}(v) holds in the semigroup S satisfying the condition of the Proposition. Let us fix a semigroup S, a chain of ideals from Lemma 3.1 and a homomorphism β from the free semigroup of infinite rank F ∞ (where all letters of the identities used here are generators) into S. We need to show that βτ^{n}(u) = βτ^{n}(v). We shall decompose the proof into a number of steps.

Lemma 3.6 For every i = 1, 2... equalities β(y_{i−1}) = β(v_{i}) and β(z_{i−1}) = β(u_{i}) imply βτ^{i−1}(u) = βτ^{i}(u) and βτ^{i−1}(v) = βτ^{i}(v).

The proof immediately follows from the definition of τ. Indeed, τ takes y_{i−1} to v_{i} and z_{i−1} to u_{i} leaving all other letters untouched.

In the next lemmas, we keep the notation from Lemma 3.6.

Lemma 3.7 For every k = 1, ..., n, if β(y) and β(z) are in I_{k} then β(u) = β(v) modulo I_{k−1}.

Proof. For simplicity we shall denote the elements which we substitute for letters from u and v by these letters. So y and z belong to I_{k}/I_{k−1} and t, p, x ∈ S/I_{k−1}.

Then yt, zp, yp are in I_{k}/I_{k−1} and (yt)^{0}, (zp)^{0}, (yp)^{0} are idempotents in this factor-semigroup. If one of them is 0 then the values of u and v are zeroes in this factor-semigroup. So we can assume that none of these idempotents is zero modulo I_{k−1}.

Therefore by Lemma 3.2 either ((zp)^{0}(yt)^{0})^{0} = 0 or (yt)^{0}((zp)^{0}(yt)^{0})^{0} = (yt)^{0}. If the first option holds then both u and v evaluate to 0 because ((zp)^{0}(yt)^{0})^{0} is a subword of both u and v. If the second option holds then

u ≡ (yt)^{0}((zp)^{0}(yt)^{0})^{0}((yp)^{0}(yt)^{0})^{0}x((zp)^{0}(yt)^{0})^{0}

is equal to

(yt)^{0}((yp)^{0}(yt)^{0})^{0}x((zp)^{0}(yt)^{0})^{0} ≡ v.

so u and v have the same value. Thus the values of u and v are always equal. The lemma is proved.

Lemma 3.8 If β(y_{k}) = β(z_{k}) then βτ^{k}(u) = βτ^{k}(v).

Proof. As we noticed before the identity u = v will hold in any periodic semigroup if we equalize y and z. This gives the base of induction.

Suppose β(y_{k}) = β(z_{k}) for some k ≥ 1. We need to show that βτ^{k}(u) = βτ^{k}(v). The identity τ^{k}(u) = τ^{k}(v) does not contain the letters y_{k−1} and z_{k−1}. Therefore we can redefine the homomorphism β on those letters without changing the values of the words τ^{k}(u) and τ^{k}(v). Let β(y_{k−1}) = β(v_{k}) and β(z_{k−1}) = β(u_{k}). Since (as we know) β(y_{k}) = β(z_{k}), we have that β(u_{k}) = β(v_{k}). Therefore β(y_{k−1}) = β(z_{k−1}). Then by the induction hypothesis, β(τ^{k−1}(u)) = β(τ^{k−1}(v)). Then by Lemma 3.6

βτ^{k}(u)) = βτ^{k−1}(u)) = βτ^{k−1}(v) = βτ^{k}(v).

The lemma is proved.

Lemma 3.9 If β(y_{k}) ∈ I_{k+1} and β(z_{k}) ∈ I_{k+1} then βτ^{k}(u) = βτ^{k}(v) for every k = 0, ..., n − 1.

Proof. Let us use induction on k. The base follows from Lemma 3.7. As in the proof of Lemma 3.8 we can redefine β(y_{k−1}) = β(v_{k}) and β(z_{k−1}) = β(u_{k}).

Suppose that β(u_{k}) = β(v_{k}). Then β(y_{k−1}) = β(z_{k−1}). By Lemma 3.8 βτ^{k−1}(v) = βτ^{k−1}(u). By Lemma 3.6 then

βτ^{k}(v) = βτ^{k}(u)

as required.

Now assume that β(u_{k}) ≠ β(v_{k}). By Lemma 3.7 β(u_{k}), β(v_{k}) are equal modulo I_{k}, therefore these elements are in I_{k}. So β(y_{k−1}), β(z_{k−1}) ∈ I_{k}. Then by the induction hypothesis βτ^{k−1}(u) = βτ^{k−1}(v). Now by Lemma 3.6

βτ^{k}(u) = βτ^{k}(v)

as required. The lemma is proved. Lemmas 3.5 and 3.9 imply Proposition 3.1 which in turn implies Theorem 3.1.

The Finite Basis Problem

4.1 Preliminaries

Here we collect the main definitions and preliminary results about identities of semigroups from S.

For every semigroup identity τ, L_{τ} and R_{τ} will denote the left and right parts of τ respectively.

The following lemma is obvious since all non-zero words in S(W) are distinct.

Lemma 4.1 Let W ⊂ A^{∗}. An identity τ holds on S(W) if and only if for any substitution Θ from the set of letters of τ to A^{∗} either

a) Θ(L_{τ}) ≡ Θ(R_{τ}) or

b) Θ(L_{τ}) and Θ(R_{τ}) do not belong to W^{c}.

Definition 4.1 In what follows U(x_{1}, ..., x_{n}) will mean a word which depends on x_{1}, ..., x_{n}. If we substitute 1 for x_{1}, ..., x_{k}, the resulting word will be denoted by U(x_{k+1}, ..., x_{n}).

Definition 4.2 A pair of letters (x, y) in an identity τ is called stable, if the identity L_{τ}(x, y) = R_{τ}(x, y) is trivial, otherwise, it is called unstable.

The following statement is obvious.

Lemma 4.2 If every pair of letters in an identity τ is stable then τ is a trivial identity.

We shall need the following well known statements.

Lemma 4.3 [26] Two words u and v in the free monoid A^{∗} commute if and only if these two words are powers of some word w. If u, v, w are words from A^{∗} and u commutes with v, v commutes with w then u commutes with w.

Lemma 4.4 Suppose that (x, y) is a stable pair of letters in an identity τ. For some natural k and m, let ϕ be a substitution which takes x to x^{k} and y to y^{m} and does not change the other letters. Then (x, y) is a stable pair of letters in ϕ(τ).

Proof. Indeed, ϕ(τ)(x, y) = ϕ(τ(x, y)). Since τ(x, y) is a trivial identity, so is ϕ(τ(x, y)).

Definition 4.3 An identity is called balanced if each letter appears in each part of it the same number of times.

Lemma 4.5 Let τ be a balanced identity and let σ_{1}, σ_{2} be two disjoint sets of letters in τ. Suppose that for each x ∈ σ_{1}, y ∈ σ_{2} the pair (x, y) is stable in τ. Consider a substitution ϕ which takes every letter x from σ_{1} to t_{1} (same t_{1} for all x ∈ σ_{1}) and every y ∈ σ_{2} to t_{2} (same t_{2} for all y ∈ σ_{2}). Then (t_{1}, t_{2}) is a stable pair of letters in ϕ(τ).

Proof. Without loss of generality we can assume that every letter in τ belongs to either σ_{1} or σ_{2}, that is ϕ(τ) has only two variables, t_{1} and t_{2}. Thus we need to show that ϕ(τ) is not a trivial identity. Suppose, by contradiction, that

ϕ(L_{τ}) ≢ ϕ(R_{τ}).

Without loss of generality we can assume that ϕ(L_{τ}) = ut_{1}u′, ϕ(R_{τ}) = ut_{2}u′′ for some words u, u′, u′′. Then L_{τ} = v_{1}xv′_{1}, R_{τ} = v_{2}yv′_{2} where ϕ(v_{1}) = u = ϕ(v_{2}), ϕ(x) = t_{1}, ϕ(y) = t_{2}. Since ϕ(v_{1}) = ϕ(v_{2}), the number of σ_{1}-letters in v_{1} is the same as the number of σ_{1}-letters in v_{2} and the number of σ_{2}-letters in v_{1} is the same as the number of σ_{2}-letters in v_{2}. Since ϕ(x) = t_{1} and ϕ(y) = t_{2}, x ∈ σ_{1}, y ∈ σ_{2}. Let v_{1} ∗ x ∗ v′_{1} be the i-th occurrence of x in L_{τ}. The i-th occurrence of x in R_{τ} belongs either to v_{2} or to v′_{2}.

Suppose that it belongs to v′_{2}. Then the number of occurrences of σ_{2}-letters preceding the i-th occurrence of x in L_{τ} is smaller than the number of σ_{2}-letters preceding the i-th occurrence of x in R_{τ}. Then for some letter z ∈ σ_{2} the number of occurrences of z in L_{τ} preceding the i-th occurrence of x is smaller than the number of occurrences of z in Rτ preceding the i-th occurrence of x. Therefore τ(z, x) is not a trivial identity. This contradicts the assumption that (z, x) is a stable pair of letters.

Thus the j-th occurrence of x in R_{τ} belongs to v_{2}. Let v_{2} ∗ y ∗ v′_{2} be the j-th occurrence of y in R_{τ}. Then the i-th occurrence of x precedes the j-th occurrence of y in R_{τ}. Since τ(x, y) is a trivial identity, the i-th occurrence of x precedes the j-th occurrence of y in L_{τ}. Therefore the j-th occurrence of y in L_{τ} belongs to v′_{1}. This leads to a contradiction as in the previous paragraph.

Lemma 4.6 Let τ be a balanced identity. Suppose that τ does not hold on S(W) for some set W. Then there exists a substitution Θ from B to A^{∗} and an unstable pair of letters (x, y) such that

1) Θ(x)Θ(y) ≠ Θ(y)Θ(x) in A^{∗}

2) Θ(L_{τ}) or Θ(R_{τ}) belongs to W^{c}.

Proof. Since τ does not hold on S(W), by Lemma 4.1, there exists a substitution Θ from B to A^{∗} such that

a) Θ(L_{τ}) ≠ Θ(R_{τ}) in A^{∗} and

b) Θ(L_{τ}) or Θ(R_{τ}) belongs to W^{c}.

Since τ is false on S(W), it is non-trivial, so it contains an unstable pair of letters by Lemma 4.2. We need to find a unstable pair of letters (x, y) such that Θ(x) and Θ(y) do not commute. Suppose that such a pair does not exist.

Consider the following binary relation ∼ on the set of letters of τ:

x ∼ y iff Θ(x)Θ(y) = Θ(y)Θ(x)

By Lemma 4.3 ∼ is an equivalence relation and for each equivalence class σ of this relation there exists a word r_{σ} such that every x ∈ σ, Θ(x) = r_{σ}^{k_{x}} for some k_{x}. Let us introduce new variables t_{σ}, one for each equivalence class of σ, and consider the substitution

ϕ : x → t_{σ}^{k_{x}}.

It is clear that Θ = ϕψ where ψ(t_{σ}) = r_{σ}. Therefore ψ(ϕ(L_{τ})) ≠ ψ(ϕ(Rτ)). In particular, ϕ(τ) is not a trivial identity. By Lemma 4.2 there exists a unstable pair of letters (t_{σ}, t_{σ′}) in the identity ϕ(τ). Then σ and σ′ are distinct ∼-classes. By our assumption, for any letter x ∈ σ and y ∈ σ′, (x, y) is a stable pair. This immediately leads to a contradiction with Lemmas 4.4, 4.5. The lemma is proved.

Definition 4.4 A letter appearing exactly once in a word is called a linear letter in this word. The letter t with or without an index is reserved to denote only linear letters in this thesis. Indices for t will be often omitted.

Definition 4.5 A word U is called an isoterms of a semigroup S if S does not satisfy any nontrivial identity of the form U = V.

Lemma 4.7 Let S be a monoid with 0 such that xy is an isoterms of S. Then a) The equational theory of S is closed under deletions. Let τ be an identity of S.

b) The contents of L_{τ} and R_{τ} are the same.

c) Suppose that a word x^{k} is an isoterms of S. If some letter y appears in L_{τ} k times or less, then y must appear in R_{τ} the same number of times. d) If a letter is linear in one part of τ then it is linear in the other part of τ.

e) Any word of the form t_{1}t_{2}...t_{n} (i.e. any product of linear letters) is an isoterms of S for any n ≥ 1.

Proof. Part a) follows from the fact that S contains the identity element. Part b) follows from the fact that S contains 0 and 1 (see [24]). If the statement in part c) is not true, then we can cancel all letters in τ but x

and get a nontrivial identity of S(W) in one variable. This identity is impossible, because x^{k} is an isoterms of S(W).

Part d) follows from part c).

e) Let t_{1}...t_{n} = W be an identity of S. Part d) implies that W is a permutation of t_{1}...t_{n}. If this permutation is not trivial, then, by part a), S satisfies the identity t_{i}t_{j} = t_{j}t_{i}. This is impossible, because xy is an isoterms. The lemma is proved. Definition 4.6 a) If u is a word and x is a letter in u, then _{i}x means the i-th occurrence of x in u.

Let τ be an identity.

b) We say that a pair of occurrences (_{i}x,_{j} y) is stable in τ if _{i}x and _{j}y follow in the same order in both parts of τ. Otherwise, it is called unstable.

c) Denote by Chaos(τ) the set of all unstable pairs (_{i}x,_{j} y). d)We say that an ordered pair (_{i}x,_{j} y) is adjacent in τ if one of the sides τ

contains _{i}x_{j}y as a subword.

d) We say that an ordered pair (i_{x}, j_{y}) is critical in τ if this pair is adjacent and unstable in τ.

The following two lemmas are obvious.

Lemma 4.8 Let τ be an identity and (_{i}x,_{j} y), (_{j}y,_{k} z) ∉ Chaos(τ) for some numbers i, j, k and letters x, y, z. Then (_{i}x,_{k} z) ∉ Chaos(τ).

Lemma 4.9 Let τ be an identity. The cardinality of Chaos(τ) is 0 if and only if τ is trivial.

Lemma 4.10 Any nontrivial identity contains a critical pair.

Proof. Let τ be a nontrivial identity. By lemma 4.9, τ contains an unstable pair (_{i}x,_{j} y). If _{i}x and _{j}y are not adjacent in L_{τ}, then one can find another pair of letters between _{i}x and _{j}y in L_{τ} which is adjacent and which is also switched in R_{τ}. Indeed, if every pair of adjacent letters between_{i}x and_{i}y in L_{τ} does not belong to Chaos(τ) then by Lemma 4.8 the pair (_{i}x,_{j} y) would not be in Chaos(τ) either (because there is a chain of pairs connecting _{i}x and _{i}y where each pair is not in Chaos(τ) and in each pair the first letter precedes the second letter in L_{τ}).

The lemma is proved.

Definition 4.7 Let U be a word. Let us place a linear letter before (after) each letter in U. The resulting word will be denoted by {t}U (U{t}) and is called the left (resp. right) linearization of U.

Example 1 Let U = abbcaa. Then

U{t} = at_{1}bt_{2}bt_{3}ct_{4}at_{5}at_{6},

{t}U = t_{1}at_{2}bt_{3}bt_{4}ct_{5}at_{6}a.

Definition 4.8 a) We say that a word U has type (*) if only one letter appears in U more than one time.

b) We say that an identity τ has type (*) if the words L_{τ} and R_{τ} have type (*).

c) We say that an identity τ has type (**) if

L_{τ} = (U{t})xy({t}V) and R_{τ} = (U{t})yx({t}V),

where U{t} and {t}V are linearizations of some words U and V in {x, y}^{∗}.

Definition 4.9 a) For each m, n ≥ 1, let Σ_{m,n} denote the set of all words U in a two-letter alphabet {x, y}, such that the letter x appears in U m times and the letter y appears in U n times.

b) Let Σ_{m,n}^{i,j} be the subset of Σ_{m,n} consisting of all words where _{i}x precedes _{j}y.

c) The sets described in parts a) and b) will be called simple sets.

Lemma 4.11 a)For any i, j, m, n, 1 ≤ i ≤ m, 1 ≤ j ≤ n (Σ_{m,n}^{i,j})^{c} ∩ Σ_{m−1,n} = Σ_{m−1,n}^{i−1,j} ∪ Σ_{m−1,n}^{i,j}

b) For every pair of numbers n and m ∩_{1≤i≤m,1≤j≤n}Σ_{m,n}^{i,j} = {x^{m}y^{n}} for any 2 ≤ i ≤ m, 1 ≤ j ≤ n.

c) The closure under taking subwords of a simple set is closed under deletions of letters and is a union of simple sets.

Proof. a) Take any word U that belongs to

(Σ_{m,n}^{i,j})^{c} ∩ Σ_{m−1,n}.

Either xU or Ux belongs to Σ_{m,n}^{i,j}. But then U belongs to Σ_{m−1,n}^{i−1,j} or Σ_{m−1,n}^{i,j}

Take any word U that belongs to the right part of the equation. If U belongs to Σ_{m−1,n}^{i−1,j}, then xU belongs to Σ_{m,n}^{i,j}. If U belongs to Σ_{m−1,n}^{i,j}, then Ux belongs to Σ_{m,n}^{i,j}. In both cases, U belongs to the left part of the equation.

Part b) becomes obvious if we observe that {x^{m}y^{n}} = Σ_{m,n}^{m,1}

c) Let (Σ_{m,n}^{i,j})^{c} be the closure under taking subwords of a simple set. Let U be any word in this set. This means that P UQ is in Σ_{m,n}^{i,j} for some P, Q in {x, y}^{∗}.Let us erase a letter in U and denote the resulting word by U′. If we erased x then P xU′Q is in Σ_{m,n}^{i,j}. If we erased y then P U′yQ is in Σ_{m,n}^{i,j}. So, U′ is in (Σ_{m,n}^{i,j})^{c}.

The second part of c) immediately follows from part a). The lemma is proved. The following sets of identities will be very useful later.

Definition 4.10 a) For any natural number k let A_{k} be the set of the following identities: x^{k+1} = x^{k+2}, x^{k+1}t = tx^{k+1} and xt_{1}xt_{2}...xt_{k+1} = x^{k+1}t_{1}t_{2}...t_{k+1}

b) Let B_{k} be the set of all identities of type (**) such that in each side every letter appears no more than k times and no two linear letters are adjacent in both sides simultaneously.

c) Let C_{k} be the set of all identities of types (*) or (**) in each side of which every letter appears no more than k times and no two linear letters are adjacent in both sides simultaneously.

The following lemma is obvious.

Lemma 4.12 a) Let W be a finite set of words. Suppose that no letter appears in any word from W more than k times. Then S(W) satisfies the system of identities A_{k}.

b) A_{k}, B_{k} and C_{k} are finite sets, A_{k} ⊂ C_{k}, B_{k} ⊂ C_{k}, C_{k} ⊂ C_{k+1}.

Definition 4.11 Let S be a semigroup. Let (_{i}x,_{j} y) be an adjacent pair of occurrences in a word W = U_{i}x_{j}yV in the alphabet {x, y}.

a)We say that the pair (_{i}x,_{j} y) is critical in W with respect to S if it is unstable in some balanced identity of S of the form W = W′ .

b)We say that pair (_{i}x,_{j} y) commutes in W modulo S if S satisfies the following identity of type (**):

U{t}_{i}x_{j}y{t}V = U{t}_{j}y_{i}x{t}V  (4.1)

Definition 4.12 Let τ be an identity of a semigroup S. Let (_{i}x,_{j} y) be a critical pair in τ.

a)We say that (_{i}x,_{j} y) is (**)-removable in τ modulo S if id(S) contains an appropriate identity of type (**) which commutes _{i}x and _{j}y.

b)We say that (_{i}x,_{j} y) is (*)-removable in τ modulo S if S contains an identity of type (*) such that after applying this identity to τ we obtain an identity τ′ such that Chaos(τ′) is a subset of Chaos(τ) and does not contain the pair (_{i}x,_{j} y).

4.2 Main Results

Definition 4.13 Denote by id^{k}(S) the set of all identities τ of a semigroup S such that each letter appears in each side of τ no more than k times.

Lemma 4.13 Let S be a semigroup. Suppose that any nontrivial identity in id^{k}(S) is balanced and contains a (**)-removable critical pair modulo S. Then id^{k}(S) follows from B_{k} ∩ id^{k}(S).

Proof. Let τ be an identity in id^{k}(S). Let us prove that we can derive τ from identities in id^{k}(S) ∩ B_{k} by induction on the cardinality of Chaos(τ) (see Definition 4.6).

Base of the induction. If the cardinality of Chaos(τ) is 0, then, by Lemma 4.9, τ is a trivial identity and we are done.

Inductive step. Suppose that Chaos(τ) is not an empty set: then τ is not trivial and contains a removable critical pair. If we remove this critical pair by applying an appropriate identity in B_{k} ∩ id^{k}(S), we get a new identity τ′ such that the cardinality of Chaos(τ′) is smaller than the cardinality of Chaos(τ). By the induction hypothesis, τ′ follows from B_{k} ∩ id^{k}(S). The induction is complete and the lemma is proved.

Lemma 4.14 Let W be a finite set of words in an alphabet A. Let k be the maximal number of times any letter appears in words in W.

Suppose that x^{k−1} is an isoterms of S(W).

Suppose that for any word u in Σ_{k,k}^{c} any critical pair in u commutes in u modulo S(W).

Then A_{k} ∪ (id^{k}(S) ∩ B_{k}) is a finite basis of identities for S(W).

Proof. By lemma 4.12, S(W) satisfies the system of identities A_{k}.

Let τ be a nontrivial identity of S(W). If some letter x occurs in one of the sides of τ more than k times, then we can use identities A_{k} to reduce the number of occurrences of this letter to k + 1 and then collect all occurrences of x on the left of the word.

Let us show that any identity in id^{k}(S(W)) contains a removable critical pair modulo S(W) and use lemma 4.13.

Let τ be a nontrivial identity in id^{k}(S(W)). Then τ is a balanced identity by lemma 4.7. By lemma 4.10, τ contains a critical pair. Let us show that any critical pair (_{i}x,_{j} y) in τ is removable. Without loss of generality, _{i}x_{j}y is a subword in L_{τ}. Then (_{i}x,_{j} y) is a critical pair in L_{τ}(x, y). By the condition in the lemma, it commutes in L_{τ}(x, y) modulo S(W). Therefore, it is (**)-removable in τ modulo S(W). Lemma is proved.

Corollary 4.1 Any finite set of words W is contained in some finite set of words U such that S(U) is finitely based.

Proof. Let W be a finite set of words in an alphabet A. Let k be the maximal number of times any letter appears in words in W. Take U be the union of W and Σ_{k,k}. S(U) obviously satisfies the first condition of Lemma 4.14. The second condition of the lemma is also satisfied, because any word in Σ_{k,k}^{c} is an isoterm of S(U) and, therefore, does not contain any critical pairs. The corollary is proved.

The next two theorems give a sufficient conditions for S(W) to be finitely based.

Theorem 4.1 Let W be a finite union of simple sets of words in a 2-letter alphabet. Then S(W) is finitely based.

Proof. By Lemma 4.11 c), we can assume that W is closed under taking subwords.

Let k be the maximal number of times a letter appears in words from W.

Let a be a letter that occurs in some word in W exactly k times. Then by part b) of Lemma 4.11, S contains the word a^{k}. Therefore, S(W) satisfies the first condition of lemma 4.14.

To check the second condition of lemma 4.14, let (_{i}x,_{j} y) be a critical pair in a word U_{i}x_{j}yV in Σ_{k,k}.

Then S(W) satisfies a nontrivial identity UxyV = R such that _{j}y precedes _{i}x in R.

We need to show that S(W) satisfies the identity (4.1).

We are going to use the fact that W is closed under deletions of letters by Lemma 4.11 c).

Suppose that identity (4.1) does not hold on S(W). By lemma 4.6, there exists a substitution Θ from B to A^{∗} and an unstable pair of letters (x, y) such that

a) Θ(x)Θ(y) ≠ Θ(y)Θ(x) in A^{∗} b) Θ(L_{(4.1)}) or Θ(R_{(4.1)}) belongs to W. Suppose that Θ(L_{(4.1)}) belongs to W. Condition a) above implies that Θ(x)

contains, say, a and Θ(y) contains another letter, say, b. Now pick one occurrence of a in Θ(x) and one occurrence of b in Θ(y) and delete all other letters in Θ(L_{(4.1)}). The resulting word D_{1} is essentially UxyV if we replace x by a and y by b. Since W is closed under deletions, D_{1} belongs to W (if we substitute x for a and y for b). On the other hand, it does not belong to W, because UxyV = R is a nontrivial identity on S(W), a contradiction. Therefore, Θ(L_{(4.1)}) does not belongs to W.

Now suppose that Θ(R_{(4.1)}) belongs to W. Again, pick one occurrence of a in Θ(x) and one occurrence of b in Θ(y) and delete all other letters in Θ(R_{(4.1)}). The resulting word D_{2} belongs to W. But D_{2} can be obtained from D_{1} by replacing ia_{j}b by _{j}b_{i}a. Since D_{1} does not belong to W and W is a union of simple sets, W contains a simple set Σ_{j+n,i+m}^{j,i}. R belongs to this simple set and therefore it belongs to W. But this is impossible, because UxyV = R is a nontrivial identity on S(W). Therefore, Θ(R_{(4.1)}) does not belongs to W.

So, we have proved that S(W) satisfies identity (4.1). Therefore (_{i}x,_{j} y) is commutative in UxyV modulo S(W). Theorem 4.1 is proved.

Definition 4.14 Let k < K be natural numbers. D_{K}^{k} denotes the subset of B_{K} consisting of all identities in B_{K} where both x and y appear > k times in both sides.

Lemma 4.15 Let W be a finite set of words. Let K be the maximal number of times a letter appears in words of W. Suppose that for some k < K, W does not contain words with two letters occurring more than k times. Then S(W) satisfies the set of identities D_{K}^{k}.

Proof. Let U and V be some words in {x, y}^{∗} such that x and y appear in UV more than k − 1 times. Then S(W) satisfies the following identity:

U{t}xy{t}V = U{t}yx{t}V  (4.2)

Indeed, suppose that identity (4.2) does not hold on S(W). Then by Lemma 4.6, there exists a substitution Θ such that Θ(xy) ≠ Θ(yx) and Θ(U{t}xy{t}V) or Θ(U{t}yx{t}V) belongs to W. Since W does not contain words with two letters occurring > k times, such a substitution is impossible. Since every identity in D_{K}^{k} has the form (4.2), the lemma is proved.

Lemma 4.16 Let W be a finite set of words in some alphabet A. Let K be the maximal number of times a letter appears in words of W. Let k be the maximal number such that all words in Σ_{k,k} are isoterms of S(W). Suppose that W does not contain words with 2 letters occurring > k times. Suppose also that every nontrivial identity where exactly one letter appears > k times in each side has a (∗)- or (∗∗)-removable critical pair. Then all identities of S(W) follow from C_{k} ∩id(S(W)).

Proof. By Lemma 4.12 S(W) satisfies the system of identities A_{k}. Let τ be an identity of S(W). As in the proof of Theorem 4.1 we can assume that τ ∈ id^{k}(S(W)). Let us denote all letters occurring > k times in each side of τ by x with indices and all other letters by y with indices. Since all words in Σ_{k,k} are isoterms, the identity τ(y_{1}, ..., y_{g}) (obtained by removing all x’s) is trivial. Let us number all letters in L_{τ}(y_{1}, ..., y_{g}) from left to right c_{1}, ..., c_{n}. Let U(x_{1}, ..., x_{m}, y_{1}, ..., y_{g}) be a word with U(y_{1}, ..., y_{g}) ≡ Lτ(y_{1}, ..., y_{g}). We say that _{ℓ}x has coordinate i in U if the ℓ-th occurrence of x is between c_{i} and c_{i+1} (if the occurrence of x is before c_{1}, the coordinate is 0, and if it is after c_{n} then the coordinate is n).

Claim 1. If τ contains an unstable pair of the form (x, y) then τ contains a critical pair modulo D_{K}^{k} of this form which is (∗)- or (∗∗)-removable. Proof immediately follows from the second condition of the lemma and from Lemma 4.15.

Claim 1 and definition 4.12 imply the following Claim, which can be easily proved by induction.

Claim 2. τ is equivalent modulo C_{K} ∩id^{K}(S(W)) to an identity τ′ in id^{K}(S(W)) such that Chaos(τ′) does not contain pairs of the form (x, y).

If Chaos(τ) does not contain pairs of the form (x, y) then each x_{i} has the same coordinates in both sides of τ. Such an identity can be easily derived from D_{K}^{k}.

Therefore all identities of S(W) follow from C_{K} ∩ id^{K}(S(W)). The lemma is proved. Theorem 4.2 Let W be a finite set of words of type (*) in some alphabet A. Then S(W) is finitely based.

Proof. Let the numbers k and K be as in lemma 4.16. If k = 0, then W^{c} does not contain ab. Therefore, W = {a^{K}} and all identities of S(W) follow from

x^{K+1} = x^{K+2}, and xy = yx.

Now assume that k > 0, then in fact k = 1.

Let us show that W satisfies the conditions of Lemma 4.16.

The first condition is obviously satisfied. Let us check the second condition. Let τ be a nontrivial identity of S(W) of the form τ(x, t_{1}, ...t_{q}). Then it obviously contains a (*)-removable critical pair because it is of the type (*). The theorem is proved.

Corollary 4.2 Let m and n be natural numbers. The following sets of words W give us examples of finitely based syntactic monoids S(W).

a) The set of all possible words U in {a, b}^{∗} such that a appears in U less than n times and b appears in U less than m times.

b) The set consisting of a single word a^{m}b^{n}.

c) The set consisting of a single word a^{m}ba^{n}.

Proof. For parts a) and b) we can apply Theorem 4.1 for simple sets Σ_{n,m} and Σ_{m,n}^{m,n}. Part c) follows immediately from Theorem 4.2.

The following lemma is well known. We present its proof only for the sake of completeness.

Lemma 4.17 Let S be a semigroup. Suppose that we can find an infinite system of identities of S τ_{n} ; n=1,2,... with the following property:

(+) For any m, there exists a number n such that τ_{n} does not follow from identities of S of length m. Then S is not finitely based.

Proof. Suppose that the equational theory of S has a finite basis of identities B. Let m be the maximal length of identities in B. Then, by condition (+), there exists an identity τ_{n} which does not follow from B, a contradiction.

Definition 4.15 Let S be a semigroup. Let m be a natural number. Let U = V be an identity. An m-derivation of U = V is a triple consisting of:

1. A sequence of words: U = U_{1}, U_{2}, ..., U_{n+1} = V

2. A sequence of identities of S of length ≤ m: u_{1} = v_{1}, ..., u_{n} = v_{n}.

3. A substitution Θ such that Θ(u_{i}) = U_{i}, Θ(v_{i}) = U_{i+1}, i = 1, 2, ..., n.

Lemma 4.18 Let S be a monoid. Let m be a natural number. Let U = V be an identity. If U = V follows from identities of S of length ≤ m, then there exists an m + 2-derivation of U = V.

Proof. An arbitrary derivation of U = V from identities of length m is a triple consisting of

1. A sequence of words U = w_{0}, ..., w_{n+1} = V.

2. A sequence of identities u_{i} = v_{i}, i = 1, ..., n.

3. A sequence of substitutions Θ_{i} such that w_{i} = p_{i}Θ_{i}(u_{i})q_{i}, w_{i+1} = p_{i}Θ_{i}(v_{i})q_{i}, for some words p_{i}, q_{i}, i = 1, ..., n.

To make it an (m + 2)-derivation in our sense, we first replace each identity u_{i} = v_{i} by t_{1}u_{i}t_{2} = t_{1}v_{i}t_{2} and extend Θ_{i} to new letters t_{1} and t_{2} so that Θ_{i}(t_{1}) = p_{i}, Θ_{i}(t_{2}) = q_{i}. Then we rewrite all these identities in disjoint alphabets, and combine all substitutions Θ_{i} in one substitution Θ.

Definition 4.16 Let U be a word, S be a semigroup. A pair of letters (x, y) in U is called stable modulo S, if it is stable in any identity U = V of S.

The next lemmas will be used sometimes without reference to show that a word is an isoterm for a semigroup S. The first lemma immediately follows from Lemma 4.2.

Lemma 4.19 Let S be a semigroup, U be a word. The word U is an isoterm of S if and only if any pair of letters in U is stable modulo S.

Lemma 4.20 A subword of an isoterm of a semigroup S is an isoterm of S.

Proof.Let ABC be an isoterm for some words A, B and C.

If B is the left part of a nontrivial identity B = W, then ABC is the left part of a nontrivial identity ABC = AW C. So, B must be an isoterm.

Lemma 4.21 Let S be a monoid . Let U = U(x, y, z_{1}, ...z_{n}, p_{1}, ..., p_{m}) be a word. If the pair (x, y) is stable in U(x, y, z_{1}, ..., z_{n}), then (x, y) is stable in U.

Proof. This easily follows from the fact that the equational theory of a monoid is closed under deletions. Indeed, suppose that U = V is an identity of S such that U(x, y) ≠ V (x, y). Then the same is true for the identity U(x, y, z_{1}, ..., z_{n}) = V (x, y, z_{1}, ..., z_{n}) which also holds on S.

Lemma 4.22 Let U be an isoterm of a monoid S. Let (x, y) be a pair of letters in a word V. Let Θ : A → B^{∗} be a substitution that fixes all letters except x and y such that

a) Θ(x) ≠ 1 and Θ(y) ≠ 1 start or end with different letters.

b) If z is a letter distinct from x and y then the pairs (x, z) and (y, z) are stable in U.

c) Θ(V) = U.

Then (x, y) is a stable pair in V.

Proof. Suppose that Θ(x) and Θ(y) start with different letters (the other case is completely similar). Let Z = {z_{1}, ..., z_{k}} be the set of all letters in V distinct from x and y.

Suppose that (x, y) is not stable in V. Then S satisfies an identity V = W, such that V (x, y) ≢ W (x, y).

Since U is an isoterm, condition c) implies that the identity Θ(V) = Θ(W) is trivial.

Let P be the maximal prefix of V and Q be the maximal prefix of W such that P coincides with Q. Then without loss of generality V ≡ P c_{1}P′, W ≡ Qc_{2}Q′ or W = Q for some possibly empty words P′, Q′ and letters c_{1} and c_{2}. It is clear that the second option (W = Q) cannot occur because otherwise Θ(V) ≢ Θ(W).

Both letters c_{1} and c_{2} cannot be distinct from x and y because otherwise Θ(c_{1}) = c_{1} ≠ c_{2} = Θ(c_{2}) and the words Θ(V) and Θ(W) would be different. Without loss of generality assume that c_{1} = x. Then the pair (x, c_{2}) is not stable in V = W, so c_{2} must be equal to y. But then Θ(V) ≢ Θ(W) because Θ(x) and Θ(y) start with different letters, a contradiction. The lemma is proved.

Lemma 4.23 Let S be a monoid. Let (x_{i}, y) for i = 1, ..., k be stable pairs of letters in a word V with respect to S. Let Θ be a substitution which fixes y. Let x be a letter which occurs only in the words Θ(x_{i}), i = 1, ..., k and not in Θ(z) for z ∉ {x_{1}, ..., x_{k}}. Then (x, y) is a stable pair in Θ(V).

Proof. Suppose that (x, y) is not stable in Θ(V). Then S satisfies the identity Θ(V) = W, where (x, y) is an unstable pair. Then Θ(V) contains ℓ occurrences of x before the j-th occurrences of y and W contains ℓ′ occurrences of x before the j-th occurrence of y, where ℓ ≠ ℓ′, for some ℓ, ℓ′, j. Since x appears in Θ(V) only in the subwords Θ(x_{i}), i = 1, ..., k, the number of occurrences of x_{i} before the j-th occurrence of y in Θ(V) is different from the number of occurrences of this x_{i} before the j-th occurrence of y in W for some i = 1, ..., k. But this means that the pair (x_{i}, y) is not stable in V, a contradiction. The lemma is proved.

Lemma 4.24 Let U be an isoterm of a monoid S. Let (x, y) be a pair of letters in a word V. Let Θ : A → B^{∗} be a substitution identical on x and y such that

a) If Θ(z) ≠ 1, z ∉ {x, y} then Θ(z) does not contain x, y and the pairs (x, z) and (y, z) are stable in V.

b) Θ(V) = U

Then (x, y) is a stable pair in V.

Proof. By Lemma 4.21 we can assume that Θ(z) ≠ 1 for every z (otherwise we can delete all these z’s). Now consider the word Θ(V). Lemma 4.23 implies that this word together with the identical substitution satisfies the conditions of lemma 4.22, so we can conclude that the pair (x, y) is stable in Θ(V). Since Θ fixes x and y, this pair is stable in V (because V (x, y) ≡ Θ(V)(x, y).

Lemma 4.25 Let U be an isoterm of a monoid S. Let (x, y) be a pair of letters in a word V. Let Θ : A → B^{∗} be a substitution such that

a) Θ(x) and Θ(y) start (end) with different letters.

b) If Θ(z) ≠ 1, z ∉ {x, y} then pairs (x, z) and (y, z) are stable in V.

c) Θ(V) = U

Then (x, y) is a stable pair in V.

Proof. Let z_{1}, ..., z_{k} be all the letters in V such that Θ(z_{i}) ≠ 1, z ∉ {x, y}. Without loss of generality we can assume that Θ(z_{i}) does not contain x and y for every i = 1, ..., k.

Consider the substitution Θ_{1} which fixes x and y and coincides with Θ on z_{1}, ..., z_{k}.

Consider the substitution Θ_{2} which coincides with Θ on x and y and fixes all other letters.

Denote Θ_{1}(V) by V′. By lemma 4.23 , Θ_{2} and V′ satisfy the conditions of lemma 4.22. Therefore, (x, y) is stable in V′. By lemma 4.24, (x, y) is a stable pair in V. The lemma is proved.

Definition 4.17 Let U be a word. A maximal subword of U which does not contain linear letters is called a block of U.

Lemma 4.26 Let S be a monoid with 0 such that xy is an isoterm of S. Let U be an isoterm of S. If we erase a prefix (suffix) of a block in U, we get an isoterm of S.

Proof. Let {t_{1}, ..., t_{k}} be the set of all linear letters in U. Erase a part B′ of a block B = B′B” between linear letters t_{1} and t_{2} in U and denote the resulting word by V. Suppose that there exists a nontrivial identity V = W of S. W has the same pattern of linear letters as V by lemma 4.7. Since the identity V = W is not trivial, W contains a block which does not match the corresponding block in V. Consider the substitution Θ which takes t_{1} to t_{1}B′ and fixes all other letters. Then Θ(V) = U and Θ(W) contains a block which does not match the corresponding block in U. Therefore, U = Θ(W) is a nontrivial identity. This contradicts the fact that U is an isoterm. So, V is an isoterm.

Lemma 4.27 Let S be a monoid. Let V = V (y, x_{1}, ..., x_{n}) and U be some words. Suppose that U and V (x_{1}, ..., x_{n}) are isoterms of S. Suppose that there exists a substitution Θ such that

a) Θ(V) = U

b) If Θ(x_{i}) ≠ 1, then the first (last) letter of Θ(y) is not the same as the first (last) letter of Θ(x_{i}) for each i = 1, ...n.

Then V is an isoterm of S.

Proof. By contradiction, suppose that V is the left part of a nontrivial identity V = W. Then V = AyB and W = Ax_{i}C or W = A for some words A, B, C and some i = 1, ..., n. Since Θ(V) = U, S satisfies the identity U = Θ(W). This identity is not trivial, because the first letter of Θ(y) is not the same as the first letter of Θ(x_{i}). But U is an isoterm. This is a contradiction.

Definition 4.18 Let X = {x_{1}, ..., x_{n}, ...}. Denote the words x_{1}x_{2}...x_{n} and x_{n}...x_{2}x_{1} by [Xn] and [nX] respectively.

Lemma 4.28 Let S be a monoid with 0. Suppose that

U = x^{α_{0}}y^{β_{1}}x^{α_{1}}y^{β_{k}}...x^{α_{k}+1}y^{β_{k+1}}x^{α_{k+1}}...y^{β_{n}}x^{α_{n}}  (4.3)

is an isoterm for S(W) for some n ≥ 2, α_{i} ≥ 1 for 1 ≤ i ≤ n − 1, β_{i} ≥ 1 for 1 ≤ i ≤ n.

Suppose also that for each m = 1, 2, ... the following word U_{m} is not an isoterm of S(W):

x^{α_{0}}[Am]t_{1}y^{β_{1}}x^{α_{1}}t_{2}...t_{k}y^{β_{k}}x^{α_{k}}[mA]y^{β_{k+1}}x^{α_{k+1}}...t_{n}y^{β_{n}}x^{α_{n}}

where A is a set of letters.

Then S is not finitely based.

Proof. Consider the system of nontrivial identities τ_{m} with the left part U_{m}. Fix a number m and take k = 2m. Let us show that there is no m-derivation for τ_{k}.

Let us write the word U_{m} as X[Am]Y [mA]Z. Suppose that we can find an mderivation for τ_{k}. Let u_{1} = v_{1} and Θ have meanings as in Definition 4.15. Let u and v be the minimal subwords of u_{1} such that Θ(u) contains [Am] and Θ(v) contains [mA]. Let z be the first letter in u. Suppose that Θ(z) contains a suffix of X. Then z is a linear letter, because the word xa_{1} appears in U_{m} exactly one time. Therefore we can change u_{1} = v_{1} by replacing z by z′z′′, where z′ and z′′ are some new letters and change Θ by letting Θ′(z′) be the suffix of X and letting Θ(z) = Θ′(z′)Θ′(z′′). Thus, we obtained an m + 1-derivation of τ_{k} such that Θ(u) does not contain a part of X.

Acting similarly with the last letter of u, we can arrange that Θ(u) does not contain a prefix of Y. Thus, there exists an m + 2 derivation of τ_{k} where Θ(u) = [AM].

Doing the same thing with v we can find an m + 4- derivation for τ_{k} such that Θ(u) = a_{1}a_{2}...a_{2m}, Θ(v) = a_{2m}...a_{2}a_{1}. Since τ_{k} is a nontrivial identity, we can assume that the identity u_{1} = v_{1} is also

nontrivial. Therefore, the word I = XuY vZ is not an isoterm.

To get a contradiction, we are going to show that I must be an isoterm.

Claim. The following words are isoterms of S:

a)

U^{∗} = x^{α_{0}}t_{1}y^{β_{1}}x^{α_{1}}t_{2}...t_{k}y^{β_{k}}x^{α_{k}}t_{k+1}y^{β_{k+1}}x^{α_{k+1}}...t_{n}y^{β_{n}}x^{α_{n}}  (4.4)

b) [Am]t[mA] for any m = 1, 2, ... c) utv

Proof of claim a) By lemma 4.7, t_{1}...t_{n} is an isoterm of S. Words U^{∗}(x, t_{1}, ..., t_{n}) and U^{∗}(y, t_{1}, ..., t_{n}) are isoterms of S by lemma 4.27. To show that pair (x, y) is stable in U^{∗}, consider the substitution Θ which is identical on x and y and sends all other letters to 1. Since Θ(U^{∗}) is U, (x, y) is stable in U^{∗} by lemma 4.25.

b) Since xtx is obviously an isoterm here, the pairs (a_{i}, t) are stable for any i = 1, ..m. To show that (a_{i}, a_{j}), i < j is a stable pair, consider the substitution which takes a_{i} to y, a_{j} to x and t to x^{α_{k+1}−2}. This substitution takes [Am]t[mA] to a subword of U. By lemma 4.25, the pair (a_{i}, a_{j}) is stable and, therefore, part b) is proved.

c) Since any subword of length ≥ 2 of [Am]t[mA] is unique, utv is an isoterm by lemma 4.27. The claim is proved.

The length of v is less than m. Since Θ(v) = a_{2m}...a_{2}a_{1} and every 2-letter subword of a_{2m}...a_{2}a_{1} appears in U_{2m} exactly one time, v contains a linear letter t.

It is easy to see that no letter of uv appears in XY Z. If we erase all the letters in uv except t, we get the isoterm (4.4) . Since utv is an isoterm by the Claim, to finish the proof that XuY vZ is an isoterm, it is left to show that any letter in uv forms a stable pair with any letter in XY Z.

Let z be a letter in uv.

Case 1. z appears only in u. Then I(x, y, z, t, t_{2}, ...t_{k}, t_{k+2}, ..., t_{n}) becomes the same word as (4.4) if we rename z by t_{1} and t by t_{k+1}. So, z forms a stable pair with any letter in XY Z.

Case 2. z appears only in v. Then I(x, y, z, , t_{1}, ...t_{k}, t_{k+2}, ..., t_{n}) becomes the same word as (4.4) if we rename z by t_{k+1}. So, z forms a stable pair with any letter in XY Z.

Case 3. z appears the first time in u and the second time in v. The pairs (z, t_{i}), (x, t_{i}), (y, t_{i}) are stable by lemma 4.26.

To show that the pair (x, z) is stable, consider the following substitution: z → y, x → x, y → 1, t_{1} → y^{β_{1}−1}, t_{k+1} → y^{β_{k+1}−1}. t_{i} → y^{β_{i}}, if i ≠ 1, k+1. This substitution takes I to U. By lemma 4.25 (x, z) is stable in I.

For (y, z) consider a substitution: z → x, x → 1, y → y, t_{1} → x^{α_{0}−1}, t_{k+1} → y^{α_{k}−1}, t_{i} → x^{α_{i−1}}, if i ≠ 1, k + 1. This substitution takes I to a maximal prefix of U which ends with y. By lemma 4.25 (y, z) is stable in I.

Since each pair of letters is stable in XuY vZ, it is an isoterm. So, there is no m-derivation for τ_{k}. Therefore, by Lemma 4.17, S is not finitely based.

In what follows we are going to deal with words containing a lot of linear letters. To avoid a mess with indices, recall that we assume that t always stands for a linear letter and different occurrences of t in the same word have different indices which we shall omit.

Lemma 4.29 Let S be a monoid with 0. Suppose that (1) The word xyt_{1}xyt_{2}...t_{m}xy is an isoterm of S for some m = 1, ....

(2) For every m ≥ 1 let us represent the word xyt_{1}xyt_{2}...t_{m}xy in the form AxyBxyC in some way. Then for each n = 2, 3, ..., S satisfies the identity τ_{n}:

A_{∗}y[Y n][Xn]xB_{∗}[nX]yx[nY]C_{∗} = A_{∗}[Xn]yx[Y n]B_{∗}y[nY][nX]xC_{∗}.

where _{∗} means the result of the substitution:

xy → yt[Y n]{t}[Xn]{t}xt

and X, Y are disjoint sets.

Then τ_{n} satisfies the condition (+) of Lemma 4.17 and, therefore, S is not finitely based.

Proof. The following properties of the identity τ_{n} are easy to check: P1. The only unstable pairs of letters in τ_{n} are: (x, y_{i}), (y, x_{i}), (x_{i}, y_{j}) P2. If (z, p) is an unstable pair in τ_{n}, then τ_{n}(z, p, {t}) becomes the identity

AxyByxC = AyxBxyC if we rename z by x and p by y.

P3. If the pair (z, p) belongs to the set {(x, y), (x, x_{i}), (y, y_{j})}, i, j = 1, ..., n, then L_{τ_{n}}(z, p, t) becomes the isoterm xyt_{1}...t_{m}xy if we rename z by x and p by y.

Fix a number m and take n = 2m. Let us show that there is no m-derivation for τ_{n}.

Claim 1. If L = L_{τ_{n}}(y, y_{j}, x_{i}, x, {t}) = W is a nontrivial identity of S, then W coincides with R_{τ_{n}}(y, y_{i}, x_{i}, x, {t}).

Indeed, since the word xyt_{1}xyt_{2}...t_{m}xy is an isoterm, so is xt_{1}x...xt_{m}x by Lemma 4.26. Therefore, each block in W is a permutation of the corresponding block in L.

Thus W contains only 2 nontrivial blocks. Number them B_{1} and B_{2} from left to right.

Case 1. Suppose that x_{i} precedes y in B_{1}. Then P3 forces it to precede y_{j} in B_{1}. Then x_{i} must succeed y_{i} in B_{2}, but it should precede x in B_{2} by P3. But then, x should precede y_{i} in B_{1}. But P3 forces x to follow y in B_{1}. So, W must coincide with R.

Case 2. Suppose that y precedes x_{i} in B_{1}. Then x_{i} precedes y in B_{2}. Then it precedes y_{i} in B_{2} by P3. Then x_{i} must succeed y_{i} in B_{1}, but it must precede x in B_{1} by P3. Then x is between y and y_{i} in B_{2}. So, W must coincide with L. Claim 1 is proved.

Consider an m-derivation of τ_{n}. Claim 1 implies that if we ignore commuting letters in [nX], [nY], [Xn], [Y n], the identity τ_{n} should be derived in one step.

Claim 2. The equational theory of S does not contain any identity u = v of length ≤ m such that τ_{n} could be derived in one step from u = v.

Assume the opposite. Then there exists a substitution Θ such that

u = A′yu_{1}u_{2}xB′u_{3}yxu_{4}C′, v = A′u_{2}yxu_{1}B′yu_{4}u_{3}xC′

for some words A′, B′, C′, u_{i}, i = 1, 2, 3, 4 and Θ(u_{1}) = [Y n] Θ(u_{2}) = [Xn] Θ(u_{3}) = [nX] Θ(u_{4}) = [nY]. Since u has length ≤ m, u_{1} contains a letter z such that Θ(z) contains y_{i}y_{i+1}

for some i = 1, ..., n − 1 and u_{2} contains a different letter p such that Θ(p) contains x_{j}x_{j+1} for some j = 1, ..., n − 1. Consider the identity u(z, p, t) = v(z, p, t). This must be a nontrivial identity, because z does not appear in u_{2} and p doesn’t appear in u_{1}.

On the other hand, u(z, p, t) is an isoterm by lemma 4.26 , because it is what we get if we erase some subwords xy in xyt_{1}...t_{m}xy and rename x by z and y by p. Claim 2 is proved.

Theorem 4.3 Let U be a word in {a, b}^{∗}. Then S({U}) is finitely based if and only if for some m, n ≥ 0 U is equal to one of the following words: a^{m}b^{n}, b^{m}a^{n}, a^{m}ba^{n}, b^{m}ab^{n}.

Proof. Corollary 4.2 gives the “if” part of the theorem. Let us prove the “only if” part.

Case 1. U = a^{α_{0}}b^{β_{1}}a^{α_{1}}...b^{β_{k}}a^{α_{k}}b^{β_{k+1}}...b^{β_{n}}a^{α_{n}} , where n ≥ 2, α_{i} ≥ 1 for 1 ≤ i ≤ n − 1, β_{i} ≥ 1 for 1 ≤ i ≤ n, and for some k, 0 < k < n + 1, α_{k} > 1.

Let us check the conditions of Lemma 4.28.

Thus first condition of Lemma 4.28 is obviously satisfied.

To check the second condition of Lemma 4.28 we will show that S({U}) satisfies the identity U_{m} = V_{m}, where

U_{m} = x^{α_{0}}[Am]t_{1}y^{β_{1}}x^{α_{1}}t_{2}...t_{k−1}y^{β_{k}}x^{α_{k}−1}[mA]y^{β_{k+1}}x^{α_{k+1}}...t_{n}y^{β_{n}}x^{α_{n}}

V_{m} = x^{α_{0}}[Am]t_{1}xy^{β_{1}}x^{α_{1}−1}t_{2}...t_{k−1}y^{β_{k}}x^{α_{k}−1}[mA]y^{β_{k+1}}x^{α_{k+1}}...t_{n}y^{β_{n}}x^{α_{n}}

Suppose that this identity does not hold on S(U). Then, by Lemma 4.6, there exists a substitution Θ such that Θ(x)Θ(y) ≠ Θ(y)Θ(x) and either Θ(U_{m}) or Θ(V_{m}) is a subword of U.

Notice that U_{m}(x, y) and V_{m}(x, y) are shorter than U only by one letter. Together with the fact that n ≥ 2, this implies that Θ(x) and Θ(y) are one letter words, namely a or b. Also this implies that Θ([mA]) = Θ([Am]) = 1 and Θ(t_{1}...t_{n}) is a one letter word.

Thus only the following 3 situations are possible.

1. Θ(U_{m}) ( Θ(V_{m}) ) coincides with U.

2. Θ(U_{m}) ( Θ(V_{m}) ) is the maximal prefix of U.

3. Θ(U_{m}) ( Θ(V_{m}) ) is the maximal suffix of U. It is easy to check that none of these can happen. Case 2. U contains the subword abab and does not contain the subwords abba

and baab. Let us use lemma 4.29. The first condition of this lemma obviously holds for some m. Let us check the second condition.

Suppose that τ_{n} does not hold on S({U}). Then there exists a substitution Θ and an unstable pair of letters (z, p) such that

a) Θ(zp) ≠ Θ(pz) for some i = 1, ..., n and

b) Θ(L_{τ}) or Θ(R_{τ}) is a subword of U. Condition a) forces Θ(L_{τ}) or Θ(R_{τ}) to contain two letters a between two occur-

rences of b or vice versa. Such a word is not a subword of U. Therefore, this identity holds on S({U}).

Theorem 4.3 is proved.

Lemma 4.30 Let S be a monoid with 0. Suppose that

(1)For some A, B and C from the monoid {xyt, yxt}^{∗}, the word U = AyxtBxytC is an isoterm of S .

(2)For each n = 1, 2, ...S satisfies the identity τ_{n}: A_{∗}y[Xn][Y n]xB_{∗}[nX]xy[nY]C_{∗} = A_{∗}[Y n]yx[Xn]B_{∗}x[nY][nX]yC_{∗}, where _{∗} means the value under the substitution: xy → xt[Xn]t[Y n]tyt, yx → yt[nY]t[nX]txt. Then τ_{n} satisfies the condition (+) in lemma 4.17 and therefore S is not finitely

based.

Proof . The following properties of τ_{n} are easy to check: Q1. The only unstable pairs of letters in τ_{n} are: (x_{i}, y_{j}), (x, x_{i}), (y, y_{j}) for

i, j = 1, ..., n.

Q2. If (z, p) is an unstable pair of letters, then τ_{n}(z, p, {t}) becomes the following identity τ: AxytBxytC = AyxtByxtC if we rename z by x and p by y.

Q3. If the pair (z, p) belongs to the set {(x_{i}, y), (x, y), (x, y_{j}), i, j = 1, ..., n}, then τ_{n}(z, p, {t}) becomes the isoterm U if we rename z by x and p by y.

Fix m and let n = 2m. Let us show that there is no m- derivation for τ_{n}. Claim 1. If L_{τ_{n}} = W is a nontrivial identity of S, then W coincides with the

right part of τ_{n}.

Proof of Claim 1 By lemma 4.7,W has the same pattern of linear letters as the left part of τ_{n}. The linear letters divide W into blocks.

Lemma 4.25 implies that the word U(x, t) is also an isoterm. This implies that each block in W is a permutation of the corresponding block in the left part of τ_{n}.

Condition Q1 implies that each block [Xn], [nX], [Y n] or [nY] is identical to the corresponding block in W.

A nontrivial permutation can only happen in blocks of W which correspond to blocks B_{1} = y[Xn][Y n]x and B_{2} = [nX]yx[nY] in the left part of τ_{n}. Call these blocks B′_{1} and B′_{2}. Condition Q1 implies that letters in y[Xn], [Y n]x, [nX]y and x[nY] do not commute. So, the block B′_{1} must be a shuffle of y[Xn] and [Y n]x and B′_{2} is a shuffle of [nX]y and x[nY].

Two cases are possible:

Case 1. x precedes y in B′_{1}. Then, block B′_{1} is identical to the corresponding block in the right part of τ_{n} and y_{1} precedes x_{n} in B′_{1}. Then y_{1} precedes x_{n} in B′_{2}. But then, block B′_{2} is identical to the corresponding block in the right part of τ_{n}. So, in this case, W coincides with the right part of τ_{n}.

Case 2. x succeeds y in B′_{1}. Then condition Q3 forces x to succeed y in B′_{2}. This implies that B′_{2} is identical to B_{2} and that x_{n} precedes y_{1} in B′_{2}. But then, x_{n} precedes y_{1} in B′_{1}. This means that B′_{1} is identical to B_{1} and that W coincides with the left part of τ_{n}. Claim 1 is proved.

Claim 2. The equational theory of S does not contain any identity u = v of length ≤ m such that τ_{n} could be derived in one step from u = v.

Assume the opposite. Then there exists a substitution Θ such that

u = A′u_{1}u_{2}B′u_{3}u_{4}C′ v = A′u_{2}u_{1}B′u_{4}u_{3}C′

for some words A′, B′, C′, u_{i}, i = 1, 2, 3, 4 and

Θ(u_{1}) = y[Xn] Θ(u_{2}) = [Y n]x Θ(u_{3}) = [Nn]y Θ(u_{4}) = x[nY].

Since u has length ≤ m, u_{1} contains a letter z such that Θ(z) contains x_{i}x_{i+1} for some i = 1, ..., n − 1 and u_{2} contains a different letter p such that Θ(p) contains y_{j}y_{j+1} for some j = 1, ..., n − 1. Consider the identity u(z, p, t) = v(z, p, t). This must be a nontrivial identity, because z does not appear in u_{2} and p doesn’t appear in u_{1}.

On the other hand, u(z, p, t) is an isoterm by lemma 4.25, because it is what we get if we erase all subwords yx in U and maybe some subwords xy and rename x by z and y by p.

Claim 2 is proved.

Definition 4.19 (The height of a set of words) a) Let U be a word in a two letter alphabet a,b. The height of U (h(U)) is the maximal among the number of distinct subwords ab and the number of distinct subwords ba. For example, the word aaabbab has height 2 because it contains 2 occurrences of ab and 1 occurrence of ba.

b) Let U be a word in an arbitrary finite alphabet. Then the height of U is the maximum height of U(a, b) for all pairs of letters (a, b) in U.

c) If W is a finite set of words, then the height of W (h(W)) is the maximum height of words in W.

Lemma 4.31 Let U be a word over an alphabet B of height h. Let (x, y) be a pair of letters in U such that the height of U(x, y) is h. Let Θ be a substitution B → A^{∗} such that none of the following conditions holds:

a) Θ(x) = 1

b) Θ(y) = 1

c) Θ(x) = a^{n} and Θ(y) = a^{m} for some letter a.

Then the height of Θ(U) is greater or equal to h.

Proof. Case 1. Suppose that Θ(x) or Θ(y) contains the subword ab. Then the number of different subwords ab in Θ(U) is at least the number of occurrences of x or y in U, which is greater than h.

Case 2. Now suppose that Θ(x) = a^{n} and Θ(y) = b^{m}. Then Θ(U) contains at least h different subwords ab. Thus in this case the height of Θ(U) is greater or equal to h also.

The following lemma gives a general necessary condition for S(W) to be nonfinitely based.

Lemma 4.32 Let W be a finite set of words of height h in an alphabet A containing letters a and b. Suppose that among words of height h we can find a word U in the alphabet {a, b} which starts and ends with a and contains a subword b^{α_{1}}a^{α_{2}}b^{α_{3}}, where α_{i} ≥ 2 for i = 1, 2, 3. Then S(W) is not finitely based.

Proof. U = U_{1}ba^{α_{2}}bU_{2} for some words U_{1} and U_{2} such that U_{1} starts with a and ends with b and U_{2} starts with b and ends with a. Let n be the height of U_{1} and m = h − n be the height of U_{2}. Let us check the conditions of lemma 4.30.

(1) Take A = (yxt)^{n}, B = 1, C = (xyt)^{m}. Let’s show that I = AxytyxC is an isoterm of S(W) in a few steps.

Step 1. The word t_{1}...t_{m+n+1} is an isoterm by Lemma 4.7 .

Step 2. If we replace all maximal subwords of type b^{k} in U by linear letters, we get an isoterm U^{∗} by Lemma 4.27.

Step 3. We apply lemma 4.26 to word U^{∗} to show that xt_{1}x...t_{n}x^{2}t_{1}x...t_{m} is an isoterm.

Step 4. We show that I(x, {t}) = xt_{1}x...t_{n+m+1}x is an isoterm.

Step 3 implies that x forms a stable pair with all linear letters but t_{n+1}. To see that (x, t_{n+1}) is also a stable pair, consider the substitution Θ such that x → b, t_{n+1} → a^{α_{2}} and Θ(I) is a maximal subword of U which starts and ends with b. By lemma 4.25, pair (x, t_{n+1}) is stable in I(x, {t}) . So, I(x, {t}) is an isoterm.

Since I(y, t) becomes the same word as I(x, t) if we rename y by x, it is also an isoterm.

Step 5. To complete the prove that I is an isoterm, it is left to show that (x, y) is a stable pair in I. To do this, use a substitution Θ which takes x to b, y to a, I to U and apply lemma 4.25.

The first condition of Lemma 4.30 is satisfied. Let us check the second condition.

(2) Suppose that the identity τ_{n} does not hold on S(W). Then there exists a substitution as in Lemma 4.6. By Property Q2, for any unstable pair of letters (z, p), τ_{n}(z, p, {t}) is essentially the identity AxytxyC = AyxtyxC if we rename z by x and p by y. Notice that the height of both parts of this identity is greater than h. By lemma

4.31, the heights of Θ(L_{τ_{n}}) and Θ(R_{τ_{n}}) are greater than h. Therefore, neither Θ(L_{τ_{n}}) nor Θ(R_{τ_{n}}) can belong to W, a contradiction. So, τ_{n} holds on S(W) . The lemma is proved.

Theorem 4.4 Let W be a finite set of words in some alphabet A. Then there exists a word u in a two-letter alphabet such that S(W ∪ u) is not finitely based.

Proof. Let W be a finite set of words of height h. Take u be a word of height h + 1 which starts and ends with letter a and contains b^{2}a^{2}b^{2}. Then S(W ∪ u) will not be finitely based by lemma 4.32. The theorem is proved.

Lemma 4.33 Let W_{1} and W_{2} be two sets of words over some alphabet A. Then S(W_{1} ∪ W_{2}) has the same identities as the direct product S(W_{1}) × S(W_{2}).

Proof. Indeed, if an identity τ holds in S(W_{1}∪W_{2}) then by Lemma 4.6 for every substitution Θ if Θ(L_{τ}) or Θ(R_{τ}) is in W_{1}^{c} or W_{2}^{c} then Θ(L_{τ}) ≡ Θ(R_{τ}). This implies, by Lemma 4.6 that τ holds in S(W_{1}) and in S(W_{2}), so it holds in S(W_{1} ∪ W_{2}). On the other hand, if τ does not hold on S(W_{1} ∪ W_{2}) then there exists a substitution Θ such that Θ(L_{τ}) or Θ(R_{τ}) is in W_{1}^{c} or W_{2}^{c} but Θ(L_{τ}) ≢ Θ(R_{τ}). But this implies by Lemma 4.6 that τ does not hold in S(W_{1}) or S(W_{2}), so it does not hold in the direct product of these monoids. The lemma is proved.

Theorem 4.5 a) There exists an infinite chain of varieties generated by syntactic monoids of finite complete languages such that finitely based and not finitely based varieties alternate.

b) There exist two finite sets of words U and V in a 2-letter alphabet such that S(U) and S(V) are infinitely based but S(U) × S(V) is finitely based.

c) There exist two finite sets of words U and V in a 2-letter alphabet such that S(U) and S(V) are finitely based but S(U) × S(V) is not finitely based.

Proof. Part a) follows from Corollary 4.1 and Theorem 4.4, because if a finite set of words U is a subset of V, then the variety generated by S(U) is a subvariety of the variety generated by S(V).

To prove part b) let U = {abab, baba}, V = {a^{2}b^{2}, b^{2}a^{2}, ab^{2}a, ba^{2}a}. Then it is easy to check that (U ∪ V)^{c} = Σ_{2,2}, so S(U ∪ V) is finitely based by Theorem 4.1. Therefore S(U) × S(V) is finitely based by Lemma 4.33.

On the other hand S(U) has the same identities as S({abab}) and so it is not finitely based by Theorem 4.3. In order to prove that S(V) is not finitely based let us use Lemma 4.30.

It is easy to check using Lemma 4.19 that the word yxt_{1}xyt_{2} is an isoterm for S(V). This word plays the role of the word U in the formulation of Lemma 4.30: the words A, B, C are empty. The identity τ_{n} from Lemma 4.30 which corresponds to this isoterm is the following:

yx_{1}...x_{n}y_{1}...y_{n}xtx_{n}...x_{1}xyy_{n}...y_{1} = y_{1}...y_{n}yxx_{1}...x_{n}txy_{n}...y_{1}x_{n}...x_{1}y.

Suppose that this identity does not hold in S(V). Then by Lemma 4.6 there exists a substitution Θ and an unstable pair of letters (s_{1}, s_{2}) such that

(i) Θ(s_{1}s_{2}) ≠ Θ(s_{2}s_{1}),

(ii) Θ(L_{τ_{n}}) or Θ(R_{τ_{n}}) belongs to V^{c}.

The substitution Θ must take all but 2 letters of τ_{n} to 1, otherwise Θ would take both sides of τ_{n} to words of length > 5. Therefore we have that Θ(L_{τ_{n}}(s_{1}, s_{2})) or Θ(R_{τ_{n}}(s_{1}, s_{2})) belongs to U. But for every pair (s_{1}, s_{2}) of unstable letters in τ_{n} (the list of these pairs is presented in Property Q1 in the proof of Lemma 4.30) L_{τ_{n}}(s_{1}, s_{2}) and R_{τ_{n}}(s_{1}, s_{2}) is essentially the word abab which does not belong to V. So our assumption was wrong and S(V) satisfies τ_{n}. Therefore by Lemma 4.30 S(V) is not finitely based. Part b) is proved.

Now let us prove Part c). Let

U = {ababa, a^{2}b^{2}a, ab^{2}a^{2}},
V = {ba^{3}b, abab, a^{2}b^{2}, ab^{2}a}.

To prove that S(U) and S(V) are finitely based, we will use Lemma 4.16. Take k = 2 and K = 3. Then S(U) and S(V) satisfy the first condition of Lemma 4.16. In order to check the second condition, we will use the following properties of U and V.

Claim 1. a) Let u(x, y) be a word where x occurs 3 times and y occurs ≤ 2 times. If u is different from yxxyx, xyxxy, xxxt and txxx, then any critical pair in u is (**)-removable modulo S(U).

b) Let u(x, y) be a word where x occurs 3 times and y occurs ≤ 2 times. If u is different from yxxyx and xyxxy, then any critical pair in u is (**)-removable modulo S(V).

c) The critical pairs (_{1}x, y) and (y,_{3} x) in the identity xyxxy = yxxyx are (**)- removable modulo S(U).

d) The critical pairs (y,_{1} x) and (_{3}x, y) in the identity xyxxy = yxxyx are (**)- removable modulo S(V).

Let τ be a nontrivial identity as in lemma 4.16. Let x denote the only 3-occurring letter in τ. Let y denote a ≤ 2-occurring letter in τ.

The next Claim follows immediately from Claim 1. Claim 2. a) Any critical pair in τ of the type (_{1}x, y), (y,_{2} x), (_{2}x, y) or (y,_{3} x) is

(**)-removable modulo S(U).

b) Any critical pair in τ of the type (y,_{1} x), (y,_{2} x), (_{2}x, y) or (_{3}x, y) is (**)- removable modulo S(U).

Let us use the notion of coordinates here as we did in the proof of lemma 4.16. Since τ is a nontrivial identity, one of the following cases must hold.

Case 1. The coordinate of _{1}x in the left part of τ is smaller than its coordinate in the right part of τ.

Case 2. The coordinate of _{3}x in the left part of τ is smaller than its coordinate in the right part of τ.

Case 3. _{1}x and _{3}x have the same coordinates in both sides of τ, but the coordinate of _{2}x in L_{τ} is smaller than its coordinate in R_{τ}.

Let us consider all three cases for the semigroup S(U). Case analysis for S(V) is similar.

In Case 1, the left side of τ contains a subword _{1}x_{2}x or a critical pair of the type (_{1}x, y). Such a pair is removable by Claim 2. If L_{τ} contains _{1}x_{2}x then R_{τ} contains the same subword or a critical pair of the type (y,_{2} x). This critical pair is also removable by Claim 2. If both sides of τ contain _{1}x_{2}x, then R_{τ} contains a subword xxx or a critical pair of the type (_{2}x, y), which is removable by Claim 2. If R_{τ} contains xxx, then L_{τ} also contains xxx or a critical pair of type (y,_{3} x) which is also removable by Claim2. If both sides of τ contain xxx, then τ contains a critical pair which is (*)-removable by using identity xxxt = txxx.

Case 2 is similar to Case 1, because of the symmetry of U and V.

In Case 3, L_{τ} contains a critical pair (_{2}x, y) which is removable by Claim 2. The case analysis is finished. So, S(U) and S(V) satisfy all the conditions of lemma 4.16. Therefore, S(U)

and S(V) are finitely based.

To show that S(U ∪V) is not finitely based, for each set of letters A = {a_{1}, ..., a_{n}} consider the following identity τ_{n}.

[An]xt_{1}xt_{2}[nA]x = x[An]t_{1}xt_{2}x[nA]  (4.5)

Suppose that for some n = 1, 2, ..., τ_{n} does not hold in S(U ∪V). Then by lemma 4.6, there exists a substitution Θ such that Θ(xa_{i}) ≠ Θ(a_{i}x) and either Θ(L_{τ}) or Θ(R_{τ}) belongs to U or V. Since x appears 3 times in each side of τ_{n} and a_{i} occurs 2 times, Θ(x) = a and Θ(a_{i}) = b. But then Θ(L_{τ}) = baaba and Θ(R_{τ}) = abaab. Neither of this two words belongs to U ∪V. Therefore, S(U ∪V) satisfies the system of identities τ_{n}.

Fix a natural number m. Take n = 2m. Let us show that there is no m-derivation for τ_{n}. It is easy to check that each of the following words are isoterms for S(U ∪V): [An]t[nA], xt_{1}xt_{2}x, xyt_{1}xt_{2}yx and yxt_{1}xt_{2}xy.

This implies that if L_{τ} = W is a nontrivial identity of S(U ∪V), then W coincides with R_{τ}. Therefore, an m-derivation for τ_{n} must be a one step derivation.

But if there exists a one step m-derivation for τ_{n}, then S(U ∪ V) must satisfy the following identity:

t_{3}xt_{1}xt_{2}t_{4}x = xt_{3}t_{1}xt_{2}xt_{4}

It is easy to see that this identity is false in S(U ∪ V). For example, consider a substitution which takes x to a, t_{1} and t_{4} to b and sends all other letters to 1. Therefore, there is no m-derivation for τ_{n}. By lemma 4.17, S(U ∪ V) is not finitely based.

The theorem is proved.

Bibliography

[1] Aĭzenštat, A. Ja. Certain sublattices of the lattice of varieties of semigroups. (Russian) Modern algebra, No. 1 (Russian), pp. 3–15. Leningrad. Gos. Ped. Inst., Leningrad, 1974.

[2] A.P. Birjukov. Varieties of idempotent semigroups. (Russian) Algebra i Logika 9 (1970), 255–273.

[3] G. Birkhoff, On the structure of abstract algebra, Proc. Cambridge Philos. Soc., 28 (1935), 433-454.

[4] A. H. Clifford and G. Preston, The algebraic theory of semigroups, American Math. Soc., Providence, 1 (1961), 2 (1967).

[5] C.F. Fennemore. All varieties of bands. I, II. Math. Nachr. 48 (1971), 237–252; ibid. 48 (1971), 253-262.

[6] J. A. Gerhard. The lattice of equational classes of idempotent semigroups. J. Algebra 15 (1970) 195–224.

[7] J.A. Green, D. Rees. On semigroups in which x^{r} = x. Proc. Cambridge Phil. Soc., 48 (1952), 35-40.

[8] B. Jonsson, G. McNulty, R. Quackenbush. The ascending and descending varietal chains of a variety, Canadian J. Math., 1975, 27, 1, 25–31.

[9] O. Kharlampovich, M. Sapir. Algorithmic problems in varieties, Internat. J. Algebra and Comput., 4,5: 379–602, 1995.

[10] Korjakov, I. O. A sketch of the lattice of commutative nilpotent semigroup varieties. Semigroup Forum 24 (1982), no. 4, 285–317.

[11] A. I. Malcev. Nilpotent semigroups. Uchen. zap. Ivanovsk. ped. in-ta., 4 (1953), 107-111.

[12] R. McKenzie. Tarski’s finite basis problem is undecidable. Internat. J. Algebra Comput. 6: 49–104, 1996.

[13] G. McNulty. Infinite chains of non-finitely based equational theories of finite algebras. Algebra Univers. 13 (1981), 373-378.

[14] Oates, Sheila and Powell, M. B. Identical relations in finite groups. J. Algebra 1 (1964), 11–39.

[15] A. Yu. Olshanskii. Just-non-cross varieties of solvable groups. Mat. Sb. (N.S.) 85(127) (1971), 115–131.

[16] P. Perkins. Bases for equational theories of semigroups. J. Algebra 11 1969 298–314.

[17] A. N. Petrov, The ascending varieties chain of a variety of semigroups, Semigroup Forum, 1987, 35, 157–162.

[18] Pin, J.-E. Varieties of formal languages. With a preface by M.-P. Schtzenberger. Translated from the French by A. Howie. Foundations of Computer Science. Plenum Publishing Corp., New York, 1986.

[19] V. Rasin. Varieties of orthodox Cliffordian semigroups. Izv. Vyssh. Uchebn. Zaved. Mat., (1979), 140-151.

[20] M. Sapir. Inherently nonfinitely based finite semigroups. Mat. Sb., 133(2) (1987), 154–166.

[21] M. Sapir, On cross semigroup varieties and related questions. Semigroup Forum, 20(4) (1990), 120–132.

[22] L.N. Shevrin. On the theory of epigroups. I. (Russian) Mat. Sb. 185 (1994), no. 8, 129–160

[23] L. N. Shevrin and E. V. Sukhanov. Structural aspects of the theory of semigroup varieties. Izv. Vyssh. Uchebn. Zaved. Mat., 6 (1989), 3-39.

[24] L. N. Shevrin and M. V. Volkov. Identities of semigroups. Izv. Vyssh. Uchebn. Zaved. Mat., 11 (1985), 3-47.

[25] M. V. Volkov. On bases of identities of Brandt semigroups. Issled. algebr. system po svojstvam ih podsistem. (1985), 38-42.