2_hollings.dvi EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 2, No. 1, 2009, (21-57) ISSN 1307-5543 – www.ejpam.com From right PP monoids to restriction semigroups: a survey Christopher Hollings∗ Centro de Álgebra da Universidade de Lisboa Av. Prof. Gama Pinto 2 1649-003 Lisboa Portugal Abstract. Left restriction semigroups are a class of semigroups which generalise inverse semigroups and which emerge very naturally from the study of partial transformations of a set. Consequently, they have arisen in a variety of different contexts, under a range of names. One of the various guises under which left restriction semigroups have appeared is that of weakly left E-ample semigroups, as studied by Fountain, Gomes, Gould and Lawson, amongst others. In the present article, we will survey the historical development of the study of left restriction semigroups, from the ‘weakly left E-ample’ perspective, and sketch out the basic aspects of their theory. AMS subject classifications: 01 A 60, 20-03, 20 M 20. Key words: right PP monoid, left ample semigroup, weakly left E-ample semigroup, restriction semi- group, partial transformation. Introduction In the mid-twentieth century, the study of systems of partial one-one mappings (partial bijections) of a set yielded the abstract notion of an inverse semigroup, as introduced (inde- pendently) by Wagner [78, 79] and Preston [60–62]. Let X be a nonempty set and let IX ∗Corresponding author. Email address: dh500� ii.f .ul.pt http://www.ejpam.com 21 c© 2009 EJPAM All rights reserved. C. Hollings / Eur. J. Pure Appl. Math, 2 (2009), (21-57) 22 denote the collection of all partial bijections of X . Then IX forms a monoid, termed a sym- metric inverse monoid, under the following composition (performed from left to right†): for α,β ∈ IX , domαβ = (imα∩ domβ)α−1 (∗) where α−1 denotes the preimage under α, and, for x in this domain, x(αβ) = (xα)β . It is clear that any partial bijection α is invertible on its image, with inverse α−1 : imα→ domα. Any inverse semigroup may be regarded as a subsemigroup of some IX that is closed under the unary operation −1. There are a number of different approaches to the study of inverse semigroups, and these may be embodied in a sequence of structure theorems (for example, Theorems 1.12, 1.13, 1.17 and 1.19). More generally, we can study systems of arbitrary partial transformations of a set, not just the injective ones. At least initially, the study of such systems was guided by analogy with the above case of partial bijections. It was discovered that if we are to obtain satisfactory analogues of various results for inverse semigroups, then we must consider so-called left re- striction semigroups. If we denote by P T X the partial transformation monoid of a set X , i.e., the collection of all partial transformations of X , under the (left-to-right) composition (∗), then a left restriction semigroup may be characterised as a subsemigroup of some P T X that is closed under the unary operation α 7→ Idomα, where Idomα denotes the identity mapping on the domain of α. On the other hand, let P T ∗X denote the dual partial transformation monoid of X : the collection of all partial transformations of X , composed from right to left. A right re- striction semigroup is a subsemigroup of some P T ∗X that is closed under the unary operation α 7→ Idomα. A semigroup that is both a left and a right restriction semigroup, with respect to the same semilattice (see Section 3), is called a two-sided restriction semigroup. So natural is the notion of a left restriction semigroup that it has appeared in a variety of different contexts, under a range of different names, to wit: (1973) in the work of Trokhimenko [76], as a special case of the Menger function systems studied †We sound a note of caution: the convention in this article will be to compose functions from left to right. However, we will also have occasion to make brief comments on right-to-left composition. C. Hollings / Eur. J. Pure Appl. Math, 2 (2009), (21-57) 23 by Schweizer and Sklar [66–69], which arose from attempts to axiomatise semigroups with additional operations embedded in some P T X (see [40,64]); (1981) as the type SL2 γ-semigroups of Batbedat [2, 3], which arose as a generalisation of in- verse semigroups whereby the unary operation x 7→ x x−1 was formally replaced by a function γ : S→ E(S); (1991) as the idempotent-connected Ehresmann semigroups of Lawson [47], who was draw- ing connections between semigroup theory and the category-theoretic work of Ehres- mann [14], with the goal of applying techniques from category theory to semigroup theory; (2001) as the twisted LC-semigroups of Jackson and Stokes [39], which arose from considera- tions of closure operators; (2006) as the guarded semigroups of Manes [51], which arose via theoretical computer science from the restriction categories of Cockett and Lack [6]. The term restriction semigroup, inspired by the nomenclature of Cockett and Lack for cate- gories, is a recent attempt to streamline and harmonise the terminology, and was first used in [7]. The idempotent-connected Ehresmann semigroups of Lawson [47] are in fact two-sided restriction semigroups and generalise the ample semigroups of Fountain [22, 24]. For this reason, they were subsequently known as weakly E-ample semigroups; the ‘E ’ reflects the fact that these semigroups may be defined in terms of a distinguished subsemilattice E ⊆ E(S), whereas ample semigroups are defined with respect to the whole of E(S). In the one-sided case, weakly left/right E-ample semigroups are simply left/right restriction semigroups; these have been studied by Gomes, Gould, and others of the ‘York-inspired’ school. In the present article, we will survey the development of restriction semigroups from the ‘York’ perspective. We will begin with notions from the homological classification of monoids, such as that of a right PP monoid, which led to the initial definition of a left ample semigroup, before mov- ing through successive generalisations to arrive at weakly left E-ample semigroups, i.e., left C. Hollings / Eur. J. Pure Appl. Math, 2 (2009), (21-57) 24 restriction semigroups. The structure of the article is as follows. We begin with an historical survey of the develop- ment of these semigroups; since this survey is quite lengthy, we break it down into two parts: Section 1 deals with left ample semigroups, via right PP monoids, whilst Section 2 completes the story by describing the work leading to the eventual definition of weakly left E-ample semigroups. Sections 3–5 collate the work of a number of authors, but of El-Qallali [15], Fountain [22, 24] and Lawson [43, 47] in particular. Much of this material is ‘folklore’, in that it is difficult to determine where and when it first appeared in print; we have drawn heavily on the notes of Gould [30]. In Section 3, we expand upon the comments made at the beginning of this Introduction by defining restriction semigroups by means of partial trans- formations. We will focus our attention on left restriction semigroups; the right-hand version may be defined dually. In Section 4 we present the abstract definition of a weakly left E- ample semigroup and prove that this is in fact equivalent to the concrete description of a left restriction semigroup, as given in Section 3. We record some of the basic results in the theory of left restriction semigroups, before moving on to Section 5, where we consider the special case of left ample semigroups. Since the nomenclature which we will have occasion to wade through in Sections 1 and 2 can be somewhat torturous, we conclude the article by providing the reader with an appendix summarising this terminology. We note that left restriction semigroups form a variety of algebras of type (2,1) and can therefore be defined by a system of identities first presented in [39]; full left restriction (see Section 3) and left ample semigroups form quasi-varieties of type (2,1). However, this is not an approach we will take in the present article; we hope to do so in a future article, as well as drawing further connections with left restriction semigroups in their various other guises. For the present, we note that the equivalence of the classes of type SL2 γ-, weakly left E-ample, left LC-, and guarded semigroups is demonstrated in [35, §2.6]. In [32], the adjective ‘left’ is dropped and left restriction semigroups are termed simply ‘restriction semigroups’, since these are the objects of interest in that paper; in [36], on the other hand, the term ‘restriction semigroup’ is used to refer to the two-sided case for similar reasons. In the present article, in the interests of clarity, we will only drop these qualifiers C. Hollings / Eur. J. Pure Appl. Math, 2 (2009), (21-57) 25 when making a statement which applies equally well to left, right and two-sided restriction semigroups. For later use, the uninitiated reader should bear in mind the definition of Green’s (equiva- lence) relation R in a semigroup S: two elements a, b ∈ S are R-related if they generate the same principal right ideal. Any idempotent is a left identity for its R-class. Green’s relation L may be defined as the left-right dual of R; the relation H is defined byH =R ∩L . Any other unexplained semigroup-theoretic terminology or notation may be found in [37]. 1. Historical development I: left ample semigroups We begin by giving a two-part historical survey of the origins of restriction semigroups, from the point of view of the ‘York’ school. In this section, we deal with left ample semigroups; weakly left E-ample semigroups follow in Section 2. The present section is based upon the similar introductory chapters of the D.Phil. theses of El-Qallali [15] and Lawson [43]. An- other invaluable source, both for this section and the next, was Ample and Left Ample Semi- groups [26], the extended abstract of a survey talk given by John Fountain in Calgary in June 2006. As indicated in the Introduction, the most natural way to introduce restriction semigroups is via the partial transformations of a set. Indeed, this is what we will do in Section 3. How- ever, our historical summary begins in a rather different place, with the homological classifica- tion of monoids. We first require the definitions of both S-acts and S-morphisms: Definition 1.1. [37, §8.1] Let S be a monoid. A set X is called a right S-act (or S-set or S-system) if S acts on X on the right, i.e., if there is a mapping X ×S→ X , written (x , s) 7→ x ·s and such that (x · s) · t = x · st, for all x ∈ X and s, t ∈ S, and x · 1 = x , for all x ∈ X . (Left S-acts are defined dually.) Let X and Y be two right S-acts. A function ϕ : X → Y is called an S-morphism if (x ·s)ϕ = xϕ · s, for all x ∈ X and s ∈ S. If S is a monoid, then any right ideal of S may be regarded as a right S-act, where the action in question is that by right multiplication. Similarly, any left ideal is a left S-act. C. Hollings / Eur. J. Pure Appl. Math, 2 (2009), (21-57) 26 Just as rings may be studied via their actions on modules [33], so too can monoids be studied via their S-acts, a study taken up in [71], for example. In the case of rings, two properties which prove useful are the categorically defined injectivity and projectivity (see [41, pp. 7, 10]). We define the ‘S-act’ versions of these properties, bearing in mind that in the category of S-acts and S-morphisms, S-epimorphisms are onto and S-monomorphisms are one-one: Definition 1.2. [21] Let S be a monoid and let X be an S-act. We say that X is injective if, for any S-acts Y and Z with Z ⊆ Y , any S-morphism ϕ : Z → X may be extended to an S-morphism ϕ′ : Y → X such that the following diagram commutes: Y Z i 6 ϕ - X ϕ′ - where i : Z → Y is inclusion. Definition 1.3. [22, p. 285] Let S be a monoid and let X be an S-act. We say that X is projective if, for any pair of S-acts Y and Z , any S-epimorphism ψ : Y → Z and any S- morphism ϕ : X → Z , there exists an S-morphism π : X → Y such that the following diagram commutes: Y Z ψ ? � ϕ X π � A monoid for which every right S-act is injective is called a completely right injective monoid. If, in addition, every left S-act is injective, then the monoid is said to be completely in- jective. The study of such monoids was initiated by Feller and Gantos [18–20], who obtained characterisations of those completely injective monoids which are unions of groups, inverse semigroups, or both. A description for the general case was obtained by Fountain [21]. Fur- C. Hollings / Eur. J. Pure Appl. Math, 2 (2009), (21-57) 27 ther necessary and sufficient conditions for a monoid to be completely right injective were obtained by Shoji [70]. The study of monoids whose every S-act is projective, on the other hand, is far less fruit- ful; Isbell [38] showed that the only such monoid is trivial. If one is to study monoids with projective S-acts, then one must relax the conditions somewhat. For example, one can con- sider monoids in which all right ideals (regarded as right S-acts) are required to be projective; these monoids are termed right hereditary monoids and were studied by Dorofeeva [10]. If we relax the conditions even further and consider those monoids for which only the principal right ideals are projective as right S-acts, then we obtain so-called right principally projective (or right PP) monoids. Left PP monoids are defined dually; a monoid which is both right and left PP is called simply PP. Any regular monoid is necessarily PP, as we will see shortly. The study of PP monoids was intiated by Kilp in [42], where the commutative case was considered; Kilp obtained a characterisation of commutative PP monoids as strong semilat- tices‡ of commutative cancellative monoids. This result was generalised to the case of right PP monoids with central idempotents by Fountain [23]; such a monoid is exactly a strong semilattice of left cancellative monoids. A left cancellative monoid is therefore right PP. It is in fact possible to give a characterisation of right PP monoids which makes no refer- ence to S-acts. For this, we need a notion introduced by Skornjakov [71] and Dorofeeva [10]: Definition 1.4. Let S be a monoid and let e ∈ E(S). An element a ∈ S is said to be left e-cancellable if e is a right identity for a and ax = a y =⇒ ex = e y, for all x , y ∈ S. Then, from [42], we have: Proposition 1.5. A monoid S is right PP if, and only if, for each element a ∈ S, there is an ea ∈ E(S) such that a is left ea-cancellable. ‡For the notion of a semilattice of semigroups, see [5, §1.8]. C. Hollings / Eur. J. Pure Appl. Math, 2 (2009), (21-57) 28 The notion of left e-cancellability, and hence the definition of a right PP monoid, were recast once more by Fountain [22]. Before we describe this important development, however, let us take a step back and consider a definition of Lyapin [50]: Definition 1.6. [50, Chapter X, §4.2] Let S be a semigroup. A potential property in S is a property which holds in some oversemigroup T of S. For example, in [50], Lyapin considered potential invertibility of elements in semigroups. A range of other potential properties were studied by Šutov in [72–75]. In particular, Šutov investigated the notion of potential divisibility of elements [73]: elements a, b of a semigroup S potentially divide each other (on the right) if, and only if, there exist an oversemigroup T of S and elements s, t ∈ T such that as = b and bt = a in T . In other words, a and b potentially divide eachother if, and only if, they are R-related in some oversemigroup. Dually for potential left division. The notion of potential divisibility arose again in work of both Pastijn [59] and McAlis- ter [54], though not under that name. In [54], McAlister arrived at the following definition of a potential property via the study of partial right translations: Definition 1.7. [54, Definition 1.6] Let S be a semigroup and let a, b ∈ S. We define the equivalence relation R∗ on S by saying that aR∗ b if, and only if, a and b are R-related in some oversemigroup T of S. Through a generalisation of a construction of Schützenberger, Pastijn arrived at the defi- nition of the dual relation L ∗ [59, p. 239].§ The relations R∗ and L ∗ may be regarded as generalisations of Green’s relations R and L ; it is clear that R ⊆R∗ and L ⊆L ∗. We note that the formulation of R∗ which will appear later as our equation (5.1), namely, aR∗ b⇐⇒∀x , y ∈ S1[xa = ya⇔ x b = y b], (1.1) is implicit both in [8] and in [50, Chapter X, §1.6]. Returning to right PP monoids, we first have the following, from [22]: §Pastijn denoted L ∗ by fL — this should not to be confused with the fL of the subsequent theory of weakly right ample semigroups! C. Hollings / Eur. J. Pure Appl. Math, 2 (2009), (21-57) 29 Lemma 1.8. [22, p. 286] Let S be a semigroup and let a, b ∈ S. Then aL ∗ b if, and only if, there is an e ∈ E(S) such that a and b are both left e-cancellable. Consequently: Proposition 1.9. [22, p. 286] A monoid S is right PP if, and only if, every element isL ∗-related to an idempotent. One thing which is immediately apparent from this characterisation of right PP monoids (and, indeed, from that in Proposition 1.5) is the fact that the presence of an identity is no longer required. We can therefore define right PP semigroups. Notice also that there is no longer any reference to S-acts or projectivity. For this reason, right PP semigroups were renamed right abundant semigroups, since “such a semigroup has a plentiful supply of idempotents” [25, p. 103]. Similarly, left PP semigroups (in which every element is R∗- related to an idempotent) became left abundant semigroups; a semigroup which is both left and right abundant is called simply abundant. Such semigroups were studied extensively in [15] and [25]. We have already commented that every regular semigroup is abundant. To see this, we recall that R ⊆ R∗ and L ⊆ L ∗, and note the following characterisation of a regular semi- group: Proposition 1.10. [37, Proposition 2.3.2] A semigroup S is regular if, and only if: (i) every R-class contains an idempotent; (ii) every L -class contains an idempotent. We see then that every R∗-class and every L ∗-class of a regular semigroup S contains an idempotent; S is therefore abundant. Indeed, in a regular semigroup, we have R∗ = R and L ∗ =L ; we will provide a proof of this in Section 4 (Lemmas 4.1 and 4.14). We now recall the definition of a Clifford semigroup [37, §4.2] as a regular semigroup with central idempotents. We recall also the following result, originally due to Clifford [4], and presented in [37, Theorem 4.2.1]: C. Hollings / Eur. J. Pure Appl. Math, 2 (2009), (21-57) 30 Theorem 1.11. A semigroup S is a Clifford semigroup if, and only if, it is a strong semilattice of groups. We see then that the result of Fountain [23] which states that every right abundant monoid with central idempotents is a strong semilattice of left cancellative monoids provides a one-sided analogue of this last theorem. Furthermore, in the two-sided case, abundant semigroups with central idempotents are strong semilattices of cancellative monoids; abun- dant semigroups with central idempotents may therefore be regarded as analogues of Clifford semigroups. More generally, abundant semigroups are analogous to regular semigroups. The validity of this analogy is demonstrated if we compare Proposition 1.9 with Proposition 1.10. The initial study of abundant semigroups was therefore guided by the existing results for regular semgroups. One important point to note at this stage is that for regular semigroups, each of conditions (i) and (ii) in Proposition 1.10 implies the other. The ‘starred’ versions of these conditions, however, are completely independent. This is why we have one-sided as well as two-sided analogues of regular semigroups. A left cancellative semigroup which is not right cancellative is an example of a right abundant semigroup which is not left abundant. Two special classes of regular semigroups which have seen extensive study are so-called or- thodox semigroups [37, §6.2], in which the idempotents form a subsemigroup, and, of course, inverse semigroups, in which the idempotents form a semilattice. This hints at two spe- cial classes of abundant semigroups whose study may be fruitful. Abundant semigroups in which the idempotents form a subsemigroup have been studied under the name of quasi- adequate semigroups [15–17], and a theory has been developed for these which mirrors that of Hall [34] for orthodox semigroups. An abundant semigroup in which the idempotents form a subsemilattice is termed an adequate semigroup, “since it contains a sufficient supply of suitable idempotents” [24, p. 113]. Left adequate and right adequate semigroups are also easily defined. The study of right adequate semigroups was initiated in [22]; the two-sided case was considered in [24]. The early study of (left/right) adequate semigroups was guided by the analogy with in- verse semigroups. In [22], Fountain (who, at this stage, was still working in the monoid case) sought an analogue for right adequate semigroups of two results of McAlister [52, 53] for C. Hollings / Eur. J. Pure Appl. Math, 2 (2009), (21-57) 31 inverse semigroups: Theorem 1.12 (McAlister’s Covering Theorem). [49, Theorem 2.2.4] Every inverse semigroup is the image of a proper inverse semigroup under an idempotent-separating morphism. Theorem 1.13 (McAlister’s P-Theorem). [49, Theorem 7.2.15] Every E-unitary inverse semi- group is isomorphic to a ‘P-semigroup’, constructed from a group, a poset and a semilattice. Fountain determined that if right adequate analogues are to be developed for these theo- rems, then we must restrict our attention to a particular subclass of right adequate monoids, which he termed right type A monoids. A right adequate monoid S is right type A if, and only if, eS ∩ aS = eaS, for a ∈ S and e ∈ E(S). (1.2) Similarly, a left adequate monoid S is left type A if, and only if, Se ∩ Sa = Sea, for a ∈ S and e ∈ E(S); (1.3) a monoid which is both left and right type A is called simply type A.¶ We note that every inverse semigroup is (left/right) type A (see Section 5). The terminology ‘type A’ was subsequently replaced by the term ‘ample’, as we will see. We have the following analogue of McAlister’s Covering Theorem: Theorem 1.14. [22, Theorem 3.3] Every right type A monoid is the image of a proper right type A monoid under an L ∗-morphism, where an L ∗-morphism is a morphism θ for which sθ = tθ =⇒ sL ∗ t. Recall that an inverse semigroup S is E-unitary if, and only if, it is proper [37, Proposi- tion 5.9.1]. However, after defining an appropriate notion of ‘proper’, Fountain observed that an E-unitary right type A monoid need not be proper in this sense — see [22, Example 3]. Fountain went on to construct a generalisation of McAlister’s P-semigroups, which he termed McAlister monoids. Using these, we have the following analogue of the P-Theorem: ¶In [22], Fountain used the term ‘type A’ to mean ‘right type A’. C. Hollings / Eur. J. Pure Appl. Math, 2 (2009), (21-57) 32 Theorem 1.15. [22, Theorem 4.3] Every proper right type A monoid is isomorphic to a McAl- ister monoid. These theorems are easily adapted to the semigroup case. Two-sided versions appear in [44] as Theorems 3.8 and 2.11, respectively. There are two other major approaches to the study of inverse semigroups: that which connects inverse semigroups with inductive groupoids, and that via the notion of a Munn semigroup. Each of these methods may be extended to the study of type A semigroups. We first consider the analogue of Munn’s work [57]. Definition 1.16. [37, p. 162] Let E be a semilattice. The Munn semigroup TE of E is the inverse subsemigroup of IE which consists of all isomorphisms between principal ideals of E. We note that E(TE) is isomorphic to E [37, Theorem 5.4.1]. Munn’s major result was the following: Theorem 1.17. [37, Theorem 5.4.4] For any inverse semigroup S, there is a morphism S → TE(S) which maps E(S) isomorphically onto E(TE(S)) and which induces the maximum idempotent- separating congruence on S. In [24], Fountain investigated the generalisation of this result to the case of adequate semigroups. He observed, however, that an adequate semigroup need not have a largest idempotent-separting congruence. It was therefore necessary to pursue the generalisation down a slightly different path. As determined by Munn [56], the maximum idempotent- separating congruence on an inverse semigroup is the largest congruence contained in Green’s relation H . Fountain therefore investigated the largest congruence contained in H ∗ = R∗ ∩ L ∗; any congruence contained in H ∗ is idempotent-separating, but the converse is not necessarily true. Moreover, it once again transpired that if one is to develop a suitable analogue of Theorem 1.17, then one must once again restrict one’s attention to type A semi- groups: Theorem 1.18. [24, Proposition 4.5] For any type A semigroup S, there is a morphism S → TE(S) which maps E(S) isomorphically onto E(TE(S)) and which induces the largest congruence contained inH ∗. C. Hollings / Eur. J. Pure Appl. Math, 2 (2009), (21-57) 33 As commented above, another major approach to the study of the structure of inverse semigroups is that via the notion of an inductive groupoid: a type of small, ordered category in which all arrows are invertible. Inverse semigroups and inductive groupoids are two solutions to the problem of finding an abstract version of the pseudogroups of Veblen and Whitehead [77, p. 38]. The inductive groupoid approach was pioneered by Ehresmann [11, 13], whilst inverse semigroups were introduced independently by Wagner and Preston, as we have seen. Thus, given that inverse semigroups and inductive groupoids share a common origin, it is not surprising that their respective theories can be connected in an extremely natural way. This linking of theories was pieced together by a number of authors [11, 12, 58, 63, 65] and is enshrined in the following result, named the Ehresmann-Schein-Nambooripad Theorem to reflect its disparate origins: Theorem 1.19. [49, Theorem 4.1.8] The category of inverse semigroups and ∨-premorphisms is isomorphic to the category of inductive groupoids and ordered functors; the category of inverse semigroups and morphisms is isomorphic to the category of inductive groupoids and inductive functors. (An ordered functor is simply an order-preserving functor; an inductive functor is a special type of ordered functor. A ∨-premorphism is a function θ : S→ T between inverse semigroups such that (st)θ ≤ (sθ)(tθ).) Further details on the Ehresmann-Schein-Nambooripad Theorem can be found in [49], for which book it provides the main focus. With this connection between inverse semigroups and inductive groupoids established, it was natural to seek generalisations. The regular case, for example, was considered by Nambooripad [58]. But what of the non-regular generalisations of inverse semigroups, such as type A semigroups? Furthermore, since a groupoid is a very specialised type of category, we might ask what type of semigroup may be associated with a more general category, or even with an arbitrary category. This question has indeed been answered, via a succession of generalisations of the Ehresmann-Schein-Nambooripad Theorem. We note here that since a category is an inherently ‘two-sided’ object (every object has a domain and a range), then it is C. Hollings / Eur. J. Pure Appl. Math, 2 (2009), (21-57) 34 two-sided type A semigroups which must be studied in this context. The first of the generalisations of Theorem 1.19 is due to Armstrong [1] and is rooted firmly in the work of Meakin [55]. Meakin had studied the structure of an inverse semi- group S by means of so-called ‘structure mappings’, that is, mappings betweenR-classes of S. Armstrong generalised this approach to the study of type A semigroups by considering map- pings betweenR∗- andL ∗-classes. In her Theorem 3.9, Armstrong extended the Ehresmann- Schein-Nambooripad Theorem to the case of type A semigroups and inductive cancellative categories: Theorem 1.20. [1] The category of type A semigroups and (2,1,1)-morphisms is isomorphic to the category of inductive cancellative categories and inductive functors. Note, however, that Armstrong did not give such a category-theoretic formulation. Since the definition of an inductive cancellative category is somewhat complicated, we will not go into further detail here; a summary appears in [35, Chapter 7]. In [24, p. 115], Fountain gave an alternative characterisation of (left/right) type A semi- groups; this is the definition which is most often used in current papers (and which will appear in Section 5). It should also be noted that type A semigroups are now known as am- ple semigroups, a term which was introduced in [31]; as interest in these semigroups grew, it was decided that they needed a more exciting name — the name ‘ample’ was chosen not only for its alliterational value, but also because such semigroups contain an ‘ample’ supply of idempotents. We will consider left ample semigroups in more detail in Section 5. 2. Historical development II: weakly left E-ample semigroups We continue our journey through the historical development of restriction semigroups by considering a generalisation of ample semigroups whose study (within the ‘York’ school) was initiated by El-Qallali [15]. El-Qallali began the final chapter of his thesis by recalling an alternative characterisation of L ∗ and R∗ which appears in [25] for abundant semigroups: Proposition 2.1. [25, Corollary 1.10] Let S be an abundant semigroup. Then, for any e ∈ E(S), C. Hollings / Eur. J. Pure Appl. Math, 2 (2009), (21-57) 35 aL ∗ e (aR∗ e) if, and only if, a ∈ Se (a ∈ eS) and Se (eS) is contained in every idempotent- generated left (right) ideal which contains a. Inspired by this last result, El-Qallali investigated a more general class of semigroups in which every element is contained in a minimum idempotent-generated left (right) ideal. Such semigroups are termed semiabundant semigroups. El-Qallali introduced equivalence relations fL and eR with L ∗ ⊆ fL and R∗ ⊆ eR , and demonstrated that a semigroup is semiabundant if, and only if, each element is both fL - and eR-related to an idempotent. It is therefore clear that any abundant semigroup is semiabundant. Left semiabundant semigroups are easily defined as semigroups in which every element is eR-related to an idempotent. Dually for right semiabundant semigroups. By analogy with abundant semigroups, El-Qallali [15] investigated semiabundant semi- groups in which the idempotents form a subsemigroup (Q-semigroups), and in which the idempotents form a subsemilattice (semiadequate semigroups). Pursuing the analogy further, El-Qallali realised that whilst L ∗ is always a right congruence andR∗ is always a left congru- ence, fL and eR need not be right and left congruences, respectively. Since these are particu- larly useful properties to have, El-Qallali restricted his attention to those Q- and semiadequate semigroups in which (CL) eR is a left congruence, and (CR) fL is a right congruence. In Chapter VIII of [15], a structure theory was obtained for Q-semigroups which mirrored that already obtained for quasi-adequate semigroups in Chapter V. Towards the end of the thesis, El-Qallali obtained structural results for so-called idempotent-connected semiadequate semigroups with (CL) and (CR), or type T semigroups, as he called them. The ‘idempotent- connected’ conditions are equivalent to the conditions (1.2) and (1.3) previously imposed on an adequate semigroup in order to make it type A. Thus type T semigroups generalise type A semigroups. El-Qallali proved an analogue of Theorem 1.18 for type T semigroups [15]. Given a left semiadequate semigroup, it is possible to define a left type T semigroup by im- posing an appropriate one-sided version of the idempotent-connected condition (equivalent C. Hollings / Eur. J. Pure Appl. Math, 2 (2009), (21-57) 36 to (1.3)), and by only insisting that (CL) hold. Dually for right type T semigroups. (Left/right) type T semigroups came to be known as weakly (left/right) ample semigroups, owing to their being a generalisation of ample semigroups. Weakly left ample analogues of McAlister’s Cov- ering and P-Theorems were developed in [27–29], whilst Lawson [43] obtained the following generalisation of Theorem 1.20: Theorem 2.2. [43] The category of weakly ample semigroups and (2,1,1)-morphisms is iso- morphic to the category of inductive unipotent categories and inductive functors. (A unipotent category is a category whose only idempotents are its identities.) Note that, just like Armstrong, Lawson did not formulate the above theorem in category- theoretic terms. In [47], Lawson began to follow up on the earlier work in his thesis [43] by drawing connections between the study of semiabundant semigroups and the category-theoretic work of Ehresmann [14]. The goal of this linking of theories was the application of techniques from category theory to semigroup theory; Lawson gave such an approach for inverse semi- groups in [45, 48]. A significant innovation introduced by Lawson was the realisation that the relations fL and eR need not be defined with respect to the whole set of idempotents of a semigroup. Recall that El-Qallali defined a semigroup to be semiabundant if every element is contained in a minimum idempotent-generated left (right) ideal; Lawson, inspired by some work of de Barros [9], extended this definition by insisting that every element be contained in a minimum left (right) ideal generated not by an arbitrary idempotent, but by an idempotent from some distinguished subset U ⊆ E(S). Such a semigroup was termed a U-semiabundant semigroup [47, p. 425]. These semigroups first appeared in [46], in which a certain special class of U-semiabundant semigroups, called Rees semigroups, provided an abstract model for Rees matrix semigroups over an arbitrary monoid. It is clear that a U-semiabundant semi- group with U = E(S) is semiabundant. Lawson wrote down new versions of the relations of fL and eR , which were defined in terms of U; we will denote these by fLU and eRU . Thus a semigroup is U-semiabundant if every element is both fLU - and eRU -related to an idempotent in U . As one might expect, given all the terminology thus far, U-semiabundant semigroups in C. Hollings / Eur. J. Pure Appl. Math, 2 (2009), (21-57) 37 which U forms a subsemilattice were called U-semiadequate [47, p. 434]. As has been observed, Lawson’s goal was to draw connections between particular classes of semigroups and small ordered categories. To this end, he defined an Ehresmann category to be a small category equipped with two partial order relations, satisfying certain conditions. He then showed that every such category gives rise to a particular type of semigroup, which was given the appropriate name of Ehresmann semigroup. Furthermore, he demonstrated the converse: that to every Ehresmann semigroup there is associated an Ehresmann category [47, §4]. Ehresmann semigroups are, in fact, precisely those U-semiadequate semigroups in which (CL) and (CR) hold. Lawson generalised the ‘morphisms’ part of Theorem 1.19 to give an isomorphism between the category of Ehresmann semigroups and certain morphisms, and the category of Ehresmann categories and certain functors. In the final section of [47], Lawson considered a number of special cases of Ehresmann semigroups. Amongst these were idempotent-connected Ehresmann semigroups; these, in fact, were none other than (two-sided) weakly E-ample semigroups, where we have exchanged Lawson’s ‘U ’ for the subsequently more usual ‘E ’. It is very easy to write down the one-sided definitions for weakly left E-ample (left restriction) and weakly right E-ample (right restriction) semigroups. Lawson specialised the above isomorphism of categories (for Ehresmann semi- groups) to this special case, thereby providing the following generalisation of Theorem 1.20, a ‘weakly E-ample’ version of the ‘morphisms’ part of Theorem 1.19:‖ Theorem 2.3. [47] The category of weakly E-ample semigroups and (2,1,1)-morphisms is isomorphic to the category of inductive categories and inductive functors. In [47, Example 3.21], Lawson presented a number of examples of the various classes of U-semiabundant semigroups. Amongst these appeared the example of the partial transforma- tion monoid P T X on a set X , which, as we have seen, is a left restriction semigroup. In fact, as we have also seen, any left restriction semigroup arises in an extremely natural way as a (2,1)-subalgebra of some P T X ; in the following section, we will introduce the specifics of the theory of left restriction semigroups via partial transformation monoids. ‖A ‘weakly E-ample’ generalisation of the ‘∨-premorphisms’ part can be found in [36]. C. Hollings / Eur. J. Pure Appl. Math, 2 (2009), (21-57) 38 3. Partial transformations Restriction semigroups arise very naturally from partial transformation monoids in much the same way that inverse semigroups arise from symmetric inverse monoids. We therefore begin by expanding upon our comments on partial transformations in the Introduction. A partial transformation of a set X is a function A→ B, where A, B ⊆ X . The collection of all partial transformations of X is denoted P T X . Under the (left-to-right) composition (∗) from the Introduction, P T X forms a monoid — the partial transformation monoid on X . The partial mapping with domain ;, called the empty transformation, is denoted by ǫ. It is clear that IX , the symmetric inverse monoid on X , is an inverse submonoid of P T X . The full transformation monoid TX is also a submonoid of P T X , since any mapping X → X qualifies as a ‘partial transformation’ of X . Amongst the elements of P T X , there are certain idempotents which will be vital to our definition of restriction semigroups. These are the idempotents of the form IZ , for Z ⊆ X , i.e., those idempotents which are identities on their domains. We will refer to such idempotents as partial identities. Let EX ⊆ E(P T X ) be the set of partial identities of P T X . We note that E(IX ) = EX . We stress, however, that, in general, P T X will have idempotents other than those in EX . For example, for any fixed element x ∈ X , the constant mapping cx : X → X which sends every element of X to x , is an idempotent of P T X which is not a partial identity. We consider the following unary operation on partial transformations: α 7→ Idomα. In P T X , we will denote this operation by +, whilst in P T ∗X , it will be denoted by ∗. Let S be a subsemigroup of P T X . We put S+ = {α+ : α ∈ S} ⊆ E(S). Definition 3.1. Let S be a subsemigroup of some P T X . If S is closed under +, i.e., if S+ ⊆ S, then we call S a left restriction semigroup with respect to S+. Now let T be a subsemigroup of some P T ∗X . We put T ∗ = {α∗ : α ∈ T} ⊆ E(T ). C. Hollings / Eur. J. Pure Appl. Math, 2 (2009), (21-57) 39 Definition 3.2. Let T be a subsemigroup of some P T ∗X . If T is closed under ∗, i.e., if T ∗ ⊆ T , then we call T a right restriction semigroup with respect to T ∗. Definition 3.3. Let S be a semigroup. If S is simultaneously isomorphic to a subsemigroup of some P T X that is closed under +, and to a subsemigroup of some P T ∗Y that is closed under ∗, and if, in addition, the (images of the) semilattices S+ and S∗ coincide, then we call S a two-sided restriction semigroup with respect to S+ = S∗. A semigroup S that forms a left/right/two-sided restriction semigroup with respect to the whole of E(S) will be termed a full left/right/two-sided restriction semigroup. It is clear that P T X is a left restriction semigroup. Furthermore, a left restriction semi- group may be regarded as a (2,1)-subalgebra of P T X . Observe that in any IX , + can be expressed as follows, for α ∈ IX : α+ = αα−1. (3.1) Therefore, the fact that IX is closed under composition and inverses ensures that it is closed under +. Furthermore, (IX ) + = EX . Thus, IX is a full left restriction semigroup. Moreover, by the Wagner-Preston Representation Theorem [49, Theorem 1.5.1], any inverse semigroup is a full left restriction semigroup. In the following section, we will prove this explicitly in an abstract setting. Note that IX is left-right dual and must therefore also be a full right restriction semigroup, hence a full two-sided restriction semigroup. In IX , the unary operation ∗ can be written as α∗ = α−1α. (3.2) By way of concluding this section, we note that a partial transformation monoid possesses an obvious partial order: α≤ β ⇐⇒ α = β |domα. (3.3) This partial order is natural, in the sense that it is compatible with composition and restricts to the usual partial order on EX . In TX , the ordering of (3.3) becomes trivial. Note also that when this ordering is applied in the inverse case, it yields, for example, the ordering in an inductive groupoid, as per Theorem 1.19. C. Hollings / Eur. J. Pure Appl. Math, 2 (2009), (21-57) 40 4. The abstract characterisation We have seen that restriction semigroups arise very naturally from partial transformation monoids; they also have a useful abstract characterisation. Harking back to the terminology we saw unfold in Section 2, we will introduce the abstract definition under the name weakly left E-ample semigroup and then prove that these are in fact precisely the left restriction semi- groups that we defined via partial transformations in the previous section. Note that we will focus our attention on the left-hand versions of these semigroups; the right-hand version is dual. Let S be a semigroup and let E ⊆ E(S) be a distinguished subset of idempotents of S. We define the relation eRE on S by the rule that a eRE b⇐⇒∀e ∈ E[ea = a⇔ eb = b], (4.1) for a, b ∈ S. Thus, two elements a, b are eRE -related if, and only if, they have the same left identities in E. It is easy to see that eRE is an equivalence relation. If E = E(S), then we denote eRE by eR . Note that eR ⊆ eRE , for any E. As indicated in Section 2, the relation eRE is a generalisation of Green’s relation R; we now prove that this is the case. We also take this opportunity to make the connection between eRE and the relation R∗ which we saw in Section 1 (as equation (1.1)) and will see again in the following section. Lemma 4.1. If S is a semigroup with subset E ⊆ E(S), then R ⊆R∗ ⊆ eR ⊆ eRE in S. Proof. Suppose that aR b in S1. Then there exist c, d ∈ S with a = bc and b = ad . For any x , y ∈ S1, it is clear that if xa = ya, then xad = yad , whence x b = y b. Similarly, the converse, hence aR∗ b. Now suppose that aR∗ b. We can set y = 1 and x = e in (1.1), for any e ∈ E(S), to obtain ea = a⇔ eb = b. Hence R∗ ⊆ eR. We observed above that eR ⊆ eRE . C. Hollings / Eur. J. Pure Appl. Math, 2 (2009), (21-57) 41 We note the following simpler condition for an element a ∈ S to be eRE-related to an idempotent e ∈ E: a eRE e⇐⇒ ea = a and ∀g ∈ E[ga = a⇒ ge = e]. (4.2) Harking back to the discussion of minimal idempotent-generated ideals in Section 2, we note that (4.2) tells us that a eRE e if, and only if, aS1 ⊆ eS1, where eS1 is the smallest principal right ideal to be generated by an idempotent from E and to contain aS1. Lemma 4.2. Let S be a semigroup with subset E ⊆ E(S). Then e eRE f if, and only if, eR f . Proof. Let e, f ∈ S and suppose that e eRE f . Then, by (4.2), e f = f and f e = e, hence eR f . The converse follows from Lemma 4.1. In the special case where E is a semilattice, we have the following easy consequence of Lemma 4.2: Lemma 4.3. Let S be a semigroup with subsemilattice E ⊆ E(S). Each element of S is eRE-related to at most one idempotent from E. Indeed, we are most interested in the case when E is a semilattice. We now give an abstract definition for a weakly left E-ample semigroup; we will ultimately prove that this is equivalent to a left restriction semigroup. Definition 4.4. A semigroup S with subsemilattice E ⊆ E(S) is called a weakly left E-ample semigroup if 1. every element a is eRE-related to an idempotent a+ ∈ E; 2. eRE is a left congruence; 3. for all a ∈ S and all e ∈ E, ae = (ae)+a. A weakly left E-ample monoid is defined analogously; in this instance, we require 1 ∈ E. C. Hollings / Eur. J. Pure Appl. Math, 2 (2009), (21-57) 42 Thus, in a weakly left E-ample semigroup, a eRE b if, and only if, a+ = b+. The idempotent a+ is well-defined, thanks to Lemma 4.3, and is a left identity for a. It is also clear that e+ = e and (a+)+ = a+, for any e ∈ E and any a ∈ S. A weakly left E-ample semigroup may be regarded (and, indeed, defined [32]) as an algebra of type (2,1). The identity in condition (3) of Definition 4.4 will be referred to throughout as the ‘left ample identity’. This identity is equivalent to the ‘idempotent connected’ condition of (1.3). With regard to the last part of Definition 4.4, we note that if S is a weakly left E-ample semigroup and we adjoin an identity 1 to S, then S1 is a weakly left E1-ample monoid. A semigroup S which is weakly left E-ample for E = E(S) is called simply a weakly left ample semigroup; in this instance, Definition 4.4 can of course be rewritten in terms of eR . Once we have completed the proof that weakly left E-ample semigroups are precisely left restriction semigroups, we will see as an easy corollary that weakly left ample semigroups are precisely full left restriction semigroups. Our first step towards proving that Definitions 3.1 and 4.4 are equivalent is the following: Proposition 4.5. A partial transformation monoid P T X is weakly left EX -ample. We first note the following lemma: Lemma 4.6. For α,β ∈ P T X , α eREX β ⇐⇒ domα = domβ . (4.3) Proof. From (4.1), we have α eREX β ⇐⇒∀IY ∈ EX [IYα= α⇔ IYβ = β]. We observe that dom IYα= Y ∩ domα, so that α eREX β ⇐⇒∀Y ⊆ X [domα⊆ Y ⇔ domβ ⊆ Y ]. The result now follows. We can now proceed with the following proof: C. Hollings / Eur. J. Pure Appl. Math, 2 (2009), (21-57) 43 Proof. [Proof of Proposition 4.5] Let α ∈ P T X . It follows immediately from Lemma 4.6 that α eREX Idomα. By Lemma 4.3, Idomα is the only idempotent in EX to which α is eREX -related. The ‘weakly left E-ample’ + of Defintion 4.4 therefore coincides with the ‘left restriction’ + of Definition 3.1. Now suppose that α eREX β , i.e., domα = domβ , and let γ ∈ P T X . We will show that γα eREX γβ by using (4.3). We have domγα= (imγ∩ domα)γ−1 = (imγ∩ domβ)γ−1 = domγβ . Thus eREX is a left congruence. It only remains to verify that the left ample identity holds. Let α ∈ P T X and IA ∈ EX . Then domαIA = (imα∩ dom IA)α −1 = (imα∩ A)α−1 ⊆ domα. Note also that im(αIA) + = dom(αIA) + = domαIA. We have dom(αIA) +α = � im(αIA) + ∩ domα �� (αIA) + �−1 = domαIA∩ domα= domαIA, as required. For any x in this domain: x(αIA) +α = xα= xαIA. It is clear that the details of the proof of Proposition 4.5 apply equally well to any sub- semigroup of P T X that is closed under +, i.e., to any left restriction semigroup. Corollary 4.7. Let S be a left restriction semigroup with respect to a subsemilattice E ⊆ E(S). Then S is weakly left E-ample. It remains to show that a given weakly left E-ample semigroup S is a left restriction semi- group with respect to E. Before we do so, however, we first record some additional properties of weakly left E-ample semigroups, including the following useful characterisation of condi- tion (2) of Definition 4.4: Lemma 4.8. Let S be a semigroup in which every element a is eRE-related to an idempotent a+ ∈ E, for some subsemilattice E ⊆ E(S). Then eRE is a left congruence if, and only if, (st)+ = (st+)+, for all s, t ∈ S. C. Hollings / Eur. J. Pure Appl. Math, 2 (2009), (21-57) 44 Proof. Suppose that eRE is a left congruence. It then follows immediately from t eRE t+ that st eRE st+, i.e., (st)+ = (st+)+. Conversely, suppose that (st)+ = (st+)+, for all s, t ∈ S. Then st eRE st+. For any u ∈ S with u eRE t, we have (st+)+ = (su+)+ = (su)+, hence st eRE st+ eRE su+ eRE su. Thus eRE is a left congruence. A weakly left E-ample semigroup possesses a (natural) partial order analogous to that in an inverse semigroup; this is, of course, an abstract version of the ordering of (3.3): a ≤ b⇐⇒ a = eb, (4.4) for some e ∈ E. Equivalently, a ≤ b⇐⇒ a = a+b. To see this equivalence, we start with a = eb and use Lemma 4.8 to obtain a+ = (eb)+ = (eb+)+ = eb+, so that a = eb = eb+b = a+b, as required. The converse is clear. The partial order in a weakly left E-ample semigroup is compatible with multiplication (thanks to the left ample identity) and, in E, restricts to the ‘usual’ ordering of idempotents: e ≤ f if, and only if, e = e f . Lemma 4.9. Let S be a weakly left E-ample semigroup with partial order ≤. If s ∈ S and e ∈ E, then se ≤ s. Proof. If we apply the left ample identity, then we have se = (se)+s ≤ s, by (4.4). We observed earlier that a+ is a left identity for a in a weakly left E-ample semigroup; we can now say a little more: Lemma 4.10. With respect to ≤, a+ is the least left identity for a. C. Hollings / Eur. J. Pure Appl. Math, 2 (2009), (21-57) 45 Proof. This follows from (4.2). Lemma 4.11. [24, Proposition 1.6] Let S be a weakly left E-ample semigroup with partial order ≤, and let s, t ∈ S. Then (st)+ ≤ s+. Proof. We make the easy observation that s+ is a left identity for st. The result then follows from Lemma 4.10. The following representation theorem, which first appeared in [76], completes the proof that left restriction and weakly left E-ample semigroups are indeed one and the same by providing a representation of a given weakly left E-ample semigroup as a (2,1)-subalgebra of a partial transformation monoid. We note that if we regard a weakly left E-ample semigroup as a subsemigroup of P T X , as per the following theorem, then Lemmas 4.9–4.11 follow easily from (3.3). Theorem 4.12. Let S be a weakly left E-ample semigroup, regarded as an algebra of type (2,1). Then the mapping φ : S→P T S given by dom sφ = Ss+ and x(sφ) = xs, ∀x ∈ dom sφ, is a representation of S as a (2,1)-subalgebra of P T S . Proof. We must show that φ is an injective (2,1)-morphism. Note that the ‘1’ part of ‘(2,1)- morphism’ indicates that φ should send the ‘weakly left E-ample’ + to the ‘left restriction’ +. We first show that φ respects + in this way. For s ∈ S, we have (sφ)+ = Idom sφ , so dom(sφ)+ = dom sφ = Ss+ = S(s+)+ = dom s+φ. Let x belong to this domain. Then x = ys+, for some y ∈ S, so x(s+φ) = xs+ = ys+s+ = ys+ = x = x(sφ)+. We now show that φ respects multiplication. Let s, t ∈ S. Then dom(sφ)(tφ) is the set of all those elements x ∈ dom sφ such that x(sφ) = xs ∈ dom tφ: dom(sφ)(tφ) = {x ∈ Ss+ : xs ∈ St+}. (4.5) C. Hollings / Eur. J. Pure Appl. Math, 2 (2009), (21-57) 46 Let x ∈ dom(sφ)(tφ). We deduce from (4.5) that xs+ = x ; (4.6) xst+ = xs. (4.7) Then x = xs+, by (4.6) = (xs+)+x , by the left ample identity = (xs)+x , by Lemma 4.8 = (xst+)+x , by (4.7) = (xst)+x , by Lemma 4.8 = (x(st)+)+x , by Lemma 4.8 = x(st)+, by the left ample identity. Hence x ∈ S(st)+ = dom(st)φ. Conversely, suppose that x ∈ dom(st)φ = S(st)+. Then x(st)+ = x , (4.8) so xs+ = x(st)+s+ = x(st)+, by Lemma 4.11 = x , in which case, x ∈ Ss+ = dom sφ. Next, x(sφ) = xs = x(st)+s, by (4.8) = x(st+)+s, by Lemma 4.8 = xst+, by the left ample identity. Thus x(sφ) ∈ St+ = dom tφ. We conclude that x ∈ dom(sφ)(tφ). Therefore, dom(sφ)(tφ) = dom(st)φ. It is clear that x(sφ)(tφ) = x(st)φ, for x in this domain, hence (sφ)(tφ) = (st)φ. Finally, we must show that φ is one-one. Suppose that sφ = tφ, for some s, t ∈ S. Then Ss+ = dom sφ = dom tφ = St+, whence s+ = ut+ and t+ = vs+, for some u, v ∈ S, i.e., C. Hollings / Eur. J. Pure Appl. Math, 2 (2009), (21-57) 47 s+L t+. It follows that s+ = t+. Finally, we have s+ = t+ ∈ dom sφ = dom tφ, so s+(sφ) = t+(tφ)⇒ s+s = t+ t ⇒ s = t, as required. Thus: Theorem 4.13. Weakly left E-ample semigroups are precisely left restriction semigroups; weakly left ample semigroups are precisely full left restriction semigroups. From here on, we will use the term ‘left restriction semigroup’. In the previous section, we observed that left restriction semigroups generalise inverse semigroups. We now prove this explicitly in the abstract setting. First note the following: Lemma 4.14. In a regular semigroup, R = eR . Proof. Let S be a regular semigroup. We know from Lemma 4.1 that R ⊆ eR . It remains to show the reverse inclusion. Let a, b ∈ S and suppose that a eR b. Since S is regular, there exists a′ ∈ S with aa′a = a, so that aa′ is a left identity for a. Consequently, aa′ is a left identity for b also: aa′b = b, whence b ≤R a. Similarly, there exists a b′ ∈ S with bb′a = a. We conclude that aR b. Lemma 4.15. Every inverse semigroup is a full two-sided restriction semigroup with a+ = aa−1 and a∗ = a−1a, for each a ∈ S. Proof. Let S be an inverse semigroup. We will show that S is a left restriction semi- group; the proof that S is a right restriction semigroup (as per the abstract description in Definition 4.16 below, where, moreover, ∗ is defined) is dual. We know that E(S) forms a semilattice and that aR aa−1. It therefore follows from Lemma 4.14 that every element a of S is eR-related to an idempotent, namely aa−1. We also know that R is a left congruence. It therefore only remains to show that the left ample identity holds: (ae)+a = (ae)(ae)−1a = aeea−1a = aea−1a = aa−1ae = ae, C. Hollings / Eur. J. Pure Appl. Math, 2 (2009), (21-57) 48 as required. Note that any monoid can be regarded as a left restriction monoid with respect to {1}, with a+ = 1, for all elements a. A unipotent monoid (i.e., a monoid whose only idempotent is its identity) is therefore a full left restriction monoid. By way of concluding this section, and for completeness, we record the definition of the dual equivalence relation fLE and, consequently, that of a right restriction semigroup (weakly right E-ample semigroup). Definition 4.16. Let S be a semigroup and let E ⊆ E(S) be a distinguished subsemilattice of S. We define the relation fLE on S by the rule that a fLE b⇐⇒∀e ∈ E[ae = a⇔ be = b], for a, b ∈ S. We call S a right restriction semigroup with respect to E if 1. every element a is fLE-related to an idempotent a∗ ∈ E; 2. fLE is a right congruence; 3. for all a ∈ S and all e ∈ E, ea = a(ea)∗. All the results of this section have right-hand analogues in terms of fLE and ∗. 5. Left ample semigroups As we saw in Sections 1 and 2, left restriction semigroups generalise the left ample semi- groups of Fountain [22,24]. As in the more general case, left ample semigroups have both a characterisation as semigroups of partial transformations (this time, one-one partial transfor- mations), and also an abstract description. We present both points of view here, but we do not prove their equivalence; the proof is easily achieved by adapting those of Corollary 4.7 and Theorem 4.12. Let IX be the symmetric inverse monoid on a set X . There are three natural unary oper- ations which we can consider on IX : the operations + and ∗, given in (3.1) and (3.2), and C. Hollings / Eur. J. Pure Appl. Math, 2 (2009), (21-57) 49 inversion α 7→ α−1. Let S be a subsemigroup of IX . We know that if S is closed under −1, then S is an inverse semigroup, which may be regarded as a (2,1)-subalgebra of IX , with unary operation −1. In contrast, if S is closed under +, say, then we call S a left ample semigroup. It is clear that such an S is also a (2,1)-subalgebra of IX , this time with unary operation +. Since IX ⊆ P T X , it is immediate that a left ample semigroup is a full left restriction semigroup. Right ample semigroups may be defined in a similar way by considering closure under ∗. Note that there is no need to introduce the intermediate notion of a ‘left E-ample’ semigroup’: such a semigroup is necessarily left ample, since it can contain idempotents only from EX . Just as we did for left restriction semigroups, we now provide an abstract characterisation of left ample semigroups. Recall from Section 1 that the equivalence relation R∗ is defined on a semigroup S by saying that aR∗ b if, and only if, aR b in some oversemigroup T . Con- sequently, R ⊆ R∗. Fountain [24, Lemma 1.1] proved that R∗ has the following equivalent description: aR∗ b⇐⇒∀x , y ∈ S1[xa = ya⇔ x b = y b]. (5.1) It is clear thatR∗ is a left congruence. As with eRE , we have a simpler condition for an element a of a semigroup S to be R∗-related to an idempotent e ∈ E(S): aR∗ e⇐⇒ ea = a and ∀x , y ∈ S1[xa = ya⇒ xe = ye]. (Cf. Definition 1.4.) Lemma 5.1. Let S be an arbitrary semigroup. For e, f ∈ E(S), eR∗ f if, and only if, eR f . Proof. Similar to Lemma 4.2. The following is an immediate consequence of Lemma 5.1: Lemma 5.2. Let S be a semigroup whose idempotents form a subsemilattice E(S). Each element of S is R∗-related to at most one idempotent. Left ample semigroups have the following abstract description: Definition 5.3. A semigroup S is left ample if C. Hollings / Eur. J. Pure Appl. Math, 2 (2009), (21-57) 50 1. every element a is R∗-related to an idempotent, denoted by a†; 2. for all a ∈ S and all e ∈ E(S), ae = (ae)†a. By Lemma 4.1 and the fact that R∗ is a left congruence, it is easy to see that every left ample semigroup is a full left restriction. Indeed, we have the following: Lemma 5.4. In a left ample semigroup, a† = a+, for all elements a. Proof. Observe that if aR∗ e ∈ E(S), then a eR e, by Lemma 4.1. It follows that a† = a+. From here on, we will drop the notation ‘a†’ in favour of ‘a+’. Lemma 5.5. Let S be a left restriction semigroup with respect to some E ⊆ E(S). Then S is left ample if, and only if, R∗ = eRE . Proof. Let S be a left ample semigroup. We know that R∗ ⊆ eRE , so we prove the reverse inclusion. Let a eRE b, for a, b ∈ S. Then a+ = b+. Hence aR∗ a+ = b+R∗ b. Conversely, suppose that R∗ = eRE . Then S is clearly left ample. Lemma 5.6. Let S be a left restriction semigroup with respect to some E ⊆ E(S), and let φ be the function of Theorem 4.12. Then S is left ample if, and only if, imφ ⊆ IS. Proof. Let S be a left ample semigroup. Let x , y ∈ dom sφ, for some s ∈ S, and suppose that x(sφ) = y(sφ), i.e., xs = ys. By Lemma 5.5, R∗ = eRE , so xs+ = ys+, since sR∗ s+. Then xs+ = ys+⇔ x(s+φ) = y(s+φ)⇔ x(sφ)+ = y(sφ)+⇔ x = y. Therefore sφ is one-one, i.e., sφ ∈ IS . Conversely, suppose that imφ ⊆ IS . Then, since φ is a (2,1)-morphism, imφ is a (2,1)- subalgebra of IS . By the remarks in the opening paragraphs of this section, S is left ample. We see from Lemmas 4.1 and 4.14 that R = R∗ = eR in a regular semigroup. It is clear from Lemmas 4.15 and 5.6 that every inverse semigroup is left ample. It is also clear that a right cancellative semigroup is left ample. Once again, for completeness, we conclude this section by recording the definition of the dual equivalence relation L ∗ and, consequently, that of a right ample semigroup. C. Hollings / Eur. J. Pure Appl. Math, 2 (2009), (21-57) 51 Definition 5.7. We define the equivalence relation L ∗ on a semigroup S by the rule that aL ∗ b⇐⇒∀x , y ∈ S1[ax = a y⇔ bx = b y], for a, b ∈ S. We call S right ample if 1. every element a is L ∗-related to an idempotent, denoted by a∗; 2. for all a ∈ S and all e ∈ E(S), ea = a(ea)∗. All the results of this section have right-hand analogues in terms of L ∗ and ∗. Appendix: Summary of terminology As we saw in Sections 1 and 2, when approached from the point of view of S-acts, the terminology associated with the class of semigroups which we are now calling ‘left restriction semigroups’ has had a somewhat torturous history, with a number of changes along the way. Unfortunately, if one is to study the earlier papers on this subject, then one must be familiar with all of the former names of these semigroups. We therefore provide a short summary of the various terms found in this area of study. We will restrict our attention to the left-hand versions of these various classes of semigroups; the right-hand version may be defined dually. Let S be a semigroup with a distinguished subset E ⊆ E(S). We will call S • left E-semiabundant if every element is eRE-related to an idempotent from E, and • left E-abundant if every element is R∗-related to an idempotent from E. In either case, if E = E(S), then we will omit the ‘E ’. These terms will serve as our basic terminology: everything else will be defined in terms of these. Let (CL) denote the condition that eRE be a left congruence, and (LA) denote the left ample identity: ae = (ae)+a, for all a ∈ S and all e ∈ E. Table 1 summarises the various classes of semigroups mentioned in Sections 1 and 2. Observe that there have been two conventions for the naming of these semigroups: in most cases, the switch from semigroups defined in terms ofR∗ to those defined in terms of eRE has been denoted by the addition of the prefix ‘semi-’, whilst in one case, it has C. Hollings / Eur. J. Pure Appl. Math, 2 (2009), (21-57) 52 been signified by the inclusion of the word ‘weakly’. The latter convention is the more recent. At the risk of causing further confusion, left E-semiabundant semigroups, for example, would probably now be called ‘weakly left E-abundant semigroups’! As a final comment, we note that Lawson’s Ehresmann semigroups appear only in their two-sided form in [47] but it is easy to see that we can write down one-sided versions also. We have omitted Lawson’s Rees semigroups [46] from Table 1, as they cannot be defined in a single line; suffice it to say that they are a special class of (two-sided) E-semiabundant semigroups. Name Definition left Ehresmann left E-semiadequate with (CL) left idempotent-connected Ehresmann = weakly left E-ample left adequate left abundant with E(S) a semilattice left E-adequate left E-abundant with E a semilattice left ample left adequate with (LA) left E-semiadequate left E-semiabundant with E a semilattice left PP = left abundant left Q- left semiabundant with E(S) a band left quasi-adequate left abundant with E(S) a band left restriction = weakly left E-ample left semiadequate left semiabundant with E(S) a semilattice left type A = left ample left type T = weakly left ample weakly left ample left semiadequate with (CL) and (LA) weakly left E-ample left Ehresmann with (LA)Table 1: Guide to the terminology of Se tions 1 and 2 REFERENCES 53 ACKNOWLEDGEMENTS. This article was completed at CAUL under FCT post-doctoral re- search grant SFRH/BPD/34698/2007. My thanks are due to Victoria Gould for many useful comments. References [1] S. Armstrong. The structure of type A semigroups. Semigroup Forum, 29:319–336, 1984. [2] A. Batbedat. γ-demi-groupes, demi-modules, produit demi-direct. In Semigroups Proceedings: Oberwolfach 1979, Lecture Notes in Mathematics 855, pages 1–18. Springer-Verlag, 1981. [3] A. Batbedat and J. B. Fountain. Connections between left adequate semigroups and γ- semigroups. Semigroup Forum, 22:59–65, 1981. [4] A. H. Clifford. Semigroups admitting relative inverses. Ann. Math. (2), 42:1037–1049, 1941. [5] A. H. Clifford and G. B. Preston. The Algebraic Theory of Semigroups, volume 1 of Mathematical Surveys, No. 7. American Mathematical Society, Providence, RI, 1961. [6] J. R. B. Cockett and S. Lack. Restriction categories I: categories of partial maps. Theoret. Comput. Sci., 270:223–259, 2002. [7] J. R. B. Cockett and E. Manes. Boolean and classical restriction categories. submitted. [8] P. M. Cohn. Embeddings in semigroups with one-sided division. J. London Math. Soc., 31:169– 181, 1956. [9] C. M. de Barros. Sur les catégories ordonnées régulières. Cah. Topol. Géom. Différ. Catég., 11:23– 55, 1969. [10] M. P. Dorofeeva. Hereditary and semi-hereditary monoids. Semigroup Forum, 4:301–311, 1972. [11] C. Ehresmann. Gattungen von lokalen Strukturen. Jahresbericht der Deutschen Mathematiker- Vereinigung, 60:49–77, 1957. [12] C. Ehresmann. Catégories inductives et pseudogroupes. Annales de l’Institut Fourier, Grenoble, 10:307–336, 1960. [13] C. Ehresmann. Catégories et Structures. Dunod, Paris, 1965. [14] C. Ehresmann. Oeuvres complètes et commentèes. In A. C. Ehresmann, editor, Supplements to Cahiers de Topolgie et Géométrie Différentielle. Amiens, 1980-83. [15] A. El-Qallali. Structure Theory for Abundant and Related Semigroups. PhD thesis, University of York, 1980. [16] A. El-Qallali. Quasi-adequate semigroups II. Semigroup Forum, 44:273–282, 1992. REFERENCES 54 [17] A. El-Qallali and J. B. Fountain. Quasi-adequate semigroups. Proc. Roy. Soc. Edinburgh Sect. A, 91:91–99, 1981. [18] E. H. Feller and R. L. Gantos. Completely injective semigroups. Pacific J. Math., 31:359–366, 1969. [19] E. H. Feller and R. L. Gantos. Completely injective semigroups with central idempotents. Glasgow Math. J., 10:16–20, 1969. [20] E. H. Feller and R. L. Gantos. Completely right injective semigroups that are unions of groups. Glasgow Math. J., 12:43–49, 1971. [21] J. Fountain. Completely right injective semigroups. Proc. London Math. Soc. (3), 28:28–44, 1974. [22] J. Fountain. A class of right PP monoids. Quart. J. Math., Oxford (2), 28:285–300, 1977. [23] J. Fountain. Right PP monoids with central idempotents. Semigroup Forum, 13:229–237, 1977. [24] J. Fountain. Adequate semigroups. Proc. Edinburgh Math. Soc. (2), 22:113–125, 1979. [25] J. Fountain. Abundant semigroups. Proc. London Math. Soc. (3), 44:103–129, 1982. [26] J. Fountain. Ample and Left Ample Semigroups: Extended Abstract. Categories and Semigroups Workshop, Calgary, June 2nd 2006. http://pages.cpsc.ucalgary.ca/∼robin/FMCS/FMCS_06/amplesurvey2.pdf. [27] G. M. S. Gomes and V. Gould. Proper weakly left ample semigroups. Internat. J. Algebra Comput., 9:721–739, 1999. [28] G. M. S. Gomes and V. Gould. Graph expansions of unipotent monoids. Comm. Algebra, 28:447– 463, 2000. [29] G. M. S. Gomes and V. Gould. Finite proper covers in a class of finite semigroups with commuting idempotents. Semigroup Forum, 66:433–454, 2003. [30] V. Gould. (Weakly) left E-ample semigroups. http://www-users.york.ac.uk/∼varg1/finitela.ps. [31] V. Gould. Graph expansions of right cancellative monoids. Internat. J. Algebra Comput., 6:713– 733, 1996. [32] V. Gould and C. Hollings. Restriction semigroups and inductive constellations. submitted. [33] W. H. Gustafson. The history of algebras and their representations. In Representations of Algebras, Lecture Notes in Mathematics 944, pages 1–28. Springer, 1982. [34] T. E. Hall. Orthodox semigroups. Pacific J. Math., 39:677–686, 1971. [35] C. Hollings. Partial Actions of Semigroups and Monoids. PhD thesis, University of York, 2007. [36] C. Hollings. Extending the Ehresmann-Schein-Nambooripad Theorem. submitted. REFERENCES 55 [37] J. M. Howie. Fundamentals of Semigroup Theory. LMS Monographs No. 12. Clarendon Press, Oxford, 1995. [38] J. R. Isbell. Beatific semigroups. J. Alg., 23:228–238, 1972. [39] M. Jackson and T. Stokes. An invitation to C-semigroups. Semigroup Forum, 62:279–310, 2001. [40] M. Jackson and T. Stokes. Algebras of partial maps. In Proceedings of the Special Interest Meet- ing on Semigroup Theory and Related Mathematics (Sydney, 2005). Sydney University Press, To appear. [41] J. P. Jans. Rings and Homology. Holt, Rinehart and Winston, 1964. [42] M. Kilp. Commutative monoids all of whose principal ideals are projective. Semigroup Forum, 6:334–339, 1973. [43] M. V. Lawson. The Structure Theory of Abundant Semigroups. PhD thesis, University of York, 1985. [44] M. V. Lawson. The structure of type A semigroups. Quart. J. Math., Oxford (2), 37:279–298, 1986. [45] M. V. Lawson. The geometric theory of inverse semigroups I: E-unitary inverse semigroups. J. Pure Appl. Alg., 67:151–177, 1990. [46] M. V. Lawson. Rees matrix semigroups. Proc. Edinburgh Math. Soc., 33:23–37, 1990. [47] M. V. Lawson. Semigroups and ordered categories I: the reduced case. J. Alg., 141:422–462, 1991. [48] M. V. Lawson. The geometric theory of inverse semigroups II: E-unitary covers of inverse semi- groups. J. Pure Appl. Alg., 83:121–139, 1992. [49] M. V. Lawson. Inverse Semigroups: The Theory of Partial Symmetries. World Scientific, 1998. [50] E. S. Lyapin. Semigroups. Translations of Mathematical Monographs, Volume 3. American Math- ematical Society, Providence, R.I., 1963. [51] E. Manes. Guarded and banded semigroups. Semigroup Forum, 72:94–120, 2006. [52] D. B. McAlister. Groups, semilattices and inverse semigroups. Trans. Amer. Math. Soc., 192:227– 244, 1974. [53] D. B. McAlister. Groups, semilattices and inverse semigroups II. Trans. Amer. Math. Soc., 196:351–370, 1974. [54] D. B. McAlister. One-to-one partial right translations of a right cancellative semigroup. J. Alg., 43:231–251, 1976. [55] J. Meakin. On the structure of inverse semigroups. Semigroup Forum, 12:6–14, 1976. REFERENCES 56 [56] W. D. Munn. A certain sublattice of the lattice of congruences on a regular semigroup. Proc. Cam. Phil. Soc., 60:385–391, 1964. [57] W. D. Munn. Uniform semilattices and bisimple inverse semigroups. Quart. J. Math., Oxford (2), 17:151–159, 1966. [58] K. S. S. Nambooripad. Structure of regular semigroups I. Memoirs of the American Mathematical Society, 22(224), 1979. [59] F. Pastijn. A representation of a semigroup by a semigroup of matrices over a group with zero. Semigroup Forum, 10:238–249, 1975. [60] G. B. Preston. Inverse semi-groups. J. London Math. Soc., 29:396–403, 1954. [61] G. B. Preston. Inverse semi-groups with minimal right ideals. J. London Math. Soc., 29:404–411, 1954. [62] G. B. Preston. Representations of inverse semi-groups. J. London Math. Soc., 29:411–419, 1954. [63] B. M. Schein. On the theory of generalised heaps and generalised groups. In The Theory of Semigroups and its Applications I, pages 286–324. University of Saratov, 1965. [64] B. M. Schein. Relation algebras and function semigroups. Semigroup Forum, 1:1–62, 1970. [65] B. M. Schein. On the theory of inverse semigroups and generalised grouds. American Mathemat- ical Society Translations (2), 113:89–122, 1979. [66] B. Schweizer and A. Sklar. The algebra of functions. Math. Ann., 139:366–382, 1960. [67] B. Schweizer and A. Sklar. The algebra of functions II. Math. Ann., 143:440–447, 1961. [68] B. Schweizer and A. Sklar. The algebra of functions III. Math. Ann., 161:171–196, 1965. [69] B. Schweizer and A. Sklar. Function systems. Math. Ann., 172:1–16, 1967. [70] K. Shoji. Completely right injective semigroups. Math. Japon., 24(6):609–615, 1979/80. [71] L. A. Skornjakov. On homological classification of monoids. Siberian Math. J., 10:843–846, 1969. [72] È. G. Šutov. Potential conjugacy of elements in semigroups (Russian). Leningrad. Gosud. Ped. Inst. Uč. Zap., 166:105–119, 1958. [73] È. G. Šutov. Potential divisibility of elements in semigroups (Russian). Leningrad. Gosud. Ped. Inst. Uč. Zap., 166:75–103, 1958. [74] È. G. Šutov. Potential one-sided invertibility of elements of semigroups (Russian). Uč. Zap. Udmurt. Ped. Inst., 12:24–36, 1958. [75] È. G. Šutov. Potential stationarity of elements of semigroups (Russian). Uč. Zap. Udmurt. Ped. Inst., 12:16–23, 1958. REFERENCES 57 [76] V. S. Trokhimenko. Menger’s function systems (Russian). Izv. Vyssh. Uchebn. Zaved. Mat., 11 (138):71–78, 1973. [77] O. Veblen and J. H. C. Whitehead. The Foundations of Differential Geometry. Cambridge Tract No. 24. Cambridge University Press, 1932. [78] V. V. Wagner. Generalised groups (Russian). Dokl. Acad. Nauk SSSR, 84:1119–1122, 1952. [79] V. V. Wagner. The theory of generalised heaps and generalised groups (Russian). Mat. Sb. (N. S.), 32:545–632, 1953.