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 iff
y = g · x for some g ∈ G. The equivalence classes are the orbits of the G-action.
3.2. Algebra of Relations
If ρ, λ are relations on A then ρ ⊆ λ means a ρ b ⇒ a λ b. Note that ι ⊆ ρ ⇔ ρ is reflexive
and so ι ⊆ ρ for any equivalence relation ρ.
We see that ι is the “smallest” equivalence relation on A and ω is the “largest” equivalence
relation on A.
20 VICTORIA GOULD (SUPPLEMENTED BY BRENT)
If ρ, λ are relations on A, then so is ρ ∩ λ. For all a, b ∈ A we have
a (ρ ∩ λ) b⇔ (a, b) ∈ ρ ∩ λ
⇔ (a, b) ∈ ρ and (a, b) ∈ λ
⇔ a ρ b and a λ b.
Lemma 3.2. If ρ, λ are equivalence relations on A then so is ρ ∩ λ.
Proof. We have ι ⊆ ρ and ι ⊆ λ, hence ι ⊆ ρ∩λ, so that ρ∩λ is reflexive. Suppose (a, b) ∈ ρ∩λ.
Then (a, b) ∈ ρ and (a, b) ∈ λ. As ρ, λ are symmetric, we have (b, a) ∈ ρ and (b, a) ∈ λ and hence
(b, a) ∈ ρ ∩ λ. Therefore ρ ∩ λ is symmetric. By a similar argument we have ρ ∩ λ is transitive
and ρ ∩ λ is an equivalence relation.
Denoting by [a]ρ the ρ-class of a and [a]λ the λ-class of a we have that,
[a]ρ∩λ = {b ∈ A | b (ρ ∩ λ) a},
= {b ∈ A | b ρ a and b λ a},
= {b ∈ A | b ρ a} ∩ {b ∈ A | b λ a},
= [a]ρ ∩ [a]λ.
If ρ, λ are relations on A, then so is ρ ∪ λ, but even if ρ and λ are equivalence relations, ρ ∪ λ
need not be an equivalence relation.
For example, on Z we have the equivalence relations ≡2 and ≡3 and
3 ≡2 1,
1 ≡3 4
If (≡2 ∪ ≡3) were to be transitive then we would have
(3, 1) ∈ (≡2 ∪ ≡3)
(1, 4) ∈ (≡2 ∪ ≡3)
hence (3, 4) ∈ (≡2 ∪ ≡3), i.e: 3 ≡2 4 or 3 ≡3 4, niether of which is true.
3.3. Kernels
Definition 3.3. Let α : X → Y be a map. Define a relation kerα on X by the rule
(2) a kerα b⇔ aα = bα.
We call kerα the kernel of α.
We may sometimes write a ≡α b. It is clear that kerα is an equivalence relation on X. The
kerα classes partition X into disjoint subsets; a, b lie in the same class iff aα = bα.
Example 3.4. Let α : [6]→ [4] where
α =
(
1 2 3 4 5 6
3 2 3 2 2 1
)
.
In this case the kerα-classes are {1, 3}, {2, 4, 5}, {6}.
SEMIGROUP THEORY 2021/22 21
If α : A → B is a map then α is one-one if and only if kerα = ιA and α is constant if and only
if kerα = ωA.
In group theory (and other areas of algebra where there are inverses) the kernel of a homomor-
phism θ : G → H is not a relation but a subgroup. We have
g ker θ h⇔ gθ = hθ ⇔ (hθ)−1gθ = 1H ⇔ (h−1g)θ = 1H
with the last part showing that we really only need to keep track of the elements of G that
are mapped by θ to the identity of H, rather than keeping track of all the elements of G that
are mapped to the same element of H. That is why ker θ = {g ∈ G : (g)θ = 1H} in group
theory. Without inverses at our disposal, i.e. without the (hθ)−1, we are forced to use the broader
definition (2) of kernal.
Definition 3.5. An equivalence relation ρ on a semigroup S is a congruence if
(a ρ b and c ρ d)⇒ ac ρ bd.
Example 3.6. The relation “congruent modulo m” is a congruence on the group (Z,+) as a ≡m b
and c ≡m d gives a + c ≡m b + d.
Lemma 3.7 (The Kernel Lemma). Let θ : S → T be a semigroup homomorphism. Then ker θ is a
congruence on S .
Proof. We know ker θ is an equivalence relation on S . Suppose a, b, c, d ∈ S with
(a ker θ b) and (c ker θ d).
Then aθ = bθ and cθ = dθ, so
(ac)θ = aθcθ = bθdθ = (bd)θ.
Therefore ac ker θ bd, so that ker θ is a congruence.
As we shall now see, congruences in semigroup theory play the same role as normal subgroups
in group theory: whenever we have a congruence we can form a quotient semigroup:
Let ρ be a congruence on S . Then define
S/ρ =
{
[a] | a ∈ S },
the set of ρ-equivalence classes.
Define a binary operation on S/ρ by
[a] ∗ [b] = [a][b] = [ab].
We need to make sure that this is a well-defined operation, that is, that the product [a][b] does
not depend on the choice of a and b. If [a] = [a′] and [b] = [b′] then a ρ a′ and b ρ b′; as ρ is a
congruence we have ab ρ a′b′ and hence [ab] = [a′b′]. Hence our operation is well-defined.
22 VICTORIA GOULD (SUPPLEMENTED BY BRENT)
Let [a], [b], [c] ∈ S/ρ. Then we have
[a]
(
[b][c]
)
= [a][bc],
=
[
a(bc)
]
,
=
[
(ab)c
]
,
= [ab][c],
=
(
[a][b]
)
[c].
and so the operation is associative and S/ρ is a semigroup.
If S is a monoid, then so is S/ρ because
[1][a] = [1a] = [a] = [a1] = [a][1]
for any a ∈ S . Hence if S is a monoid, then so is S/ρ.
Definition 3.8. We call S/ρ the quotient semigroup (or monoid) of S by ρ.
Define a map νρ : S → S/ρ by
sνρ = [s].
Then:
sνρtνρ = [s][t] definition of νρ,
= [st] definition of multiplication in S/ρ,
= (st)νρ definition of νρ.
Hence νρ is a semigroup homomorphism. Moreover if S is a monoid then 1νρ = [1], so that νρ is
a monoid homomorphism. We now want to examine the kernel of νρ:
s ker νρ t ⇔ sνρ = tνρ definition of ker νρ,
⇔ [s] = [t] definition of νρ,
⇔ s ρ t definition of ρ.
Therefore ρ = ker νρ, and so every congruence is the kernel of a morphism. Combining with the
kernel lemma gives that a relation on a semigroup is a conguence if and only if it is the kernel of
a homomorphism.
Since Im νρ = S/ρ we have that every quotient semigroup is the image of a morphism. To
complete the picture, we have:
Theorem 3.9 (First isomorphism theorem for semigroups). Let θ : S → T be a semigroup homo-
morphism. Then ker θ is a congruence on S , Im θ is a subsemigroup of T and S/ ker θ Im θ.
Proof. Define θ¯ : S/ ker θ → Im θ by [a]θ¯ = aθ. We have
[a] = [b]⇔ a ker θ b
⇔ aθ = bθ
⇔ [a]θ¯ = [b]θ¯.
SEMIGROUP THEORY 2021/22 23
Figure 5. The ker θ classes in Example 3.10 are the columns.
Hence θ¯ is well-defined and one-one. For any x ∈ Im θ we have x = aθ = [a]θ¯ and so θ¯ is onto.
Finally, (
[a][b]
)
θ¯ = [ab]θ¯ = (ab)θ = aθbθ = [a]θ¯[b]θ¯.
Therefore θ¯ is an isomorphism and S/ ker θ Im θ.
Note that the analogue of Theorem 3.9 holds for monoids.
Example 3.10. From Section 2 we have the homomorphism θ : I × J → TJ from the rectangular
band to the full transformation monoid on J given by
(i, j)θ = c j
where c j is the constant map [n]→ [n]. This maps I × J onto the subsemigroup of TJ consisting
of the constant maps. Two elements of the rectangular band lie in the same equivalence class of
the kernel exactly when they are in the same column – see Figure 5.
The multiplication (i, j)(k, `) = (i, `) on the rectangular band corresponds to the multiplica-
tion c jc` = c` of the corresponding constant maps. Replacing (i, j)(k, `) = (i, `) by different
representatives of the kernal class gives (i′, j)(k′, `) = (i′, `), which still corresponds to c jc` = c`.
Example 3.11. θ : B → (Z,+) given by (a, b)θ = a − b is a monoid morphism. Check that θ is
onto, so by FTH we have
B/ ker θ Z.
Moreover, ker θ is the congruence given by
(a, b) ker θ (c, d)⇔ a − b = c − d.
24 VICTORIA GOULD (SUPPLEMENTED BY BRENT)
4. Ideals
4.1. Notation
If A, B ⊆ S then we write
AB = {ab | a ∈ A, b ∈ B},
A2 = AA = {ab | a, b ∈ A}.
Note. A is a subsemigroup if and only if A , ∅ and A2 ⊆ A.
We write aB for {a}B = {ab | b ∈ B}. For example
AaB = {xay | x ∈ A, y ∈ B}.
Facts:
(1) A(BC) = (AB)C therefore 2S = {S | A ⊆ S }, equipped by the above-defined operation, is
a semigroup – the power semigroup of S .
(2) A ⊆ B⇒ AC ⊆ BC and CA ⊆ CB for all A, B,C ∈ 2S .
(3) If A is a subsemigroup, then A is isomorphic to the subsemigroup {{a} | a ∈ A} of 2A (this
certainly applies if A = S ).
(4) S 1S = S = S S 1.
Definition 4.1. Let ∅ , I ⊆ S then I is
(1) a left ideal if S I ⊆ I (i.e. a ∈ I, s ∈ S ⇒ sa ∈ I);
(2) a right ideal if IS ⊆ I;
(3) an (two-sided) ideal if IS ∪ S I ⊆ I, that is, I is both a left and a right ideal.
So, as I = 1 · I ⊆ I anyway, we have S I ⊆ I iff S 1I ⊆ I. Thus:
(1) I is a left ideal⇔ S 1I ⊆ I;
(2) I is a right ideal⇔ IS 1 ⊆ I;
(3) I is an ideal⇔ S 1IS 1 ⊆ I.
Note that if S is commutative, (1),(2) and (3) above coincide.
Note also that any (left/right) ideal is a subsemigroup.
Example 4.2. (1) Let i ∈ I, i ∈ J then {i} × J is a right ideal and I × { j} is a left ideal in a
rectangular band I × J – see Figure 6.
(2) Let m ∈ N0 be fixed. Then Bm = {(x, y) | x > m, y ∈ N0} is a right ideal in the bicyclic
semigroup B.
Indeed, let (x, y) ∈ Bm and let (a, b) ∈ B. Then
(x, y)(a, b) = (x − y + t, b − a + t),
where t = max{y, a}. Now, we know that x ≥ m and that t ≥ y, so t − y ≥ 0. Adding up
these two inequalities, we get that x − y + t ≥ m, thus the product is indeed in Bm.
(3) If Y ⊆ X then we have {α ∈ TX | imα ⊆ Y} is a left ideal of TX: for any β ∈ TX we have
im βα ⊆ Y as in Figure 7.
SEMIGROUP THEORY 2021/22 25
Figure 6. Right and left ideals in the rectangular band I × J.
Figure 7. {α ∈ TX | imα ⊆ Y} is a left ideal of TX.
(4) For any n ∈ N we define
S n = {a1a2 . . . an | ai ∈ S }.
This is an ideal of S . If S is a monoid then S n = S for all n, since for any s ∈ S we can
write
s = s 11 . . . 1︸ ︷︷ ︸
n−1
∈ S n.
(5) S itself is always an ideal.
(6) If S has a zero 0, then {0} (usually written 0), is an ideal.
Definition 4.3. Let S be a semigroup.
(1) We say that S is simple if S is the only (two sided) ideal.
(2) If S has a zero 0, then S is 0-simple if S and {0} are the only ideals and S 2 , 0.
(Here is the reason for the odd-looking condition S 2 , 0: a semigroup S is called null if S has
a 0 and st = 0 for all s, t ∈ S . We don’t want null semigroups to be 0-simple, much like we don’t
want 1 to be prime, or the trivial group to be a simple group. If S is null and |S | > 2, then there
is an s ∈ S with {0, s} a proper ideal of S . Thus, null semigroups with at least three elements
26 VICTORIA GOULD (SUPPLEMENTED BY BRENT)
are automatically not 0-simple. If S = {0, s} is null, then 0 and S are the only ideals. It also has
the property that S 2 = 0. To rule out this one example, the S 2 , 0 is added to the definition of
0-simple.)
Example 4.4. Let G be a group. Then G is simple and G0 is 0-simple.
Proof. Let I be an ideal of G and let a ∈ I. Then
g = (ga−1)a ∈ I
and so I = G. Therefore G has no proper ideals. Hence G is simple. The proof for G0 is an
exercise.
Example 4.5. We have (N,+) is a semigroup. Let n ∈ N. Now define N≥n ⊆ (N,+) to be
N≥n = {n, n + 1, n + 2, . . . },
which is an ideal. Hence N is not simple. {2, 4, 6, . . . } is a subsemigroup but not an ideal.
Example 4.6. The bicyclic semigroup B is simple.
Proof. Let I ⊆ B be an ideal, say (m, n) ∈ I. Then (0, n) = (0,m)(m, n) ∈ I. Thus (0, 0) =
(0, n)(n, 0) ∈ I. Let (a, b) ∈ B. Then
(a, b) = (a, b)(0, 0) ∈ I
and hence B = I ⇒ B is simple.
4.2. Principal Ideals
We make note of how the S 1 notation can be used. For example
S 1A = {sa | s ∈ S 1, a ∈ A},
= {sa | s ∈ S ∪ {1}, a ∈ A},
= {sa | s ∈ S , a ∈ A} ∪ {1a | a ∈ A},
= S A ∪ A ⊆ S
In particular, if A = {a} then S 1a = S a ∪ {a}. So,
S 1a = S a⇔ a ∈ S a,
⇔ a = ta
for some t ∈ S . We have S 1a = S a for a ∈ S if:
(1) S is a monoid (then a = 1a).
(2) a ∈ E(S ) (then a = aa).
But in (N,+) we have 1 < N + 1.
Dually,
aS 1 = aS ∪ {a}
and similarly
S 1aS 1 = S aS ∪ aS ∪ S a ∪ {a}.
SEMIGROUP THEORY 2021/22 27
Claim. aS 1 (S 1a, S 1aS 1) is the “smallest” right (left, two-sided) ideal containing a.
Proof. (for aS 1). We have a = a1 ∈ aS 1 and (aS 1)S = a(S 1S ) ⊆ aS 1. So, aS 1 is a right ideal
containing a. If a ∈ I and I is a right ideal, then aS 1 ⊆ IS 1 = I ∪ IS ⊆ I.
Definition 4.7. We call aS 1 (S 1a, S 1aS 1) the principal right (left, two-sided) ideal generated by
a.
If S is commutative then aS 1 = S 1a = S 1aS 1.
Example 4.8. In a group G we have
aG1 = G1a = G1aG1 = G
for all a ∈ G.
Example 4.9. In N under addition we have
n + “N1” = {n, n + 1, n + 2, . . . }
(“N1” = N ∪ {0})
Example 4.10. The bicyclic monoid B is simple, so
B(m, n)B = B1(m, n)B1 = B
for all (m, n) ∈ B. However:
Claim. (m, n)B = (m, n)B1 =
{
(x, y) | x > m, y ∈ N0}
Proof. We have
(m, n)B =
{
(m, n)(u, v) | (u, v) ∈ B}
⊆ {(x, y) | x > m, y ∈ N0}.
Let x > m then
(m, n)
(
n + (x − m), y) = (m − n + n + (x − m), y),
= (x, y).
Therefore (x, y) ∈ (m, n)B ⇒ {(x, y) | x > m, y ∈ N0} ⊆ (m, n)B. Hence we have proved our
claim.
Dually we have B(m, n) =
{
(x, y) | x ∈ N0, y > n}.
Lemma 4.11 (Principal Left Ideal Lemma). The following statements are equivalent;
(i). S 1a ⊆ S 1b,
(ii). a ∈ S 1b,
(iii). a = tb for some t ∈ S 1,
(iv). a = b or a = tb for some t ∈ S .
Note. If S 1a = S a and S 1b = S b, then the Lemma can be adjusted accordingly.
28 VICTORIA GOULD (SUPPLEMENTED BY BRENT)
Figure 8
Proof. That (iii) and (iv) are equivalent is clear. (i)⇒ (ii): If S 1a ⊆ S 1b then a = 1a ∈ S 1a ⊆ S 1b
hence a ∈ S 1b. (ii)⇒ (iii): is by definition. (iii)⇒ (i): a = tb implies that sa = (st)b ∈ S 1b for
all s ∈ S 1, hence S 1a ⊆ S 1b.
Lemma 4.12 (Principal Right Ideal Lemma). The following statements are equivalent:
(i). aS 1 ⊆ bS 1,
(ii). a ∈ bS 1,
(iii). a = bt for some t ∈ S 1,
(iv). a = b or a = bt for some t ∈ S .
Note. If aS = aS 1 and bS = bS 1 then aS ⊆ bS ⇔ a ∈ bS ⇔ a = bt for some t ∈ S .
4.3. Example: principal ideals in IX
For a fixed s ∈ Ix we describe the principal right ideal sIX. Suppose that A, B are subsets of X
with
(i). A ⊆ dom s, and
(ii). |A| = |B|.
Let t : A → B be any bijection. Then define a bijection u : As → B as follows: if x ∈ As then
x = (y)s for a (unique) y ∈ A. Let (x)u = (y)t – see Figure 8. Then u is 1-1 (as t is 1-1) and
su = t.
The conclusion is that: post-multiplying s by an element can yield any t ∈ IX that has domain
A some subset of dom s and any image B whatsoever, as long as it has the same cardinality.
In particular, {t : dom t ⊆ dom s} ⊆ sIX. On the other hand dom su ⊆ dom s and so sIX ⊆ {t :
dom t ⊆ dom s} and so the principal right ideal
(3) sIX = {t : dom t ⊆ dom s}
SEMIGROUP THEORY 2021/22 29
Figure 9. sI3, I3s and I3sI3.
as in Figure 9. In an entirely analogous way, pre-multiplying s by an element can yield any t ∈ IX
that has image A some subset of im s and any domain B whatsoever, as long as it has the same
cardinality, and the principal left ideal
(4) IX s = {t : im t ⊆ im s}
See Figure 9.
What about the (two-sided) ideals? It is not the case that you need merely combine (3) and (4)
so that IX sIX consists of the t with dom t ⊆ dom s and im t ⊆ im s.
Instead, I claim that
(5) IX sIX = {t : | dom t| ≤ | dom s|} = {t : |im t| ≤ |im s|}
– see Figure 9. To see this, let t : A → B be any element with |A| = | dom t| ≤ | dom s|. Then
there is a subset A′ of dom s having the same size as A, so that for suitable u, the element su has
domain A′ and image B. But then, for a suitable v, the element v(su) has domain A and image B,
and can equal any bijection between these two sets. In particular it can equal t. This shows (5).
If n > 1 then the symmetric inverse monoid In is a semigroup with a 0, but is not a 0-simple
semigroup. For, if s is such that 0 < | dom s| = k < n, then the ideal InsIn consists of all the
elements having domain size at most k, and this is a proper non-trivial ideal.
In does contain a 0-simple subsemigroup however, and it is:
I≤1n = {t ∈ In : | dom t| ≤ 1}
30 VICTORIA GOULD (SUPPLEMENTED BY BRENT)
In Figure 9 these elements are the bottom 3 × 3 grid together with 0 : ∅ → ∅. We saw that I≤1n
(indeed I≤kn ) is a subsemigroup in Section 2. If 0 , I is an ideal in I
≤1
n , then it contains an element
s : {i} → { j}, and hence the principal ideal I≤1n sI≤1n = I≤1n . As I≤1n sI≤1n ⊂ I we get I = I≤1n , and the
subsemigroup is 0-simple.
4.4. Green’s relations
The following relation is crucial in semigroup theory.
Definition 4.13. The relationL on a semigroup S is defined by the rule a L b iff a and b generate
the same principal left ideal. In other words:
a L b⇔ S 1a = S 1b
for any a, b ∈ S .
Note.
(1) L is an equivalence.
(2) If a L b and c ∈ S then S 1a = S 1b, so S 1ac = S 1bc and hence ac L bc.
Corollary 4.14. We have that
a L b⇔ there exists s, t ∈ S 1 with a = sb and b = ta.
Proof.
a L b⇔ S 1a = S 1b
⇔ S 1a ⊆ S 1b and S 1b ⊆ S 1a
⇔ there exists s, t ∈ S 1 with a = sb, b = ta
by the Principal Left Ideal Lemma.
This statement about L can be used as a definition of L.
Remark.
(1) a L b⇔ a = b or there exist s, t ∈ S with a = sb, b = ta.
(2) If S a = S 1a and S b = S 1b, then a L b⇔ there exists s, t ∈ S with a = sb, b = ta.
Dually, the relation R is defined on S by a R b iff a and b generate the same principle right
ideal., i.e.
a R b⇔ aS 1 = bS 1
and
a R b⇔ there exists s, t ∈ S 1 with a = bs and b = at,
⇔ a = b or there exists s, t ∈ S with a = bs and b = at.
We can adjust this if aS 1 = aS as before. The relation R satisfies a R b ⇒ ca R cb for any
c ∈ S .
SEMIGROUP THEORY 2021/22 31
Definition 4.15. We define the relation H = L ∩ R and note that H is an equivalence. Spelling
it out: a H b iff a L b and a R b iff there are s, t ∈ S 1 with a = sb and b = ta and there are
u, v ∈ S 1 with a = bu and b = av.
The relations L,R,H are called Green’s relations. We will see two others, calledD and J .
Notation: La is the L class of a ∈ S , Ra is the R-class of a ∈ S and Ha is theH-class of a ∈ S .
Example 4.16. (1) If S is commutative, L = R = H .
(2) In a group G,
G1a = G = G1b and aG1 = G = bG1 for all a, b ∈ G.
So a L b and a R b for all a, b ∈ G and hence a H b for all a, b ∈ G too.
Example 4.17. In N under + we have
a + N1 = {a, a + 1, . . . }
and so a + N1 = b + N1 ⇔ a = b. Hence elements of N are L, R or H related only when they
are equal to each other.
Example 4.18. In B we know
(m, n)B1 =
{
(x, y) | x > m, y ∈ N0}
and so we have
(m, n)B1 = (p, q)B1 ⇔ m = p.
Hence (m, n) R (p, q)⇔ m = p. Dually,
(m, n) L (p, q)⇔ n = q.
Thus (m, n) H (p, q)⇔ (m, n) = (p, q), which gives usH = ι.
Example 4.19. In the symmetric inverse monoid IX we have
(1) aIX ⊆ bIX iff dom a ⊆ dom b. For, if dom a ⊆ dom b then
{t : dom t ⊆ dom a} ⊆ {t : dom t ⊆ dom b}
hence aIX ⊆ bIX by (3). On the other hand, if aIX ⊆ bIX then a = bt for some t ∈ IX and
hence dom a = dom bt ⊆ dom b. Thus a R b iff aIX = bIX iff dom a = dom b.
(2) In a completely analogous way, a L b iff im a = im b.
(3) (Thus a H b iff im a = im b and dom a = dom b).
In our pictures of In, the elements have been divided into boxes depending on the size of the
domain and image; these boxes have in turn been divided into grids with rows indexed by the
possible domains and columns indexed by the possible images. By what we have said above,
each column of a grid is an L-class, each row of a grid is an R-class, and the boxes that form the
intersections of columns and rows are theH-classes – see Figure 10.
32 VICTORIA GOULD (SUPPLEMENTED BY BRENT)
Figure 10. The R-classes in In are the rows; the L-classes are the columns and
theH-classes are the boxes formed by the intersections of the rows and columns.
4.5. L and R in TX
Claim. αTX ⊆ βTX ⇔ ker β ⊆ kerα.
(Recall kerα =
{
(x, y) ∈ X × X | xα = yα}.)
Proof. (⇒) Suppose αTX ⊆ βTX. Then α = βγ for some γ ∈ TX. Let (x, y) ∈ ker β. Then
xα = x(βγ) = (xβ)γ = (yβ)γ = y(βγ) = yα.
SEMIGROUP THEORY 2021/22 33
Figure 11. Defining the map γ in the proof that αTX ⊆ βTX ⇔ ker β ⊆ kerα.
Hence (x, y) ∈ kerα and so ker β ⊆ kerα.
(⇐) Suppose ker β ⊆ kerα. Define γ : X → X by
zγ =
{
xα z = xβ
z z < im β
(See Figure 11). If z = xβ = yβ, then (x, y) ∈ ker β ⊆ kerα so xα = yα. Hence γ is well-defined.
So γ ∈ TX and βγ = α. Therefore α ∈ βTX so that by the Principal Ideal Lemma, αTX ⊆ βTX.
Corollary 4.20 (R-TX-Lemma). In TX we have α R β⇔ kerα = ker β.
Proof. We have
α R β⇔ αTX = βTX
⇔ αTX ⊆ βTX and βTX ⊆ αTX
⇔ ker β ⊆ kerα and kerα ⊆ ker β
⇔ kerα = ker β.

Fact: TXα ⊆ TXβ⇔ Imα ⊆ Im β (See Exercises).
Corollary 4.21 (L-TX-Lemma). In TX we have α L β⇔ imα = im β.
Consequently α H β⇔ kerα = ker β and Imα = Im β.
Example 4.22. Let us define
ε =
(
1 2 3
2 2 3
)
∈ E(T3)
Now we have Im ε = {2, 3}. We can see that ker ε has classes {1, 2}, {3}. So
α H ε⇔ Imα = Im ε and kerα = ker
⇔ Imα = {2, 3} and kerα has classes {1, 2}, {3}.
34 VICTORIA GOULD (SUPPLEMENTED BY BRENT)
So we have:
ε α
and the elements that areH-related to ε are:
ε α
ε ε α
α α ε
which is the table of a 2-element group. Thus theH-class of ε is a group.
5. Subgroups of Semigroups
Let S be a semigroup and let H ⊆ S . Then H is a subgroup of S if it is a group under the
restriction of the binary operation on S to H; i.e.
• a, b ∈ H ⇒ ab ∈ H;
• there is an e ∈ H with ea = a = ae for all a ∈ H (and in particular ee = e so e is an
idempotent);
• for all a ∈ H there is a b ∈ H with ab = e = ba.
Remark.
(1) A semigroup can contain (many) disjoint subgroups even though it is not itself a group!
(2) If H is a subgroup with identity e, then e is the only idempotent in H, as the identity of a
group is unique.
(3) If e ∈ E(S ), then {e} is a trivial subgroup.
(4) With α =
(
1 2 3
3 3 2
)
and =
(
1 2 3
2 2 3
)
we have {, α} is a subgroup of T3 (and this is the
H-class containing the idempotent ε).
(5) S X is a subgroup of TX. Notice
α H idX ⇔ imα = im idX and kerα = ker idX,
⇔ imα = X and x kerα y iff x = y,
⇔ α is onto and α is one-one,
⇔ α ∈ S X.
Therefore S X is theH-class of idX.
SEMIGROUP THEORY 2021/22 35
(6) In our running example of I3 the idempotents are the partial identities eA = idA on some
subset A ⊆ [n]. The elements
HA = {s : dom s = A = im s}
form a square on the diagonal in the row and column labelled by A (see Figure 12). They
are a subgroup isomorphic to the symmetric group S A on the set A. Moreover,
s H idA ⇔ im s = im idA and dom s = dom idA,
⇔ im s = A and dom s = A,
so that HA is theH-class of the idempotent idA.
(7) If S is a band (i.e. all of the elements of S are idempotents) then any subgroup of S is
the trivial group.
Remark. (1) La = Lb ⇔ a L b;
(2) and Ha = La ∩ Ra (see notes on intersection of equivalence classes).
For example, in B, we have L(2,3) =
{
(x, 3) | x ∈ N0} and H(a,a) = {(a, a)} for any a ∈ N0.
We are going to show that:
(1) TheH-class He containing an idempotent e is a subgroup having identity the idempotent
e.
(2) If H is any subgroup then it is a subgroup of an He for some idempotent e.
As a consequence, we will see that whenever two subgroups are not disjoint, then they are both
contained within the same subgroup.
For example in Figure 12, the subgroups {id, (1, 2)} and {id, (2, 3)} are both contained in the
copy of S 3 at the top of the picture.
Lemma 5.1 (principal ideal for idempotents). Let a ∈ S , e ∈ E(S ). Then
(i). S 1a ⊆ S 1e⇔ ae = a
(ii). aS 1 ⊆ eS 1 ⇔ ea = a.
Proof. (We prove part (i); (ii) is dual). If ae = a, then a ∈ S 1e so S 1a ⊆ S 1e by the Principal
Ideal Lemma. Conversely, if S 1a ⊆ S 1e then by the Principal Ideal Lemma we have a = te for
some t ∈ S 1. Then
ae = (te)e = t(ee) = te = a.

Corollary 5.2. Let e ∈ E(S ). Then we have
a L e⇒ ae = a,
a R e⇒ ea = a,
a H e⇒ a = ae = ea.
Thus, e is a right identity for its L-class Le, a left identity for its R-class Re and an identity for
itsH-class He.
36 VICTORIA GOULD (SUPPLEMENTED BY BRENT)
Figure 12. TheH-classes of the idempotents idA are subgroups of I3.
SEMIGROUP THEORY 2021/22 37
Example 5.3. If s : A→ B is in In then s L t iff im s = im t = B. The idempotents are the partial
identities, and there is precisely one that has image the set B, and that is idB. Consider then, s idB:
it has:
dom s idB = s-preimage of B ∩ B, im s idB = t-image of B ∩ B
i.e. dom s idB = A and im s idB = B and for x ∈ A we have (x)s idB = (x)s. Thus s idB = s.
Lemma 5.4. Let G be a subgroup with identity e. Then G ⊆ He. In particular, the elements of G
are allH-related.
Proof. Let G be a subgroup with identity e. Then for any a ∈ G we have ea = a = ae and there
exists a−1 ∈ G with aa−1 = e = a−1a. Then
ea = a
aa−1 = e
⇒ a R e
ae = a
a−1a = e
⇒ a L e
⇒ a H e.
Therefore a H e for all a ∈ G, so G ⊆ He.
Theorem 5.5 (maximal subgroup theorem). Let e ∈ E(S ). Then He is a subgroup with identity e
and any other subgroup G with identity e is contained in He. Thus, He is the maximum subgroup
of S with identity e.
Proof. We have shown that if G is a subgroup with identity e, then G ⊆ He. We show now that
He itself is a subgroup with identity e.
We know that e is an identity for He. Suppose a, b ∈ He. Then b H e, so b R e hence abR ae
(see the properties of R given straight after its definition) so
ab R ae⇒ ab R a⇒ ab R a R e
Also, a L e⇒ ab L eb⇒ ab L b⇒ ab L b L e, hence ab H e so ab ∈ He.
It remains to show that for all a ∈ He there exists b ∈ He with ab = e = ba. Let a ∈ He. Then,
by definition ofH = R ∩ L, there exist s, t ∈ S 1 with
at =︸︷︷︸
aRe
e = sa︸︷︷︸
aLe
.
We have
a(ete) = (ae)te = ate = ee = e = ee = esa = es(ea) = (ese)a.
Let x = ete, y = ese so x, y ∈ S and ex = xe = x, ey = ye = y. Also e = ax = ya. Now
x = ex = (ya)x = y(ax) = ye = y.
So let b = x = y. Then ab = e = ba and:
eb = b ba = e︸ ︷︷ ︸
bRe
be = b ab = e︸ ︷︷ ︸
bLe
so b H e, thus b ∈ He. Hence He is indeed a subgroup and the maximum subgroup with identity
e.
38 VICTORIA GOULD (SUPPLEMENTED BY BRENT)
α
1 n
1 n
fibers/kernel of α
Figure 13. The number of kerα-classes equals the size of the image.
Let e, f ∈ E(S ) with e , f . Since He and H f are subgroups containing the idempotents e and
f , respectively, He , H f . This implies that He ∩ H f = ∅, as H-equivalence classes are either
equal, or disjoint.
Example 5.6. An idempotent in In is a partial identity idA for some A ⊆ [n]. Writing HA for
the H-class of idA, we have a H idA iff a L idA and a R idA iff im a = im idA = A and
dom a = dom idA = A. Thus the maximal subgroup is
HA = {a ∈ In : dom a = A = im A}
the group of bijections from A to A, a copy of the symmetric group S A.
Theorem 5.7 (Green’s Theorem). An a ∈ S lies in a subgroup iff a H a2.
Proof. See later.
Corollary 5.8. Let a ∈ S . Then the following are equivalent:
(i). a lies in a subgroup,
(ii). a H e, for some e ∈ E(S ),
(iii). Ha is a subgroup,
(iv). a H a2.
Proof. (i)⇒ (ii): If a ∈ G, then G ⊆ He where e2 = e is the identity for G. Therefore a ∈ He so
a H e.
(ii)⇒ (iii): If a H e, then Ha = He and by the maximal subgroup theorem, He is a subgroup.
(iii)⇒ (i): Straightforward, for a ∈ Ha.
(iv)⇔ (i) This is Green’s Theorem.
5.1. Subgroups of Tn
We know Imα2 ⊆ Imα (as any ((x)α)α has the form (y)α . . .) so
Imα = Imα2 ⇔ | Imα| = | Imα2|.
We know that kerα ⊆ kerα2 (as (x)α = (y)α implies that ((x)α) = ((x)α)α) which means that
the kerα2-classes are just unions of kerα-classes.
SEMIGROUP THEORY 2021/22 39
We thus have kerα = kerα2 iff the number of kerα-classes is the same as the number of
kerα2-classes. Finally, for any α : [n] → [n] the kerα-classes are in 1-1 correspondence with
the elements of the image imα, with this bijection provided by α – see Figure 13.
Claim. For α ∈ Tn we have imα = imα2 ⇔ kerα = kerα2.
Proof.
imα = imα2 ⇔ |imα| = |imα2|
⇔ | kerα-classes| = | kerα2-classes|
⇔ kerα = kerα2.

We use Green’s Theorem to prove the following.
Lemma 5.9. An α ∈ Tn lies in a subgroup if and only if imα2 = imα.
Proof. We have
α lies in a subgroup ⇔ α H α2
⇔ α L α2, α R α2
⇔ imα = imα2, kerα = kerα2
⇔ imα = imα2.

Example 5.10. Consider the following element of T5:
α =
(
1 2 3 4 5
3 1 4 3 1
)
∈ T5.
This has map diagram:
The elements of imα are in green and the elements of imα2 are in orange. As imα \ imα2 , ∅,
the element α is not in a subgroup.
Example 5.11. The constant element c1 ∈ T5:
c1 =
(
1 2 3 4 5
1 1 1 1 1
)
.
has the following map diagram
40 VICTORIA GOULD (SUPPLEMENTED BY BRENT)
As im c1 = im c21, it lies in a subgroup. Note that actually c
2
1 = c1. Now for any β,
β ∈ Hc1 ⇔ β H c1,
⇔ β R c1 and β L c1,
⇔ ker β = ker c1 and Im β = Im c1,
⇔ ker β has classes {1, 2, 3, 4, 5} and Im β = {1},
⇔ β = c1.
Therefore the maximal subgroup containing c1 is Hc1 = {c1}.
Example 5.12. Take the element
α =
(
1 2 3 4 5
2 3 2 3 5
)
.
with map diagram:
As imα = imα2, the element α lies in a subgroup, hence α lies in a maximal subgroupHα. For
any β
β ∈ Hα ⇔ β H α,
⇔ β R α and β L α,
⇔ ker β = kerα and Im β = Imα,
⇔ Im β = {2, 3, 5} and ker β has classes {1, 3}, {2, 4}, {5}.
We now figure out what the elements ofHα are. We start with the idempotent. We know that the
image of the idempotent is {2, 3, 5} and that idempotents are identities on their images. Thus we
must have
ε =
(
1 2 3 4 5
2 3 5
)
.
We also know that 1 and 3 go to the same place and 2 and 4 go to the same place. Thus we must
have
ε =
(
1 2 3 4 5
3 2 3 2 5
)
.
SEMIGROUP THEORY 2021/22 41
We now have what the idempotent is and then the other elements of Hα are (note that 1 and 3
must have the same images, just as 2 and 4):(
1 2 3 4 5
2 3 2 3 5
)
(
1 2 3 4 5
5 2 5 2 3
) (
1 2 3 4 5
3 5 3 5 2
)
(
1 2 3 4 5
5 3 5 3 2
) (
1 2 3 4 5
2 5 2 5 3
)
.
These are all 6 elements. CheckHα ' S 3.
6. D,J and Green’s Lemmas
Recall S 1aS 1 = {xay | x, y ∈ S 1}.
Definition 6.1. We say that a J b if and only if S 1aS 1 = S 1bS 1. That is, a and b generate the
same principal (two sided) ideal.
This is equivalent to:
aJ b⇔ ∃ s, t, u, v ∈ S 1 with a = sbt b = uav.
Note. If a L b, then S 1a = S 1b so S 1aS 1 = S 1bS 1 so a J b, i.e. L ⊆ J , dually R ⊆ J .
Note. An S without 0 is simple iff any two elements of S are J-related.
Proof. If S is simple and a, b ∈ S then
S 1aS 1 = S = S 1bS 1 so a J b
Conversely if any two elements of S are J-related and I is an ideal of S , then pick any a ∈ I and
any s ∈ S . We have
s ∈ S 1sS 1 = S 1aS 1 ⊆ I.
Therefore I = S and S is simple.
Similarly if S has a zero, then {0} and S \ {0} are the only J-classes iff {0} and S are the only
ideals.
6.1. Composition of Relations
Definition 6.2. If ρ and λ are relations on A we define
ρ ◦ λ = {(x, y) ∈ A × A | there is a z ∈ A with x ρ z λ y}.
Lemma 6.3. If ρ, λ are equivalence relations and if ρ ◦ λ = λ ◦ ρ then ρ ◦ λ is an equivalence
relation. It is the smallest equivalence relation containing ρ ∪ λ.
Proof. Put ν = ρ ◦ λ = λ ◦ ρ
42 VICTORIA GOULD (SUPPLEMENTED BY BRENT)
• Reflexive: for any a ∈ A, a ρ a λ a so a ν a.
• Symmetric: for any a, b ∈ A with a ν b we have c ∈ A with a ρ c λ b. As ρ, λ are symmetric
this gives b λ c ρ a so b ν a.
• Transitive: if a, b, c ∈ A with a ν b ν c then there exists x, y ∈ A with
a ρ x λ b ρ z λ c⇒ a ρ x λ b λ y ρ c.
(Note that first we use that ν = ρ ◦ λ, and next we use that ν = λ ◦ ρ.) From x λ b λ y we
have x λ y, so
a ρ x λ y ρ c.
Therefore x ν c hence there exists z ∈ A such that x ρ z λ c, therefore a ρ z λ c and hence
a ν c.
We have shown that ν is an equivalence relation. If a ρ b then a ρ b λ b so a ν b. Similarly if
a λ b then a ρ a λ b so a ν b, Hence ρ ∪ λ ⊆ ν.
Now, suppose ρ∪ λ ⊆ τ where τ is an equivalence relation. Let a ν b. Then we have a ρ c λ b
for some c. Hence a τ c τ b so a τ b as τ is transitive. Therefore ν ⊆ τ.
The smallest equivalence relation containing any ρ and λ is denoted by ρ ∨ λ; we have shown
that if ρ and λ commute, then ρ ∨ λ = ρ ◦ λ.
Definition 6.4. D = R ◦ L, i.e. a D b⇔ there exists c ∈ S with a R c L b.
Lemma 6.5 (TheD Lemma). R ◦ L = L ◦ R
Proof. We prove that R ◦ L ⊆ L ◦ R, the proof of the other direction being dual. Suppose that
a (R ◦ L) b. Then there exists c ∈ S with
a R c L b
There exists u, v, s, t ∈ S 1 with
a = cu
(1)
c = av
(2)
c = sb
(3)
b = tc
(4)
.
Put d = bu then we have
a =
(1)
cu =
(3)
sbu = sd,
d = bu =
(4)
tcu =
(1)
ta.
Therefore a L d. Also
b =
(4)
tc =
(2)
tav =
(1)
tcuv =
(4)
buv = dv.
Therefore d R b and hence a (L ◦ R) b.
HenceD is an equivalence relation andD = L ∨ R. By definition
H = L ∩ R ⊆ L ⊆ D,
H = L ∩ R ⊆ R ⊆ D.
AsJ is an equivalence relation and L ∪ R ⊆ J we must haveD ⊆ J . The relationship between
all these relations is shown in Figure 14.
Notation: Da is theD class of a ∈ S and Ja is the J-class of a ∈ S .
SEMIGROUP THEORY 2021/22 43
Figure 14. Relationship between the various Green’s relations (left) and the pic-
ture (right) never happens.
Note. Ha ⊆ La ⊆ Da ⊆ Ja and also Ha ⊆ Ra ⊆ Da ⊆ Ja.
Egg-Box Pictures
Let D be a D-class. Then for any a ∈ D we have Ra ⊆ D = Da, and La ⊆ D. We write the
R-classes horizontally and the L-classes vertically. We claim that every R-class intersects every
L-class, so we never have the situation shown on the right of Figure 14.
Let u, v ∈ D then u D v. This implies that there exists h ∈ S with u R h L v, so Ru ∩ Lv , ∅,
that is, the R- and L-classes intersect. Moreover
Ru ∩ Lv = Rh ∩ Lh = Hh.
i.e. the intersection of an R-class and an L-class is an H-class. As D is an equivalence, S is
the union of such “egg-boxes”: the rows represent the R-classes, and the columns represent the
L-classes – see Figure 15.
6.2. Structure ofD-classes
Let S be a semigroup, s ∈ S 1. We define ρs : S → S by aρs = as for all a ∈ S
Lemma 6.6 (Green’s Lemma). Let a, b ∈ S be such that a R b and let s, s′ ∈ S be such that
as = b and bs′ = a.
Then ρs : La → Lb and ρs′ : Lb → La are mutually inverse, R-class preserving bijections (i.e. if
c ∈ La, then c R cρs and if d ∈ Lb then d R dρs′).
See Figure 17.
Proof. If c ∈ La then
cρs = cs and cL a⇒ csL as⇒ csL b
because L is a right congruence. So cρs L b therefore ρs : La → Lb. Dually ρs′ : Lb → La.
44 VICTORIA GOULD (SUPPLEMENTED BY BRENT)
Figure 15. An eggbox: a D-class is a union of R-classes (rows) and a union of
L-classes (columns) and a union ofH-classes (cells).
Let c ∈ La. Then c = ta for some t ∈ S . Now
cρsρs′ = tasρs′ = tass′ = tbs′ = ta = c.
So c = css′ hence ρsρs′ = ILa; dually, ρs′ρs = ILb .
Again, let c ∈ La. Then
cs = c · s,
c = cs · s′.
Therefore c R cs = cρs.
Lemma 6.7 (Continuing Lemma 6.6). For any c ∈ La we have ρs : Hc → Hcs is a bijection with
inverse ρs′ : Hcs → Hc. In particular, when c = a:
ρs : Ha → Hb and ρs′ : Hb → Ha
are mutually inverse bijections.
Let s ∈ S 1. Then we define λs : S → S by aλs = sa.
Lemma 6.8 (Dual of Green’s Lemma). Let a, c ∈ S be such that a L c and let t, t′ ∈ S be such
that ta = c and t′c = a. Then λt : Ra → Rc and λt′ : Rc → Ra are mutually inverse L-class
preserving bijections. In particular, for any b ∈ Ra we have λt : Hb → Htb, λt′ : Htb → Hb are
mutually inverse bijections. So, if b = a we have λt : Ha → Hc, λt′ : Hc → Ha are mutually
inverse bijections.
See Figure 17.
Corollary 6.9. If a D d then there exists a bijection Ha → Hd.
SEMIGROUP THEORY 2021/22 45
Figure 16. Green’s lemma (left) its dual (middle) and the H-classes Ha and Hd
have the same cardinality (right).
Proof. If a D d then there exists b ∈ S with a R b L d. There exists a bijection Ha → Hb by
Green’s Lemma and there exists a bijection Hb → Hd by the dual of Green’s Lemma. Therefore
there exists a bijection Ha → Hd.
Thus any two H-classes in the same D-class have the same cardinality (just like any two R-
and L-classes) – see Figure 17.
Theorem 6.10 (Green’s Theorem – Strong Version). Let H be an H-class of a semigroup S .
Then either H2 ∩ H = ∅ or H is a subgroup of S .
Proof. Suppose H2 ∩ H , ∅ so that there is a b ∈ H2 ∩ H. Then b = as for some a, s ∈ H. We
have aH b hence aR b. Indeed, b = as (and a = bs′ for some s′) with ρs : Ha → Hb a bijection,
i.e. ρs : H → H a bijection. In particular, s ∈ H and so there is a e ∈ H with s = es.
As s R e, we have e = sx for some x ∈ S 1 and then e = sx = esx = e2. Hence H contains the
idempotent e so, by the Maximal Subgroup Theorem, H is a subgroup.
Corollary 6.11 (Green’s Theorem – Weak Version, Theorem 5.7). a H a2 ⇔ Ha is a subgroup.
Proof. We know Ha is a subgroup ⇒ a, a2 ∈ Ha so aH a2. Conversely, if aHa2, then a2 ∈
Ha ∩ (Ha)2. Hence Ha ∩ (Ha)2 , ∅. By Theorem 6.10, Ha is a subgroup.
Interlude: some strategic pictures
A “strategic picture” of a semigroup is a picture of theD-classes, divided up into eggbox pic-
tures consisting of L,R and H-classes, the idempotents, the H-classes containing idempotents,
and hence the maximal subgroups.
Example 6.12. One of the nicest pictures comes about for In, and we have drawn it already, using
ad-hoc reasoning, in the case n = 3. We know that
a L c iff im a = im c and a R b iff dom a = dom b
hence a H d iff both of these things happen.
46 VICTORIA GOULD (SUPPLEMENTED BY BRENT)
Figure 17. Strategic picture of In.
Fix an a : X → Y where |X| = k = |Y |. If d : Z → W is any other partial bijection where
|Z| = k = |W |, then let
b : X → W and c : Z → Y
be any bijections. Then a and b have the same domain, hence are R-related, and a and c have
the same image, hence are L-related – see Figure 17. Similarly, c, d are R-related and b, d are
L-related. The result is that a and d are D-related, and the D-class Da of the map a consists of
all partial bijections between two sets of size k.
AD-class thus has rows (R-classes) and columns (L-classes) labelled by the subsets of a fixed
size k, for 0 ≤ k ≤ n. In particular the eggbox is a
(
n
k
)
×
(
n
k
)
square grid.
The H-class of a is the intersection of the row labelled X and the column labelled Y , and so
consists of all the bijections from X to Y .
We have seen that the idempotents in In are the partial identities idX : X → X. As the domain
and image of idX are the same set X, theH-class containing idX lies on the diagonal of the eggbox
(in blue in Figure 17). If e = idX then theH-class
He = { all bijections X → X } = S X S k
the symmetric group of degree k.
Stacking theD-class eggboxes, one on top of the other, we get n+1 eggboxes as shown on the
right of Figure 17. The number inside the eggbox is the domain/image size, and each is a square
grid of size shown at the right.
SEMIGROUP THEORY 2021/22 47
We can also illustrate the strong version of Green’s theorem. If a lies on the diagonal of an
eggbox, hence in a subgroup, then a2 does too, as subgroups are closed. If a : X → Y lies off the
diagonal then X , Y , so that there is an x ∈ X \ Y and a y ∈ Y \ X (we can’t have that one of X or
Y is contained in the other, as they both have the same size).
Suppose now that a′ : X → Y is another element in the sameH-class as a. There is an element
x′ ∈ X mapping via a to y. Then x′ is not in the domain of aa′. There is also an element y′ that is
the image under a′ of x. Then y′ is not in the image of aa′. The result is that the sizes:
| dom(aa′)| = |im (aa′)| < k
and so the product aa′ does not lie in the same H-class as a (it doesn’t even lie in the same
D-class as a). Thus Ha ∩ H2a is either Ha or completely disjoint from Ha.
Example 6.13. With the full transformation semigroup T3, and more generally Tn, the process is
the same but the answers are a little different.
We have:
a L c iff im a = im c and a R b iff ker a = ker b
hence a H d iff a and d have both the same kernel and the same image.
When n = 3 the image can have size k = 1, 2 or 3. The kernels are equivalence classes on the
set {1, 2, 3}, where the equivalence classes partition this set. The possible partitions of {1, 2, 3}
are:
1|2|3, 12|3, 13|2, 23|1 and 123
where 12|3 is the partition that has 1, 2 in one equivalence class and 3 in the other; 123 has all
three elements in the same class, and so on. A map a ∈ Tn maps the equivalence classes of the
kernel bijectively to the elements of the image, so a map with kernel 1|2|3 has image size 3; a
map with kernel 12|3 has image size 2 and map with kernel 123 has image size 1.
Thinking then of the elements of T3 as bijections between equivalence classes of a kernel and
elements of an image, an argument similar to the above for In shows that a and d are D-related
exactly when their images have the same size, or equivalently, their kernels have the same number
of classes.
Stacking the D-classes by size of image gives Figure 18(a). Each D-class has rows labelled
by the partitions of {1, 2, 3} having k = 1, 2, 3 blocks and columns labelled by subsets of size
k = 1, 2, 3. The H-classes then consist of the maps whose kernel is the partition labelling the
row and whose image is the subset labelling the column. We can see straight away that not all
the eggboxes are square: the bottom one is a 1 × 3 grid.
The idempotents in Tn are the maps that restrict to the identity map on their images. Such
maps come about by choosing a point in each block of the kernel partition and then mapping the
block to that point. For example, in the row with kernel the partition 12|3 there is an idempotent
that maps the block 12 to 1 and the block 3 to 3; this map has image the set {1, 3}. There is also
an idempotent mapping the block 12 to 2 and 3 to 3, and this map has image {2, 3}.
There are thus several idempotents in the same row, hence several maximal subgroups, con-
trasting with the picture for In. These maximal subgroups consist of all the bijections from k
blocks of a partition to k elements of an image, hence each is a copy of the symmetric group S k.
48 VICTORIA GOULD (SUPPLEMENTED BY BRENT)
(a). (b). (c).
Figure 18. (a). Strategic picture of T3. (b). a D-class in T5. (c). the correspond-
ingD-class in I5.
A generic D-class in Tn has rows labelled by the partitions of {1, 2, . . . , n} into k blocks and
columns labelled by subsets of size k. The number of partitions of {1, 2, . . . , n} into k blocks is
called a Stirling number of the second kind:{
n
k
}
=
1
k!
k∑
i=0
(−1)i
(
k
i
)
(k − i)n
so that theD-class is a
{
n
k
}
×
(
n
k
)
grid. These are generally not very square.
The D-classes in In are square grids of H-classes with the maximal subgroups strung along
the diagonal. TheD-classes in Tn are not square and with multiple groupH-classes in each row
and column. Figure 18 (b) and (c) show the D-classes in T5 and I5 corresponding to the maps
having image size 3.
7. Finite 0-simple semigroups
Just as the main building blocks of groups are simple groups, the main building blocks of
semigroups are simple and 0-simple semigroups. Recall that a semigroup with 0 is called 0-
simple iff {0} and S are the only ideals of S and S 2 , 0.
In general, the structure of 0-simple semigroups is very complicated. In the finite case their
structure is much more transparent – they can be described by a group and a matrix.
SEMIGROUP THEORY 2021/22 49
7.1. Rees Matrix Semigroups
Example 7.1. Here is a motivating example. Consider the symmetric inverse monoid In and the
subset:
I≤1n := {s ∈ In : |im s| = | dom s| ≤ 1}
In our running example pictures, I≤1n consists of the bottom two D-classes: the D-class of maps
with domain and image of size 1, and the D-class of maps with domain and image of size 0
(which contains the single element 0 : ∅ → ∅). By Theorem 7.4 and Lemma 7.8 later in this
section, I≤1n is a 0-simple monoid.
The non-zero elements of I≤1n are thus maps
{i} a−→ {λ}
where i, λ ∈ [n]. We will just write i a−→ λ. The composition is given by:
(†) (i a−→ λ) · (k b−→ µ) =
0 if λ , k,i ab−→ µ if λ = k.
The λ equal/not equal to k condition can be encoded in an n × n matrix P with entries:
Pλk =
0 if λ , k,1 if λ = k.
so that the composition (†) then becomes:
(i
a−→ λ) · (k b−→ µ) =
0 if pλk = 0,i apλkb−→ µ if pλk , 0.
Construction: Let G be a group, let I,Λ be non-empty sets and let P be a Λ × I matrix with
entries from G ∪ {0} such that every row and every column of P contains at least one non-zero
entry.
LetM0 =M0(G; I,Λ; P) be the set
I ×G × Λ ∪ {0}
with binary operation given by 0n = 0 = n0 for all n ∈ M0 and
(i, a, λ)(k, b, µ) =
0 if pλk = 0,(i, apλkb, µ) if pλk , 0.
Check thatM0(G; I,Λ; P) is a semigroup with zero 0.
Definition 7.2. M0 =M0(G; I,Λ; P) is called a Rees matrix semigroup over G.
Proposition 7.3 (Rees matrix facts). LetM0 =M0(G; I,Λ; P) be a Rees matrix semigroup over
a group G.
(1) (i, a, λ) is idempotent⇔ pλi , 0 and a = p−1λi .
(2) (i, a, λ) R (k, b, µ)⇔ i = k.
(3) (i, a, λ) L (k, b, µ)⇔ λ = µ.
50 VICTORIA GOULD (SUPPLEMENTED BY BRENT)
Figure 19
(4) (i, a, λ) H (k, b, µ)⇔ i = k and λ = µ.
(5) TheD = J-classes are {0} andM0 \ {0}.
(6) M0 is 0-simple.
(7) The so-called rectangular property:
xy D x⇔ xy R x
xy D y⇔ xy L y
}
for all x, y ∈ M0
The structure of a Rees matric semigroup is thus as shown in Figure 19.
Proof. (1) We have that
(i, a, λ) ∈ E(M0)⇔ (i, a, λ) = (i, a, λ)(i, a, λ),
⇔ pλi , 0 and (i, a, λ) = (i, apλia, λ),
⇔ pλi , 0 and a = apλia,
⇔ pλi , 0 and pλi = a−1.
(2) {0} is an R-class. If (i, a, λ) R (k, b, µ) then there exists ( j, c, ν) ∈ M0 with
(i, a, λ) = (k, b, µ)( j, c, ν) = (k, bpµ jc, ν)
and so i = k. Conversely, if i = k, pick j with pµ j , 0. Then
(i, a, λ) = (i, b, µ)( j, p−1µ j b
−1a, λ)
and together with the dual we have (i, a, λ) R (k, b, µ).
SEMIGROUP THEORY 2021/22 51
(3) Dual.
(4) This follows from (3) and (4).
(5) {0} is aD-class and a J-class. If (i, a, λ), (k, b, µ) ∈ M0 then
(i, a, λ) R (i, a, µ) L (k, b, µ)
so (i, a, λ) D (k, b, µ) and so (i, a, λ) J (k, b, µ). Therefore {0} andM0 \ {0} are the only
D-classes and J-classes, henceD = J .
(6) We have already shown that the onlyJ-classes are {0} andM0 \{0}. Let I , 0 be an ideal
and 0 , a ∈ I. Then 0a = 0 ∈ I. Let 0 , s ∈ M0. Then s ∈ M0sM0 = M0aM0 ⊆ I,
henceM0 ⊆ I and I =M0. Let i ∈ I, then there exists λ ∈ Λ with pλi , 0 so (i, 1, λ)2 , 0.
Therefore (M0)2 , 0 and soM0 is 0-simple.
(7) If xy R x, then clearly xy D x, because R ⊆ D. For the other direction, suppose that
xy D x. Notice that the two D-classes are {0} and everything else. If xy = 0, then
necessarily x = 0, because D0 = {0} and so xyR x as 0R 0. If xy , 0, then necessarily
x, y , 0 (as otherwise 0y = x0 = 0), so we have that
x = (i, a, λ) y = (k, b, µ).
Then xy = (i, apλkb, µ), so xy R x. The result for L is dual.
Some more facts!
(8) Put Hiλ =
{
(i, a, λ) | a ∈ G}. By (4) we have Hiλ is an H-class. If pλi , 0 we know
(i, p−1λi , λ) is an idempotent and so Hiλ is a group, by the Maximal Subgroup Theorem.
The identity is (i, p−1λi , λ) and (i, a, λ)
−1 = (i, p−1λi a
−1 p−1λi , λ).
(9) If pλi , 0 and pµk , 0 then Hiλ and Hkµ are in bijective correspondence. It is clear that
(i, a, λ) 7→ (k, a, µ) is a bijection, but this is not in general a morphism. Exercise: find a
morphism!
7.2. Finite semigroups
Theorem 7.4 (TheD = J Theorem). Suppose S is a semigroup such that:
(?)
for all a ∈ S , there exists n ∈ N with an L an+1,for all a ∈ S , there exists m ∈ N with am R am+1.
ThenD = J .
Example 7.5. (1) If S is a band (i.e. a semigroup of idempotents) then a = a2 for all a ∈ S
and so (?) holds.
(2) Let S be a finite semigroup.Then the sequence of left ideals:
S 1a ⊇ S 1a2 ⊇ S 1a3 ⊇ . . . .
must stabilize, so there exists n ∈ N such that S 1an = S 1an+1, which means that an L an+1.
Similarly, am R am+1 for every a.
52 VICTORIA GOULD (SUPPLEMENTED BY BRENT)
Proof. We knowD ⊆ J . Let a, b ∈ S with a J b. Then there exists x, y, u, v ∈ S 1 with
b = xay, a = ubv.
Then
b = xay = x(ubv)y = (xu)b(vy) = (xu)2b(vy)2 = · · · = (xu)nb(vy)n = · · ·
for all n ∈ N. By (?), there exists n with (xu)n L (xu)n+1. Therefore
b = (xu)nb(vy)n L (xu)n+1b(vy)n = xu((xu)nb(vy)n) = xub.
with the L-relation because L is a right congruence. Therefore b L xub, so
S 1b = S 1xub ⊆ S 1ub ⊆ S 1b.
So S 1b = S 1ub, which means that b L ub. Dually, b R bv. Therefore a = ubv R ub L b with the
R-relation because it is a left congruence. So a D b and J ⊆ D. Consequently,D = J .
As a consequence:
Corollary 7.6. If S is a finite semigroup thenD = J .
In the same vein we have:
Lemma 7.7 (The Rectangular Property). Let S satisfy (?). Then for all a, b ∈ S we have
(i) a J ab⇔ a D ab⇔ a R ab,
(ii) b J ab⇔ b D ab⇔ b L ab.
Proof. We prove (i) with (ii) being dual. Now,
a J ab⇔ a D ab
asD = J . Clearly if a R ab then a D ab; as R ⊆ D.
Conversely, If a J ab then there exists x, y ∈ S 1 with
a = xaby = xa(by) = x2a(by)2 = · · · = xna(by)n = · · ·
for all n. Pick n with (by)n R (by)n+1. Then
a = xna(by)n R xna(by)n+1 = xna(by)nby = aby.
(R is a left congruence) Now
aS 1 = abyS 1 ⊆ abS 1 ⊆ aS 1.
Hence aS 1 = abS 1 and a R ab.
SEMIGROUP THEORY 2021/22 53
7.3. Finite 0-simple semigroups
Let S have a 0. Recall that S is 0-simple if and only if 0 and S are the only ideals and S 2 , 0.
Lemma 7.8 (0-Simple Lemma). Let S have a 0 and S 2 , 0. Then the following are equivalent:
(i) S is 0-simple,
(ii) S aS = S for all a ∈ S \ {0},
(iii) S 1aS 1 = S for all a ∈ S \ {0},
(iv) the J-classes are {0} and S \ {0}.
Proof. (i)⇔ (iii)⇔ (iv) is a standard exercise.
(ii)⇒ (iii): Let a ∈ S \ {0}. Then
S = S aS ⊆ S 1aS 1 ⊆ S
and therefore S = S 1aS 1.
(i)⇒ (ii): Since S 2 , 0 and S 2 is an ideal, then S 2 = S . Therefore
S 3 = S S 2 = S 2 = S , 0.
Let I = {x ∈ S | S xS = 0}. Clearly 0 ∈ I and hence I , ∅. If x ∈ I and s ∈ S , then
S xsS ⊆ S xS = 0.
Therefore S xsS = 0 and so xs ∈ I. Dually sx ∈ I; therefore I is an ideal. If I = S , then
S 3 = S IS ,
=
⋃
x∈I
S xS ,
= 0.
This is a contradiction, therefore I , S . Hence I = 0. Let a ∈ S \ {0}. Then S aS is an ideal and
as a < I we have S aS , 0. Hence S aS = S .
Corollary 7.9. Let S be finite and 0-simple. Then S contains a non-zero idempotent.
Example 7.10. We showed in Section 2 that if a ∈ S then the monogenic subsemigroup 〈a〉
contains an idempotent if 〈a〉 is finite. In particular, a finite semigroup contains an idempotent.
In the Corollary above, we want the idempotent to be non-zero, and even if a , 0, it may still
be the case that the idempotent in 〈a〉 is equal to 0. For example, take the semigroup M2(F2) of
2 × 2 matrices over the finite field F2 and where the operation is matrix multiplication. Then
A =
(
0 1
0 0
)
is a non-zero matrix with A2 = 0 (a matrix A with An = 0 for some n is called nilpotent). Thus
A2 = A3 are the first powers that give the same element and A has index 2 and period 1 with the
idempotent in 〈A〉 the zero matrix.
The example above is by way of saying that Corollary 7.9 requires a separate proof:
54 VICTORIA GOULD (SUPPLEMENTED BY BRENT)
Proof. Let a ∈ S \ {0}. Then S aS = S , therefore there exists a u, v ∈ S with a = uav. So,
a = uav = u2av2 = · · · = unavn = · · ·
for all n. Hence un , 0 for all n ∈ N. Pick n,m with un R un+1, um L um+1. Notice
un+1 R un+2
as R is a left congruence. Similarly,
un+2 R un+3
and we deduce that un R un+t for all t > 0. Similarly um L um+t for all t > 0. Let s = max{m, n}.
Then us R u2s, us L u2s so us H u2s = (us)2. Hence by the corollary to Green’s theorem, us
lies in a subgroup. Therefore us H e for some idempotent e. As us , 0 and H0 = {0}, we have
e , 0.
Theorem 7.11 (Rees’ Theorem – 1940). Let S be a finite semigroup with zero. Then S is 0-simple
if and only if S is isomorphic to a Rees matrix semigroupM0(G; I,Λ; P) where G, I,Λ (and then
necessarily P) are finite.
(Actually, this theorem is normally stated more generally: for the completely 0-simple semi-
groups, that includes all the finite semigroups as examples.)
Proof. If S M0(G; I; Λ; P) where G, I,Λ are finite, then |S | = |I||G||Λ| + 1 < ∞ is finite and S
is 0-simple by the Rees matrix semigroup facts above.
Conversely, suppose that S is finite and 0-simple. Then D = J , and as S is 0-simple, the
D = J-classes are {0} and S \ {0}. Let D = S \ {0}. By Corollary 7.9, D contains an idempotent
e = e2.
Let {Ri | i ∈ I} be the set of R-classes in D (so I indexes the non-zero R-classes) and let
{Lλ | λ ∈ Λ} be the set of L-classes in D (so Λ indexes the non-zero L-classes).
Denote theH-class Ri ∩ Lλ by Hiλ. Since D contains an idempotent e, theD-class D contains
the subgroup He (Maximum Subgroup Theorem or Green’s Theorem). Without loss of generality
we can assume that both I and Λ contain a special symbol 1, and we can also assume that e ∈ H11.
Put G = H11, which is a group.
For each λ ∈ Λ choose and fix an arbitrary qλ ∈ H1λ (with q1 = e). Similarly, for each i ∈ I let
ri ∈ Hi1 (with r1 = e). See Figure 20.
Now,
e = e2, e R qλ ⇒ eqλ = qλ
as the idempotent e is a left identity for its R-class. Thus, by Green’s Lemma,
ρqλ : He = G → H1λ
is a bijection. Also,
e = e2, e L ri ⇒ rie = ri.
as the idempotent e is a right identity for its L-class. By the dual of Green’s Lemma
λri : H1λ → Hiλ
is a bijection. Therefore for any i ∈ I, λ ∈ Λ we have
ρqλλri : G → Hiλ
SEMIGROUP THEORY 2021/22 55
Figure 20
is a bijection. Thus, by the definition of ρqλ and λri , we have that
aρqλλri = riaqλ
for every a ∈ G, i ∈ I and λ ∈ Λ, and so, each element of Hiλ has a unique expression as riaqλ
where a ∈ G. Hence the mapping
θ : (I ×G × Λ) ∪ {0} → S
given by 0θ = 0, (i, a, λ)θ = riaqλ is a bijection. See Figure 21.
Put pλi = qλri. If pλi , 0 then qλri D qλ D ri. By the rectangular property
e R qλ R qλri L ri L e
so that qλri isH-related to e and qλri ∈ G.
The result is that P = (pλi) = (qλri) is a Λ× I matrix over G∪{0}. For any i ∈ I, by the 0-simple
Lemma (Lemma 7.8), we have S riS = S . So, uriv , 0 for some u, v ∈ S . Write u = rkbqµ for
some k, µ and b. Then
pµi = qµri , 0
as rkbqµriv , 0. Therefore every column of P has a non-zero entry. Dually for rows. Therefore
M0 =M0(G; I; Λ; P)
56 VICTORIA GOULD (SUPPLEMENTED BY BRENT)
Figure 21
is a Rees Matrix Semigroup over a group G. For any x ∈ M0 (x = 0 or x is a triple) then
(0x)θ = 0θ = 0 = 0(xθ) = 0θ · xθ.
Also, (x0)θ = xθ · 0θ. For (i, a, λ), (k, b, µ) ∈ M0 we have(
(i, a, λ)(k, b, µ)
)
θ =
0θ if pλk = 0,(i, apλkb, µ)θ if pλk , 0,
=
0 if pλk = 0,riapλkbqµ if pλk , 0,
= riapλkbqµ,
= riaqλrkbqµ,
= (i, a, λ)θ(k, b, µ)θ.
Therefore θ is a morphism, and since it is bijective, it is an isomorphism.