SEMIGROUP THEORY 2021/22 VICTORIA GOULD (SUPPLEMENTED BY BRENT) 1. The Basic Concept Definition 1.1. A group is a pair (G, ) where G is a non-empty set and is a binary operation : (g, h) 7→ g h (where g h is normally written just gh) such that (1) Closure: gh is a uniquely defined element of G; (2) Associativity: g(hk) = (gh)k for all g, h, k ∈ G; (3) Identity: there is a 1 = 1G ∈ G such that g1 = g = 1g for all g ∈ G. (4) Inverses: For each g ∈ G there is a h ∈ G such that gh = 1 = hg. Write g 1 for this h. Example 1.2. The integers Z = {. . . , 2, 1, 0, 1, 2, . . .} form a group under the usual + of intgers. Beware! We have to change notation and write m + n rather than gh. Associativity is then m + (n + k) = (m + n) + k; the identity is 0 as 0 + m = m = m + 0 for all m, and (4) is asking for an n such that n + m = 0 = m + n (n = m obviously). Definition 1.3. A monoid is a pair (M, ) satisfying (1)-(3) in Definition 1.1, but not necessarily (4). Example 1.4. N0 = {0, 1, 2, . . .} under the usual addition. The identity is 0, but there is now no element m of N0 such that 2 + m = 0. Note. The identity of a monoid is unique (see the Exercises). Definition 1.5. A semigroup is a pair (S , ) satisfying (1)-(2) in Definition 1.1, but not necessarily (3) or (4). Spelling it out: S is a set and is an associative binary operation on S . [i.e. is a function S × S → S with (a, b) 7→ a b, normally written just ab, and for all a, b, c ∈ S we have ab ∈ S and a(bc) = (ab)c]. Example 1.6. N = {1, 2, . . .} under the usual addition. There is no longer an identity element. Example 1.7. A group is a monoid and a monoid is a semigroup. Thus we have Groups Monoids Semigroups. We abbreviate “(S , )” by “S ” and often omit in “a b” and write “ab”. By induction a1a2 . . . an is unambiguous. Thus we write an for aa . . . a︸ ︷︷ ︸ n times . Index Laws: For all n,m ∈ N = {1, 2, . . . }: 1 2 VICTORIA GOULD (SUPPLEMENTED BY BRENT) n Semigroups Groups 1 1 1 2 4 1 3 18 1 4 126 2 5 1160 1 6 15973 2 7 836 021 1 8 1 843 120 128 5 9 52989400714478 2 Table 1. The number (whatever that means) of semigroups and groups of order n anam = an+m( an )m = anm. The one element trivial group {e} with multiplication table e e e is also called the trivial semigroup or trivial monoid. Example 1.8. If (R,+,×) is a ring with 1 then R is a group under + and a monoid under ×. Example 1.9. Of the phenomenon in Example 1.8: (1) (Z,+) is a group and (Z,×) is a monoid. (2) (Zn,+ mod n) is a group and (Zn,× mod n) is a monoid. (Zn {0},× mod n) is a group iff n = p a prime. (3) Let Mn(R) be all n × n matrices with R-entries. Then Mn(R) is a group under + of matices; it is a monoid under × of matrices (to get a group under × you need to restrict to the invertible matrices, usually denoted GLn(R)). (4) Let R[x] be all polynomials in the variable x and with R coefficients. Then R[x] is a group under + of polynomials and a monoid under × of polynomials. Example 1.10. Let X be a set and M = 2X be the set of all subsets of X. Then M is a monoid under ∩: we have A ∩ (B∩C) = (A ∩ B) ∩C for all subsets A, B,C and the identity is the subset X, as A ∩ X = A = X ∩ A for all A. In this monoid, every element A has the property A2 = A∩A = A. An element e of a semigroup such that e2 = e is called an idempotent. We will come back to idempotents later. Example 1.11. Similarly, 2X is a monoid under∪with identity the empty set (and every element is an idempotent here too). Example 1.12. Let I, J be non-empty sets and set T = I × J with the binary operation SEMIGROUP THEORY 2021/22 3 Figure 1. Multiplication in the semigroup of Example 1.12. (i, j)(k, `) = (i, `). Note ( (i, j)(k, `) ) (m, n) = (i, `)(m, n) = (i, n), (i, j) ( (k, `)(m, n) ) = (i, j)(k, n) = (i, n), for all (i, j), (k, `), (m, n) ∈ T and hence multiplication is associative. Then T is a semigroup called the rectangular band on I × J. Notice: (i, j)2 = (i, j)(i, j) = (i, j), i.e. every element is an idempotent. This shows that not every semigroup is the multiplicative semigroup of a ring, since any ring where every element is an idempotent is commutative (see the Exercises). However, a rectangular band does not have to be commutative. Adjoining an Identity: Let S be a semigroup. Find a symbol not in S , call it “1”. On S ∪ {1} we define by a b = ab for all a, b ∈ S , a 1 = a = 1 a for all a ∈ S , 1 1 = 1. Then is associative (check this) so S ∪ {1} is a monoid with identity 1. Multiplication in S ∪ {1} extends that in S . 4 VICTORIA GOULD (SUPPLEMENTED BY BRENT) The monoid S 1 is defined by S 1 = S if S is a monoid,S ∪ {1} if S is not a monoid. Definition 1.13. S 1 is S with a 1 adjoined. Example 1.14. Let T be the rectangular band on {a} × {b, c}. Then T 1 = {1, (a, b), (a, c)}, which has multiplication table 1 (a, b) (a, c) 1 1 (a, b) (a, c) (a, b) (a, b) (a, b) (a, c) (a, c) (a, c) (a, b) (a, c) Notation: Let X be a set and recall the definition of a function f : X → X. All your life you have been writing f (x) ∈ X for the image value of a function at x ∈ X. In this course we will instead write: (x) f for this image. If f : X → X is a function and g : X → X another function then their composition f g : X → X is defined by: (x)( f g) = ((x) f )g i.e. the result of first applying f to x and then applying g to the image of x under f . The advantage of writing “(x) f ” rather than the usual “ f (x)” is that the expression f g can be read from left to right as “do f then do g”. In this course, all functions, homomorphisms (see Section 2), etc, will be written like this, on the right of their arguments. Example 1.15. The full transformation monoid: Let TX be the set of all functions X → X under the usual composition of functions. You know that composition of functions is associative! (i.e. that f (gh) is the same function as ( f g)h.) Thus TX is a semigroup. If id : X → X is the identity function (x)id = x then for any f : (x)(id f ) = ((x)id) f = (x) f = ((x) f )id = (x)( f id) i.e. id f = f = f id, so that id is an identity under composition and TX is a monoid. If X = {1, 2, . . . , n} then write Tn for TX. Example 1.16. The symmetric group: you know this one well. It consists of all bijective functions X → X under composition and is a group. When X = {1, 2, . . . , n} write S n for S X. Notice that S n Tn. We will come back to this point later. Example 1.17. The symmetric inverse monoid: a partial bijection of a set X to itself is a bijection s : A→ B between subsets A, B X. Notice that s is not defined outside of A, i.e. on X A. Let IX be the set of all partial bijections of X (or In if X = {1, 2, . . . , n}). Two partial bijections are the same when they have the same domain, the same image and they have the same effect on every point in their domains. SEMIGROUP THEORY 2021/22 5 If s : A → B ∈ IX we will often write s : dom s → im s instead. The composition st of partial bijections is just the usual composition of functions (s followed by t) wherever this makes sense: Thus, if there is an x ∈ dom s such that (x)s ∈ dom t then (x)st is defined and is equal to ((x)s)t ∈ im t. Otherwise, (x)st is not defined. We have (1) dom st = s-preimage of im s ∩ dom t, im st = t-image of im s ∩ dom t for the domain and image of a composition of partial bijections. To see which partial bijection st actually is, you need to: (i). find the domain and image of st using (1), and (ii). see what effect st has on an x ∈ dom st. If im s ∩ dom t = , then the composition is not defined anywhere, and so is the unique bijection: → from the empty set to itself. Notice that IX contains all the full bijections X → X. In particular the symmetric group S X IX. IX is a monoid with identity the identity function id : X → X. Example 1.18. The bicyclic monoid: if A Z, such that |A| < ∞, then max A is the greatest element in A. We note some things about max: max{a, 0} = a if a ∈ N0, max{a, b} = max{b, a}, max{a, a} = a, max {a,max{b, c}} = max{a, b, c} = max { max{a, b}, c}. Thus we have that (Z,max) where max(a, b) = max{a, b} is a semigroup and (N0,max) is a monoid. 6 VICTORIA GOULD (SUPPLEMENTED BY BRENT) Note. The following identities hold for all a, b, c ∈ Z ( ) {a + max{b, c} = max{a + b, a + c}, max{b, c} = a + max{b a, c a}. Put B = N0 × N0. On B we define a binary operation by (a, b)(c, d) = (a b + t, d c + t), where t = max{b, c}. Proposition 1.19. B is a monoid with identity (0, 0). Proof. With (a, b), (c, d) ∈ B and t = max{b, c} we have t b > 0 and t c > 0. Thus we have a b + t > a and d c + t > d. Therefore, in particular (a b + t, d c + t) ∈ B so multiplication is closed. We have that (0, 0) ∈ B and for any (a, b) ∈ B we have (0, 0)(a, b) = (0 0 + max{0, a}, b a + max{0, a}), = (0 0 + a, b a + a), = (a, b), = (a, b)(0, 0). Therefore (0, 0) is the identity of B. We need to verify associativity. Let (a, b), (c, d), (e, f ) ∈ B. Then( (a, b)(c, d) ) (e, f ) = ( a b + max{b, c}, d c + max{b, c})(e, f ), = ( a b d + c + max{d c + max{b, c}, e}, f e + max{d c + max{b, c}, e}). (a, b) ( (c, d)(e, f ) ) = (a, b) ( c d + max{d, e}, f e + max{d, e}), = (a b + max{b, c d + max{d, e}} f e c + d + max{b, c d + max{d, e}}). Now we have to show that a b d + c + max {d c + max{b, c}, e} =a b + max {b, c d + max{d, e}}, f e + max {d c + max{b, c}, e} =f e c + d + max {b, c d + max{d, e}}. We can see that these equations are the same and so we only need to show c d + max {d c + max{b, c}, e} = max {b, c d + max{d, e}}. Now, we have from ( ) that this is equivalent to max { max{b, c}, c d + e} = max {b, c d + max{d, e}}. SEMIGROUP THEORY 2021/22 7 The RHS of this equation is max { b, c d + max{d, e}} = max {b,max{c d + d, c d + e}}, = max { b,max{c, c d + e}}, = max{b, c, c d + e}, = max { max{b, c}, c d + e}. Therefore multiplication is associative and hence B is a monoid. Definition 1.20. A semigroup S is commutative if ab = ba for all a, b ∈ S . For example N with + is commutative. The bicyclic monoid B is not because (0, 1)(1, 0) = (0 1 + 1, 0 1 + 1) = (0, 0), (1, 0)(0, 1) = (1 0 + 0, 1 0 + 0) = (1, 1). Thus we have (0, 1)(1, 0) , (1, 0)(0, 1). Notice that in B; (a, b)(b, c) = (a, c). Definition 1.21. A semigroup is cancellative if ac = bc a = b, and ca = cb a = b. Example 1.22. Examples of cancellative semigroups: (1) Groups. (2) (N0,+) (3) (Z,×), polynomials R[x] and indeed (R,×) for a ring R that is an integral domain (i.e. has the property that ab = 0 only if a = 0 or b = 0). Non-examples of cancellative semigroups: (1) In Z6 = {0, 1, 2, 3, 4, 5} with ×modulo 6 we have 2 ·2 = 2 ·5 but 2 , 5 (How this example came about: as a ring Z6 is not an integral domain, as 2 · 3 = 0, hence 2 · (5 2) = 2 · 5 2 · 2 = 0). (2) In the rectangular band on {1, 2} × {1, 2} we have (1, 1)(1, 2) = (1, 2) = (1, 2)(1, 2) but (1, 1) , (1, 2). (3) The bicyclic monoid B is not cancellative as e.g. (1, 1)(2, 2) = (2, 2)(2, 2). Definition 1.23. If S has at least two elements then a zero of S is an element 0 such that, for all a ∈ S , 0a = 0 = a0. Example 1.24. Examples of zeroes in a semigroup: (1) Z under × has both a 1 (that is why it is a monoid) and a 0. (2) Mn(R) under × of matrices has both a 1 (the identity matrix) and a 0 (the zero matrix). 8 VICTORIA GOULD (SUPPLEMENTED BY BRENT) (3) The symmetric inverse monoid In has a 1 (the identity bijection id : X → X) and 0 the partial bijection 0 : → . To see this, if s : A→ B is a partial bijection then 0s has dom 0s = 0-preimage of dom 0 ∩ dom s = 0-preimage of ∩ dom s = 0-preimage of = = dom 0 and similarly im 0s = im 0 = , with 0s and 0 having the same effect on . Non-Examples of zeroes in a semigroup: (1) The full transformation monoid Tn has a 1 (the identity bijection id : X → X) but does not have a 0. Adjoining a Zero Let S be a semigroup, then pick a new symbol “0”. On S ∪ {0} define a binary operation by a · b = ab for all a ∈ S , 0 · a = 0 = a · 0 for all a ∈ S , 0 · 0 = 0. Then · is associative. Define S 0 = S if S has a 0 already,S ∪ {0} otherwise. 2. Standard algebraic tools We introduce some familiar ideas (sub-object, homomorphism, etc.) in the context of semi- groups and monoids. Definition 2.1. A subsemigroup of a semigroup S is a subset T that forms a semigroup under the restriction of the binary operation on S to T . Similarly a submonoid is a subset that forms a monoid under the restriction of the binary operation and a subgroup is a subset that forms a group under the restriction of the binary operation. In practice: , T S is a subsemigroup if and only if for all a, b ∈ T we have ab ∈ T and T is a submonoid of S iff for all a, b ∈ T we have ab ∈ T and there is an element 1T ∈ T such that 1T a = a = a1T for all a ∈ T . Finally, T is a subgroup if it is a submonoid and for all a ∈ T there is a b ∈ T with ab = 1T = ba. Example 2.2. (1) The group (Z,+) has submonoid (N0,+) and subsemigroup (N,+). (2) (N,×) is a subsemigroup of (the semigroup) (Z,×). (3) Let Tn be the full transformation monoid on the set [n] := {1, 2, . . . , n}. For m ∈ [n] let cm : [n]→ [n] SEMIGROUP THEORY 2021/22 9 be the constant map that maps every element to m, i.e. (i)cm = m for all i ∈ [n]. Let R = {cm |m ∈ [n]} be the set of all constant maps. Then cmck = ck for all m, k ∈ [n] as (i)cmck = (m)ck = k = (i)ck. Thus, R is a subsemigroup of Tn. (4) The symmetric group S n is a submonoid of both the symmetric inverse monoid In and Tn. Of course, S n is more than just a semigroup or a monoid; it is a group. Thus, S n is a subgroup of In and Tn. Later on, we will devote a whole section to subgroups of semigroups. (5) Beware! A T can be a submonoid of an S where S isn’t a monoid (i.e. is only a semi- group); also, even if S is a monoid, with identity 1S , then a submonoid T will have identity 1T which may not be the same as 1S . For example, in I8 let T be those partial bijections with domain and image the set Y = {1, 2, 3}, i.e. the partial bijections s : {1, 2, 3} → {1, 2, 3}. If t is another such then so is st and T is a subsemigroup of I8. Moreover, if idY : {1, 2, 3} → {1, 2, 3} is the identity bijection from {1, 2, 3} to itself, then idY s = s = sidY for all s ∈ T and so this is an identity for T . Thus, T is a submonoid. Notice that 1T = idY but 1S = idX where X = {1, 2, . . . , 8} and idY , idX. (Moreover, moreover: if s : {1, 2, 3} → {1, 2, 3} is a bijection then there is a bijection t : {1, 2, 3} → {1, 2, 3} that is the inverse of s, but just on the set {1, 2, 3}. Put another way, st = idY = ts and so T forms a group! Thus T is a subgroup.) (6) For 1 ≤ k ≤ n let I≤kn = {s ∈ In : | dom s| ≤ k} be the partial bijections [n] → [n] whose domain (and hence image) has size at most k. If s, t are two such then: dom st = s-preimage of im s ∩ dom t which is the s-preimage of a subset of dom t. As s is 1-1 this preimage has size no bigger than this subset of dom t, i.e. has size ≤ k. Thus st ∈ I≤kn and I≤kn is a subsemigroup of In (and again, the identity 1 ∈ I≤kn iff k = n, so I≤kn is not a submonoid if k < n). (7) Let B be the bicyclic monoid from Section 1 and E = {(a, a) ∈ B | a ∈ N0}. Then E is a commutative submonoid of B. We have (0, 0) ∈ E and for (a, a), (b, b) ∈ E: (a, a)(b, b) = (a a + t, b b + t) where t = max{a, b}, = (t, t), = (b, b)(a, a). Definition 2.3. Let S ,T be semigroups then θ : S → T is a semigroup homomorphism if, for all a, b ∈ S , (ab)θ = aθbθ. If S ,T are monoids then θ is a monoid homomorphism if θ is a semigroup homomorphism and 1S θ = 1T . 10 VICTORIA GOULD (SUPPLEMENTED BY BRENT) Notice how θ is written on the right of its argument. A composition θ of homomorphisms is thus read from left to right, i.e. as θ followed by . Example 2.4. (1) θ : B→ Z given by (a, b)θ = a b is a monoid homomorphism because( (a, b)(c, d) ) θ = (a b + t, d c + t)θ t = max{b, c} = (a b + t) (d c + t) = (a b) + (c d) = (a, b)θ + (c, d)θ. Furthermore (0, 0)θ = 0 0 = 0. (2) Let S = I × J be the rectangular band. Then define α : T → TJ (the full transofrmation monoid on J) by (i, j)α = c j. Then we have( (i, j)(k, `) ) α = (i, `)α, = c`, = c jc`, = (i, j)α(k, `)α. So α is a semigroup homomorphism (S is not a monoid although TJ is). (3) Define θ : Mn(R) → R by (A)θ = det(A). Then (AB)θ = det(AB) = det(A) det(B) = (A)θ(B)θ. (I�
�m sorry, but I plain refuse to write “det” on the right-hand side of a matrix). As an exercise you can show that if θ : S → T is a homomorphism then the image im θ = {t ∈ T : t = θ(s) for some s ∈ S } is a subsemigroup of T . Definition 2.5. A bijective homomorphism is an isomorphism. If there is an isomorphism from S to T then write S T . Isomorphisms preserve algebraic properties (e.g. commutativity). Embeddings Suppose α : S → T is a homomorphism. Then imα is a subsemigroup (sub- monoid) of T . If α is 1-1, then α : S → imα is an isomorphism, so that S imα. Thus S is isomorphic to a subsemigroup of T and we say that S is embedded in T . Last year, in group theory, we saw the following: Theorem 2.6 (Cayley’s Theorem). Let G be a group. Then G is isomorphic to a subgroup of the symmetric group S G. (Actually, last year we saw a special case of this: if |G| = n then G is isomoprhic to a subgroup of S n.) Thus, any group can be thought of as a group of permutations, if you so wish. If you watch the video of the proof from last year then the proof of Cayley’s theorem goes as follows: you make G act on itself by (left) multiplication so that any g ∈ G can be thought of as a bijection G → G; you then send g to this bijection in S G. SEMIGROUP THEORY 2021/22 11 An analogous result holds for semigroups, where now every semigroup can be thought of as a group of functions from a set to itself. The proof is completely analogous to that for Cayley’s theorem, except that S will act on itself on the right now, as we are writing homomorphisms on the right: Theorem 2.7 (Cayleys Theorem for Semigroups). Let S be a semigroup. Then S is isomorphic to a subsemigroup of TS 1 . (Note that it is the full transformation monoid TS 1 , on the set S 1 of the semigroup S with a 1 adjoined, that we are embedding S in). Proof. Let S be a semigroup and set X = S 1. We need a 1-1 homomorphism S → TX. For s ∈ S , define ρs ∈ TX by (x)ρs = xs (right multiplication by s). Now define α : S → TX by sα = ρs. We show α is an injective homomorphism. For 1-1: if sα = tα then ρs = ρt and so (x)ρs = (x)ρt for all x ∈ S 1; in particular (1)ρs = (1)ρt (this is where we use the fact that S 1 contains a 1) and so 1s = 1t hence s = t and α is 1-1. We show α is a homomorphism: let s, t ∈ S . For any x ∈ X we have x(ρsρt) = (xρs)ρt = (xs)ρt = (xs)t = x(st) = xρst. Hence ρsρt = ρst and so sαtα = ρsρt = ρst = (st)α. Therefore α is a homomorphism and α : S → TX is an embedding. Theorem 2.8 (Cayley’s Theorem for Monoids). Let M be a monoid. Then M is isomorphix to a submonoid of TM. (Now M has a 1 built-in, so there is no need to attach it). Proof. M1 = M so TM = TM1 . We know the α above is a semigroup embedding. We need only check 1α = idX. Now, 1α = ρ1 and for all x ∈ X = M we have xρ1 = x1 = x = xidX and so 1α = ρ1 = idX as required. 2.1. Idempotents Definition 2.9. e ∈ S is an idempotent iff e2 = e. We put E(S ) = {e ∈ S | e2 = e} for the set of idempotents of a semigroup. Example 2.10. (1) E(S ) may be empty, e.g. if S is N under +, then E(S ) = . (2) If G is a group and e ∈ G is an idempotent, then e2 = e e 1e2 = e 1e e = 1. Thus the only idempotent in a group is the identity (i.e. idempotents play no role in group theory). (3) If M is a monoid then 1 ∈ E(M). (4) More generally, if M is a cancellative monoid, then 1 is the only idempotent: for if e2 = e then ee = e1 and so e = 1 by cancellation. 12 VICTORIA GOULD (SUPPLEMENTED BY BRENT) (5) In M2(R) the following are idempotents:( 1 0 0 1 ) and ( 1 0 0 0 ) The first is the identity of the monoid M2(R); the second is not. (6) Idempotents in In (and more generally IX): let A [n] = {1, 2, . . . , n} and idA the identity bijection from A to A, i.e. (x)idA = x when x ∈ A; otherwise idA is not defined. The partial bijection idA is called a partial identity on A. Then E(In) consists of the partial identities on all subsets of [n]. To see this, idA is indeed an idempotent: for any x ∈ A we have (x)idAidA = (x)idA; if x < A then idA and idAidA are undefined. In any case, id2A = idA. On the other hand, if e ∈ In is an idempotent, then for any x ∈ dom e we have (x)ee = (x)e. In particular, (x)e and x have the same image under e and as e is 1-1 this gives (x)e = x. Thus e fixes every element of its domain, so that e = iddom e. (7) For the bicyclic semigroup B we have from Exercises 1 E(B) = { (a, a) | a ∈ N0}. (8) E(S ) may be all of S . If S = I × J is a rectangular band then for any (i, j) ∈ S we have (i, j)2 = (i, j)(i, j) = (i, j). The last example is a special case of: Definition 2.11. If E(S ) = S , then S is a band. Example 2.12. If M = 2X, the subsets of X, then M is a monoid under ∩. For any A X we have A ∩ A = A, so that every element of M is an idempotent. Moreover, A ∩ B = B ∩ A, so that M is commutative. Definition 2.13. If E(S ) = S and S is commutative, then S is a semilattice. (The reason for the terminology “semilattice” may be a little obscure at the moment.) Lemma 2.14. Let E(S ) , and suppose e f = f e for all e, f ∈ E(S ). Then E(S ) is a subsemi- group of S . Proof. Let e, f ∈ E(S ). Then (e f )2 = (e f )(e f ) = e( f e) f = e(e f ) f = (ee)( f f ) = e f and hence e f ∈ E(S ). From Lemma 2.14 if E(S ) , and idempotents in S commute then E(S ) is a subsemigroup, hence a semilattice. Example 2.15. (1) If A, B [n] and idA, idB are partial identities (hence idempotents) in In, then idAidB = idA∩B To see this: dom idAidB = idA-preimage of im idA ∩ dom idB = idA-preimage of A ∩ B = A ∩ B SEMIGROUP THEORY 2021/22 13 and similarly, im idAidB = A ∩ B. If x ∈ A ∩ B then (x)idAidB = (x)idB = x and so idAidB is the identity map on A ∩ B. This shows idAidB = idA∩B. In particular, idAidB = idA∩B = idB∩A = idBidA The conclusion is that idempotents in In commute and so E(In) is a semilattice and sub- semigroup of In. (2) E(B) = { (a, a) | a ∈ N0} is a semilattice. (3) A rectangular band I × J is not a semilattice (unless |I| = |J| = 1) since (i, j)(k, `) = (k, `)(i, j) i = k and j = `. Definition 2.16. Let a ∈ S and define 〈a〉 = {an | n ∈ N}. We call 〈a〉 the monogenic subsemi- group of S generated by a. Proposition 2.17. Let a ∈ S . Then 〈a〉 is a commutative subsemigroup of S . Moreover, either (i). |〈a〉| = ∞ and 〈a〉 (N,+) or (ii). 〈a〉 is finite. In this case there are n, r ∈ N such that 〈a〉 = {a, a2, . . . , an, an+1, . . . , an+r 1}, so that {an, an+1, . . . , an+r 1} is a subsemigroup of 〈a〉 with an+s = an+t s ≡ t (mod r). for all s, t ∈ N0. Proof. If ai , a j for all i, j ∈ N with i , j then θ : 〈a〉 → N defined by aiθ = i is an isomorphism (Exercise!). This is case (i). Suppose that in the list of elements a, a2, a3, . . . there is a repetition, i.e. ai = a j for some i < j. Let m be least such that am = an for some n < m. Then m = n + r for some r ∈ N – where n is called the index of a, r is the period of a. Then the elements a, a2, a3, . . . , an+r 1 are all distinct and an = an+r. (Warning! Do not cancel here. This is semigroup theory!) Let s, t ∈ N0 with s = s′ + ur, t = t′ + vr and 0 ≤ s′, t′ ≤ r 1, u, v ∈ N0. Then an+s = an+s ′+ur = as ′ an+ur in S 1 = as ′ an+ra(u 1)r = as ′ ana(u 1)r = as ′ an+(u 1)r ... = as ′ an = an+s ′ 14 VICTORIA GOULD (SUPPLEMENTED BY BRENT) Figure 2. A finite monogenic subsemigroup for a periodic (left) and the trajectory of powers of a (right). Similarly, an+t = an+t ′ . Therefore an+s = an+t an+s′ = an+t′ s′ = t′ s ≡ t( mod r). Notice that an+ur = an for all u. We have shown {a, a2, . . . , an, an+1, . . . , an+r 1} = 〈a〉 with an+san+t = an+u where u ≡ s + n + t (mod r) and 0 ≤ u ≤ r 1 so that {an, an+1, . . . , an+r 1} is a subsemigroup. This is case (ii). We can express Proposition 2.17 as in Figure 2. If 〈a〉 is finite, that is, a has finite index and period, then we say that a is periodic. Example 2.18. If a ∈ G a finite group, then the index n = 0 (i.e. the monogenic subsemigroup has no “tail”) and 〈a〉 = {a0, a, a2, . . . , ar 1} and r is the order of a. If a does not have finite order then 〈a〉 = {. . . , a 2, a 1, a0, a, a2, . . .} (a really big circle). If a ∈ S a semigroup then we still have that {an, an+1, . . . , an+r 1} is a cyclic (sub)group with identity an+s. Lemma 2.19 (The Idempotent Power Lemma). If 〈a〉 is finite, then it contains an idempotent. Proof. Let n, r be the index and period of a. Choose s ∈ N0 with s ≡ n (mod r). Then s+n ≡ 0 (mod r) and so s + n = kr for k ∈ N. Then (an+s)2 = an+n+s+s = an+kr+s = an+s and so an+s ∈ E(S ). Corollary 2.20. Any finite semigroup contains an idempotent. SEMIGROUP THEORY 2021/22 15 Figure 3. An idempotent in Tn. 2.2. Example: Idempotents in TX We know cxcy = cy for all x, y ∈ X and hence cxcx = cx for all x ∈ X. Therefore cx ∈ E(TX) for all x ∈ X. But if |X| > 1 then there are other idempotents in TX as well. Example 2.21. Define an element α = ( 1 2 3 2 2 3 ) ∈ E(TX). Then α2 = ( 1 2 3 2 2 3 ) · ( 1 2 3 2 2 3 ) = ( 1 2 3 2 2 3 ) , thus α is an idempotent. (Read the above expression like you would a composition of permuta- tions except that you compose from left to right). Alternatively, see the picture in Figure 3. Definition 2.22. Let α : X → Y be a map and let Z X. Then the restriction of α to the set Z is the map α|Z : Z → Y, with z 7→ zα for every z ∈ Z. Example 2.23. Define a map with domain {a, b, c, d} and codomain {1, 2, 3} by: α = ( a b c d 1 3 1 2 ) . Then α|{a,d} is the following map: α|{a,d} = ( a d 1 2 ) . Looking at Figure 3, the image of α is the set {2, 3}, and on this set α is just the identity mapping. This is always true and gives a useful characterization of the idempotents of a trans- formation monoid. Lemma 2.24 (The E(TX) Lemma). An element ε ∈ TX is idempotent iff ε|im ε = idim ε. 16 VICTORIA GOULD (SUPPLEMENTED BY BRENT) Proof. ε|Im ε = idIm ε means that for all y ∈ Im εwe have (y)ε = y. Note that im ε = {(x)ε : x ∈ X}. Then ε ∈ E(TX) ε2 = ε, (x)ε2 = (x)ε for all x ∈ X, ((x)ε)ε = (x)ε for all x ∈ X, (y)ε = y for all y ∈ Im ε, ε|Im ε = idIm ε. Example 2.25. We can create an idempotent in T7. First we determine its image: let it be the subset {1, 2, 5, 7}. Our map must fix these elements, but can then map the other elements to any of these in any way, e.g:( 1 2 3 4 5 6 7 1 2 5 7 ) → ( 1 2 3 4 5 6 7 1 2 5 7 5 2 7 ) ∈ E(T7). Example 2.26. We can list all the idempotents in T3. We start with the constant maps, i.e. the ε ∈ E(T3) such that | Im ε| = 1. These are: c1 = ( 1 2 3 1 1 1 ) , c2 = ( 1 2 3 2 2 2 ) , c3 = ( 1 2 3 3 3 3 ) . Now consider all elements ε ∈ E(T3) such that |im ε| = 2. These are( 1 2 3 2 2 3 ) , ( 1 2 3 1 1 3 ) , ( 1 2 3 3 2 3 ) ,( 1 2 3 1 3 3 ) , ( 1 2 3 1 2 1 ) , ( 1 2 3 1 2 2 ) . There is only one idempotent |im ε| = 3, and that is the identity map:( 1 2 3 1 2 3 ) . 2.3. Example: I3 (summarising what we know so far) Let’s draw a nice picture of the symmetric inverse monoid on the set [3] = {1, 2, 3} – see Figure 4. We will see later that, to some extent, this picture is indicative of the structure of all finite semigroups. The elements of I3 are the partial bijections s : A → B where A, B are subsets of [n], neces- sarily of the same size, as s is a bijection. Arrange the elements of I3 according to the size of A, with the elements having domain A of size 3 at the top, then those with |A| = 2, etc, and the domain size decreasing as you go down the picture. The box at the top, where |A| = 3, contains all the (full) bijections [3] → [3]; in other words, it contains the elements of the symmetric group S 3. In the second box down, where |A| = 2, the box has been divided into a 3 × 3 grid, with the ( 3 2 ) possible A labelling the rows and the ( 3 2 ) possible B labelling the columns. (The subset {1, 2} has been abbreviated to 12, etc.) Similarly SEMIGROUP THEORY 2021/22 17 Figure 4. A strategic picture of I3. for the next box down, that contains all the partial bijections with domain and image having size one. Put the s : A → B into the box that is in the row labelled by A and the column labelled by B. Thus, the box in row 13 and column 12 contains the two partial bijections s, t : {1, 3} → {1, 2} 18 VICTORIA GOULD (SUPPLEMENTED BY BRENT) and their composition st is shown at the left. It is a (the) partial bijection st : {1} → {2}, to be found in row 1 and column 2 of the next 3 × 3 grid down. Another example of a composition su of partial bijections is shown next to the the lower 3× 3 grid. This time the result is the bijection 0 : → . We have seen that the idempotents in In are the partial identities idA (or occasionally eA), where idA is the identity map of the set A to itself. They all lie in the blue shaded boxes down the diagonals. For example, the box in the row and column labelled 13 contains the partial identity e13 and one other element g that swaps 1 and 3 over. Looking at the set {e13, g}, the multiplication table for these two elements is shown on the left. The set is closed, the partial identity e13 is an identity, and the element g has an inverse, namely itself. Thus, {e13, g} is a group in its own right, hence is a subgroup of In. This is true for all the blue boxes, but not for any other boxes. There is only one group of order 2, although it can be represented in many ways. As the group {e13, g} consists of the two permutations of the numbers {1, 3}, the best description of it would be as being (isomorphic to) the symmetric group S 2. Thus, the blue box at the top is S 3; the blue boxes down the diagonal in the next 3 × 3 grid are S 2’s; the next ones are S 1’s, and the bottom box, containing the 0, is also a group of order 1. 3. Relations In group theory, quotients (and hence homomorphic images) of groups are determined by normal subgroups. The situation is more complicated in semigroup theory – the homomorphic images of semigroups are determined by special equivalence relations called congruences. There are other relations, called Green’s relations, which are an integral part of this course. These examples show that relations play a central role in semigroup theory. Definition 3.1. A (binary) relation ρ on a set A is a subset of A × A. We write “a ρ b” instead of “(a, b) ∈ ρ” and say that a nd b are ρ-related. Of course, we are usually given a ‘rule’ for deciding when elements of A are related by ρ; nevertheless, the notion of a relation as a subset has distinct advantages. 3.1. Some special relations Properties of the relation 6 on R: a 6 a for all a ∈ R, a 6 b and b 6 c a 6 c for all a, b, c ∈ R, a 6 b and b 6 a a = b for all a, b ∈ R, a 6 b or b 6 a for all a, b ∈ R. These are called: reflexivity, transitivity, anti-symmetry and that R is totally ordered. We say the relation 6 is a total order on R. SEMIGROUP THEORY 2021/22 19 Recall that if X is any set, we denote by 2X the set of all subsets of X. Properties of the relation on a power set 2X of an arbitrary set X: A A for all A ∈ 2X A B and B C A C for all A, B,C ∈ 2X A B and B A A = B for all A, B ∈ 2X Notice that if |X| > 2 and x, y ∈ X with x , y then {x} * {y} and {y} * {x}. Thus 2X with the relation is reflexive, transitive and anti-symmetric but not totally ordered. We say that is a partial order on 2X. Recall that a relation ρ is symmetric if aρb bρa for all a, b ∈ A. A relation ρ on a set A is an equivalence if ρ is reflexive, symmetric and transitive. In this case write [a] = {b ∈ A | a ρ b} for the elements of A related to a, called the equivalence-class, or the ρ-class, of a. The equiva- lence classes of ρ partition A into a disjoint union of subsets. An example is the universal relation ω on A: ω = A × A. So x ω y for all x, y ∈ A, and [x] = A for all x ∈ A. At the other end of the spectrum denote by ι be the equality relation on A: ι = { (a, a) | a ∈ A}. Thus x ι y x = y and so [x] = {x} for all x ∈ A. Recall also for an equivalence realtion that: (1) If a, b ∈ A then [a] = [b] or [a] ∩ [b] = . (2) aρb iff [a] = [b] iff a ∈ [b]. Examples of equivalence relations: (1) ≡m on Z, where a ≡m b iff a and b are congruent moduo m. (2) If G is a group and H is a subgroup then define g and h to be equivalent iff the cosets gH = hH ( h 1g ∈ H). The equivalence classes are the cosets of H. (3) If the group G acts on the set X then define two elements x, y ∈ X to be equivalent