Semigroups96.pdf

Lecture Notes on

SEMIGROUPS Tero Harju Department of Mathematics University of Turku FIN-20014 Turku, Finland

19961

1

Small corrections in 2010

Contents

1

Basic Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.1 Definitions and examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2 Subsemigroups and Direct Products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.3 Homomorphisms and transformations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.4 Partial orders and semilattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2

General Structure Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1 Quotients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Homomorphism theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Ideals and Rees congruences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

18 18 21 24

3

Free Semigroups and Presentations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1 Free semigroups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Presentations of semigroups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Embeddings into 2-generator semigroups . . . . . . . . . . . . . . . . . . . . . . . . . .

26 26 31 35

4

Combinatorial Topics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 The defect theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Ehrenfeucht’s conjecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Isbell’s Zig-Zag Theorem for Dominions . . . . . . . . . . . . . . . . . . . . . . . . . . .

37 37 40 49

5

Green’s Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 5.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 5.2 Green’s Lemma and Its Corollaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

6

Inverse Semigroups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.1 Regular Semigroups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Inverse Semigroups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3 Representations by Injective Partial Mappings . . . . . . . . . . . . . . . . . . . . . . 6.4 Congruences of Inverse semigroups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

61 61 63 67 70

Contents 6.5 Free Inverse Semigroups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.6 Concrete Free Inverse Semigroups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 76 80

Books on semigroups: A.H. Clifford and G.B. Preston, The algebraic theory of semigroups, Vol. I & II, Mathematical Surveys of the Amer. Math. Soc. 7 (1961 & 1967). [A two-volume ‘handbook’ on semigroups from their algebraic point of view.] P.M. Higgins, Techniques of semigroup theory, Oxford University Press, 1992 [Goes to the advanced topics rather fast. Contains up-to-date proofs for free inverse semigroups, topics on biordered sets, Isbell’s zig-zags, and some combinatorics of transformation semigroups.] J.M. Howie, An introduction to semigroup theory, Academic Press, 1976. [An easy introduction. See the next entry.] J.M. Howie, Fundamentals of semigroup theory, 1995. [Probably the best introduction. Contains more advanced material such as Isbell’s zig-zags, and the free inverse semigroups]. G. Lallement, Semigroups and combinatorial applications, Wiley, 1979. [Concentrates on combinatorial topics such as codes and free word semigroups, formal languages and related topics.] E.S. Lyapin, Semigroups, Translations of Math. Monographs, Vol 3, Amer. Math. Soc., 1974. [Easy to read.] M. Petrich, Introduction to semigroups, Merrill, 1973. [More advanced topics from the structural point of view.] M. Petrich, Lectures in semigroups, Wiley, 1977. [Bands, varieties, and lattices of varieties.] M. Petrich, Inverse semigroups, Wiley, 1984. [The bible on inverse semigroup.] M. Petrich and N.R. Reilly, Completely regular semigroups, in preparation. [A large book on one of the popular themes in semigroup theory.] Related books: J. Berstel and D. Perrin, Theory of Codes, Academic Press, 1985. [Formal languages, codes, word semigroups.] S. Burris and H.P. Sankappanavar, A course in universal algebra, Springer, 1981. [A good introduction to general properties of algebras.] P.M. Cohn, Universal algebra, Reidel, 1981. [A more comprehensive treatment of universal algebras.] S. Eilenberg, Automata, Languages, and Machines, Vol. A, Academic Press, 1974. [One of the basic books on automata.] M. Lothaire, Combinatorics on Words, Addison-Wesley, 1983. [Combinatorial topic on words and related areas.]

Contents

4

R.C. Lyndon and P. Schupp, Combinatorial group theory, Springer, 1977. [Contains some theory of free groups among other topics.] W. Magnus, A. Karrass and D. Solitar, Combinatorial group theory, Dover, 1976 [Contains some theory of free groups among other topics.] A. Salomaa and G. Rozenberg (eds), Handbook of formal languages, Vol. I, Springer, 1996. [A collection of survey articles by various authors on combinatorial topics on words, and formal languages in general. Includes two proofs of Ehrenfeucht’s conjecture; one of which is in these Lecture Notes. Includes also many other interesting results of combinatorial nature.]

1 Basic Concepts 1.1 Definitions and examples Semigroups Let S be a set and σ : S ×S → S a binary operation that maps each ordered pair (x, y) of S to an element σ(x, y) of S. The pair (S, σ) (or just S, if there is no fear of confusion) is called a groupoid. The mapping σ is called a product of (S, σ). We shall mostly write simply xy instead of σ(x, y). If we want to emphasize the place of the operation, then we often write x · y. The element xy (= σ(x, y)) is the product of x and y in S. We also use other notations for the product, when this is natural or otherwise convenient. In particular, the following symbols may be used: ·, +, ⋆, ◦, ⊕, ⊗. If we do not explicitly (or implicitly) mention the (notation for the) product, we choose the dot: x · y. A groupoid S is a semigroup, if the operation σ is associative: for all x, y, z ∈ S, x · (y · z) = (x · y) · z . That is, σ(x, σ(y, z)) = σ(σ(x, y), z) using the unfriendly notation. This means that the order in which the operation σ is carried out is irrelevant, and therefore we may write x1 x2 . . . xn = x1 · (x2 · (· · · · xn )) . . . ) . Of course, the order of the operands x1 , . . . , xn (where we can have repeated elements, xi = xj ), is important. For an element x ∈ S we let xn be the product of x with itself n times. So, x1 = x, 2 x = x · x, and xn+1 = x · xn for n ≥ 1. • S is a finite semigroup if it has only a finitely many elements. • S is a commutative semigroup, if it satisfies ∀x, y ∈ S : x · y = y · x . We let N = {0, 1, . . . } be the set of all non-negative integers, and N+ = {1, 2, . . . } the set of all positive integers. Example 1.1. (1) (N, ·) is a semigroup for the usual multiplication of integers, n · m. Also (N, +) is a semigroup, when + is the ordinary addition of integers. Define (N, ⋆) by n ⋆ m = max{n, m} .

1.1 Definitions and examples

6

(N, ⋆) is a semigroup, since n ⋆ (m ⋆ k) = max{n, max{m, k}} = max{n, m, k} = max{max{n, m}, k} = (n ⋆ m) ⋆ k . (2) The previous case generalizes to other familiar sets of numbers: (Z, ·), (Z, +), (Q, ·), (Q, +), (R, ·), (R, +), (C, ·), (C, +) of integers, rationals, reals and complex numbers. In the multiplicative cases one may remove the zero element 0 from the domain, and still obtain a semigroup. (3) Consider the upper triangular integer matrices    1 n S= n≥1 . 0 1

Then S is a semigroup with the usual matrix product. All the semigroups in the above examples have been commutative. (4) Let TX be the set of all functions α : X → X. Then (TX , ◦) is a semigroup, where ◦ is the composition of functions: (β ◦ α)(x) = β(α(x)) for all x ∈ X. (5) Let S = {a, b, c} be a set of three elements, and define the product in the table. Then S is a finite semigroup. In order to check this we should run · a b c through all the triples: x · (y · z) = (x · y) · z. In this case, there a a b c are some helpful restrictions in S. For instance, if z = c, then the b b a c product is always c no matter what x and y are. ⊔ ⊓ c c b c

Monoids and groups Let S (that is, (S, ·)) be a semigroup. An element x ∈ S is a left identity of S, if ∀y ∈ S : x · y = y . Similarly, x is a right identity of S, if ∀y ∈ S : y · x = y . If x is both a left and a right identity of S, then x is called an identity of S. A semigroup is a monoid, if it has an identity. Lemma 1.1. A semigroup S can have at most one identity. In fact, if S has a left identity x and a right identity y, then x = y. In particular, the identity of a monoid is unique. Proof. By the definitions, y = xy = x.

⊔ ⊓

1.1 Definitions and examples

7

The identity of a monoid S is usually denoted by 1S , or just by 1, for short. Of course, if the monoid S has an established identity, we do not change its notation. So, the identity of the monoid (N, +) is 0. For a semigroup S we define a monoid S 1 by adjoining an identity to S, if S does not have one: ( S if S is a monoid, 1 S = S ∪ {1} if S is not a monoid, where 1 is a (new) identity element. A monoid G is a group, if every x ∈ G has a (group) inverse x−1 ∈ G: x · x−1 = 1 = x−1 · x . Although semigroups and groups seem to be rather close to each other, semigroups lack the basic symmetry properties of groups, and therefore the general theory of semigroups differs quite a lot from the theory of groups. The theory of semigroups is more applicable in theoretical computer science and also in some parts of combinatorial mathematics.

Zeros and idempotents An element x ∈ S is a left zero, if ∀y ∈ S : x · y = x . Similarly, x is a right zero, if ∀y ∈ S : y · x = x . A zero element is both a left and a right zero of S. Lemma 1.2. A semigroup can have at most one zero. Proof. Exercise.

⊔ ⊓

An element e ∈ S is an idempotent, if e2 = e. The set of all idempotents of S is denoted by E = ES . Example 1.2. (1) Consider the finite semigroup S as defined above in Example 1.1(5). The element a is an identity of S, and hence S is a monoid. The element c is a right zero. There are no left zeros, and hence S does not have a zero. Both a and c are idempotents. Indeed, all left and right identities and zeros are idempotents. The element b is not an idempotent, since b2 = a. (2) The matrix semigroup from Example 1.1(3) has no idempotents let alone identities or zeros. (3) Consider the set of all n-by-n-matrices with integer entries. This is a monoid Zn×n . For instance,

1.1 Definitions and examples Z

2×2

8 

=

a b c d



a, b, c, d ∈ Z



.

The identity matrix I is the identity of Z2×2 and the zero matrix 0 is its zero:     0 0 1 0 . and 0 = I= 0 0 0 1   −1 −1 This monoid has quite many idempotents. As an example, is an idempotent. 2 2

(4) Let GL(n, R) denote the monoid of all nonsingular n-by-n-matrices A with real entries – so that det(A) 6= 0. Apart from the identity matrix GL(n, R) has no other idempotents, because it is a group, called the generalized linear group over R. Also the monoid SL(n, R) of all n-by-n-matrices A in Rn×n such that det(A) = 1 forms a group. This is the special linear group over R. (5) Let us define a product in a set S by ∀x, y ∈ S : x · y = x . We obtain thus a semigroup, where each element x ∈ S is a right identity and at the same time a left zero. Moreover, all the elements in this semigroup are idempotents, S = ES . ⊔ ⊓ Lemma 1.3. If G is a group, then EG = {1}. ⊔ ⊓

Proof. Exercise.

Example 1.3. For any two subsets A, B ⊆ S of a semigroup S, define their product by A · B = {a · b | a ∈ A, b ∈ B} . The so obtained binary operation is associative, and hence the subsets of S form a semigroup, the global semigroup of S. We denote this new semigroup by 2S . For a subset A ⊆ S, we let, as usual, A2 = A · A. ⊔ ⊓

Cancellation semigroups A semigroup S is left cancellative, if zx = zy =⇒ x = y , and S is right cancellative, if xz = yz =⇒ x = y . If S is both left and right cancellative, then it is cancellative.

1.2 Subsemigroups and Direct Products

9

Example 1.4. (1) All groups are cancellative semigroups. (2) Consider the matrix semigroup Z2×2 . Here       1 0 1 1 1 0 1 1 = , 0 0 1 1 0 0 0 0 and hence Z2×2 is not cancellative. However, if we take all matrices A with det(A) = 1, then this semigroup is cancellative. ⊔ ⊓

1.2 Subsemigroups and Direct Products Subsemigroups Let A 6= ∅ be a (nonempty) subset of a semigroup (S, ·). We say that (A, ·) is a subsemigroup of S, denoted by A ≤ S, if A is closed under the product of S: ∀x, y ∈ A : x · y ∈ A , that is, A ≤ S ⇐⇒ A2 ⊆ A . A subsemigroup uses the operation of its mother semigroup, and hence if A is a subsemigroup of S, then certainly the operation of A is associative, and thus A is a semigroup by its own right. Example 1.5. Consider the additive semigroup S = (Q, +) of rationals. Now, (N, +) is a subsemigroup of S, but (N, ·) is not, because its operation (multiplication) is not the operation of S. ⊔ ⊓ Lemma 1.4. Let Ai ≤ S be subsemigroups of S for all i ∈ I. If their intersection is nonempty, then \ Ai ≤ S . i∈I

Proof. Suppose the intersection is nonempty. If x, y ∈ A = ∩i∈I Ai , then x, y ∈ Ai for each i ∈ I, and hence xy ∈ A as required. ⊔ ⊓ For a subset X ⊆ S with X 6= ∅ denote \ [X]S = {A | X ⊆ A, A ≤ S} .

By Lemma 1.4, [X]S is a subsemigroup of S, called the subsemigroup generated by X. It is the smallest subsemigroup of S that contains X. Again, [X]S is sometimes written simply [X], if the semigroup S is clear from the context. When X is a singleton set, X = {x}, then we write [x]S rather than [{x}]S . More generally, if X = {x1 , x2 , . . . } is finite or infinite, then we write [x1 , x2 , . . . ]S instead of [{x1 , x2 , . . . }]S .

1.2 Subsemigroups and Direct Products

10

Theorem 1.1. Let X 6= ∅, X ⊆ S for a semigroup S. Then [X]S =

∞ [

X n = {x1 x2 . . . xn | n ≥ 1, xi ∈ X} .

n=1 n n Proof. Write A = ∪∞ n=1 X . It is easy to show that A ≤ S. Also, X ⊆ [X]S for all n ≥ 1, since [X]S ≤ S, and hence the claim follows. ⊔ ⊓

Example 1.6. (1) Let S be the finite semigroup from Example 1.1(5). Now, [a]S = {a, a2 , a3 , . . . } = {a}, and hence {a} is a subsemigroup of S. Also, [c]S = {c}. On the other hand, [b]S = {a, b} = [a, b]S , and [b, c]S = {a, b, c} = S. Here {b, c} generates the full semigroup S. (2) Consider the matrix semigroup S = Z2×2 , and let   0 1 M= . −1 0 Now, 2

M =



−1 0 0 −1



,

3

M =



0 −1 1 0



,

4

M =



1 0 0 1



,

M 5 = M,

and hence [M ]S = {I, M, M 2 , M 3 } is a finite subsemigroup of S. In fact, [M ]S is a subgroup of S, that is, a subsemigroup which is a group. Note that Z2×2 is not a group itself. ⊔ ⊓ We say that a subset X of a monoid M generates M (as a monoid), if [X]M = M or [X]M = M \ {1M }. Hence in a monoid the identity element is always taken into granted – a generator set need not produce it.

Index and period If X = {x} is a singleton subset of a semigroup S, then [x]S = {x, x2 , x3 , . . . }, is called a monogenic semigroup (also called a cyclic semigroup). Hence [x]S = {xn | n ≥ 1} consists of the positive powers of x. There are two possibilities for [x]S : Either it is an infinite monogenic semigroup, where xn 6= xm for all n 6= m, or there exists an integer k such that [x]S = {x, x2 , . . . , xk−1 }. In the latter case xk = xr for some 1 ≤ r ≤ k − 1. Here r is called the index and p = k − r the period of x. You should notice that xr+p = xr , xr+p+1 = xr+1 , . . . , xr+p+p = xr+p = xr , and so forth, that is, ∀n ≥ r : xn = xn+p . Lemma 1.5. Let r be the index and p the period of an element x ∈ S. Then Kx = {xr , xr+1 , . . . , xr+p−1 } is a subgroup (i.e., a subsemigroup that is a group) of S. Proof. A nontrivial exercise.

⊔ ⊓

1.3 Homomorphisms and transformations

11

Direct products The direct product S × T of two semigroups S and T is defined by (x1 , y1 ) · (x2 , y2 ) = (x1 x2 , y1 y2 )

(xi ∈ S, yi ∈ T ) .

It is easy to show that the so defined product is associative on the pairs (x, y) ∈ S × T , and hence the direct product is, indeed, a semigroup. Example 1.7. Let S = (N, +) and T = (N, ·). Then in the direct product S × T we have (n, r) · (m, s) = (n + m, rs). ⊔ ⊓ The direct product is a convenient way of combining two semigroup operations. The new semigroup S × T inherits properties of both S and T . The mappings π1 : S × T → S and π2 : S × T → T such that π1 (x, y) = x and π2 (x, y) = y are called the projections of the direct product S × T . In general S × T 6= T × S, as already verified in the previous example. However, the direct product operation is associative on semigroups: S × (T × U ) = (S × T ) × U , and hence we can define S1 ×S2 ×· · ·×Sn as the (finite) direct product of the semigroups Si .

1.3 Homomorphisms and transformations Definition Let (S, ·) and (P, ⋆) be two semigroups. A mapping α : S → P is a homomorphism, if ∀x, y ∈ S : α(x · y) = α(x) ⋆ α(y) . Thus a homomorphism respects the product of S while ‘moving’ elements to P (which may have a completely different operation as its product). However, a homomorphism may also identify elements: α(x) = α(y). Example 1.8. (1) Let S = (N, +) and P = (N, ·), and define α(n) = 2n for all n ∈ N. Now, α(n + m) = 2n+m = 2n · 2m = α(n) · α(m) , and hence α : S → P is a homomorphism. (2) Define S and P by the following tables: · a b c d

a a b c d

b b a d c

c c d c d

d d c d c

⋆ e f g

e e f g

f f e g

g g g g

1.3 Homomorphisms and transformations

12

These are semigroups – which is never too obvious! Define a mapping α : S → P , that identifies the elements c and d of S, as follows α(a) = e, α(b) = f, α(c) = g = α(d) . Now, a is the identity of S, and its image e = α(a) is the identity of P . Therefore for all x ∈ S, α(a · x) = α(x) = e ⋆ α(x) = α(a) ⋆ α(x), and similarly α(x · a) = α(x) ⋆ α(a). Also, the other cases can be checked easily to ensure that α is a homomorphism. (2) Let S be the semigroup of integers S = (Z, ·) under multiplication, and let P be the semigroup of integers P = (Z, +) under addition. Define a mapping α : S → P by α(n) = n for all n ∈ Z. Then α is not a homomorphism, because 6 = α(6) = α(2·3) 6= α(2) + α(3) = 5. (3) If α : S → P is a homomorphism, then α(xn ) = (α(x))n for all x ∈ S and n ≥ 1. ⊔ ⊓ Below we write for a subset X ⊆ S and for a mapping α : S → P , α(X) = {α(x) | x ∈ X} . Lemma 1.6. Let α : S → P be a homomorphism. If X ⊆ S, then α([X]S ) = [α(X)]P . Proof. If x ∈ [X]S , then, by Lemma 1.1, x = x1 x2 . . . xn for some xi ∈ X. Since α is a homomorphism, α(x) = α(x1 )α(x2 ) . . . α(xn ) ∈ [α(X)]P , and so α([X]S ) ⊆ [α(X)]P . On the other hand, if y ∈ [α(X)]P , then, again by Lemma 1.1, y = α(x1 )α(x2 ) . . . α(xn ) for some α(xi ) ∈ α(X) (xi ∈ X). The claim follows now, since α is a homomorphism: y = α(x1 x2 . . . xn ), where x1 x2 . . . xn ∈ [X]S . ⊔ ⊓ Corollary 1.1. If A ≤ S and α : S → P is a homomorphism, then α(A) ≤ P . ⊔ ⊓

Proof. Immediate from the previous lemma.

Lemma 1.7. If α : S → P and β : P → T are homomorphisms, then so is βα : S → T . Proof. Indeed, for all x and y, βα(x · y) = β(α(x · y)) = β(α(x) · α(y)) = β(α(x)) · β(α(y)) = βα(x) · βα(y). ⊔ ⊓ For a mapping α : S → P we denote by α↾X the restriction of α to the subset X ⊆ S, that is, α↾X : X → P is defined by (α↾X)(x) = α(x)

(x ∈ X) .

The following result states that two homomorphisms are the same if they map the generators in the same way.

1.3 Homomorphisms and transformations

13

Theorem 1.2. Let α, β : S → P be two homomorphisms and let X ⊆ S. Then α↾X = β↾X ⇐⇒ α↾[X]S = β↾[X]S .

Proof. Exercise.

⊔ ⊓

Isomorphism and embeddings A homomorphism α : S → P is • an embedding or a monomorphism, denoted α : S ֒→ P , if it is injective, that is, if α(x) = α(y) implies x = y; • an epimorphism, denoted α : S ։ P , if it is surjective, that is, if for all y ∈ P there exists an x ∈ S with α(x) = y; • an isomorphism, denoted α : S ֌ P , if it is both an embedding and an epimorphism; • an endomorphism, if P = S; • an automorphism, if it is both an isomorphism and an endomorphism. Lemma 1.8. If α : S → P is an isomorphism, then also the inverse map α−1 : P → S is an isomorphism. Proof. First of all the inverse mapping α−1 exists, because α is a bijection. Furthermore, αα−1 = ι, and thus because α is a homomorphism, α(α−1 (x) · α−1 (y)) = α(α−1 (x)) · α(α−1 (y)) = xy , and so α−1 (x) · α−1 (y) = α−1 (xy), which proves the claim.

⊔ ⊓

A semigroup S is embeddable in another semigroup P , if there exists an embedding α : S ֒→ P , and S is isomorphic to P , denoted S ∼ = P , if there exists an isomorphism α : S ֌ P . Two isomorphic semigroups share their algebraic properties (but they may differ in their combinatorial properties). Example 1.9. (1) Let S be an infinite monogenic semigroup, that is, S is generated by one element S = [x] = {x, x2 , x3 , . . . }. Define α : S → (N+ , +) by α(xn ) = n. Now, α is a homomorphism, since α(xn · xm ) = α(xn+m ) = n + m = α(xn ) + α(xm ). Moreover, α is a bijection, and thus an isomorphism. Therefore, S ∼ = (N+ , +). In conclusion, each infinite monogenic semigroup is isomorphic to the additive semigroup of positive integers. (2) If P ≤ S, then the inclusion mapping ι : P → S, ι(x) = x, is a homomorphism, and it is injective (but need not be surjective). Therefore ι is an embedding (of P into S). In particular, the identity function ι : S → S, ι(x) = x, is always an automorphism, the trivial automorphism, of S. ⊔ ⊓

1.3 Homomorphisms and transformations

14

The endomorphisms of a semigroup S are closed under composition, that is, if α, β : S → S are endomorphisms, then so is βα. The same holds true for automorphisms. Theorem 1.3. 1. The endomorphisms of a semigroup S form a monoid. 2. The automorphisms of a semigroup S form a group. ⊔ ⊓

Proof. Exercise.

The full transformation semigroup Let X be again a set, and denote by TX the set of all functions α : X → X. Then TX is the full transformation semigroup on X with the operation of composition of functions. Example 1.10. Let X = {1, 2, 3}. There are altogether 33 = 27 functions in TX . A mapping α : X → X, which is defined by α(1) = 2, α(2) = 3 and α(3) = 3, can be represented conveniently in two different ways:   123 α= 233 or

α

α

1 → 2 → 3. Let then β=



123 112



,

and S = [α, β]TX the subsemigroup of TX generated by α and β. We have then       123 123 123 2 2 α = β = βα = 333 111 122     123 123 = α2 β . βα2 = αβ = 222 223 One may check that there are no other elements in this semigroup, and hence S has seven elements, S = {α, β, α2 , β 2 , αβ, βα, βα2 }. ⊔ ⊓

Representations A homomorphism ϕ : S → TX is a representation of the semigroup S. We say that ϕ is a faithful representation, if it is an embedding, ϕ : S ֒→ TX . The following theorem states that semigroups can be thought of as subsemigroups of the full transformation semigroups, that is, for each semigroup S there exists a set X such that S ∼ = P ≤ TX for a subsemigroup P of transformations.

1.3 Homomorphisms and transformations

15

Theorem 1.4. Every semigroup S has a faithful representation. Proof. Let X = S 1 , that is, add the identity 1 to S if S is not a monoid. Consider the full transformation semigroup T = TS 1 . For each x ∈ S define a mapping ρx : S 1 → S 1 ,

ρx (y) = xy

(y ∈ S 1 ) .

Thus ρx ∈ T , and for all x, y ∈ S and for all z ∈ S 1 , ρxy (z) = (xy)z = ρx (yz) = ρx (ρy (z)) = ρx ρy (z) , and hence ρxy = ρx ρy . Consequently, the mapping ϕ : S → T,

ϕ(x) = ρx

is a homomorphism. For injectivity we observe that ϕ(x) = ϕ(y) =⇒ ρx = ρy =⇒ ρx (1) = ρy (1) =⇒ x = y . ⊔ ⊓ In the previous proof the special element 1 is needed (only) to ensure injectivity of ϕ. It is needed, because there exists a semigroup S (without identity) that has two left identities x 6= y. In such a case, xz = yz for all z ∈ S. Hence, loosely speaking (by Theorem 1.4) the theory of semigroups can be taught of as the theory of transformations. This situation is reflected in a more restricted manner in the theory of groups, where we have the following fundamental theorem of representations. Theorem 1.5 (Cayley). Each group can be represented faithfully as a (semi)group of permutations (bijections X → X). ⊔ ⊓

Proof. Exercise. Example 1.11. Let S = {e, a, b, c} (see the table). By the above definitions we obtain the following faithful representation ϕ : S → T{e,a,b,c} for S. Notice that the mappings ρx are just the rows of the multiplication table on the right.  e a bc , ϕ(e) = e a bc   eabc , ϕ(b) = b b bb 

· e a b c

e e a b c

a a e b c

b b c b c

c c b b c

 eabc , ϕ(a) = a e cb   e ab c . ϕ(c) = c c cc 

The representation ϕ is by no means unique. Consider ϕ1 : S → T{1,2} defined by         12 12 12 12 ϕ1 (e) = , ϕ1 (a) = , ϕ1 (b) = , ϕ1 (c) = . 12 21 11 22

One may check that this simpler ϕ1 also represents S by checking that the transformations ϕ1 (x) satisfy the multiplication table of S. ⊔ ⊓

1.4 Partial orders and semilattices

16

1.4 Partial orders and semilattices Equivalences Let X be a nonempty set. A subset δ ⊆ X × X is a relation on X. We shall write both (x, y) ∈ δ and xδy to denote that the (ordered) pair (x, y) is in relation δ. Let B(X) be the set of all relations on X. This set forms a monoid under the operation of composition: ρ ◦ δ = {(x, y) ∈ X × X | ∃z : (x, z) ∈ ρ, (z, y) ∈ δ} . The identity element of B(X) is the identity relation ι = ιX = {(x, x) | x ∈ X}. (It is the identity function on X). The universal relation of B(X) is the relation ω = ωX = X × X = {(x, y) | x, y ∈ X}. Let δ ∈ B(X) and assume Y ⊆ X. We adopt the following notations: [ xδ = {y | (x, y) ∈ δ}, Y δ = yδ, ran(δ) = Xδ, dom(δ) = Xδ−1 , y∈Y

where δ−1 = {(y, x) | (x, y) ∈ δ}. In particular, δ ⊆ dom(δ) × ran(δ). A relation δ ∈ B(X) is an equivalence relation, if its is reflexive (ιX ⊆ δ), symmetric (δ−1 = δ) and transitive (δ2 ⊆ δ). The sets xδ are called equivalence classes (with respect to δ), and they form a partition of the set X: [ X= xδ and xδ ∩ yδ 6= ∅ ⇐⇒ xδ = yδ . x∈X

A relation δ ∈ B(X) is a partial order, if it is reflexive, antisymmetric (δ∩δ−1 ⊆ ι) and transitive. A partial order is often denoted by the symbols ≤ or ⊆ (with or without indices).

Semilattice of idempotents The idempotents ES of a semigroup can be given a partial order (if ES 6= ∅) as follows. Define for e, f ∈ ES : e ≤ f ⇐⇒ ef = e = f e . Lemma 1.9. The relation ≤ is a partial order on ES . Proof. First of all, for all e ∈ ES , e2 = e, and so e ≤ e (reflexive). If e ≤ f and f ≤ e, then e = ef = f (antisymmetric). If e ≤ f and f ≤ h, then e = ef = ef h = eh and so also e ≤ h (transitive).

and

e = f e = hf e = he , ⊔ ⊓

1.4 Partial orders and semilattices

17

If S is a commutative semigroup and all its elements are idempotents (S = ES ), then S is called a semilattice. Hence, in this case, for all x, y ∈ S: x2 = x and xy = yx. The relation ≤ on idempotents is defined on the whole of a semilattice S. An element g is a lower bound of elements e and f , if g ≤ e and g ≤ f . Lemma 1.10. Let S be a semilattice. Then ef ∈ S is the greatest lower bound of the elements e and f of S. Proof. Let e, f ∈ S. Then ef = f e = f f e = ef f , and so (ef )f = ef = f (ef ), which means that ef ≤ f . Similarly, ef ≤ e holds, and thus ef is a lower bound of e and f . If g is also a lower bound of e and f , then g = gf = ge, and therefore g(ef ) = (ge)f = gf = g , and hence g ≤ ef . Hence ef ∈ S is the greatest lower bound of the elements e and f in the semilattice S. ⊔ ⊓

2 General Structure Results 2.1 Quotients Congruences An equivalence relation ρ on a semigroup S is a left congruence, if ∀x, y, z ∈ S : xρy =⇒ (zx)ρ(zy) . Similarly, ρ is a right congruence, if ∀x, y, z ∈ S : xρy =⇒ (xz)ρ(yz) and ρ is a congruence, if it both a left and a right congruence. Recall that an equivalence relation ρ partitions the domain S into the equivalence classes xρ (x ∈ S). An equivalence class of a congruence is called a congruence class. If ρ is a congruence, then it respects the product of S, that is, if the elements x1 , y1 and x2 , y2 are in the same equivalence class (i.e., x1 ρ = y1 ρ and x2 ρ = y2 ρ), then x1 x2 and y1 y2 are in the same equivalence class. A formal statement of this is in the following lemma.

x1 y1

x1 · x2

y1 · y2 x2 y2

Lemma 2.1. An equivalence relation ρ on S is a congruence if and only if for all x1 , x2 , y1 , y2 ∈ S:  x1 ρy1 =⇒ (x1 x2 )ρ(y1 y2 ) . x2 ρy2 Proof. Suppose first that ρ is a congruence. If x1 ρy1 and x2 ρy2 , then, by the definition, (x1 x2 )ρ(x1 y2 ) and (x1 y2 )ρ(y1 y2 ) and hence also (x1 x2 )ρ(y1 y2 ) by transitivity. In the converse direction the claim is trivial. ⊔ ⊓

2.1 Quotients

19

Syntactic congruences We say that a congruence ρ saturates a subset X ⊆ S, if X is a union of congruence classes of ρ. Lemma 2.2. A congruence ρ saturates X ⊆ S if and only if [ X= xρ .

(2.1)

x∈X

Proof. Since x ∈ xρ, X is always included in the union of (2.1). Consequently, if ρ saturates X, then X equals the union in (2.1). In converse the claim is also trivial. ⊔ ⊓ Let X be a subset of a semigroup S. Define a relation ΓX as follows: (x, y) ∈ ΓX if and only if ∀u, v ∈ S 1 : uxv ∈ X ⇐⇒ uyv ∈ X . Lemma 2.3. For all X ⊆ S the relation ΓX is a congruence, called the syntactic congruence of X in S. It is the largest congruence that saturates X. Proof. We leave it as an exercise to show that ΓX is an equivalence relation. Write Γ = ΓX . Assume that xΓ y holds, and let z ∈ S and u, v ∈ S 1 . Now, u(zx)v = (uz)xv and u(zy)v = (uz)yv, and hence (when the definition of ΓX is applied to uz ∈ S 1 and v ∈ S 1 ), u(zx)v ∈ X implies that u(zy)v ∈ X. The same argument gives that if u(zy)v ∈ X, then u(zx)v ∈ X; and also that u(xz)v ∈ X if and only if u(yz)v ∈ X. Hence zxΓ zy and xzΓ yz. This shows that Γ is a congruence. Certainly, X is included in the union of all xΓ (x ∈ X). Moreover, if y ∈ xΓ , then by choosing u = 1 = v in the definition of Γ we obtain: x ∈ X implies y ∈ X. Hence xΓ ⊆ X for all x ∈ X. We have shown that X is the union as required in the claim. We still have to show that Γ is the largest such congruence. Assume ρ is any congruence of S that saturates X. By Lemma 2.2, [ X= xρ . x∈X

Assume xρy holds, and let u, v ∈ S 1 be any elements. By Lemma 2.3, also (ux)ρ(uy), and, by the same lemma, (uxv)ρ(uyv). Hence (uxv)ρ = (uyv)ρ, from which it follows that uxv ∈ X if and only if uyv ∈ X, since ρ saturates X. Thus xΓ y, and so ρ ⊆ Γ as required. ⊔ ⊓

2.1 Quotients

20

Quotients Let ρ be a congruence of S, and let S/ρ = {xρ | x ∈ S} be the set of all congruence classes of ρ. We define a new semigroup, the quotient semigroup (of S modulo ρ), on the domain S/ρ by xρ · yρ = (xy)ρ . This is a well defined binary operation by Lemma 2.1, and its associativity is easily checked: xρ · (yρ · zρ) = xρ · (yz)ρ = (x(yz))ρ = ((xy)z)ρ = (xy)ρ · zρ = (xρ · yρ) · zρ . The quotient S/ρ is thus obtained from S by contracting each congruence class xρ into a single element. b =•yi ρ

y1 z1 z2 z3

x2 x1 u1

u2

• c = zi ρ

a = xi ρ•

• d = ui ρ S/ρ

S

Example 2.1. (1) Consider the finite semigroup S defined in the leftmost table. Here e and f are idempotents. Indeed, e is an identity of S. · e a f b

e e a f b

a a e b f

f f b f b

b b f b f

· c d g

c c d g

d d c g

g g g g

Let ρ be the relation, where apart from the relations xρx (x ∈ S), we have only f ρb and bρf . Then ρ is a congruence of S, and its congruence classes (with a short hand notations) are: c = {e}, d = {a} and g = {f, b}. The multiplication table for the quotient semigroup S/ρ is given in the second table. Also, the symmetric relation ρ′ (with ιS ⊆ ρ′ ) so that eρ′ a and f ρ′ b, is a congruence. It has only two congruence classes, {e, a} and {f, b}, and hence the quotient S/ρ′ is a semigroup having two elements.

2.2 Homomorphism theorem

21

The symmetric relation ρno (with ιS ⊆ ρno ) so that aρno b is not a congruence, because a · a = e and a · b = f in S, but eρno f does not hold. In this case, ρno does not respect the product of S: aρno b holds, but (aa)ρno (ab) does not hold. (2) Consider the semigroup S = (Z, +). If ρ is a congruence on S, then nρm implies that (n + k)ρ(m + k) holds for all integers k, by the definition of a congruence. Suppose that k is the smallest non-negative integer such that nρ(n + k) for some n ∈ Z. In particular, (n − n)ρ(n + k − n), i.e., 0ρk. Denote by m the remainder of m when divided by k: 0 ≤ m ≤ m and m ≡ m (mod k). By above mρm. Also the converse holds, and thus the congruences of (Z, +) are exactly the ordinary number theoretic congruences, ρ equals mod k (k ≥ 0). ⊔ ⊓ We prove now that the congruences of a semigroup S are closed under intersections. Lemma T 2.4. 1. If ρi is a congruence of S for each i ∈ I, then so is the intersection i∈I ρi . 2. Let δ ⊆ S × S be a relation, then \ δc = {ρ | δ ⊆ ρ, ρ a congruence of S} is the smallest congruence of S that contains δ.

Proof. Denote ρ = ∩i∈I ρi for the congruences ρi (i ∈ I). Assume xρy and z ∈ S, then also xρi y for all i ∈ I, and hence (zx)ρi (zy) and (xz)ρi (yz), which implies that (zx)ρ(zy) and (xz)ρ(yz). Therefore ρ is a congruence of S. For the other claim we observe first that δc is a congruence, since it is an intersection of congruences. If ρ is any congruence such that δ ⊆ ρ, then ρ takes part in the intersection, and thus δc ⊆ ρ. The claim follows from this. ⊔ ⊓

2.2 Homomorphism theorem Natural homomorphisms For a congruence ρ, define a mapping ρ♯ : S → S/ρ as follows ρ♯ (x) = xρ . Theorem 2.1. Let ρ be a congruence of S. The mapping ρ♯ is an epimorphism, called the natural epimorphism. Proof. Let x, y ∈ S. Now, ρ♯ (xy) = (xy)ρ = xρ · yρ = ρ♯ (x)ρ♯ (y), and hence ρ♯ is a homomorphism. On the other hand, if u = xρ ∈ S/ρ, then clearly ρ♯ (x) = u, and therefore ρ♯ is surjective. ⊔ ⊓

2.2 Homomorphism theorem

22

For a homomorphism α : S → P we define its kernel as the relation ker(α) = {(x, y) | α(x) = α(y)} . One could also set ker(α) = αα−1 , where α−1 (y) = {x ∈ S | α(x) = y}, and αα−1 is thought as a product of relations. (Functions are read from right to left, and relations from left to right; this causes some complications while writing compositions). Lemma 2.5. For each homomorphism α : S → P , ker(α) is a congruence of S. Proof. We leave it as an exercise to show that ker(α) is an equivalence relation. Let (x, y) ∈ ker(α), that is, α(x) = α(y). Now, for all z ∈ S, α(zx) = α(z)α(x) = α(z)α(y) = α(xy) , and similarly, α(xz) = α(yz). This proves the claim.

⊔ ⊓

Lemma 2.6. If ρ is a congruence of S, then ρ = ker(ρ♯ ). Proof. Indeed, xρy ⇐⇒ xρ = yρ ⇐⇒ ρ♯ (x) = ρ♯ (y) ⇐⇒ (x, y) ∈ ker(ρ♯ ) . ⊔ ⊓ Corollary 2.1. Every congruence is a kernel of some homomorphism. Example 2.2. Often homomorphisms are much easier to handle that congruences. Consider S = (N, +). If α : S → P is a homomorphism, then α(n) = α(1 + 1 + · · · + 1) = α(1) + α(1) + · · · + α(1) = nα(1) . In particular, α(0) = 0. This implies that α depends only on 1. (Of course, this follows already from the fact that 1 generates (N, +)). It is now easy to show that ker(α) equals mod k for some k. ⊔ ⊓

Homomorphism theorem Theorem 2.2. Let α : S → P be a any homomorphism. There exists a unique embedding β : S/ ker(α) ֒→ P such that the following diagram commutes. α -P S 

ker(α)♯

R

β

S/ ker(α) A commuting diagram: α = β ◦ ker(α)♯ .

2.2 Homomorphism theorem

23

Proof. Let ρ = ker(α), and ρ♯ : S → S/ρ the corresponding natural homomorphism. Define β : S/ρ → P by β(xρ) = α(x) (x ∈ S) . First of all, β is well defined, that is, it is a function, because xρ = yρ ⇐⇒ (x, y) ∈ ker(α) ⇐⇒ α(x) = α(y) ⇐⇒ β(xρ) = β(yρ) , (2.2) and so β(xρ) has a specific value (in P ), which is independent of the choice of the representative of the congruence class xρ. Secondly, β is a homomorphism, since β(xρ · yρ) = β((xy)ρ) = α(xy) = α(x)α(y) = β(xρ)β(yρ) . Thirdly, β is injective by (2.2). Finally, β is unique, since if γ : S/ρ → P is another such embedding, then α = γρ♯ , and hence α(x) = γ(xρ) for all x ∈ S. But this means that γ = β. ⊔ ⊓ The previous theorem has the following improvement. Theorem 2.3 (Homomorphism theorem). Let α : S → P homomorphism and ρ ⊆ ker(α) a congruence of S. Then there exists a unique homomorphism β : S/ρ → P such that the following diagram commutes. α -P S 

ρ♯

R

β

S/ρ Proof. The proof is quite similar to the previous one. Here we observe that the mapping β defined by β(xρ) = α(x) is well defined, since xρ = yρ =⇒ xρy =⇒ (x, y) ∈ ker(α) =⇒ α(x) = α(y) , since ρ ⊆ ker(α).

⊔ ⊓

The homomorphism theorem, as well as the next isomorphism theorem, are standard (universal) algebraic results, that is, they hold in all algebras (groups, rings, Boolean algebras, and so on). Below α(S) is the image semigroup of S in P . In particular, α(S) ≤ P , by Lemma 1.1. Theorem 2.4 (Isomorphism theorem). Let α : S → P be a homomorphism. Then α(S) ∼ = S/ ker(α) .

2.3 Ideals and Rees congruences

24

Proof. The homomorphism α is surjective as a homomorphism S → α(S) ≤ P . When Theorem 2.2 is applied to α : S → α(S) we obtain a unique embedding β : S/ ker(α) → α(S). Moreover, β is surjective, since α is surjective onto α(S) and α = βγ for the homomorphism γ = ker(α)♯ . Consequently, β is a bijective homomorphism, i.e., an isomorphism. ⊔ ⊓

2.3 Ideals and Rees congruences Ideals A nonempty subset I of a semigroup S is • a left ideal, if SI ⊆ I; • a right ideal, if IS ⊆ I; • an ideal, if it is both a left and a right ideal. Lemma 2.7. A nonempty subset I ⊆ S is 1. a left ideal of S, if for all a ∈ I and x ∈ S, sa ∈ I; 2. a right ideal of S, if for all a ∈ I and x ∈ S, as ∈ I; 3. an ideal of S, if for all a ∈ I and x ∈ S, as, sa ∈ I. ⊔ ⊓

Proof. Exercises. Lemma 2.8. If I is a (left or a right) ideal of S, then I is a subsemigroup of S. Proof. If SI ⊆ I or IS ⊆ I, then certainly II ⊆ I, since I ⊆ S.

⊔ ⊓

Lemma 2.9. If I and J are left (right) ideals of a semigroup S with I ∩ J 6= ∅, then I ∩ J is a left (right) ideal. Proof. Let a ∈ I ∩ J and x ∈ S. Then sa ∈ I and sa ∈ J, since I and J are ideals, and so sa ∈ I ∩ J. Hence (I ∩ J)S ⊆ (I ∩ J). ⊔ ⊓

Rees congruences Let I be an ideal of S. Define the Rees congruence (with respect to I) as follows: ρI = I × I ∪ ι . Hence xρI y holds if and only if either x, y ∈ I or x = y. This means that ρI contracts the ideal I and leaves the rest of S as it was. Lemma 2.10. The relation ρI is a congruence for every ideal I of S. Proof. Exercise.

⊔ ⊓

2.3 Ideals and Rees congruences

25

The quotient semigroup S/ρI will be denoted simply S/I, and it is called the Rees quotient (of the ideal I). S/I has the elements I and {x} for x ∈ S \ I. In order to simplify notation we identify the element {x} (= xρI ) with the element x ∈ S \ I. The product of elements in S/I is as follows: x · y = xy for x, y ∈ / I, and Ix = I = xI for all x. Therefore I is a zero element of the semigroup S/I.

Minimal ideals An ideal I of S is said to be minimal, if for all ideals J of S, J ⊆ I implies that J = I. Lemma 2.11. If I is a minimal ideal, and J is any ideal of S, then I ⊆ J. Proof. First of all, I ∩ J 6= ∅. Indeed, by the definition of an ideal IS ⊆ I, and hence also IJ ⊆ I. Similarly, IJ ⊆ J, and so IJ ⊆ I ∩ J. Here, of course, IJ 6= ∅. Now, I ∩ J ⊆ I implies that I ∩ J = I, since I is a minimal ideal, and I ∩ J is an ideal. It follows that I ⊆ J as required. ⊔ ⊓ By the above Theorem 2.5. If a semigroup S has a minimal ideal, then it is unique. Every finite semigroup S does have a minimal ideal. Indeed, consider an ideal I, which has the least number of elements. Such an ideal exists because S is finite and S is its own ideal. Example 2.3. The ideals of the semigroup (N, +) are exactly the sets n + N = {n + k | k ≥ 0} (Exercise). Further, m + N ⊆ n + N if and only if m ≥ n. Therefore (N, +) has no minimal ideals. ⊔ ⊓

Simple semigroups A semigroup S is said to be simple, if it has no ideals I 6= S. Lemma 2.12. S is simple if and only if S = SxS for all x ∈ S. Proof. Clearly, for any x ∈ S, SxS is an ideal of S, and hence if S is simple, then S = SxS for all x ∈ S. In converse, assume S = SxS for all x ∈ S. Let I is an ideal of S and let x ∈ I. Hence S = SxS ⊆ I, and so I = S, from which it follows that S is simple. ⊔ ⊓ Example 2.4. By the above, a semigroup S is simple if and only if for all s, r ∈ S the equation xsy = r has a solution in S. Using this one can show that the semigroup of all 2-by-2-matrices   x 0 (x, y ∈ Q with x, y > 0) y 1 is a simple semigroup. This is an exercise.

⊔ ⊓

3 Free Semigroups and Presentations 3.1 Free semigroups Word semigroups Let A be a set of symbols, called an alphabet. Its elements are letters. Any finite sequence of letters is a word (or a string) over A. The set of all words over A, with at least one letter, is denoted by A+ . For clarity, we shall often write u ≡ v, if the words u and v are the same (letter by letter). The set A+ is a semigroup, the word semigroup over A, when the product is defined as the catenation of words, that is, the product of the words w1 ≡ a1 a2 . . . an , w2 ≡ b1 b2 . . . bm (ai , bi ∈ A) is the word w1 · w2 = w1 w2 ≡ a1 a2 . . . an b1 b2 . . . bm . When we join the empty word 1 (which has no letters) into A+ , we have the word monoid A∗ , A∗ = A+ ∪ {1}. Clearly, 1 · w = w = w · 1 for all words w ∈ A∗ . Example 3.1. Let A = {a, b} be a binary alphabet. Then a, b, aa, ab, ba, bb, aaa, aab, . . . are words in A+ . Now, ab · bab ≡ abbab. As usual, wk means the catenation of w with itself k times, and so, for example, v ≡ ab3 (ba)2 ≡ abbbbaba ≡ ab4 aba. ⊔ ⊓

Free semigroups Let S be a semigroup. A subset X ⊆ S generates S freely, if S = [X]S and every mapping α0 : X → P (where P is any semigroup) can be extended to a homomorphism α : S → P such that α↾X = α0 . Here we say that α is a homomorphic extension of the mapping α0 . If S is freely generated by some subset, then S is a free semigroup. Example 3.2. (1) (N+ , +) is free, for X = {1} generates it freely: Let α0 : X → P be a homomorphism, and define α : N+ → P by α(n) = α0 (1)n . Now, α↾X = α0 , and α is a homomorphism: α(n + m) = α0 (1)n+m = α0 (1)n · α0 (1)m = α(n) · α(m). (2) On the other hand, (N+ , ·) is not free. For, suppose X ⊆ N+ , choose P = (N+ , +), and let α0 (n) = n for all n ∈ X. If α : (N+ , ·) → P is any homomorphism, then α(n) = α(1 · n) = α(1) + α(n), and thus α(1) = 0 ∈ / P . So certainly no α can be an extension of α0 . (3) Let S = {a, a2 } be a monogenic semigroup with index 2 and period 1, that is, a3 = a2 . If X generates S, then necessarily a ∈ X (since a is not a product of two elements of S). Let α0 : S → P = (N+ , +) be such that α0 (a) = 1. If α : S → P is an extension of α0 , then α(aa) = α(a) + α(a) = α0 (a) + α0 (a) = 2 and similarly α(aaa) = 3. However, aa = aaa in S, and this is a contradiction. Thus S is not free. ⊔ ⊓

3.1 Free semigroups

27

The word semigroups are free: Theorem 3.1. For any alphabet A, A+ is a free semigroup, and it is freely generated by A. Proof. Clearly, A generates A+ , since all words are strings of letters from A. Let then S be any semigroup, and α0 : A → S any mapping. We define α : A+ → S by α(a1 a2 . . . an ) = α0 (a1 )α0 (a2 ) . . . α0 (an )

(n ≥ 1, ai ∈ A) .

Clearly, α↾A = α0 , and α is a homomorphism by its definition.

⊔ ⊓

Theorem 3.2. If S is freely generated by X and α0 : S → P is a mapping, then α0 has a unique homomorphic extension α : S → P . Proof. By the definition, each α0 has an extension. For the uniqueness suppose both α : S → P and β : S → P are homomorphic extensions of α0 . Now, for all x ∈ S, x = x1 x2 . . . xn for some xi ∈ X, since X generates S. Therefore, α(x) =α(x1 )α(x2 ) . . . α(xn ) = α0 (x1 )α0 (x2 ) . . . α0 (xn ) = β(x1 )β(x2 ) . . . β(xn ) = β(x) , ⊔ ⊓

and so α = β.

The next result states that every semigroup S is a homomorphic image of a word semigroup, and therefore the word semigroups are basic semigroups wherefrom all other semigroups can be derived. Two sets X and Y have the same cardinality, denoted |X| = |Y |, if there is a bijection α : X → Y . In this case the function α−1 : Y → X is also a bijection, and so there is a 1-to-1 correspondence between the elements of X and Y . If X is finite, then |X| = |Y | if and only if X and Y have exactly the same number of elements. However, for infinite sets we cannot ‘count’ the number of elements. Indeed, |N| = |Q|, although N ⊂ Q properly. Theorem 3.3. For each semigroup S there exists an alphabet A and an epimorphism ψ : A+ ։ S. Proof. Let X be any generating set of S; you may even choose X = S. Let A be an alphabet with |A| = |X|, and let ψ0 : A → X be a bijection. By definition of freeness, ψ0 has a homomorphic extension ψ : A+ → S. This extension is surjective, since [ψ(X)]S = ψ([X]S ) = ψ(S), for X generates S. ⊔ ⊓ Corollary 3.1. Every semigroup is a quotient of a free semigroup. Indeed, S∼ = A+ / ker(ψ) for a suitable epimorphism ψ.

3.1 Free semigroups

28

There are other free semigroups than the word semigroups, but all of them are isomorphic to word semigroups. Theorem 3.4. A semigroup S is free if and only if it is isomorphic to a word semigroup A+ for some alphabet A. Proof. Suppose S is freely generated by a subset X ⊆ S, and let A be an alphabet with |A| = |X|. Let ψ0 : A → X be a bijection. Since A generates A+ freely there is an epimorphic extension ψ : A+ ։ S as in the previous theorem. Also, the mapping ψ0−1 : X → A is a bijection, which has an epimorphic extension β : S ։ A+ , since S is freely generated by X. The composition βψ : A+ → A+ is an epimorphism, for which βψ↾A = βψ0 = (β↾X)ψ0 = ψ0−1 ψ0 = ιA . Now, the mapping ιA : A → A extends uniquely to the identity homomorphism ιA+ : A+ → A+ , and hence βψ↾A extends also uniquely to ιA+ , that is, βψ = ιA+ . It follows from this that β = ψ −1 and that ψ is a bijection, and thus an isomorphism. On the other hand, suppose that there exists an isomorphism ψ : A+ → S. In this case, S = [ψ(A)]S , and ψ has an inverse mapping ψ −1 : S → A+ , which is a homomorphism (an isomorphism, by Lemma 1.8). Denote ψ0 = ψ↾A and X = ψ(A). Let P be any semigroup, and α0 : X → P any mapping. Now, the mapping α0 ψ0 : A → P extends uniquely to a homomorphism γ : A+ → P . Consider the mapping β = γψ −1 : S → P . This is a homomorphism, since both ψ −1 and γ are. Further, for each x ∈ X, β(x) = γ(ψ −1 (x)) = α0 ψ0 ψ0−1 (x) = α0 (x) and hence β↾X = α0 , that is, β is a homomorphic extension of α0 . By the definition, S is freely generated by X. ⊔ ⊓ The above proof reveals also Corollary 3.2. If S is freely generated by a set X, then S ∼ = A+ , where |A| = |X|. Corollary 3.3. If S and R are free semigroups generated by X and Y , respectively, such that |X| = |Y |, then S ∼ = R. Corollary 3.4. Every free semigroup is cancellative. Proof. This is immediate, since A+ is cancellative.

⊔ ⊓

A criterion for freeness Let X ⊆ S. We say that x = x1 x2 . . . xn is a factorization of x over X, if each xi ∈ X. Now, if X generates S, then every element x ∈ X has a factorization over X. Usually, this factorization is not unique, that is, we may have x1 x2 . . . xn = x = y1 y2 . . . ym for some xi ∈ X (i = 1, 2, . . . , n) and for some different yi ∈ X (i = 1, 2, . . . , m).

3.1 Free semigroups

29

Theorem 3.5. A semigroup S is freely generated by X if and only if every x ∈ S has a unique factorization over X. Proof. We observe first that the claim holds for the word semigroups A+ , for which A is the only minimal generating set. Let A be an alphabet such that |A| = |X| and let α0 : X → A be a bijection. Suppose X generates S freely, and that there is an x ∈ S, for which x = x1 x2 . . . xn = y 1 y 2 . . . y m

(xi , yi ∈ X) .

For the homomorphic extension α of α0 , α(x) = α0 (x1 )α0 (x2 ) . . . α0 (xn ) = α0 (y1 )α0 (y2 ) . . . α0 (ym ) in A+ . Since A+ satisfies the condition of the theorem, and α0 (xi ), α(yi ) are letters for each i, we must have that α0 (xi ) = α0 (yi ) for all i = 1, 2, . . . , n (and m = n). Moreover, α0 is injective, and so xi = yi for all i, and thus also S satisfies the claim. Suppose then that S satisfies the uniqueness condition. Denote β0 = α−1 0 and let β : A+ → S be the homomorphic extension of β0 . Now, β is surjective, since X generates S. It is also injective, because if β(u) = β(v) for some words u 6= v ∈ A+ , then β(u) would have two different factorizations over X. Hence β is an isomorphism, and the claim follows from this. ⊔ ⊓ Let the base of a semigroup S be defined by Base(S) = S \ S 2 = {x ∈ S | ∀y, z ∈ S : x 6= yz} , consisting of those elements x ∈ S which are not products of any two or more elements of S. The following result is an exercise. Theorem 3.6. A semigroup is free S if and only if Base(S) generates it freely. Example 3.3. (1) Let A = {a, b, c} be an alphabet. The words ab, bab, ba generate a subsemigroup of A+ . This semigroup S = [ab, bab, ba] is not free, since the element w = babab has two different factorizations in S: w = ba · bab = bab · ab. (2) If A is as above, but S = [aab, ab, aa], then S is a free subsemigroup of A+ . Indeed, if there were two different factorizations w = u1 u2 . . . un = v1 v2 . . . vm of a word w ∈ S, then either u1 = v1 (and, by cancellation, there would be a shorter word u2 . . . un = v2 . . . vm with two different factorizations) or u1 = aa and v1 = aab (or symmetrically, u1 = aab and v1 = aa). But in this case u2 cannot be found, because it should start with the letter b. (3) Let then A = {a, b} be a binary alphabet, and consider S = [abn | n ≥ 1] = [ab, ab2 , ab3 , . . . ] . Clearly, Base(S) = S \ S 2 = {abn | n ≥ 1}, and S is freely generated by Base(S). (4) For S = (R, ·), we have Base(S) = ∅. In particular, this semigroup cannot be free. ⊔ ⊓

3.1 Free semigroups

30

Free monoids Observe that no monoid M can be a free semigroup, because 1 = 1·1. Hence the identity 1 cannot be among the free generator of M . It follows that 1 is a product of generators of M , 1 = x1 x2 . . . xn , but now x = 1 · x gives two factorizations of an element x. We say that M is a free monoid (freely generated by a subset X with 1 ∈ / X), if X ∪ {1} is a generator set for M , and every mapping α0 : X → P (where P is a monoid) extends to a monoid homomorphism α : M → P such that α↾X = α0 and α(1M ) = 1P . Again, if M is free and α0 : X → P a mapping to a monoid P , then its extension α : M → P is unique. We have immediately: Theorem 3.7. If S is a free semigroup, then S 1 is a free monoid. Corollary 3.5. The word monoid A∗ is a free monoid for all alphabets A. The converse of Theorem 3.7 holds, too. Theorem 3.8. A monoid M is a free monoid if and only if M \{1M } is a free semigroup. Proof. Suppose first that M is a free monoid, freely generated by X. Then M \ {1M } is a subsemigroup of M , for otherwise, 1M = x1 x2 . . . xn for some xi ∈ X, and a mapping α0 : X → A∗ with α0 (xi ) ∈ A does not extend. The rest of the claim follows from the definition of a free semigroup. The converse claim is an exercise. ⊔ ⊓ The other results for free semigroups can also be modified for free monoids: Theorem 3.9. 1. A monoid M is freely generated by X if and only if each nonidentity x ∈ M \ {1M } has a unique factorization over X. 2. Every monoid is an epimorphic image of a word monoid A∗ . 3. A monoid M is free if and only if it is isomorphic to A∗ for some alphabet A.

Free matrix monoids Let SL(2, N) be the set of all matrices M ∈ N2×2 with det(M ) = 1, that is,   n11 n12 , n11 n22 − n12 n21 = 1 (nij ∈ N) . M= n21 n22 This is a monoid, called a special linear monoid, with the identity matrix I as its identity. Note that if det(M1 ) = 1 = det(M2 ), then also det(M1 M2 ) = 1.

3.2 Presentations of semigroups

31

Theorem 3.10. SL(2, N) is a free monoid, freely generated by the matrices     1 0 1 1 . and B= A= 1 1 0 1 Proof. The matrices A and B have the following inverse matrices     1 −1 1 0 −1 −1 A = and B = 0 1 −1 1 with integer entries. Note that these matrices are not in SL(2, N). Let M ∈ SL(2, N) be any matrix as above with M 6= I. Then   n11 − n21 n12 − n22 −1 A M= n21 n22   n11 n12 −1 B M= . n21 − n11 n22 − n12 Either one of these is in SL(2, N): A−1 M ∈ SL(2, N), if n11 ≥ n21 ; and B −1 M ∈ SL(2, N), if n11 < n21 . Moreover, the trace of M , tr(M ) = n11 + n22 , is greater than the trace of A−1 M or B −1 M whichever is in SL(2, N): tr(A−1 M ) = tr(M ) − n21 , tr(B −1 M ) = tr(M ) − n12 . Therefore, for each M ∈ SL(2, N) with M 6= I, there exists a unique sequence −1 . . . C1−1 M = I, that is, M = C1 , C2 , . . . , Ck (Ci = A or B) such that Ck−1 Ck−1 C1 C2 . . . Ck . By Theorem 3.5 and Theorem 3.8, SL(2, N) is a freely generated by A and B. ⊔ ⊓

3.2 Presentations of semigroups Generators and relations Let S be a semigroup. By Theorem 3.3 there exists an epimorphism ψ : A+ ։ S, where A+ is a suitable word semigroup. By Theorem 2.4, S∼ = A+ / ker(ψ) , since now ψ(A+ ) = S. We say that ψ is a homomorphic presentation of S. The letters in A are called generator symbols or just generators of S, and if (u, v) ∈ ker(ψ) (that is, ψ(u) = ψ(v)) then u = v is called a relation or an equality in S. (In order to avoid confusion we write usually u ≡ v, if the words u, v ∈ A+ are equal).

3.2 Presentations of semigroups

32

Define a presentation of S in generators (generator symbols) A = {a1 , a2 , . . . } and relations R = {ui = vi | i ∈ I}, S = ha1 , a2 , · · · | ui = vi (i ∈ I)i

or

S = hA | Ri ,

if ker(ψ) is the smallest congruence of A+ that contains the relation {(ui , vi ) | i ∈ I}. In particular, ψ(ui ) = ψ(vi ) for all ui = vi in R . (3.1) The set R of relations is supposed to be symmetric, that is, if u = v is in R, then v = u also holds. One should remember that the words w ∈ A+ are not elements of S but of the word semigroup A+ , which is mapped onto S. We say that a word w ∈ A+ presents the element ψ(w) of S. The same element can be presented by many different words. In fact, if ψ(u) = ψ(v), then both u and v present the same element of S. Let S = hA | Ri be a presentation. We show that S satisfies a relation u = v (that is, ψ(u) = ψ(v)) if and only if there exists a finite sequence u = u1 , u2 , . . . , uk+1 = v of words such that ui+1 is obtained from ui by substituting a factor ui by vi for some ui = vi in R. To be more precise, we say that a word v is directly derivable from the word u, if u ≡ w1 u′ w2

and

v ≡ w1 v ′ w2

for some u′ = v ′ in R .

(3.2)

Clearly, if v is derivable from u, then u is derivable from v, since R is supposed to be symmetric, and, in the notation of (3.2), ψ(u) = ψ(w1 u′ w2 ) = ψ(w1 )ψ(u′ )ψ(w2 ) = ψ(w1 )ψ(v ′ )ψ(w2 ) = ψ(w1 v ′ w2 ) = ψ(v) , and hence u = v is a relation in S. The word v is derivable from u, if there exists a finite sequence u ≡ u1 , u2 , . . . , uk ≡ v such that for all j = 1, 2, . . . , k − 1, uj+1 is directly derivable from uj . Now, if v is derivable from u, then also ψ(u) = ψ(v), since ψ(u) = ψ(u1 ) = · · · = ψ(uk ) = ψ(v), and therefore u = v is a relation in S. This can be written as u ≡ u1 = u2 = · · · = uk ≡ v . Theorem 3.11. Let S = hA | Ri be a presentation (with R symmetric). Then Rc = {(u, v) | u = v or v is derivable from u} . Hence u = v in S if and only if v is derivable from u. Proof. Let the relation ρ be defined by uρv ⇐⇒ u = v or v is derivable from u . It is clear that ιS ⊆ ρ, and hence ρ is reflexive. Since R is symmetric, so is ρ. The transitivity of ρ is easily verified, and hence ρ is an equivalence relation.

3.2 Presentations of semigroups

33

If w ∈ A+ and v is derivable from u, then clearly also wv is derivable from wu and vw is derivable from uw. This proves that ρ is a congruence. Let θ be any congruence such that R ⊆ θ. Suppose v is directly derivable from u: u = w1 u′ w2 , v = w1 v ′ w2 with u′ = v ′ in R. Since R ⊆ θ, also (u′ , v ′ ) ∈ θ, and since θ is a congruence, also (w1 u′ w2 , w1 v ′ w2 ) ∈ θ, that is, uθv. Therefore, by transitivity of ρ and θ, ρ ⊆ θ. In conclusion, ρ is the smallest congruence that contains R, that is, ρ = Rc . ⊔ ⊓ Theorem 3.12. Let A be an alphabet and R ⊆ A+ × A+ a symmetric relation. The semigroup S = A+ /Rc , where Rc is the smallest congruence containing R, has the presentation S = hA | u = v for all (u, v) ∈ Ri . Moreover, all semigroups having a common presentation are isomorphic. Proof. The claim is immediate from the above.

⊔ ⊓

Example 3.4. (1) Consider the following presentation S = ha, b | aa = ab, ba = aab, bbb = abai . In this presentation there are two generators and three relations. For instance, S satisfies the relation baabbaa = bbaaaba, since u1 = baabbaa ≡ b · aab · baa = b · ba · baa ≡ u2 and u2 = bbabaa ≡ bba · ba · a = bba · aab · a ≡ bbaaaba. Also, aaab = aabb = abbb = aaba = baa = bab in S and hence aaab = bab in S. (2) A word semigroup does not need any relations: A+ = hA | ∅i. (3) The presentation S = ha, b, c, d, e | ac = ca, ad = da, bc = cb, bd = db, eca = ce, edb = de, cca = ccaei is called Tzeitin’s semigroup. This surprisingly simple semigroup has an undecidable word problem, that is, there exists no algorithm that determines whether u = v is a relation in this semigroup, where u, v ∈ {a, b, c, d, e}+ are given (input) words. Hence in Tzeitin’s semigroup one cannot effectively decide whether a word is derivable from another given word. ⊔ ⊓ All semigroups (and monoids and groups) have presentations. Indeed, S = hA | ker(ψ)i is one such presentation, when ψ : A+ → S is the presenting epimorphisms. Usually this presentation is all too complicated. We are mostly interested in semigroups that have a finite presentation, that is, a presentation S = hA | Ri, where A is a finite alphabet and R is finite set of relations. However, not all semigroups have such presentations.

3.2 Presentations of semigroups

34

Monoid presentations All monoids have a semigroup presentation, but it is more convenient to use monoid presentations for these in order to take advantage of the identity element: M = ha1 , a2 , · · · | ui = vi (i ∈ I)i is a monoid presentation, if ui , vi ∈ A∗ where A = {a1 , a2 , . . . } is an alphabet. In a monoid presentation we may thus have relations of the form u = 1, which means that the word u can be erased from another word or added somewhere in between two letters. Example 3.5. (1) Let M = ha, b | ab = bai be a monoid presentation. Hence M ∼ = ∗ c A /R , where A = {a, b} and R has a single relation ab = ba. There is an epimorphism ψ : A∗ ։ M and M is generated by the elements x = ψ(a) and y = ψ(b). The monoid M is commutative, because of the relation ab = ba. If the generators of M commute with each other, then M is commutative. Furthermore, each element z ∈ M has a normal form: Suppose z = z1 z2 . . . zn with zi = ψ(ai ) (ai = a or b), and so z = ψ(a1 )ψ(a2 ) . . . ψ(an ) = ψ(a1 a2 . . . an ) = ψ(ak bm ) = ψ(a)k ψ(b)m for some k, m ≥ 0. The monoid M is a free commutative monoid, and it can be shown that every commutative monoid, which is generated by two elements, is an epimorphic image of M . (2) The (monoid) presentation ha, b | aba = 1i defines a group. In fact, this group is isomorphic to (Z, +). Indeed, let M be a monoid with the above presentation, i.e., M ∼ = A∗ /Rc , where A = {a, b} and R = {aba = 1}, ∗ and let ψ : A ։ M be the corresponding epimorphism. Then M is generated by the elements x = ψ(a) and y = ψ(b). Furthermore, ab = ab · aba ≡ aba · ba = ba, and hence xy = yx. It follows that M is a commutative monoid. Consequently, every element z ∈ M has the form z = ψ(an bm ) for some n, m ≥ 0. Also, a · ba = 1 and ba · a = ab · a = 1 means that ba is a group inverse of a. Similarly, a2 is a group inverse of b, b = (aa)−1 . This means that all elements of M have the form z = ψ(ak ) for k ∈ Z. It is now easy to show that α : M → (Z, +) defined by α(a) = −1 and α(b) = 2 is an isomorphism. (3) Define two mappings α, β : N → N as follows: ( 0 if n = 0 and β(n) = n + 1 (n ≥ 0) . α(n) = n − 1 if n ≥ 1 Consider the bicyclic monoid B = [α, β] generated by these two transformations. We observe that αβ = ι, but ( 1 if n = 0 βα(n) = n if n ≥ 1,

3.3 Embeddings into 2-generator semigroups and, more generally, k k

β α (n) =

(

k n

35

if n < k if n ≥ k.

Let A = {a, b} be an alphabet, and define a homomorphism ψ : A∗ → B by ψ(a) = α and ψ(b) = β. By the extension property ψ becomes uniquely defined by the images of the generator symbols a and b. Hence ψ is an epimorphism and B ∼ = A+ / ker(ψ). By above ab = 1 is a relation in B. Let then γ ∈ B be any element of the bicyclic monoid, γ = γn γn−1 . . . γ1 , where γi = α or γi = β. Since αβ = ι, we may assume that if γj = β for some index j, then γt = β for all t with j ≤ t ≤ n. This shows that γ = β k αm for some k, m ≥ 0, and hence B = {β k αm | k, m ≥ 0} . Furthermore, these elements are all different from each other: if γ = β k αm and δ = β r αs , then γ(0) = β k αm (0) = β k (0) = k

and

δ(0) = β r αs (0) = β r (0) = r ,

and for n ≥ max{m, s}, γ(n) = β k αm (n) = β k (n − m) = n + k − m , δ(n) = β r αs (n) = β r (n − s) = n + r − s . Therefore, γ = δ just in case k = r and m = s. This means that B = ha, b | ab = 1i is a (monoid) presentation of B. The bicyclic monoid has many (semigroup) presentations, of which we mention B = ha, b | aba = aab, a = aab, bab = abb, b = abbi . ⊔ ⊓

3.3 Embeddings into 2-generator semigroups Evans’ embedding result The following embedding result was proved by Evans in 1952. The proof given here is due to Subbiah (1973). We say that a set X is denumerable, if it is finite or if it has the cardinality of N. The elements of a denumerable set X can be listed: X = {x1 , x2 , . . . }. (This is not the case for R, which is not denumerable). Theorem 3.13 (Evans). Let S be a semigroup generated by denumerably many elements. Then S can be embedded into a semigroup generated by two elements.

3.3 Embeddings into 2-generator semigroups

36

We shall use the fact that each semigroup is isomorphic to a subsemigroup of the full transformation semigroup, and we actually prove Theorem 3.14 (Sierpinski). Let α1 , α2 , . . . : N+ → N+ be any transformations. There exist two transformations β1 , β2 : N+ → N+ such that each αi is a composition of these two transformations: αi ∈ [β1 , β2 ]. Proof. Define Xn = {2n (2m − 1) − 1 | m = 1, 2, . . . } . Now, Xn ∩ Xm = ∅ for all n 6= m, because k ∈ Xn if and only if n is the highest power for which 2n divides k + 1. Also, [ Xn = 2N + 1 , n≥1

and hence the sets Xn form a partition of the odd positive integers. Define ( n−1 if n is even, β1 (n) = 2n (n ≥ 1) , β2 (n) = −(k+1) −1 αk (2 (n + 1) + 2 ) if n ∈ Xk . Now, for all k ≥ 1, αk = β22 β1k β2 β1 , since β22 β1k β2 β1 (n) = β22 β1k β2 (2n) = β22 β1k (2n − 1) = β22 (2k (2n − 1)) = β2 (2k (2n − 1) − 1) = αk (2−(k+1) (2k (2n − 1) + 2−1 ) = αk (2−1 (2n − 1 + 1) = αk (n) . ⊔ ⊓

This proves the claim.

Theorem 3.13 follows from Sierpinski’s result by using suitable isomorphisms. We omit this straightforward reduction.

Embedding word monoids Let A = {a1 , a2 , . . . , an } be a finite alphabet, and let B = {a, b} be a binary alphabet. The homomorphism α : A∗ → B ∗ defined by α(ai ) = abi

(i = 1, 2, . . . , n)

is injective as can be easily shown. Therefore Theorem 3.15. Each finitely generated word monoid A∗ can be embedded in a word monoid B ∗ generated by two letters.

4 Combinatorial Topics 4.1 The defect theorem Submonoids of word monoids For a subset X ⊆ A∗ of words we shall write X + = [X]A∗ for the subsemigroup that X generates in the word monoid A∗ , that is, X + consists of all catenations of the words in X. Also, the corresponding monoid is denoted by X ∗ , that is, X ∗ = X + ∪ {1}. Notice that if 1 ∈ X already, then X ∗ = X + . If w ∈ A∗ is a word, then we write simply w∗ = {w}∗ . Let u, v ∈ A+ be two words. Henceforth we write u = v (not u ≡ v) for the equality in A∗ . Then u is • a factor of v, if v = w1 uw2 for some words w1 , w2 ∈ A∗ ; • a prefix of v, if v = uw for some w ∈ A∗ ; • a suffix of v, if v = wu for some w ∈ A∗ . The length |w| of a word w ∈ A∗ is the number of the occurrences of the letters in it: if w = a1 a2 . . . an with ai ∈ A, then |w| = n. The length of the empty word is zero. Clearly, if w = uv, then |w| = |u| + |v|, and so the length function is a homomorphism | | : A∗ → (N, +). The next lemma is immediate. Lemma 4.1. If u1 u2 = v1 v2 in A∗ , then either u1 is a prefix of v1 or v1 is a prefix of u1 , that is, there is a word w ∈ A∗ such that either u1 = v1 w or v1 = u1 w. We first prove another criterion for freeness of submonoids of a word monoid. For a submonoid M of a word monoid A∗ we let M+ = M \ {1}. Here M+ is always a subsemigroup of A+ , because the empty word cannot be a catenation of nonempty words. The base of M , Base(M ) = M+ \ M+2 , is the base of the semigroup M+ . Recall that the identity (the empty word) is automatically in a submonoid. The base of a free monoid is called a code. A submonoid M of a word monoid A∗ need not be free. As an example, consider the monoid M = {a, ab, ba}∗ .

4.1 The defect theorem

38

Lemma 4.2. For all submonoids M of A∗ the base Base(M ) is the unique minimal generating set of M (as a monoid), i.e., if a subset N generates M , then Base(M ) ⊆ N . Proof. In order to show that Base(M ) generates M suppose to the contrary that there exists a word w ∈ M that cannot be written as a product of words from Base(M ), and let w is a shortest word such that w ∈ M+ but w ∈ / Base(M )+ . Since w ∈ / Base(M ), there are two words u, v ∈ M+ such that w = uv. By the minimality of w, the shorter words u and v are in Base(M )+ , but now also w ∈ Base(M )+ , which is a contradiction. If a subset N ⊆ M generates M , then for all u ∈ Base(M ), u ∈ N ∗ (= M ), but u is not a product of two or more words from M , and hence necessarily u ∈ N , too. ⊔ ⊓ Theorem 4.1. Let M be a submonoid of a word monoid A∗ . M is free if and only if u, v, uw, wv ∈ M =⇒ w ∈ M . Proof. Let X = Base(M ). Assume first that M is free. Suppose that for a word w, both uw and wv are in M , where u, v ∈ M : u = u1 u2 . . . uk ,

wv = uk+1 uk+2 . . . uk+r

uw = v1 v2 . . . vt ,

v = vt+1 vt+2 . . . vt+s ,

where each ui , vi ∈ X. Now, uwv = u1 u2 . . . uk uk+1 . . . uk+r = v1 v2 . . . vt vt+1 . . . vt+s , and since M is freely generated by X, k+r = t+s and ui = vi for all i = 1, 2, . . . , k+r. It follows that w = uk+1 . . . ut (since k ≤ t), and so w ∈ M as required. Assume then that the condition is valid for M . Suppose that there exists a word, which has two different factorizations over X, u1 u2 . . . un = v1 v2 . . . vm

(ui , vi ∈ X) .

We may suppose here that u1 6= v1 , for otherwise we have already u2 . . . un = v2 . . . vm . Now, either u1 is a prefix of v1 or v1 is a prefix of u1 . Suppose that the former holds, v1 = u1 w (the other case is quite symmetric to this one). It follows that u1 w ∈ M

and

u2 u3 . . . un = wv2 v3 . . . vm .

The latter holds, since A+ is cancellative. By assumption, w ∈ M , but this contradicts the fact that v1 = u1 w ∈ Base(M ). We conclude that M is free. ⊔ ⊓

4.1 The defect theorem

39

The defect theorem For the defect theorem we need the following result, which is interesting on its own. Theorem 4.2. If Mi (i ∈ I) are free submonoids of A∗ , then so is M = ∩i∈I Mi . Proof. Clearly, the intersection M is a submonoid of A∗ . If now u, v, uw, wv ∈ M , then u, v, uw, wv ∈ Mi for all i ∈ I and hence by Theorem 4.1, w ∈ Mi for all i ∈ I, that is, w ∈ M . The claim follows from Theorem 4.1. ⊔ ⊓ By above, if X ⊆ A∗ is any subset then the intersection \ {M | X ⊆ M, M is a free submonoid}

is a free submonoid. Clearly, it is the smallest free submonoid that contains the subset X. The base of this intersection is denoted simply by Hull(X), and it is called the free hull of X. In particular, X ∗ ⊆ Hull(X)∗ , since X ∗ is a monoid and X ⊆ Hull(X)∗ . Theorem 4.3 (Defect theorem). Let X ⊆ A+ be a finite set of words. If X is not a code (a base of a free monoid), then | Hull(X)| ≤ |X| − 1. Proof. Since X ⊆ Hull(X)∗ , each word u ∈ X can be uniquely written in terms of Hull(X), u = x1 x2 . . . xk with xi ∈ Hull(X). Let α : X → Hull(X) be the mapping such that α(u) = x1 if u ∈ x1 · Hull(X)∗ . Assume that X ∗ is not free, and hence that there exists a word w ∈ X ∗ having two different factorizations over X: w = u1 u2 . . . un = v1 v2 . . . vm

(ui , vi ∈ X) ,

where u1 6= v1 . (Note that if u1 = v1 , then there is a shorter word u2 . . . un with two different factorizations over X). We have α(u1 ) = α(v1 ), and therefore α is not injective. (If α(u1 ) 6= α(v1 ), then the word w would have two different factorizations over Hull(X), but Hull(X)∗ is free.) We show next that α is surjective. Suppose to the contrary that there exists a word w ∈ Hull(X) such that α(u) 6= w for all u ∈ X. Let Y = (Hull(X) \ {w})w∗ . Hence X ⊆ Y ∗ . Now, Y ∗ is free, since if w1 w2 . . . wm = v1 v2 . . . vr

for some wi , vi ∈ Y ,

where wi = yi wki and vi = zi wti for yi , zi ∈ Hull(X) \ {w} and ki , ti ≥ 0. Then y1 wk1 y2 wk2 . . . ym wkm = z1 wt1 z2 wt2 . . . zr wtr ,

4.2 Ehrenfeucht’s conjecture

40

and, since Hull(X) is free, y1 = z1 , k1 = t1 , . . . , yk = zk , km = tm and m = r. But now also wi = vi for all i, which shows that Y ∗ is free. We have, however, that X ⊆ Y ∗ , and also that Y ∗ ⊂ Hull(X)∗ , which contradicts the minimality of Hull(X) as the smallest base of a free submonoid containing X. This shows that α is surjective. Because α is not injective, it follows that | Hull(X)| = |α(X)| < |X|, and the claim is proven. ⊔ ⊓ Example 4.1. Let A = {a, b} and X = {ab, aba, bab, ba}. The submonoid X ∗ is not free, since ab·aba = aba·ba. Consider any free submonoid M such that X ∗ ⊆ M . Now, for u = ab, v = ba and w = a, u, v, uw, wv ∈ X ∗ ⊆ M , and hence by Theorem 4.1, also w = a ∈ M . Similarly, b ∈ M , and hence M = A∗ , which means that Hull(X) = {a, b}. Here |X| = 4 > 2 = | Hull(X)| as required by Theorem 4.3. ⊔ ⊓

Some corollaries A word w ∈ A+ is said to be primitive, if it is not a proper power of another word, that is, w = uk implies that k = 1 and u = w. Two words u, v ∈ A+ are conjugates (of each other), if there are words w1 , w2 ∈ A∗ such that u = w1 w2 and v = w2 w1 . Hence, if u is a conjugate of v, then u is obtained from v by cyclically permuting the word v. Corollary 4.1. Each word w ∈ A+ is a power of a unique primitive word. Proof. Suppose w = un = v m for some words u 6= v ∈ A+ and integers n, m ≥ 1. Now, the set X = {u, v} is not a code, since w has two different factorizations over {u, v}. By Theorem 4.3, | Hull(X)| < |X|, and hence Hull(X) = {z} for some z ∈ A∗ , but this means that u, v ∈ z ∗ , that is, they are powers of the word z: u = z r and v = z s . If above u and v are primitive, then r = 1 = s, and hence u = v. This shows the claim. ⊔ ⊓ Corollary 4.2. Two words u, v ∈ A∗ commute, uv = vu, if and only if they are powers of a common word. Proof. If uv = vu, then X = {u, v} is not a code, and hence again | Hull(X)| < |X| = 2, and so u and v are powers of a common word. ⊔ ⊓

4.2 Ehrenfeucht’s conjecture Equality sets Let α, β : A∗ → B ∗ be two homomorphisms between the word monoids A∗ and B ∗ , where we assume that the alphabets are finite. Their equality set is defined to be

4.2 Ehrenfeucht’s conjecture

41

E(α, β) = {w ∈ A∗ | α(w) = β(w)} . Thus the equality set of α and β consists of all those words on which these homomorphisms agree. A word w ∈ E(α, β) is also called a solution of (α, β). A solution w 6= 1 is a nontrivial solution. Notice that we always have 1 ∈ E(α, β). The empty word is the trivial solution of (α, β). Lemma 4.3. E(α, β) is a free monoid, for which v, uv ∈ E(α, β) =⇒ u ∈ E(α, β) . Proof. First of all the empty word is always in E = E(α, β), since α(1) = 1 = β(1). We use a restricted version of Theorem 4.1 to show the rest of the claim. Suppose v, uv ∈ E. Then α(uv) = α(u)α(v) = α(u)β(v) and α(uv) = β(uv) = β(u)β(v), and hence α(u) = β(u), because A∗ is cancellative. This means that u ∈ E, too. Now, if u, v, uw, wv ∈ E, then v, wv ∈ E and, by above, w ∈ W . Thus E is free. ⊔ ⊓ The base Base(E(α, β)) is the set of all minimal solutions of (α, β). By above, it is a code. Example 4.2. (1) Consider the endomorphisms α, β : A∗ → A∗ , where A = {a, b}, and α and β are defined by the images of the generators a and b: α(a) = aba β(a) = ab

α(b) = ba β(b) = aba.

Now, if w ∈ E = E(α, β) is nonempty, then it must begin with the letter a (because α(b) and β(b) are ‘incomparable’). The next letter must be b, and, we obtain thus a solution ab ∈ E: α(ab) = aba · ba = uivab · aba = β(ab). It is easy to show that E = (ab)∗ = {(ab)n | n ≥ 0}. (2) Let then α, β : A∗ → A∗ for A = {a, b, c} be defined by α(a) = ab β(a) = a

α(b) = bb β(b) = bb

α(c) = c β(c) = bc

If now a nonempty w ∈ A∗ is in E = E(α, β), then either w begins with a or b, and it ends with b or c. In this case we have E(α, β) = b∗ ∪ ab∗ c = {bn | n ≥ 0} ∪ {abn c | n ≥ 0}. ⊔ ⊓ Remark 4.1. It can be shown that the problem whether E(α, β) contains a nonempty word is algorithmically unsolvable, that is, there exists no algorithm which decides whether or not E(α, β) = {1} on inputs α and β. This is know as the Post correspondence problem. There are thus arbitrarily complex equality sets. ⊔ ⊓

4.2 Ehrenfeucht’s conjecture

42

Test sets We are going to prove the following result, which was conjectured by Ehrenfeucht at the beginning of 1970s and proved by Albert and Lawrence and independently by Guba in 1985. Theorem 4.4 (Ehrenfeucht’s conjecture). Let L ⊆ A∗ be any set of words. There exists a finite subset T ⊆ L such that for all homomorphisms α, β : A∗ → B ∗ α↾T = β↾T ⇐⇒ α↾L = β↾L .

The subset T of L is called a test set of L, since in order to check whether any two homomorphisms agree on the set L, it suffices to check whether they agree on the finite subset T . Theorem 4.4 may be restated in the following form: Theorem 4.5. Let L ⊆ A∗ be any set of words. There exists a finite subset T ⊆ L such that for all homomorphisms α, β : A∗ → B ∗ T ⊆ E(α, β) ⇐⇒ L ⊆ E(α, β) .

Systems of equations Let X = {x1 , x2 , . . . , xn } be a special alphabet, the letters of which we call variables. An equation over X is a pair of words (u, v) (for u, v ∈ X + ). We shall usually write u = v instead of (u, v). We say that (w1 , w2 , . . . , wn ) with wi ∈ A∗ is a solution of the equation u = v, if the substitution xi 7→ wi in u and v results in the same word of A∗ . In other words, a solution is a (monoid) homomorphism α : X ∗ → A∗ such that α(u) = α(v) (here α(xi ) = wi ), that is, (u, v) ∈ ker(α). Example 4.3. Let X = {x, y, z}. Then a solution of the equation xyx = zyxz is a homomorphism α : X ∗ → A∗ (A is some alphabet) such that α(xyx) = α(zyxz), that is, w1 w2 w1 = w3 w2 w1 w3 , where w1 = α(x), w2 = α(y) and w3 = α(z). Of course, w1 = w2 = w3 = 1 is a solution. This is the trivial solution. Let x 7→ w1 , y 7→ w2 , z 7→ w3 be any solution. By comparing the lengths we obtain |w1 w2 w1 | = |w3 w2 w1 w3 |, that is, 2|w1 | + |w2 | = |w1 | + |w2 | + 2|w3 |, and so |w1 | = 2|w3 |, which means that w1 = w3 w for a word w with |w| = |w3 | (since w1 and w3 begin the same word). When we substitute w1 by w3 w, we obtain that w3 ww2 w3 w = w3 w2 w3 ww3 , from which we get ww2 w3 w = w2 w3 ww3 by cancellation. Here w and w3 end this word, and hence w = w3 , since |w| = |w3 |. Therefore, w3 w2 w3 w3 = w2 w3 w3 w3 , and so w3 w2 = w2 w3 , which means that w2 and w3 are powers of the same word, w2 = ur and w3 = us , and w1 = w3 w = w3 w3 = u2s . Further, if u is any word, then w1 = u2s , w2 = ur , w3 = us is a solution for any r, s ≥ 0. We have thus found all the solutions of the equation xyx = zyxz. ⊔ ⊓

4.2 Ehrenfeucht’s conjecture

43

Any set E = {(ui , vi ) | i = 1, 2, . . . } of equations (in variables from X) is a system of equation. A solution of E is a homomorphism α : X ∗ → A∗ such that α is a common solution to all ui = vi . Example 4.4. Let X = {x1 , x2 , y1 , y2 } and consider the system of equations xi1 y1i = xi2 y2i (i ≥ 1):    x1 y 1 = x2 y 2 x1 x1 y 1 y 1 = x2 x2 y 2 y 2 .  ..  . This system of equations has the trivial solution α(xi ) = 1 = α(yi ) (i = 1, 2), and the solutions α(x1 ) = w1 = α(x2 ), α(y1 ) = w2 = α(y2 ) (in any alphabet); also α(x1 ) = aa, α(x2 ) = a, α(y1 ) = a, α(y2 ) = aa is a solution. ⊔ ⊓ Two systems E1 and E2 of equations are equivalent, if they have the same solutions. The following was proved by Culik and Karhum¨aki: Theorem 4.6. Ehrenfeucht’s conjecture is equivalent to the statement: Every system of equations E is equivalent to a finite subsystem T ⊆ E. Proof. For any alphabet B we let B = {a | a ∈ B} be a new alphabet, and write for + all words u = a1 a2 . . . ak ∈ B + , u = a1 a2 . . . ak ∈ B . Hence the function is an ∗ isomorphism B ∗ → B . Let us first assume that Ehrenfeucht’s conjecture is true, and let E be a system of equations in variables X = {x1 , x2 , . . . , xn }. Let X be a new set of variables defined as + above. To each equation u = v in E we attach a word uv ∈ X + · X . Let L = {uv | u = v ∈ E} ⊆ (X ∪ X)∗ . By assumption, L has a finite test set T ⊆ L: for any homomorphisms α, β : (X∪X)∗ → A∗ , if α(uv) = β(uv) for all uv ∈ T , then α(uv) = β(uv) for all uv ∈ L. For each homomorphism α : X ∗ → A∗ define homomorphisms α1 , α2 : (X ∪X)∗ → ∗ A as follows

α1 (x) = α(x)

α2 (x) = 1

α1 (x) = 1

α2 (x) = α(x)

It follows that if α is a solution to T = {u = v | uv ∈ T } , then α(u) = α(v) for all u = v in T, and α1 (uv) = α2 (vv) for all uv in T , and so α1 (uv) = α2 (vv) for all uv in L, and α(u) = α(v) for all u = v in E. This proves that E is equivalent to the finite subsystem T.

4.2 Ehrenfeucht’s conjecture

44

Assume then that each system of equations has an equivalent finite subsystem. Let L ⊆ B ∗ be any set of words. Let B be a new alphabet as above. We form a system of equations E from L as follows: E = {u = u | u ∈ L} . By assumption this system has an equivalent subsystem T. Let T = {u | u = u ∈ T} . Hence T is a finite subset of X. Let α, β : B ∗ → A∗ be homomorphisms such that α(u) = β(u) for all u ∈ T . Let X = B ∪ B be our set of variables, and define a homomorphism γ : X ∗ → A∗ : For all x ∈ B, γ(x) = α(x)

and

γ(x) = β(x) .

Now, γ(u) = γ(u) for all u ∈ T , and hence γ is a solution to the finite system T. By assumption, γ is then a solution to the whole system E, and, consequently, α(u) = β(u) for all u ∈ L. This shows that T is a finite test set of L. ⊔ ⊓

Hilbert’s basis theorem In the proof of Ehrenfeucht’s conjecture we need the following original version of Hilbert’s basis theorem. Let Z[x1 , x2 , . . . , xn ] denote the ring of polynomials with integer coefficients in (commuting) variables x1 , x2 , . . . , xn . Theorem 4.7 (Hilbert’s basis theorem). Let Pi (i ≥ 1) be any polynomials in the ring Z[x1 , x2 , . . . , xn ]. There exists a finite subset P1 , P2 , . . . , Pt of these polynomials such that every Pi can be expressed as a linear combination Pi = P1 Fi1 + P2 Fi2 + · · · + Pt Fit , where Fij ∈ Z[x1 , x2 , . . . , xn ]. The proof goes by showing first that Z satisfies the above property, that is, for all integers pi ∈ Z (i = 1, 2, . . . ) there are finitely many of these, p1 , p2 , . . . , pt , such that all the integers pi can be expressed as a linear combination of these. In the second step we suppose that a ring R satisfies the finiteness (Noetherian) condition as stated in the claim, and show that also the polynomial ring R[x] satisfies it. The claim then follows because Z[x1 , . . . , xn−1 , xn ] is isomorphic Z[x1 , . . . , xn−1 ][xn ]. We omit the proofs of these claims (and refer to a ‘standard text book in algebra’). Corollary 4.3. Let Pi = Qi (i = 1, 2, . . . ) be a system of polynomial equations, where Pi , Qi ∈ Z[x1 , x2 , . . . , xn ]. There exists a finite subsystem P1 = Q1 , P2 = Q2 , . . . , Pt = Qt of these equations such that if (m1 , . . . , mn ) is a solution of this finite subsystem, Pi (m1 , . . . , mn ) = Qi (m1 , . . . , mn ) then it is a solution the whole system of equations.

(i = 1, 2, . . . , t) ,

4.2 Ehrenfeucht’s conjecture

45

Proof. Consider the polynomials Ri = Pi − Qi ∈ Z[x1 , x2 , . . . , xn ]. By Hilbert’s basis theorem there exists a finite subset of these, R1 , . . . , Rt , such that Ri = R1 Fi1 + R2 Fi2 + · · · + Rt Fit , for each Ri (for some Fij ). Now, 0 = Ri (m1 , . . . , mn ) = Pi (m1 , . . . , mn ) − Qi (m1 , . . . , mn ) for i = 1, 2, . . . , t implies Pi (m1 , . . . , mn ) = Qi (m1 , . . . , mn ) for all i.

⊔ ⊓

A proof of Ehrenfeucht’s conjecture By Theorem 4.6 we need to prove that every infinite system of equations has an equivalent finite subsystem. In order to make advantage of Hilbert’s Basis Theorem we transform the word equations u = v into polynomial equations in Z[x1 , x2 , . . . , xn ]. To overcome the commutativity of the variables in the ring of polynomials, we use noncommuting matrices of these polynomial. For this we use of the free monoid SL(2, N) of the previous chapter. Here SL(2, N) consists of unimodular matrices, that is, those matrices with determinant equal to 1. Recall that SL(2, N) is a free monoid generated by the matrices     1 1 1 0 A= and B= . 0 1 1 1 The homomorphism µ : {a, b}∗ → SL(2, N) defined by     1 1 1 0 µ(a) = and µ(b) = 0 1 1 1

(4.1)

is an isomorphism. Let X = {x1 , x2 , . . . , xk } be a set of word variables. We introduce for each xi four new integer variables xi1 , xi2 , xi3 and xi4 , and denote ¯ = {xij | 1 ≤ i ≤ k, 1 ≤ j ≤ 4} . X Further, for each i = 1, 2, . . . , k define Xi =



xi1 xi2 xi3 xi4



,

¯ be the submonoid of the matrix monoid Z[X] ¯ 2×2 generated by the matriand let M(X) ces X1 , X2 , . . . , Xk .

4.2 Ehrenfeucht’s conjecture

46

¯ is freely generated by X1 , X2 , . . . , Xk . Lemma 4.4. The monoid M(X) Proof. Consider two elements M = Xr1 Xr2 . . . Xrm and M ′ = Xs1 Xs2 . . . Xst of ¯ The upper right corner entry M12 of M contains the monomial M(X). xr1 1 xr2 1 . . . xrj−1 1 xrj 2 xrj+1 4 . . . xrm−1 4 xrm 4

(4.2)

for j = 1, 2, . . . , m. It is now easy to see that if these monomials exist in (M ′ )12 , then t = m and Xrj = Xsj for j = 1, 2, . . . , m. Therefore, (M )12 = (M ′ )12 implies that Xr1 = Xs1 , Xr2 = Xs2 , . . . , Xrm = Xsm . The claim follows from this. ⊔ ⊓ ⊔ ⊓ ¯ defined by In particular, the monoid homomorphism ϕ : X ∗ → M(X)   xi1 xi2 ϕ(xi ) = xi3 xi4

(4.3)

is an isomorphism. The following lemma is now immediate. Lemma 4.5. Let B be a binary alphabet. There exists a bijective correspondence α ↔ α ¯ → between the homomorphisms α : X ∗ → B ∗ and the monoid homomorphisms α : M(X) SL(2, N) such that the following diagram commutes: α - B∗ X∗ ϕ

?

M(X)

µ

α

? - SL(2, N)

We shall now prove the main result of this section, from which Theorem 4.4. Theorem 4.8. Each system of equations over a finite set of variables has an equivalent finite subsystem. ¯ be as above. Since, by Theorem 3.15, each monoid B ∗ can be Proof. Let X and X embedded into a free monoid generated by two elements, we can restrict our solutions α : X ∗ → B ∗ to the case where B is binary, say B = {a, b}. For a word w ∈ X ∗ we denote   Pw1 Pw2 ϕ(w) = , Pw3 Pw4 ¯ Consider any equation u = v, where u, v ∈ X ∗ . Define a finite where Pwj ∈ Z[X]. system P(u, v) of polynomial equations as follows: ( Puj = Pvj for 1 ≤ j ≤ 4, P(u, v) = xt1 xt4 − xt2 xt3 = 1 for 1 ≤ t ≤ k.

4.2 Ehrenfeucht’s conjecture

47

Let α : X ∗ → B ∗ be a homomorphism, and let α be the corresponding monoid homomorphism from Lemma 4.5. Now, by Lemmas 3.10, 4.4 and 4.5, α(u) = α(v) ⇐⇒ µα(u) = µα(v) ⇐⇒ αϕ(u) = αϕ(v) .

(4.4)

¯ → N by Define then a mapping α′ : X   ′ α (xi1 ) α′ (xi2 ) . α(Xi ) = α′ (xi3 ) α′ (xi4 ) Now, α′ is a solution of the equations on the second line of the definition of P(u, v). This is because α is into SL(2, N). Further, α′ extends in a unique way to a ring homo¯ → Z, for which morphism α′ : Z[X]  ′  α (Pw1 ) α′ (Pw2 ) αϕ(w) = α′ (Pw3 ) α′ (Pw4 ) for all w ∈ X ∗ . Therefore by (4.4), α(u) = α(v) if and only if α′ is a solution of the whole P(u, v). Let now E = {ui = vi | i ∈ I} be a system of equations, and let P = ∪i∈I P(ui , vi ). By Hilbert’s Basis Theorem, P has an equivalent finite subsystem P0 = ∪i∈I0 P(ui , vi ). Consider the subsystem E0 = {ui = vi | i ∈ I0 } of E. By above, α is a solution to E0 ⇐⇒ α′ is a solution to P0 ⇐⇒ α′ is a solution to P ⇐⇒ α is a solution to E , which proves that E0 is equivalent to E, and this proves the theorem.

⊔ ⊓

Equations with Constants Let X be a set of variables and A an alphabet of constants. An equation u = v with constants A is a pair of words u, v ∈ (X ∪ A)∗ . A solution of such an equation u = v is a homomorphism α : (X ∪ A)∗ → B ∗ , where A ⊆ B, α(u) = α(v) and α(a) = a for all a ∈ A. A homomorphism α is a solution to a system E of equations with constants A, if it is a common solution to the equations in E. With each constant a ∈ A we associate a new variable xa and in this way each equation u = v with constants A can be presented as a finite system of equations:  ′ u = v′ xa = a for all a ∈ A, where u′ and v ′ are obtained from u and v, resp., by substituting xa for a ∈ A. Therefore each system of equations with constants A can be presented as a system of equations over the variables X ∪ {xa | a ∈ A} together with a finite number of equations xa = a containing a unique constant. Therefore Theorem 4.8 can be generalized:

4.2 Ehrenfeucht’s conjecture

48

Corollary 4.4. Each system of equation with constants is equivalent to a finite subsystem. Let u1 = v1 and u2 = v2 be two equations, and let a, b be two different constants. It is easy to show that α is a solution to the above pair of equations if and only if α is a solution to the single equation u1 av2 u1 bv2 = v1 au2 v1 bu2 . In particular, we have Theorem 4.9. Each finite set of equations with constants is equivalent to a single equation with constants. Note, however, that the single equation of Theorem 4.9 need not be among the original ones.

On generalizations to arbitrary monoids We consider here examples of the equality sets and systems of equations in a more general setting of monoids. Let again X = {x1 , x2 , . . . , xn } be a finite set of variables. A solution of an equation u = v over X in a monoid M is a monoid homomorphism α : X ∗ → M , for which α(u) = α(v). We say that a monoid M satisfies the compactness property (for systems of equations), or CP for short, if for all sets of variables X every system E ⊆ X ∗ × X ∗ is equivalent to one of its finite subsystems T ⊆ E. Hence Ehrenfeucht’s Conjecture states that the finitely generated free monoids satisfy CP. Below we mention two examples, where (the generalization of) Ehrenfeucht’s Conjecture does not hold. Example 4.5. (1) Let F in(A∗ ) denote the monoid of all nonempty finite subsets of the word monoid A∗ . It was shown by Lawrence that the monoid F in(A∗ ) does not satisfy CP even when A is a binary alphabet. Indeed, in this case the system E of equations x1 xi2 x1 = x1 xi3 x1

(i ≥ 1)

over three variables does not have an equivalent finite subsystem in F in(A∗ ). (2) Recall that the bicyclic monoid B is a 2-generator and 1-relator semigroup with a presentation ha, b | ab = 1i. The monoid B is isomorphic to the monoid generated by the functions α, β : N → N: α(n) = max{0, n − 1},

β(n) = n + 1 .

Define γi = β i αi , for i ≥ 0. Hence ( i γi (n) = n

if n ≤ i, if n > i.

We observe that γi γj = γmin{i,j} . Consider the system E ⊆ {x1 , x2 , x3 }∗ consisting of the equations

4.3 Isbell’s Zig-Zag Theorem for Dominions xi1 xi2 x3 = x3

49

(i = 1, 2, . . . ) .

As is easily seen the homomorphism δj defined by δj (x1 ) = β, δj (x2 ) = α and δj (x3 ) = γj , is a solution of xi1 xi2 x3 = x3 for all i ≤ j, but δj is not a solution of j+1 xj+1 1 x2 x3 = x3 . Hence the system E does not have an equivalent finite subsystem, and therefore the bicyclic monoid B does not satisfy CP. ⊔ ⊓ However, as an example, we have Theorem 4.10. Every commutative monoid satisfies CP.

4.3 Isbell’s Zig-Zag Theorem for Dominions Dominions Let now S be any semigroup. An element x ∈ S is said to be dominated by a subset U ⊆ S, if α(x) = β(x) for all homomorphisms α, β : S → P (to any semigroup P ) whenever α and β agree on U , α|U = β|U . The dominion of a subset U in a semigroup S is the set of all elements of S that are dominated by U : Dom(U, S) = {x ∈ S | α|U = β|U =⇒ α(x) = β(x) for all homomorphisms α, β : S → T } Lemma 4.6. Let U ⊆ S. The dominion Dom(U, S) is a subsemigroup of S, and [U ]S ⊆ Dom(U, S). Proof. Assume x, y ∈ Dom(U, S), and suppose α, β : S → P are homomorphisms, for which α|U = β|U . Now, α(xy) = α(x)α(y) = β(x)β(y) = β(xy) (since α and β are homomorphisms, and x and y are dominated by U ), and so also xy ∈ Dom(U, S). Therefore Dom(U, S) is a subsemigroup of S. It is clear that U ⊆ Dom(U, S), and thus the second claim follows from the first. ⊔ ⊓

Zig-zag theorem A rather neat condition for Dom(U, S) was given by Isbell in 1966 using zig-zags: Let x ∈ S. A sequence x = u0 y1 = x1 u1 y1 = x1 u2 y2 = x2 u3 y2 = · · · = xm u2m−1 ym = xm u2m (4.5) is called a zig-zag of x (in S over U ), if ui ∈ U for 0 ≤ i ≤ 2m and xi , yi ∈ S for 1 ≤ i ≤ m, and u2i−1 yi = u2i yi+1 u0 = x1 u1

and

and

xi u2i = xi+1 u2i+1

u2m−1 ym = u2m .

(i = 1, 2, . . . , m − 1) (4.6) (4.7)

4.3 Isbell’s Zig-Zag Theorem for Dominions

50

The length of the zig-zag (4.5) is m. The sequence u0 , u1 , . . . , u2m of elements of U is called the spine of the zig-zag (4.5). The value of the zig-zag (4.5) is x. The zig-zag sequence becomes more appealing, when it is written in the following form: z}|{ x = u0 y 1 = z}|{ z }| { x1 u1 y1 = x1 u1 y1 = z}|{ z }|{ x1 u2 y2 = x1 u2 y2 = z }| { z}|{ x2 u3 y2 = x2 u3 y2 = .. . }| { z }| { z xm−1 u2m−3 ym−1 = xm−1 u2m−3 ym−1 = z }| { z }| { xm−1 u2m−2 ym = xm−1 u2m−2 ym = z }| { z}|{ xm u2m−1 ym = xm u2m . Lemma 4.7. If two elements x and y in S have the same spine u0 , u1 , . . . , u2m , then x = y. Proof. If x = u0 y1 = x1 u1 y1 = · · · = xm u2m−1 ym = xm u2m , y = u0 v1 = z1 u1 v1 = · · · = zm u2m−1 vm = zm u2m , then y = u0 v1 = x1 u1 v1 , since u0 = x1 u1 ; and therefore y = x1 u1 v1 = · · · = xm u2m−1 vm = xm u2m = x , ⊔ ⊓

by the conditions required in (4.5).

We prove the following theorem only in one direction, the proof in the opposite direction requires either new methods (topological as in the original Isbell’s proof (1966), or tensor products as in the proofs by Stenstr¨om (1971), Howie (1976) and Storrer (1976), or semigroup diagrams and HNN extensions as in Jackson’s proof (1991)), or extensive technics in combinatorics of presentations (as in Higgins’ proof (1991) based on Jackson’s proof). Theorem 4.11 (Isbell’s Zig-Zag Theorem). Let U be a subsemigroup of a semigroup S. Then Dom(U, S) = U ∪ {x | there is a zig-zag of x in S over U } .

Proof. (1) Assume first that there exists a zig-zag (4.5) of x, and let α, β : S → P be two homomorphisms that agree on the subsemigroup U : α|U = β|U . In particular, α(ui ) = β(ui )

(for all 1 ≤ i ≤ 2m) .

(4.8)

4.3 Isbell’s Zig-Zag Theorem for Dominions

51

For notational convenience we extend the homomorphisms α and β to S 1 (where an identity element 1 is added, if it was not there) by setting α(1) = 1 = β(1). Let x0 = 1 and ym+1 = 1. Hence (4.5) becomes x = x 0 u0 y 1 ,

xi−1 u2i−2 yi = xi u2i−1 yi ,

xi u2i−1 yi = xi u2i yi+1 ,

(4.9)

for all 1 ≤ i ≤ m. We prove by induction that α(x) = β(xi u2i ) · α(yi+1 )

(for all 0 ≤ i ≤ m) ,

(4.10)

from which it follows that α(x) = β(xm u2m )α(ym+1 ) = β(x) as required. To begin the induction, we obtain using (4.8) that α(x) = α(u0 y1 ) = α(u0 )α(y1 ) = β(u0 )α(y1 ) = β(x0 u0 )α(y1 ) , and hence the claim (4.10) holds for i = 0. Make an induction hypothesis that the claim (4.10) holds for i < m. We show that it holds for i + 1. Indeed, (4.6)

IH

α(x) = β(xi u2i )α(yi+1 ) = β(xi+1 u2i+1 )α(yi+1 ) (4.8)

= β(xi+1 )β(u2i+1 )α(yi+1 ) = β(xi+1 )α(u2i+1 )α(yi+1 ) (4.6)

= β(xi+1 )α(u2i+1 yi+1 ) = β(xi+1 )α(u2i+2 yi+2 ) (4.8)

= β(xi+1 )α(u2i+2 )α(yi+2 ) = β(xi+1 )β(u2i+2 )α(yi+2 ) = β(xi+1 u2i+2 )α(yi+2 ) , and this completes the induction on (4.10), and proves that each zig-zag produces an element of the dominion. (2) In converse, we give only the very basic idea of the proof due to Jackson (1991) as modified by Higgins (1991). Assume that x ∈ Dom(U, S), but x ∈ / U . (The claim is trivial for x ∈ U ). Let S = hA | Ri be a presentation of S, and assume t ∈ / A is anew letter. Let P be a semigroup which is obtained from S by adding a new generator t and the following additional relations: t2 = 1,

tu = ut

and

tut = u .

for all u ∈ U . Hence P = hA, t | R, tt = 1, tu = ut (u ∈ U )i . Define α, β : S → P by α(y) = y

and

β(y) = tyt

(y ∈ S) .

Now, α(u) = u = tut = β(u) for all u ∈ U , and therefore α|U = β|U , and, by assumption, also α(x) = β(x) holds, since x ∈ Dom(U, S). Since now x = txt and so tx = ttxt = xt, also tx = xt. The proof goes on now by showing that the condition tx = xt implies that x has zig-zag in S over U . ⊔ ⊓

5 Green’s Relations 5.1 Definitions Introducing the relations Let S be a semigroup, and define the following relations on S, xLy ⇐⇒ S 1 x = S 1 y xRy ⇐⇒ xS 1 = yS 1 xJy ⇐⇒ S 1 xS 1 = S 1 yS 1 . Here S 1 x, xS 1 and S 1 xS 1 are the principal left ideal, the principal right ideal and the principal ideal generated by x ∈ S. By the definitions, xLy ⇐⇒ ∃s, s′ ∈ S 1 : x = sy and y = s′ x xRy ⇐⇒ ∃r, r ′ ∈ S 1 : x = yr and y = xr ′ . As an exercise we have Lemma 5.1. The relations L, R and J are equivalence relations on S. In fact, L is a right congruence and R is a left congruence of S. We denote the corresponding equivalence classes containing x by Lx = {y | xLy},

Rx = {y | xRy},

Jx = {y | xJy} .

Example 5.1. Consider the semigroup S from the table. Then

S 1 a = {a, d}, S 1 b = {a, b, c, d}, S 1 c = {a, b, c, d}, S 1 d = {a, d} aS 1 = {a}, bS 1 = {a, b}, cS 1 = {a, c}, dS 1 = {d} .

· a b c d

a a a a d

b a b c d

The equivalence classes with respect to L are La = {a, d} = Ld and Lb = {b, c} = Lc and those with respect to R, Ra = {a}, Rb = {b}, Rc = {c} and Rd = {d}. ⊔ ⊓ Example 5.2. Let TX be the full transformation semigroup on X. Now, for α, β ∈ TX , αRβ ⇐⇒ ∃γ, γ ′ ∈ TX : α = βγ and β = αγ ′ .

c a b c d

d a a a d

5.1 Definitions

53

Therefore, αRβ implies that α(X) = β(X). On the other hand, if α(X) = β(X), then define γ ∈ TX as a function, for which γ(x) = some x with β(x) = α(x) . Then, in the above notations, βγ(x) = β(x) = α(x), and hence α ∈ βTX1 . Similarly, β ∈ αTX1 , and hence, αRβ ⇐⇒ α(X) = β(X). ⊔ ⊓ Theorem 5.1. The relations L and R commute: L ◦ R = R ◦ L. Proof. Suppose that (x, y) ∈ L ◦ R. This means that there exists an element z ∈ S such that xLz and zRy. Therefore there are elements s, s′ , r, r ′ ∈ S such that x = sz, z = s′ x, z = yr, y = zr ′ . Denote t = szr ′ . Now, t = sz · r ′ = xr ′ , x = sz = syr = szr ′ r = tr , which means that xRt. On the other hand, t = s · zr ′ = sy, y = zr ′ = s′ xr ′ = s′ szr ′ = s′ t , which implies that yLt. Since xRt and tLy, also (x, y) ∈ R ◦ L. We have shown that L ◦ R ⊆ R ◦ L. The inclusion in the other direction is proved in the same way. ⊔ ⊓

D- and H-relations The previous result is important because it implies that the product D =L◦R is an equivalence relation. Lemma 5.2. D is the smallest equivalence relation that contains both L and R. Proof. Clearly, L ⊆ D and R ⊆ D, since xLx and xRx hold for all x ∈ S 1 . In order to show that D is an equivalence relation one needs to show that it is transitive: if xDz and zDy, then also xDy. This is an exercise. In order to show that D is the smallest equivalence relation containing L ∪ R one assumes an equivalence relation C with L ∪ R ⊆ C, and shows that D ⊆ C. This is an exercise. ⊔ ⊓

5.1 Definitions

54 J

D

L

R

H

Fig. 5.1. The inclusion diagram of the Green’s relations

Let H = L ∩ R. Hence H is an equivalence relation, and it is the largest equivalence relation of S that is contained in both L and R. The inclusion diagram of the Green’s relations is given in Fig. 5.1. Here one needs to observe that D ⊆ J by Lemma 5.2. We denote by Dx and Hx the corresponding equivalence classes that contain the element x ∈ S. Clearly, for all x ∈ S H x = L x ∩ Rx .

On D-classes Lemma 5.3. For each semigroup S we have xDy ⇐⇒ Lx ∩ Ry 6= ∅ ⇐⇒ Ly ∩ Rx 6= ∅ . Moreover, Dx =

[

y∈Dx

Ly =

[

Ry .

y∈Dx

Proof. By the definition of D, xDy ⇐⇒ ∃z ∈ S : xLz and zRy ⇐⇒ ∃s ∈ S : xRs and sLy . The first claim follows from this. For the second claim is trivial, since L ⊆ D and R ⊆ D.

⊔ ⊓

The situation can be visualized by the following eggbox picture: Here the rows are R-classes and the columns are L-classes. Their intersections are H-classes, if nonempty (the intersection Ly ∩ Rz is nonempty, if yDz). Indeed, if u ∈ Ly ∩ Rz , then Ly = Lu and Rz = Ru , and so Ly ∩ Rz = Hu .

5.1 Definitions

55 Ly

Rz

Ly ∩ Rz

Fig. 5.2. The eggbox visualization of a D-class Dx

Example 5.3. Let X = {1, 2, . . . , 7}, and consider the subsemigroup S of the full transformation semigroup TX generated by α and β as defined in the table. 1 2 3 4 5 6 7 α 2 2 5 6 5 6 5 β 3 4 3 4 7 4 7 This semigroup consists of six elements α, β, αβ, βα, αβα and βαβ. By computing we get βαβα = βα, and hence βαRβαβ. Also, αβRαβα holds, as do βαLαβα and αβLβαβ.

αβ

αβα

βαβ

βα

Fig. 5.3. Eggbox for Dβα

We conclude (after some calculations) that the eggbox for the class Dβα looks like in the figure. ⊔ ⊓

5.2 Green’s Lemma and Its Corollaries

56

5.2 Green’s Lemma and Its Corollaries Green’s lemma(s) Let S be a semigroup. For each s ∈ S we define (as before) the mapping ρs : S 1 → S 1 by ∀z ∈ S 1 : ρs (z) = sz . The usefulness of the Green’s relations are due to the following version of Green’s lemma. Lemma 5.4. Let S be a semigroup, xLy, and let s, s′ ∈ S 1 be such that sx = y and s′ y = x. Then 1. ρs : Rx → Ry is a bijection, and ρs′ : Ry → Rx is a bijection, 2. ρs′ = ρ−1 s is the inverse function of ρs restricted to Rx , 3. ρs fixes the L-classes, that is, zLρs (z) for all z ∈ Rx , 4. ρs preserves H-classes, that is, for all u, v ∈ Rx : uHv ⇐⇒ ρs (u)Hρs (v) .

Rx

x

z

Ry

y

ρs (z)



Lx

Fig. 5.4. Green’s lemma

Proof. First we have to prove that ρs maps Rx into Ry . For this, let z ∈ Rx , that is, zS 1 = xS 1 . We have now szS 1 = sxS 1 = yS 1 , which shows that ρs (z) = sz ∈ Ry as required. A symmetric argument shows that ρs′ maps Ry into Rx . If z ∈ Rx , then zRx and therefore there are elements u, u′ ∈ S 1 such that z = xu and x = zu′ . Now, s′ sz = s′ s · xu = s′ · sx · u = s′ yu = xu = z , and hence ∀z ∈ Rx : s′ sz = z .

(5.1)

5.2 Green’s Lemma and Its Corollaries

57

Hence ρs′ ρs (z) = ρs′ (sz) = s′ sz = z , and so ρs′ ρs is the identity mapping of Rx . Similarly, ρs ρs′ is the idenitity mapping of Ry , from which we conclude Claims (1) and (2). For Case (3) assume z ∈ Rx . By (5.1), the elements z and ρs (z) (= sz) are in the same L-class. For Case (4) we notice that uHv if and only if uLv and uRv; and so uHv =⇒ ρs (u)Lρs (v) and ρs (u)Rρs (v) =⇒ ρs (u)Hρs (v) by Case (3) and since R is a left congruence (and ρs (u) = su, ρs (v) = sv). On the other hand, if ρs (u)Hρs (v), that is, suHsv, then uHv, since, by equation (5.1), u = s′ su and ⊔ ⊓ v = s′ sv (and since R is a left congruence and ρs′ fixes the L-classes). In particular, ρs maps each H-class Hz (with z ∈ Rx ) bijectively onto the H-class Hρs (z) . The next dual version of Lemma 5.4 is proved similarly. Here λr : S 1 → S 1 is the opposite version of ρr : ∀z ∈ S : λr (z) = zr . Lemma 5.5. Let S be a semigroup, yRz, and let r, r ′ ∈ S 1 be such that yr = z and zr ′ = y. Then 1. λr : Ly → Lz is a bijection, and λr′ : Lz → Ly is a bijection, 2. λr′ = λ−1 r is the inverse function of λr restricted to Ly , and 3. λr preserves the R-classes, that is, wRλr (w) for all w ∈ Ly . λr

? -

x

u

ρs′

ρs y

z



6 λr ′

Fig. 5.5. Combination of Green’s lemmas

Lemma 5.6. Let e ∈ ES be an idempotent. If xLe, then xe = x. If xRe, then ex = x.

5.2 Green’s Lemma and Its Corollaries

58

Proof. If xLe, then x ∈ Le , that is, x = se for some s ∈ S 1 . Therefore, since e = ee, x = se · e = xe. The other case is similar. ⊔ ⊓ Corollary 5.1. Each H-class contains at most one idempotent.

Sizes of the H-classes In the above notations, ρs is a bijection Rx → Ry and λr is a bijection Ly → Lz and therefore Corollary 5.2. The H-classes inside a D-class have the same cardinality, that is, if xDy, then there exists a bijection between Hx and Hy . Proof. Indeed, if x, z ∈ S are in the same D-class such that xLy, yRz with sx = y, s′ y = x, yr = z, zr ′ = y , then by the above lemmas ρs : Hx → Hy and λr : Hy → Hz are bijections. Therefore λr ρs : Hx → Hz is a bijection. ⊔ ⊓

Green’s theorem for H-classes The following rather crusial result is the location theorem of Miller and Clifford (1956). Theorem 5.2. Let x, y ∈ S. Then xy ∈ Rx ∩ Ly ⇐⇒ Ry ∩ Lx contains a unique idempotent.

Rx

x

xy

Ry

e

y

Lx

Ly

Fig. 5.6. Location theorem

Proof. Suppose first that xy ∈ Rx ∩ Ly . Since yLxy, we may choose s = x in Lemma 5.4, and so ρx : Ry → Rxy is a bijection. Also xyRx, and hence Rxy = Rx , which means that ρx : Ry → Rx is a bijection. The mapping ρx preserves L-classes and so ρx maps Ry ∩ Lx onto Rx ∩ Lx = Hx . Therefore there exists a z ∈ Ry ∩ Lx such that ρx (z) = x, that is, xz = x.

5.2 Green’s Lemma and Its Corollaries

59

Because zLx, there exists a u ∈ S 1 with z = ux. We have thus obtained xux = xz = x, and thus zz = uxux = ux = z, which means that z ∈ ES . In the other direction, suppose there exists an idempotent e ∈ Ry ∩ Lx . Now, by Lemma 5.6, ey = y and xe = x. From eRy we obtain that xeRxy, and thus xRxy. From eLx we obtain that eyLxy, and thus yLxy. So xy ∈ Rx ∩ Ly as required. Finally, if Ry ∩ Lx contains an idempotent, it must be unique by Corollary 5.1, since Ry ∩ Lx is an H-class. ⊔ ⊓ In the following Green’s theorem, G is a subgroup of a semigroup S, if G is a subsemigroup, which is a group. We start with a small lemma. Lemma 5.7. Let e, f ∈ ES . Then for all x ∈ Re ∩ Lf there exists y ∈ Rf ∩ Le such that xy = e and yx = f . Proof. Let x ∈ Re ∩ Lf . Hence by Lemma 5.6, x = ex = xf , and there are u, v ∈ S 1 , for which e = xu and f = vx. Now, y = f u is the required element of the claim: First of all f = vx = vex = vxux = f ux = yx (5.2) and e = xu = xf u = xy .

(5.3)

Hence, y ∈ Rf by (5.2) and the fact that y = f · u; and y ∈ Le , by (5.3) and since y = f u = vxu = ve. So y ∈ Rf ∩ Le . ⊔ ⊓ Theorem 5.3. Let H be an H-class of S. Then the following are equivalent: 1. H contains an idempotent. 2. There exists x, y ∈ H such that xy ∈ H. 3. H is a subgroup of S. Proof. That Case (1) implies Case (2) is clear, since we can choose x = e = y for the idempotent e ∈ H. Assume Case (2). Then Case (1) follows by Theorem 5.2, since now Rx ∩ Ly = H = Ry ∩ Lx . Therefore H contains an idempotent e, and hence by the converse claim of Theorem 5.2, we know that H is a subsemigroup of S. Further, H is a monoid with identity e by Lemma 5.6. We apply then Lemma 5.7 for e = f . This shows that H is a group. Hence Case (2) implies Case (3). Case (3) implies Case (1), since the identity element of the group H is an idempotent of S. ⊔ ⊓

Example: periodic semigroups We say that a semigroup S is periodic, if each of its elements has a finite order, that is, the monogenic subsemigroup [x] is finite for all x ∈ S. As an exercise we have

5.2 Green’s Lemma and Its Corollaries

60

Lemma 5.8. If S is periodic, then each [x] contains an idempotent. Theorem 5.4. For periodic semigroups J = D. Proof. The inclusion D ⊆ J is valid for all semigroups. Thus we have to show that J ⊆ D. Suppose that xJy. Therefore there exist u, v, r, s ∈ S 1 such that x = uyv

and

y = rxs .

Now, ∀i ≥ 0 : x = (ur)i x(sv)i

and y = (ru)i y(vs)i .

By Lemma 5.8, there exists a nonnegative n such that (ur)n ∈ ES . We may suppose here that ur 6= 1, for otherwise already xRy and thus xDy, since R ⊆ D. Denote z = rx, for short. We have then x = (ur)n x(sv)n = (ur)n (ur)n x(sv)n = (ur)n x = (ur)n−1 uz , and so xLz, since z = r · x. Further, y = rxs = zs and if (vs)k ∈ ES , then z = rx = r(ur)k+1 x(sv)k+1 = (ru)k+1 rxs(vs)k v = (ru)k+1 y(vs)k v = (ru)k+1 y(vs)k (vs)k v = (ru)k+1 y(vs)k+1 (vs)k−1 v = y(vs)k−1 v , which shows that zRy, and so xDy. This proves that J = D. Corollary 5.3. For all finite semigroups S, J = D.

⊔ ⊓

6 Inverse Semigroups 6.1 Regular Semigroups Basic properties of regular elements We say that an element x of a semigroup S is regular, if there exists an element y ∈ S such that x = xyx . Also, S is regular, if each of its elements is regular. Example 6.1. (1) All groups are regular: x = xx−1 x, where x−1 is the group inverse of x. A regular semigroup is a group if and only if it has exactly one idempotent (Exercise). (2) If e ∈ ES is an idempotent, then e = eee, and hence all idempotents of a semigroup are regular elements of S. (3) The full transformation semigroup TX is regular (Exercise).

⊔ ⊓

We obtain immediately Lemma 6.1. Let x be a regular element in S: x = xyx. Then xy ∈ ES and yx ∈ ES . Lemma 6.2. Let x ∈ S. Then the following are equivalent: 1. x is regular. 2. ∃e ∈ ES : xRe. 3. ∃f ∈ ES : xLf . Proof. Assume first that x is regular, and let x = xyx. Then e = xy ∈ ES and f = yx satisfy xRe and xLf . Suppose then that xRe. Now, x = ex by Lemma 5.6, and there exists a y ∈ S 1 such that e = xy. Therefore x = ex = xyx, and x is regular. The case for L is similar. ⊔ ⊓ Note that, by Lemma 5.7, if e, f ∈ ES , then for all x ∈ Re ∩ Lf there exists a (unique) y ∈ Rf ∩ Le such that xy = e and yx = f .

6.1 Regular Semigroups

62

Rx = Re

x

e = xy

Rf

f = yx

y

Lx = Lf

Le

Fig. 6.1. The eggbox of Dx for a regular x

Regular D-classes We say that a class Dx is regular, if it contains only regular elements. Lemma 6.3. If x ∈ S is regular element, then Dx is regular. Proof. Suppose that x is regular. Hence, by Lemma 6.2, the class Dx contains an idempotent e, that is, Dx = De . Let then z ∈ Dx . Now, zDe, and thus there exists u ∈ Dx with eRu and uLz. So there are elements r, s, s′ ∈ S such that e = ur, u = eu, u = sz, z = s′ u . Here, u = eu by Lemma 5.6. Now, z = s′ u = s′ eu = s′ esz = s′ ursz = z · rs · z , and so z is regular.

⊔ ⊓

In particular, De is regular for each idempotent e ∈ ES . Lemma 6.4. If a D-class D is regular, then each Lx ⊆ D and each Rx ⊆ D contains an idempotent. Proof. When x ∈ D, then x = xyx for some y, and hence xLyx and xRxy, where xy and yx are idempotents. ⊔ ⊓ From these we obtain Theorem 6.1. A D-class is regular if and only if it contains an idempotent.

6.2 Inverse Semigroups

63

Inverse elements in semigroups We say that y ∈ S is an inverse element of x ∈ S, if x = xyx

and

y = yxy .

Note that an inverse element of x, if such an element exists, need not be unique. Lemma 6.5. Each regular element x ∈ S has an inverse element. Proof. If x ∈ S is regular, then for some y ∈ S, x = xyx. Now, yxy = yxy · x · yxy, and so yxy is also regular. Also, x = x · yxy · x and consequently yxy is an inverse element of x. ⊔ ⊓

Lallement’s lemma Lemma 6.6. Let S be a regular semigroup, and let α : S ։ P be an epimorphism onto a semigroup P . If e ∈ EP , then α−1 (e) ∩ ES 6= ∅, that is, there exists an idempotent f ∈ ES such that α(f ) = e. Proof. Let x ∈ S be such that α(x) = e, and let y be an inverse element of x2 in S: x2 = x2 yx2 and y = yx2 y. Then for f = xyx, α(f ) = α(x)α(y)α(x) = α(x)2 α(y)α(x)2 = α(x2 yx2 ) = α(x2 ) = α(x)2 = e2 = e , that is, α(f ) = e. Here f is an idempotent: xyx · xyx = x · yx2 y · x = xyx.

⊔ ⊓

As a consequence we have Theorem 6.2. Let ρ be a congruence of a regular S, then xρ ∈ ES/ρ =⇒ ∃e ∈ ES : xρ = eρ .

As an exercise Theorem 6.3. If α : S → P is a homomorphism from a regular semigroup S, then α(S) is regular. In particular, if α is an epimorphism, then P is regular.

6.2 Inverse Semigroups Example A semigroup S is called an inverse semigroup, if each x ∈ S has a unique inverse element x−1 : x = xx−1 x and x−1 = x−1 xx−1 .

6.2 Inverse Semigroups

64

Example 6.2. (1) If S is a group, then it is an inverse semigroup, and x−1 is the group inverse of the element x. (2) Consider Z × Z as a drawing board so that you can draw a unit line up u, down d, right r and left ℓ. A word w ∈ A∗ = {u, d, r, ℓ}∗ produces a figure on Z × Z, when you start from (0, 0) and follow the instructions given by the word w. ·

·

·

•

◦ w = uurd

·

•

◦

·

v = ruℓdur

Fig. 6.2. The figures drawn by the words w and v

We identify the words w1 and w2 , and denote w1 ⊲⊳ w2 , if they draw the same figure with the same endpoint. This means that u ⊲⊳ udu, d ⊲⊳ dud, r ⊲⊳ rℓr, and ℓ ⊲⊳ ℓrℓ .

(6.1)

It should be clear that if w1 ⊲⊳ w2 and v ∈ A∗ , then also vw1 ⊲⊳ vw2 and w1 v ⊲⊳ w2 v, and hence ⊲⊳ is a congruence on the word semigroup A+ . The quotient T2 = A+ / ⊲⊳ might be called the (two-dimensional) turtle semigroup. It is an inverse semigroup with u−1 = d, d−1 = u, r −1 = ℓ and ℓ−1 = r, and the inverse of an element w ⊲⊳ for a word w = x1 x2 . . . xn ∈ A+ is obtained by reversing the order of the instructions: −1 −1 w−1 = x−1 ⊔ ⊓ n xn−1 . . . x1 .

The semilattice of idempotents If e ∈ ES for an inverse semigroup, then eee = e, and hence for all idempotents e, e−1 = e. Theorem 6.4. Let S be an inverse semigroup. Then the idempotents ES form a subsemigroup of S. Moreover, ES is a semilattice, that is, the idempotents of an inverse semigroup commute. Proof. Let e, f ∈ ES and consider the (unique) inverse element x = (ef )−1 of ef . Now, ( ef · xe · ef ef = ef · x · ef = ef · f x · ef and xe · ef · xe = xef x · e = xe , f x · ef · f x = f · xef x = f x .

6.2 Inverse Semigroups

65

This means that x = (ef )−1 = xe = f x. Here x ∈ ES , since x2 = xe · f x = x · ef · x = x , and so ef ∈ ES for all e, f ∈ ES , that is, ES is a subsemigroup of S. Further, ES is commutative: For e, f ∈ ES , also ef, f e ∈ ES , and ef · f e · ef = ef ef = (ef )2 = ef

and

f e · ef · f e = f ef e = (f e)2 = f e ,

meaning that f e = (ef )−1 = ef .

⊔ ⊓

Corollary 6.1. Assume S = [X]S . If each generator x ∈ X has a unique inverse element, then S is an inverse semigroup: −1 −1 (x1 x2 . . . xn )−1 = x−1 n xn−1 . . . x1

for all xi ∈ X. Proof. Assume x, y ∈ S have unique inverse elements x−1 and y −1 , respectively. Then xy · y −1 x−1 · xy = x · yy −1 · x−1 x · y = x · x−1 x · yy −1 · y = xy . The rest of the claim follows by induction.

⊔ ⊓

Corollary 6.2. In an inverse semigroup S, for all x ∈ S, x = (x−1 )−1 .

A characterization Theorem 6.5. Let S be a semigroup. The following are equivalent: 1. S is an inverse semigroup. 2. S is regular and its idempotents commute. 3. Each L-class and R-class contains an idempotent. Proof. Case (1) implies Case (2) by Theorem 6.4. Suppose Case (2). By Lemma 6.4, each L-class and R-class contains a unique idempotent. For the uniqueness let f ∈ Le , where e, f ∈ ES . Hence eLf , and therefore there are x, y ∈ S 1 such that e = xf and f = ye. From here we obtain e = xf = xf f = ef = f e = yee = ye = f . Similarly, eRf implies that e = f . So Case (2) implies Case (3). Suppose Case (3). Now each D-class contains an idempotent, and hence, by Theorem 6.1, each x ∈ S has an inverse element. Suppose an element x has two inverse elements y and z. Now, yx, zx ∈ ES with yxLx and zxLx. Then, by assumption, yx = zx. A similar reasoning using R shows that xy = xz. Therefore y = yxy = zxz = z, and Case (1) follows. ⊔ ⊓

6.2 Inverse Semigroups

66

As exercises we have Corollary 6.3. Let S be an inverse semigroup. Then ∀x ∈ S : x−1 ES x ⊆ ES . Theorem 6.6. Let S be an inverse semigroup, and let x, y ∈ S and e, f ∈ ES . Then 1. xLy ⇐⇒ x−1 x = y −1 y. 2. xRy ⇐⇒ xx−1 = yy −1 . 3. eDf ⇐⇒ ∃z ∈ S : e = zz −1 and f = z −1 z.

Partial ordering inverse semigroups Recall that in any semigroup S the idempotents can be partially ordered by the relation: e ≤ f ⇐⇒ ef = e = f e . This partial order generalizes in an inverse semigroup S to all elements of S as follows, x ≤ y ⇐⇒ ∃e ∈ ES : x = ey . Indeed, here ≤ is • reflexive, since x = (xx−1 ) · x, where xx−1 ∈ ES ; • antisymmetric, since if x = ey and y = f x, then x = ey = eey = ex, and so x = ey = ef x = f ex = f x = y; • transitive, since if x = ey and y = f z, then also x = ey = ef z, where ef ∈ ES . If you restrict ≤ onto ES you get the above partial order of idempotents. Indeed, if e ≤ f , then there exists g ∈ ES such that e = gf , and here e = gf f = ef = f e as required. As an exercise we state Lemma 6.7. In an inverse semigroup S we have x ≤ y ⇐⇒ ∃e ∈ ES : x = ye ⇐⇒ xx−1 = yx−1 ⇐⇒ x = xy −1 x ⇐⇒ xx−1 = xy −1 ⇐⇒ x−1 x = y −1 x ⇐⇒ x−1 x = x−1 y ⇐⇒ x = xx−1 y .

Groups as inverse semigroups All groups are inverse semigroups, and moreover Theorem 6.7. Let S be a semigroup. Then the following are equivalent: 1. S is a group. 2. ∀x ∈ S ∃!x′ ∈ S : x = xx′ x.

6.3 Representations by Injective Partial Mappings

67

3. ∀x ∈ S ∃!x′ ∈ S : xx′ ∈ ES . 4. S is an inverse semigroup that satisfies: x = xyx =⇒ y = yxy. Proof. Case (1) implies Case (2) by choosing x′ = x−1 , the group inverse of x. Case (2) implies Case (3): In one direction, the claim is clear, since if x = xx′ x, then ′ xx ∈ ES . Conversely assume that x = xx′ x for a unique x′ (in which case xx′ ∈ ES ), and xy ∈ ES . Now, xyx = xy · xy · x = xyx · x′ · xyx , and xyx = xyx · y · xyx , wherefrom we obtain that y = x′ , when (2) is applied to xyx. Case (3) implies Case (4), since if x = xyx, then xy ∈ ES , and from xy = xyxy ∈ ES we get y = yxy by the uniqueness assumption, and here y = x′ = x−1 . Case (4) implies Case (1), since xyy −1 = xx−1 x · yy −1 yy −1 = xyy −1 · x−1 · xyy −1 =⇒ x−1 = x−1 · xyy −1 · x−1 =⇒ x = x · yy −1 x−1 · x = xx−1 x · ·yy −1 = xyy −1 . Similarly, x = yy −1 x, and so y −1 is a group inverse of y.

⊔ ⊓

Theorem 6.8. If an inverse semigroup S is right cancellative, then it is a group. Proof. Suppose xy ∈ ES . We have xy = xyxy, and hence by cancellation, x = xyx and y = yxy, which means that y = x−1 , since S is inversive. ⊔ ⊓

6.3 Representations by Injective Partial Mappings Partial mappings Let X 6= ∅ be a set. A partial mapping α : X → X is a function from a subset Y = dom(α) of X onto ran(α) = α(Y ) ⊆ X. A partial mapping α : X → X is undefined on all x ∈ / dom(α). Example 6.3. Let X = {1, 2, . . . , 5} and let dom(α) = {2, 4, 5} with α(2) = 1, α(4) = 5 and α(5) = 1. We can represent α as follows   245 α= . 151 Here ran(α) = {1, 5}.

⊔ ⊓

6.3 Representations by Injective Partial Mappings

68

We say that a partial mapping α : X → X is injective, if α(x) 6= α(y) for all x 6= y with x, y ∈ dom(α). The injective partial mappings form a semigroup, denoted IX , under the usual composition: (βα)(x) = β(α(x))

if

x ∈ dom(α) and α(x) ∈ dom(β) .

We observe that dom(βα) = α−1 (ran(α) ∩ dom(β))

ran(βα) = β(ran(α) ∩ dom(β)) . (6.2) We denote by ιY : X → X the partial function such that dom(ιY ) = Y = ran(ι) and ιY (y) = y for all y ∈ Y . and

Theorem 6.9. IX is an inverse semigroup. Proof. Let α ∈ IX , and let α−1 : X → X be defined by α−1 (y) = x

if α(x) = y

for x ∈ dom(α) ,

that is, dom(α−1 ) = ran(α) and ran(α−1 ) = dom(α). Moreover, α−1 (α(x)) = x for all x ∈ dom(α). Clearly, α−1 ∈ IX . Furthermore, α−1 α = ιdom(α)

and

αα−1 = ιran(α) .

Now, αα−1 α = α and α−1 αα−1 = α−1 , and so α−1 is an inverse element of α, and IX is a regular semigroup. By Theorem 6.4, we need to show that the idempotents of IX commute. For this we prove that ε ∈ EIX ⇐⇒ ε = ιY for some Y ⊆ X . Indeed, suppose ε is an idempotent of IX . Then by (6.2), dom(ε2 ) = ε−1 (ran(ε) ∩ dom(ε)) = dom(ε) , and so by injectivity, ran(ε) ∩ dom(ε) = ε(dom(ε)) = ran(ε) , which implies that dom(ε) ⊆ ran(ε). Similarly, ran(ε2 ) = ran(ε) implies that ran(ε) ⊆ dom(ε), and so ran(ε) = dom(ε). Further, ε2 (x) = ε(x) for all x ∈ dom(ε), and thus, by injectivity, ε(x) = x for all x ∈ dom(ε). Finally, the idempotents commute, since for all Y, Z ⊆ X, ιZ ιY = ιY ∩Z = ιY ιZ , and so the theorem is proved.

⊔ ⊓

6.3 Representations by Injective Partial Mappings

69

The Vagner-Preston representation Theorem 6.10. Each inverse semigroup S has a faithful representation as a semigroup of injective partial mappings, that is, there exists an embedding ϕ : S ֒→ IX for some set X. Proof. We choose X = S itself, and define for each x ∈ S the mapping τx : x−1 S → S

by

τx (y) = xy

(y ∈ x−1 S) .

First of all x−1 S = x−1 xS,

(6.3)

because x−1 xS ⊆ x−1 S, and x−1 S = x−1 xx−1 S ⊆ x−1 xS. In particular, since x−1 x ∈ ES , y ∈ dom(τx ) = x−1 S ⇐⇒ y = x−1 xy . (6.4) To show that τx ∈ IX we need to show that it is injective. For this let y, z ∈ x−1 S be such that τx (y) = τx (z). Thus xy = xz, and so by (6.4), y = x−1 xy = x−1 xz = z. We need also: dom(τyx ) = dom(τy τx ) . (6.5) To prove this we notice that z ∈ dom(τy τx ) ⇐⇒ z ∈ dom(τx ) and τx (z) ∈ dom(τy ) , that is z ∈ dom(τy τx ) ⇐⇒ z = x−1 xz and xz = y −1 yxz , by (6.4). Therefore if z ∈ dom(τy τx ), then z = x−1 xz = x−1 y −1 yxz = (yx)−1 · yx · z and hence z ∈ dom(τyx ) by (6.4). On the other hand, if z ∈ dom(τyx ), then z = (yx)−1 · yx · z, and so z = x−1 x · x−1 y −1 yxz = x−1 xz, from which it follows that z ∈ dom(τx ). Also, in this case, by commuting the idempotents, xz = xx−1 y −1 yxz = y −1 yxx−1 xz = y −1 yxz , and hence τx (z) = xz ∈ dom(τy ). This proves (6.5). Define then ϕ : S → IX by ϕ(x) = τx

(x ∈ S) .

Now, ϕ is a homomorphism: When z ∈ dom(τy τx ) = dom(τyx ), then τy τx (z) = τy (xz) = yxz = τyx (z) , and so τy τx = τyx , that is,

6.4 Congruences of Inverse semigroups

70

ϕ(yx) = τyx = τy τx = ϕ(y)ϕ(x) . Finally, ϕ is injective: If ϕ(x) = ϕ(y), then τx = τy , and so by (6.3), x−1 xS = from which it follows that x−1 xRy −1 y for the idempotents x−1 x and y −1 y. By Theorem 6.6, x−1 x = y −1 y. Now, since x−1 x ∈ x−1 S = dom(τx ) = dom(τy ), it follows that τx (x−1 x) = τy (x−1 x). Here τx (x−1 x) = xx−1 x = x and τy (x−1 x) = yx−1 x = yy −1 y = y. Therefore x = y as required. ⊔ ⊓ y −1 yS,

6.4 Congruences of Inverse semigroups Heritage of images Lemma 6.8. Let S be an inverse semigroup and α : S → P a homomorphism. Then α(S) is an inverse subsemigroup of P . Proof. We have for all x ∈ S, α(x) = α(xx−1 x) = α(x) · α(x−1 ) · α(x), and so α(S) is a regular subsemigroup of P . Again, it sufficies to show that the idempotents of α(S) commute. Let g, h ∈ Eα(S) . By Lemma 6.6, there exist e, f ∈ ES so that g = α(e) and h = α(f ). Now, gf = α(ef ) = α(f e) = f g, from which the claim follows. ⊔ ⊓ In particular, Corollary 6.4. If ρ is a congruence of an inverse semigroup S, then S/ρ is an inverse semigroup. Therefore, Lemma 6.9. Let S be an inverse semigroup, and ρ its congruence. Then xρy ⇐⇒ x−1 ρy −1 . We obtain also that for each homomorphism α : S → P for an inverse semigroup S, ∀x ∈ S : α(x−1 ) = α(x)−1 . A subsemigroup T of an inverse semigroup S is called a inverse subsemigroup, if for all x ∈ T also x−1 ∈ T , where x−1 is the inverse element of x in S. Notice that not all subsemigroups of an inverse semigroup are inverse subsemigroups. The following lemma is an exercise. Lemma 6.10. Let S be an inverse semigroup, and let A be a subsemigroup of S. Then A is an inverse subsemigroup of S if and only if x−1 ∈ A for all x ∈ A. Lemma 6.11. Let S be an inverse semigroup, α : S → P an epimorphism, and let e ∈ EP . Then α−1 (e) is an inverse subsemigroup of S.

6.4 Congruences of Inverse semigroups

71

Proof. First of all, if α(x) = e = α(y), then α(xy) = e2 = e, and so xy ∈ α−1 (e). This means that α−1 (e) is a sunsemigroup of S. The claim follows when we show that x ∈ α−1 (e) implies x−1 ∈ α−1 (e). For this we just notice that if α(x) = e, then α(x−1 ) = α(x)−1 = e−1 = e. ⊔ ⊓ For ideals we have the following rather strong closure property (which will be an exercise). In general, if I is an ideal of a semigroup S, then S is called an ideal extension of I by S/I, where S/I is the Rees quotient. Theorem 6.11. Let I be an ideal of a semigroup S. Then S is an inverse semigroup if and only if I and S/I are inverse semigroups

Kernels and traces RES? Let ρ be a congruence of a semigroup S. We define its kernel ker(ρ) and trace tr(ρ) as follows: [ ker(ρ) = {x ∈ S | xρe for some e ∈ ES } = eρ , e∈ES

tr(ρ) = ρ(res)E = {(e, f) | e, f ∈ ES } .

Theorem 6.12. Let S be an inverse semigroup. Then for all congruences ρ and δ, ρ ⊆ δ ⇐⇒ ∀e ∈ ES : eρ ⊆ eδ . Proof. In one direction the claim is trivial. Suppose then that eρ ⊆ eδ for all e ∈ ES . Now, xρy =⇒ xx−1 ρyx−1 =⇒ xx−1 δyx−1 =⇒ xδyx−1 x , xρy =⇒ x−1 xρx−1 y =⇒ x−1 xδx−1 y =⇒ yx−1 xδyx−1 y , and thus xρy =⇒ xδyx−1 y .

(6.6)

On the other hand, xρy =⇒ x−1 ρy −1 =⇒ x−1 yρy −1 y =⇒ x−1 yδy −1 y =⇒ yx−1 yδy , and, by combining this with (6.6), we obtain that xδy holds. This shows that ρ ⊆ δ. Corollary 6.5. For an inverse semigroup S, ρ = δ ⇐⇒ ∀e ∈ ES : eρ = eδ for all congruences ρ and δ.

⊔ ⊓

6.4 Congruences of Inverse semigroups

72

We have then Vagner’s theorem: Theorem 6.13. Let S be an inverse semigroup, and let ρ and δ be its congruences. Then ρ = δ ⇐⇒ ker(ρ) = ker(δ) and tr(ρ) = tr(δ) .

In other words, If α : S ։ P and β : S ։ T are epimorphisms from an inverse semigroup S, then ker(α) = ker(β) if and only if for all x ∈ S and e, f ∈ ES , α(x) ∈ EP ⇐⇒ β(x) ∈ ET , α(e) = α(f ) ⇐⇒ β(e) = β(f ) . Proof. In one direction the claim is again trivial. Suppose then that ker(ρ) = ker(δ) and tr(ρ) = tr(δ). If e ∈ ES , then eρx =⇒ ∃f ∈ ES : f δx =⇒ f f −1 = f δxx−1 , eρx =⇒ ee−1 = eρxx−1 =⇒ eδxx−1 , and thus eδf and f δx hold, from which we obtain eδx, that is, eρ ⊆ eδ. The case for eδ ⊆ eρ is similar, and hence we can conclude that eρ = eδ, and finally ρ = δ by Corollary 6.5. ⊔ ⊓

Classifications according to traces Congruences of an inverse semigroup are classified according to their traces. Lemma 6.12. For all x ∈ S and e ∈ ES , x−1 ex ∈ ES . Proof. Indeed, by commuting idempotents, x−1 ex · x−1 ex = x−1 xx−1 eex = x−1 ex. ⊔ ⊓ For a congruence ρ of an inverse semigroup S, we obtain a congruence ρmin by defining xρmin y ⇐⇒ ∃e ∈ ES : xe = ye, x−1 xρe and y −1 yρe . The next theorem states that ρmin identifies as few elements as possible under the restriction that it should identify exactly the same idempotents as the original ρ. In this way the quotient S/ρmin is as large as possible. Theorem 6.14. For a congruence ρ of an inverse semigroup S, ρmin is the smallest congruence whose trace equals tr(ρ).

6.4 Congruences of Inverse semigroups

73

Proof. To show that ρmin is an equivalence relation demands some calculations, which we leave as an exercise. We show that ρmin is a congruence. For this suppose xρmin y and let e ∈ ES be such that xe = ye. Let z ∈ S. Now, f = z −1 ez ∈ ES , and xz · f = xzz −1 · ez = xe · zz −1 z = ye · zz −1 z = yzz −1 · ez = yz · f , and so there exists an idempotent f ∈ ES such that xz · f = yz · f . Further, (xz)−1 · xz = z −1 x−1 xz ρ z −1 ez ρ z −1 y −1 yz = (yz)−1 · yz ,

(6.7)

and therefore xzρmin yz. On the other hand, xe = ye implies that ex−1 = ey −1 by taking inverses of both sides, and using this we obtain (zx)−1 · zx = x−1 · z −1 z · x = x−1 x · x−1 z −1 z · x ρ ex−1 z −1 zx , (zy)−1 · zy = y −1 · z −1 z · y = y −1 y · y −1 z −1 zy · y −1 y ρ ey −1 z −1 zye = ex−1 · z −1 z · xe ρ ex−1 z −1 zx · x−1 x = ex−1 z −1 zx , which shows that zxρmin zy, since ex−1 z −1 zx is an idempotent. Thus ρmin is a congruence. Next we show that tr(ρmin ) = tr(ρ). For f, g ∈ ES , f ρmin g =⇒ ∃e ∈ E : f e = ge, f ρe and gρe =⇒ f ρg . On the other hand, suppose f ρg. Now, for e = f g we have f e = f f g = f g = f gg = gf g = ge, and, clearly, f ρe and gρe. Hence also f ρmin g and the traces are the same. Finally, ρmin is the smallest of such congruences: For any congruence δ with tr(δ) = tr(ρ), xρmin y =⇒ ∃e ∈ ES : xe = ye, x−1 xρe, y −1 yρe =⇒ x−1 xδe and y −1 yδe =⇒ xδxe and yδye =⇒ xδy , and therefore ρmin ⊆ δ as required.

⊔ ⊓

In particular, we have that ρmin ⊆ ρ for all congruences ρ of an inverse semigroup S. For a congruence ρ of an inverse semigroup S define ρmax by xρmax y ⇐⇒ ∀e ∈ ES : x−1 exρy −1 ey . Theorem 6.15. Let S be an inverse semigroup and ρ its congruence. Then ρmax is the largest congruence of S whose trace equals tr(ρ). Proof. First of all we show that ρmax is a congruence. That it is an equivalence relation is an easy exercise. Let then xρmax y and let z ∈ S. We have zxρmax zy ⇐⇒ ∀e ∈ ES : (zx)−1 ezxρ(zy)−1 ezy ⇐⇒ x−1 z −1 ezxρy −1 z −1 ezy .

6.4 Congruences of Inverse semigroups

74

Since z −1 ez ∈ ES , we have xρmax y =⇒ x−1 · z −1 ez · xρy −1 · z −1 ez · y , and thus zxρmax zy holds if xρmax y holds. Similarly, for xzρmax yz. We conclude that ρmax is a congruence. Next we show that tr(ρmax ) = tr(ρ). For this let f, g ∈ ES . Then f ρmax g =⇒ f −1 f f ρg −1 f g =⇒ f ρf g , and in the same way, f ρmax g =⇒ gρf g, from which we get that f ρg, and so tr(ρmax ) ⊆ tr(ρ). In the other direction, for all e ∈ ES , if f ρg, then f −1 ef ρg −1 eg and so we deduce that f ρmax g, that is, the traces are the same. Finally ρmax is the largest of such congruences. For this assume δ isa congruence such that tr(δ) = tr(ρ). Now, for all e ∈ ES , xδy =⇒ x−1 eaδy −1 ey =⇒ x−1 eaρy −1 ey =⇒ xρmax y , since x−1 ex, y −1 ey ∈ ES ; and so δ ⊆ ρmax as required.

⊔ ⊓

The above theorem states that ρmax identifies as many elements of S as possible with the restriction that it does not identify any idempotents unless ρ does so. Certainly, ρ ⊆ ρmax , and so the quotient S/ρmax is an epimorphic image of S/ρ.

Group congruences We say that a congruence ρ of a semigroup S is a group congruence, if S/ρ is a group. The following lemma holds already for regular semigroups. Lemma 6.13. An inverse semigroup is a group if and only if it has a unique idempotent. For a congruence ρ of an inverse semigroup, we have by Theorem 6.2 that xρ ∈ ES/ρ =⇒ ∃e ∈ ES : eρ = xρ , and hence Theorem 6.16. A congruence ρ of an inverse semigroup S is a group congruence if and only if tr(ρ) = ES × ES . Proof. If tr(ρ) = ES × ES , then S/ρ has exactly one idempotent by Theorem 6.2. In the other direction the claim is equally clear. ⊔ ⊓ If ρ is a group congruence of an inverse semigroup S, then so is ρmin , because now tr(ρ) = tr(ρmin ) = ES × ES . In particular, ρmin is the smallest group congruence of S, and for all group congruences δ of S, δmin = ρmin . The smallest group congruence of an inverse semigroup S is denoted by σS . Let then ρ be a group congruence. Then σS = ρmin ⊆ ρ, and hence, by the homomorphism theorem, there exists a unique homomorphism β such that the following diagram commutes:

6.4 Congruences of Inverse semigroups S

75 ρ♯

- S/ρ 

β σS♯ R S/σS

This means that every group G, which is a homomorphic image of S, is a homomorphic image of the group S/σS , and in this sense S/σS is a maximal homomorphic image of S. Remark 6.1. If S is not an inverse semigroup, it need not have the smallest group congruence. As an example consider (N+ , +). The group congruences of this semigroup are exactly ρn = {(p, q) | p ≡ p( mod n)}. ⊔ ⊓ Theorem 6.17 (Munn). In an inverse semigroup S, xσS y ⇐⇒ ∃e ∈ ES : xe = ye . Proof. Now, σS = σmin , and so xσS y ⇐⇒ ∃e ∈ ES : xe = ye, x−1 xσS e, y −1 yσS e , where x−1 x, y −1 y ∈ ES , and so the condition reduces to the claim.

⊔ ⊓

As an exercise we have Theorem 6.18. In an inverse semigroup S, 1. xσS y ⇐⇒ ∃e ∈ ES : ex = ey. 2. ker(σS ) = {x ∈ S | ∃y ∈ S : xy = x}.

Idempotent separating congruences A group congruence puts all idempotents in the same congruence class. An idempotent separating congruence does the opposite, it puts different idempotents to different classes. A congruence ρ of a semigroup S is idempotent separating, if ∀e, f ∈ ES : eρf =⇒ e = f . From this definition we have immediately Lemma 6.14. If ρ is an idempotent separating congruence of an inverse semigroup S, then tr(ρ) = ιE = {(e, e) | e ∈ ES }. By Theorem 6.15, for each inverse semigroup S there exists the greatest idempotent separating congruence, which will be denoted by µS .

6.5 Free Inverse Semigroups

76

Theorem 6.19. For all inverse semigroups S, xµS y ⇐⇒ ∃e ∈ ES : x−1 ex = y −1 ey . Proof. This is clear, since from Theorem 6.15, since tr(µS ) = ιE , and so the claim follows. ⊔ ⊓ As an exercise, using Theorem 6.6, we have Theorem 6.20. For an inverse semigroup S, 1. µS ⊆ H; 2. if ρ ⊆ L, then ρ is idempotent separating.

6.5 Free Inverse Semigroups Generalized notion Free inverse semigroups (and monoids) are defined in a similar way as free semigroups except now the homomorphic extensions of mappings must be homomorphisms of inverse semigroups. It is somewhat more convenient to consider a generalized (but equivalent) notion of freeness. This is as follows. Let L be a class of semigroups. Let F ∈ L be a semigroup in this class, X a nonempty set, and ϕ : X → F an injective mapping into F such that ϕ(X) generates F . We say that the pair (F, ϕ) is a free L-semigroup on X, if for any P ∈ L and any mapping α0 : X → P there exists a homomorphism α : F → P such that the following diagram commutes, that is, α0 = αϕ. ϕ -F X α0

α R

P In this case, we say also that ϕ(X) generates F freely. The homomorphism α is called a ϕ-extension of the mapping α0 . The mapping ϕ is often omitted from the notation, and then we talk about free L-semigroups F (on a set X). Note that here we do not assume that X is a subset of F . Nor do we claim that such a L-free semigroup exists for a given class L. Note also that we require that ϕ is a bijection from X onto a generating set ϕ(X) of F . In literature one usually omits this requirement, and derives it from a more general condition in certain classes (like ‘varieties of semigroups’). The following is immediate.

6.5 Free Inverse Semigroups

77

Lemma 6.15. If F is a free L-semigroup F on X and α0 : X → P a mapping for P ∈ L, then the ϕ-extension α : F → P is unique.

Free semigroups with involution Let S be a semigroup. A mapping δ : S → S is called an involution of S, if it satisfies ∀x, y ∈ S : δ(xy) = δ(y)δ(x)

and

δ(δ(x)) = x .

The pair (S, δ) or simply S is then a semigroup with involution. Usually we write δ(x) = xδ , since δ behaves in much the same fashion as the inverse function on a inverse semigroup or on a group. Hence the above conditions become (xy)δ = y δ xδ

and

(xδ )δ = x .

Example 6.4. (1) If S is an inverse semigroup, then the mapping δ(x) = x−1 , where x−1 is the inverse element of x in S, is an involution. This is the involution we are mainly interested in. (2) If G is the special linear group of n-by-n-matrices (with entries in Z and determinant equal to 1), then the mapping δ(A) = AT , which maps a matrix A to its transpose, is an involution of G. ⊔ ⊓ Let (S, δ) be a semigroup with involution. A subsemigroup P of S is a subsemigroup with involution, if P is closed under the involution δ, that is, if for all x ∈ P , also δ(x) ∈ P . Let (S, δ) and (P, ν) be two semigroups with involution. Then a mapping α : S → P is a homomorphism α : (S, δ) → (P, ν), if ∀x, y ∈ S : α(xy) = α(x)α(y)

and

α(xδ ) = α(x)ν ,

that is, if α is a homomorphism that respects (or is compatible with) the involutions. If in the above both S and P are inverse semigroups and their involutions are the inverse functions, x 7→ x−1 , then the latter condition becomes: ∀x ∈ S : α(x−1 ) = α(x)−1 . Let X and X ′ be two nonempty sets of the same cardinality such that X ∩ X ′ = ∅, and let ψ : X → X ′ be a bijection. Write Y = X∪X ′ , and define the mapping w 7→ w−1 of words w ∈ Y + by ( ψ(x) if x ∈ X , −1 x = −1 ψ (x) if x ∈ X ′ . and

6.5 Free Inverse Semigroups

78

−1 −1 w = x1 x2 . . . xn =⇒ w−1 = x−1 n xn−1 . . . x1 .

Now, (Y + ,−1 ) is a semigroup with involution, and the following theorem states that it is a free semigroup with involution. Note that here Y + itself is just the free semigroup on the set Y of letters – it is not an inverse semigroup. Later we shall usually write X ′ = X −1 = {x−1 | x ∈ X}

and

Y = X ∪ X −1 .

Theorem 6.21. (Y + ,−1 ) is a free semigroup with involution, that is, if (P, δ) is a semigroup with involution and α0 : X → P is any mapping, then there exists a (unique) homomorphism α : (Y + ,−1 ) → (P, δ) such that α0 (x) = α(x) and α0 (x−1 ) = α(x)δ for all x ∈ X. Proof. Let α0 : X → P be a s stated. We extend α0 as follows: ( α0 (x) if x ∈ X , α(x) = δ α0 (x) if x ∈ X ′ , and for all xi ∈ Y , α(x1 x2 . . . xn ) = α(x1 )α(x2 ) . . . α(xn ) . By the second condition, α is a homomorphism, and by the first condition it respects the involutions: −1 −1 −1 −1 −1 α((x1 x2 . . . xn )−1 ) = α(x−1 n xn−1 . . . x1 ) = α(xn )α(xn−1 ) . . . α(x1 )

= α(xn )δ α(xn−1 )δ . . . α(x1 )δ = (α(x1 )α(x2 ) . . . α(xn ))δ = α(x1 x2 . . . xn )δ . ⊔ ⊓

Freeness of inverse semigroups Let F be an inverse semigroup, X be a nonempty set and ϕ : X → F an injective mapping onto a generating set ϕ(X) of F . We say that (F, ϕ) is a free inverse semigroup on X, if for all mappings α0 : X → P , where P is an inverse semigroup, there exists a homomorphism α : F → P such that α(x−1 ) = α(x)−1 and α0 = αϕ. Here x−1 is the inverse element of x in the inverse semigroup.

Existence of free inverse semigroups That a free inverse semigroup on a set X exists follows from general results on varieties of algebras. These are classes of algebras (say, semigroups with involution) that are closed under homomorphic images, taking subalgebras (subsemigroups with involution)

6.5 Free Inverse Semigroups

79

and arbitrary direct products. It was shown by Birkhoff some 60 years ago that if a class V of algebras forms a variety, then it has the free algebras on every nonempty set X. Birkhoff also gave a characterization of the varieties by identities that are special relations on words. We prove the existence of a free inverse semigroup by taking the approach of Vagner. Let (Y + ,−1 ) be the free semigroup with involution as constructed in the above. Define a relation ρX on (Y + ,−1 ) as follows, ρX = {(uu−1 u, u) | u ∈ Y + } ∪ {(uu−1 vv −1 , vv −1 uu−1 ) | u, v ∈ Y + } . Further, let ρcX be the congruence generated by ρX , that is, ρcX is the smallest congruence that contains the relation ρX . Let us denote by ZX = (Y + ,−1 )/ρcX the quotient semigroup. For readability, we write uρcX = [u] , so that ZX = {[u] | u ∈ Y + } and the product [u][v] = [uv] satisfies the following properties (of ρX ): [uu−1 u] = [u]

and

[uu−1 vv −1 ] = [vv −1 uu−1 ] .

Theorem 6.22. ZX is a free inverse semigroup on X. Proof. First, we show that ZX is a regular semigroup. Indeed, for all u ∈ Y + , [u][u−1 ][u] = [uu−1 u] = [u] , and thus [u−1 ] = [u]−1 is an inverse element of [u]. In order to show that ZX is an inverse semigroup, we need to prove that its idempotents commute. For this it is clearly enough to show that the idempotents are exactly the elements [uu−1 ], since then [uu−1 ][vv −1 ] = [uu−1 vv −1 ] = [vv −1 uu−1 ] = [vv −1 ][uu−1 ] . First of all each [uu−1 ] is an idempotent, since [uu−1 ] = [u][u]−1 and ZX is regular. Suppose then that [w] is an idempotent of ZX . Then [u−1 u][uu−1 ] = [uu−1 ][u−1 u] by the definition of ρX , and consequently, [w] = [w][w] = [ww−1 w][ww−1 w] = [w][w−1 w][ww−1 ][w] = [w][ww−1 ][w−1 w][w] = [w]2 [w−1 ]2 [w]2 = [w][w−1 ]2 [w] = [ww−1 ][w−1 w] = [(ww−1 )(ww−1 )−1 ] , which is of the required form. Therefore, EZX = {[uu−1 ] | u ∈ Y + } .

(6.8)

6.6 Concrete Free Inverse Semigroups

80

In particular, ZX is an inverse semigroup. Evidently, the set {[x] | x ∈ X} generates ZX as an inverse semigroup. Denote simply ϕ : (Y + ,−1 ) → ZX the natural epimorphism onto ZX , that is, ∀u ∈ Y + : ϕ(u) = [u] . Here the restriction of ϕ : X → ZX is clearly a bijection. Let P be any inverse semigroup, and let α0 : X → P be a mapping. The mapping α0 can be extended immediately to α0 : Y → P by setting ∀x ∈ X : α0 (x−1 ) = α0 (x)−1 . Since Y + is a free semigroup, the mapping α0 extends in a unique way to a homomorphism α : Y + → P . We just have to show that this homomorphism respects the involutions. First of all, ρcX ⊆ ker(α), since P is an inverse semigroup and thus for all u, v ∈ Y + , α(uu−1 u) = u and α(uu−1 vv −1 ) = α(vv −1 uu−1 ). Now, according to the homomorphism theorem there exists a homomorphism β : ZX → P for which α = βϕ. In particular, for all x ∈ Y , we have α0 (x) = α(x) = β(ϕ(x)), and the claim follows. (The uniqueness of β is also immediate). ⊔ ⊓ If we add an identity (the empty word) to ZX we obtain a free inverse monoid on 1 . This monoid satisfies the property that if α : X → P is a X, which is denoted ZX 0 mapping into a inverse monoid P , then there exists a unique monoid homomorphism 1 → P that respects the involutions. α : ZX 1 is a free inverse monoid on X. Theorem 6.23. For a nonempty set X, ZX

6.6 Concrete Free Inverse Semigroups Free groups The free inverse semigroup ZX as constructed in the above is abstract in the sense that it is defined as a quotient semigroup. We shall have now a quick look at a more concrete representation of ZX due to Scheiblich (1973). This construction is more difficult than Vagner’s approach, but using Scheiblich’s approach McAlister has contributed to the theory of semigroups some of its most beautiful results. In this section we concentrate on the construction a free inverse monoid. Recall that a group homomorphism α : G → H is a mapping between the groups G and H such that α(xy) = α(x)α(y)

and

α(x−1 ) = α(x)−1 ,

where x−1 denotes the group inverse of x ∈ G, that is, xx−1 = 1G = x−1 x. In particular, α(1G ) = 1H . We say that a group F is freely generated by its subset X (and that F is a free group), if all mappings α0 : X → G for a group G can be extended to a group homomorphism α : F → G.

6.6 Concrete Free Inverse Semigroups

81

Free groups on words Let X be an alphabet and let X −1 = {x−1 | x ∈ X} be a new alphabet with X ∩ X −1 = ∅. Denote Y = X ∪ X −1 . Consider the monoid presentation GX = hY | ∀x ∈ X : xx−1 = 1, x−1 x = 1i . It is immediate that GX is a presentation of a group, where two words u and v present the same element if and only if one gets v from u by a finite number of (I) insertions of factors xx−1 or x−1 x for x ∈ X, and (D) deletions of factors xx−1 or x−1 x for x ∈ X. Write u ∼ v, if there exists a sequence w1 , w2 , . . . , wk of words such that u = w1 and wk = v, and wi+1 is obtained from wi by using a rule (I) or (D). This relation is clearly an equivalence relation, and it is a congruence on Y ∗ , since if u ∼ v and w ∈ Y ∗ , then wu ∼ wv and uw ∼ vw hold. Let us denote the congruence classes by [u] = {v | v ∼ u}. Now, Y ∗ / ∼ is a group. Indeed, this quotient has [1] as its identity and the inverse elements are determined by the rule [u]−1 = [u−1 ], where u−1 comes from the obvious involution: u 7→ u−1 and (u−1 )−1 7→ u. We say that a word w ∈ Y ∗ is reduced, if it contains no factor xx−1 or x−1 x for any letters x ∈ X. Clearly, from any word w ∈ Y ∗ one gets a reduced word by deleting all the factors xx−1 and x−1 x iteratively. Therefore each congruence class [u] contains a reduced word. Example 6.5. For X = {a, b}, we have the following reduction of the word w = ab−1 abaa−1 b−1 ba−1 b, w ∼ ab−1 abb−1 ba−1 b ∼ ab−1 aba−1 b , where the last word is reduced, and presents the same word w in GX .

⊔ ⊓

Lemma 6.16. For each word w ∈ Y ∗ there exists a unique reduced word r(w) such that w = r(w) in GX . Therefore each congruence class [u] contains a unique reduced word. Proof. Assume there are two different reduced words u and v in the same class, and let u = w1 , w2 , . . . , wk = v bePa sequence of words, where wi+1 ∼ wi using once a rule (I) or (D). Denote N = ki=1 |wi | (the sum of the lengths of the words in this sequence). We can assume that the sequence w1 , w2 , . . . , wk is chosen such that N is minimum. Since u and v are both reduced (and different), we must have |u| < |w2 | and |wk−1 | > |v|, that is, rule (I) is used in w1 ∼ w2 and (D) is used in wk−1 ∼ wk . It follows that the sequence |w1 |, |w2 |, . . . , |wk | has a maximal value (a turning point): for some i, |wi−1 | < |wi | > |wi+1 |. This means that wi is obtained from wi−1 by adding a factor xx−1 , and wi+1 by deleting a factor yy −1 . These factors cannot coincide, for otherwise wi−1 = wi+1 contradicts the minimality of N . If the factors overlap with

6.6 Concrete Free Inverse Semigroups

82

each other, then x−1 = y and wi contains a factor xx−1 x or x−1 xx−1 . In this case, again wi−1 = wi+1 . Hence the factors xx−1 and yy −1 should be disjoint. However, now we get a smaller value of N by replacing wi by the word where yy −1 is removed from wi−1 and replacing wi+1 by the word where the factor xx−1 is then added at its place. ⊔ ⊓ Hence two words u, v ∈ Y ∗ are equal in GX if and only if r(u) = r(v). This allows us to present GX more concretely as follows. Let FX = {w ∈ Y ∗ | w = r(w)} be the set of all reduced words in Y ∗ (for Y = X ∪ X −1 ), and define a product by u · v = r(uv) for all u, v ∈ FX . The relations of GX are just the group axioms, and therefore Theorem 6.24. FX is a free group, freely generated by X. Proof. Let α0 : X → G be a mapping into a group G. Each w ∈ FX is a reduced word in the letters of Y = X ∪ X −1 , and it can be uniquely written as a product w = xε11 xε22 . . . xεkk

(6.9)

where xi ∈ X and εi ∈ {−1, +1} (so that x+1 = x), and xi 6= xi+1 . Extend α0 to FX by setting α(w) = α0 (x1 )ε1 α0 (x2 )ε2 . . . α0 (xk )εk . By the uniqueness in (6.9), this is a well defined mapping, and it is rather immediate that α is a group homomorphism. ⊔ ⊓

Idempotents: The idea behind Scheiblich’s construction 1 . If e is an idempotent of M , then by (6.8) Consider a free inverse monoid M = ZX there exists a word u ∈ Y ∗ such that e = [uu−1 ]. If here the word u is not reduced, say u = v1 xx−1 v2 , then

uu−1 = v1 xx−1 v2 · v2−1 xx−1 v1−1 = v1 · v1−1 v1 xx−1 v2 · v2−1 xx−1 v1−1 = v1 xx−1 v1−1 v1 v2 v2−1 v1−1 = (v1 x)(v1 x)−1 (v1 v2 )(v1 v2 )−1 , and therefore e = [(v1 x)(v1 x)−1 ][(v1 v2 )(v1 v2 )−1 ], where the factors v1 x and v1 v2 are shorter than u and they more reduced. From this observation we obtain

6.6 Concrete Free Inverse Semigroups

83

1 ), then there are reduced words u , u , . . . u Lemma 6.17. If e ∈ EM (where M = ZX 1 2 n such that −1 −1 e = [u1 u−1 (ui ∈ FX ) . (6.10) 1 ][u2 u2 ] . . . [un un ] −1 In (6.10) the idempotents [ui u−1 i ] and [uj uj ] commute in all places, and so for each finite subset A = {u1 , u2 , . . . , un } of reduced words there corresponds a unique idempotent e as in (6.10): A 7→ e . (6.11)

Lemma 6.18. If A 7→ e and B 7→ f , then A ∪ B 7→ ef . Note that the mapping (6.11) is not injective: for e = xyy −1 x−1 = xyy −1 x−1 ·xx−1 , we have both {xy} 7→ e and {xy, x} 7→ e. To overcome the noninjectivity we do the following. Let A = {u1 , u2 , . . . , un } 7→ e, so that (6.10) holds. If here ui = v1 v2 , then −1 −1 −1 −1 −1 −1 u1 u−1 1 . . . ui ui . . . un un = u1 u1 . . . v1 v2 v2 v1 . . . un un −1 −1 −1 −1 = u1 u−1 1 . . . v1 v2 v2 v1 · v1 v1 . . . un un −1 −1 = u1 u−1 1 . . . un un · v1 v1

and so also A ∪ {v1 } 7→ e. This means that we can safely add all the prefixes of the words ui into A without changing its value e. Denote A = {v | v a prefix of a u ∈ A} the set of all words that are prefixes of words from A, including the empty word 1 and the words u ∈ A, themselves. By the above, A 7→ e, and this mapping is injective. In conclusion, let K = {A | A = A} be the set of all finite nonempty subsets of reduced words that are closed under taking prefixes, A ∈ K if and only if w = uv ∈ A =⇒ u ∈ A . 1 ) given by A 7→ e is a bijection. Lemma 6.19. The mapping K → EM (where M = ZX

Write Ae 7→ e for the unique Ae ∈ K that corresponds to the idempotent e. Hence −1 −1 Ae = {u1 , u2 , . . . , un } =⇒ e = [u1 u−1 1 ][u2 u2 ] . . . [un un ]

and Ae ∪ Af = Aef . Therefore the idempoyents of M can be identified with the closed sets A of reduced words, and the product of the idempotents becomes defined as the union of such sets.

6.6 Concrete Free Inverse Semigroups

84

An overview of Scheiblich’s construction We take now a look at the free inverse monoids without proofs. Let again Y = X ∪ X −1 , and let FX be the free group of reduced words on X. For each w ∈ Y ∗ , say w = x1 x2 . . . xn with xi ∈ Y , denote w b = {1, r(x1 ), r(x1 x2 ), . . . , r(x1 x2 . . . xn )} ,

where each r(u) is the reduced word corresponding to u. Hence w b consists of the reduced words of the prefixes of w. Define also K = {A ⊆ FX | 0 < |A| < ∞ and w ∈ A =⇒ w b ⊆ A} .

Note that if w ∈ FX , then also w b ⊆ FX . In general, K consists of those nonempty and finite sets of words such that the reduced prefixes of the words in A are also in A. From now on we let g and h denote the elements (reduced words) of the free group FX , and we write g · h for r(gh). Denote MX = {(A, g) ∈ K × FX | g ∈ A} , and define a product in MX as follows, (A, g)(B, h) = (A ∪ g · B, g · h) , where g · B = {g · h′ | h′ ∈ B} consists of reduced words only. Here the component g · B need not be in K, but A ∪ g · B is always in K (because g ∈ A), and hence the product is well defined, (A, g)(B, h) ∈ MX . (Already the proof of this requires some effort). Lemma 6.20. For all g ∈ FX and A ∈ K, g−1 · A ∈ K ⇐⇒ g ∈ A. Theorem 6.25. MX is a free inverse monoid on X. In the following we sketch out some of the highlights of the proofs. If (A, g) ∈ MX , then by the definition g ∈ A, say A = {u1 , u2 , . . . , un } and g = un . If −1 −1 ∗ w = u1 u−1 1 u2 u2 . . . un−1 un−1 un ∈ Y ,

then w b = A and r(w) = g. This gives us a simpler representation of the elements of MX : (A, g) = (w, b r(w)) and thus

MX = {(w, b r(w)) | w ∈ Y ∗ } .

1 (that is, with the congruence ρc ): The following result binds MX with ZX X

u b = vb and r(w) = r(u) ⇐⇒ uρcX .

1 → M defined by It follows from this that the mapping ψ : ZX X

uρcX 7→ (w, b r(w))

is a bijection. In fact, one more proof shows that ψ is an isomorphism.

6.6 Concrete Free Inverse Semigroups

85

On Reynolds construction Reynolds (1986) proved that we get the free inverse semigroups also from the partial mappings as follows. Recall that IFX consists of the injective partial mappings of the free group FX into itself. Let ψ : X → IFX be defined by ψ(g) = ψg

where ψg (h) = g · h (h 6= 1, h 6= g −1 ) .

′ generated by ψ(X) is a free inverse semigroup (on Then the inverse subsemigroup IX X).

On Munn’s construction Munn presented the free inverse semigroups using (oriented word) trees. His variant is probably the most intuitive, but it is also (probably) less useful than Scheiblich’s construction.