ORDERED GROUPOID QUOTIENTS AND CONGRUENCES ON INVERSE SEMIGROUPS 6 1 0 NOUFALYAMANI 2 n a J KingdomofSaudiArabia,MinistryofHigherEducation, 9 UniversityofDammam, 2 P.O.Box1982,Dammam31441,SaudiArabia. ] [email protected] R G . h t N.D.GILBERT a m [ 1 SchoolofMathematicalandComputerSciences v andtheMaxwellInstitutefortheMathematicalSciences, 4 Heriot-WattUniversity, 9 1 EdinburghEH144AS,U.K 8 [email protected] 0 . 1 0 6 ABSTRACT. WeintroduceapreorderonaninversesemigroupSassoci- 1 atedtoanynormalinversesubsemigroupN,thatliesbetweenthenatural : partialorderandGreen’sJ–relation.Thecorrespondingequivalencere- v lation(cid:39) isnotnecessarilyacongruenceonS,butthequotientsetdoes i N X inheritanaturalorderedgroupoidstructure. Weshowthatthisconstruc- r tionpermitsthefactorisationofanyinversesemigrouphomomorphism a into a composition of a quotient map and a star-injective functor, and thatthisdecompositionimpliesaclassificationofcongruencesonS.We give an application to the congruence and certain normal inverse sub- semigroupsassociatetoaninversemonoidpresentation. 2010MathematicsSubjectClassification. Primary: 20L05;Secondary18D15,18B40. Keywordsandphrases. inversesemigroup,congruence,normalsubsemigroup. TheauthorsgratefullyacknowledgesthesupportofaresearchgrantfromtheUniversity ofDammam. 1 INTRODUCTION LetS beaninversesemigroupwithsemilatticeofidempotentsE(S). Recall thatthenaturalpartialorder onS isdefinedby s (cid:54) t ⇐⇒ thereexists e ∈ E(S) with s = et. The natural partial order may be characterized in a number of alternative ways,including: • thereexistsf ∈ E(S)withs = tf, • s = ss−1t, • s = ts−1s. (see [6, Proposition 5.2.1]). In this paper, we shall generalize the natural partial order by introducing a preorder (cid:54) on S for any normal inverse N subsemigroup N: the natural partial order then corresponds to the minimal normal inverse subsemigroup E(S), and at the other extreme, the preorder associated to S itself is the J–preorder. Symmetrizing the preorder (cid:54) N yields an equivalence relation (cid:39) (the identity when N = E(S) and the N J–relation when N = S). However, this relation need not be a congru- ence, and so the set of equivalence classes S/ (cid:39) need not be an inverse N semigroup. However, we may investigate (cid:39) further by exploiting the relationship be- N tweeninversesemigroupsandorderedgroupoids. Anorderedgroupoidisa small category in which every morphism is invertible, equipped with a par- tial order on morphisms. (The definition is recalled in detail in section 1.) An inverse semigroup can be considered as an ordered groupoid in which the identities form a semilattice, and from any such ordered groupoid a corresponding inverse semigroup can be constructed. In the study of in- verse semigroups, it is often fruitful to extend the point of view to ordered groupoids, and this is a major theme of [8]. We show that the quotient set S/ (cid:39) always inherits a natural ordered groupoid structure. Moreover, to N any homomorphism φ : S → Σ of inverse semigroups, we associate its kernelK = {s ∈ S : sφ ∈ E(Σ)},andφthenfactorisesas S −→ S/ (cid:39) −→ Σ K withthemapS/ (cid:39) → Σastar-injectivefunctorfromtheorderedgroupoid K S/ (cid:39) toΣ(consideredasanorderedgroupoid). K Now any congruence ρ on an inverse semigroup determines a normal in- verse subsemigroup K, its kernel, which consists of all elements of S that are ρ–equivalent to idempotents. We compare the structures of the ordered groupoidS/ (cid:39) andthequotientinversesemigroupS/ρ,andweshowthat K 2 if(cid:39) isacongruence,thenitistheminimalcongruencewithkernelK. We K showhowtoclassifycongruencesbythefactorisation S −→ S/ (cid:39) −→ S/ρ K andlookatcertaincongruencesandtheirkernelsassociatedwithaninverse monoidpresentation,andtherelationshipsbetweenthem. 1. ORDERED GROUPOIDS AND INVERSE SEMIGROUPS AgroupoidGisasmallcategoryinwhicheverymorphismisinvertible. We consideragroupoidasanalgebraicstructurefollowing[5]: theelementsare the morphisms, and composition is an associative partial binary operation. The set of identities in G is denoted E(G), and an element g ∈ G has domaingg−1 andrangeg−1g. Anorderedgroupoid(G,(cid:54))isagroupoidGwithapartialorder(cid:54)satisfy- ingthefollowingaxioms: OG1 forallg,h ∈ G,ifg (cid:54) htheng−1 (cid:54) h−1, OG2 if g (cid:54) g ,h (cid:54) h and if the compositions g h and g h are 1 2 1 2 1 1 2 2 defined,theng h (cid:54) g h , 1 1 2 2 OG3 if g ∈ G and x is an identity of G with x (cid:54) gd, there exists a unique element (x|g), called the restriction of g to x, such that (x|g)(x|g)−1 = xand(x|g) (cid:54) g, Asaconsequenceof[OG3]wealsohave: OG3* if g ∈ G and y is an identity of G with y (cid:54) gr, there exists a unique element (g|y), called the corestriction of g to y, such that (g|y)−1(g|y) = y and(g|y) (cid:54) g, sincethecorestrictionofg toy maybedefinedas(y|g−1)−1. Let G be an ordered groupoid and let a,b ∈ G. If a−1a and bb−1 have a greatest lower bound (cid:96) ∈ E(G), then we may define the pseudoproduct of a and b in G as a ⊗ b = (a|(cid:96))((cid:96)|b), where the right-hand side is now a composition defined in G. As Lawson shows in Lemma 4.1.6 of [8], this is apartiallydefinedassociativeoperationonG. If E(G) is a meet semilattice then G is called an inductive groupoid. The pseudoproduct is then everywhere defined and (G,⊗) is an inverse semi- group. Ontheotherhand,givenaninversesemigroupS withsemilatticeof idempotentsE(S),thenS isaposetunderthenaturalpartialorder,andthe restrictionofitsmultiplicationtothepartialcomposition s·t = st ∈ S definedwhen s−1s = tt−1 3 gives S the structure of an ordered groupoid, with set of identities E(S). These constructions give an isomorphism between the categories of in- verse semigroups and inductive groupoids: this is the Ehresmann-Schein- Nambooripad Theorem [8, Theorem 4.1.8]. We call a product st ∈ S with s−1s = tt−1 a trace product. Any product in S can be expressed as a trace product,attheexpenseofchangingthefactors,sincest = stt−1 ·s−1st. Let e ∈ E(G). Then the star of e in G is the set star (e) = {g ∈ G : G gg−1 = e}. A functor φ : G → H is said to be star-injective if, for each e ∈ E(G), the restriction φ : star (e) → star (eφ) is injective. A star- G H injectivefunctorisalsocalledanimmersion. IfGisinductive,thenstar (e) G isjusttheGreenR–classofeintheinversesemigroup(G,⊗). 2. NORMAL INVERSE SUBSEMIGROUPS AND QUOTIENTS An inverse subsemigroup N of an inverse semigroup S is normal [13] if it isfull–thatis,ifE(N) = E(S)–andif,foralls ∈ S andn ∈ N,wehave s−1ns ∈ N. A normal inverse subsemigroup N of S determines a relation (cid:54) onS,definedusingthenaturalpartialorder(cid:54)onS,asfollows: N (2.1) s (cid:54) t ⇐⇒ thereexist a,b ∈ N suchthat a·s·b (cid:54) t. N Note the requirement that trace products occur here. We define the relation (cid:39) bysymmetrizing(cid:54) : N N (2.2) s (cid:39) t ⇐⇒ thereexist a,b,c,d ∈ N suchthat a·s·b (cid:54) t and c·t·d (cid:54) s N Lemma2.1. (a) Therelation(cid:54) isthenaturalpartialorder(cid:54)onS. E(S) (b) Therelation(cid:54) istheJ–preorder(cid:22) onS. S J (c) Ifs (cid:54) tinthenaturalpartialorderonS thens (cid:54) tforanynormal N inversesubsemigroupN ofS. (d) s (cid:54) eforsomee ∈ E(S)ifandonlyifs ∈ N. N (e) Ifs (cid:54) s2 thens ∈ N. N (f) Ifs (cid:54) tthenst−1 ∈ N. N (g) Therelation(cid:54) isapreorderonS andhence(cid:39) isanequivalence N N relationonS. Proof. (a) This is clear, since if e,f ∈ E(S), a trace product e·s·f is equaltos. (b) Ifa·s·b (cid:54) tthenaa−1 (cid:54) tt−1 anda−1a = ss−1. Hences (cid:22) t. On J the other hand, if s (cid:22) t then there exists p ∈ S with pp−1 (cid:54) tt−1 J 4 andp−1p = ss−1. Then p·s·(s−1 ·p−1 ·pp−1t) (cid:54) t andsos (cid:54) t. S (c) SinceN isfull,ss−1,s−1s ∈ N ands = ss−1 ·s·s−1s (cid:54) t. (d) Supposethata,b ∈ N witha·s·b (cid:54) e. Thereforea·s·b = f (cid:54) ewith f ∈ E(S),andthens = a−1a·s·bb−1 = a−1fb−1 ∈ N. Conversely, ifn ∈ N thennn−1 ·n·n−1 = nn−1 andson (cid:54) nn−1. N (e) Wehavea,b ∈ N witha·s·b (cid:54) s2 andsos (cid:54) a−1s2b−1. Therefore s = ss−1a−1s2b−1 anditfollowsthat s−1 = s−1ss−1 = s−1ss−1a−1s2b−1s−1 = (s−1a−1s)(sb−1s−1) ∈ N andsos ∈ N. (f) If a · s · b (cid:54) t then s = a−1a · s · bb−1 (cid:54) a−1tb−1 and so st−1 (cid:54) a−1(tb−1t−1) ∈ N. SinceN isfull,wededucethatst−1 ∈ N. (g) It is clear that (cid:54) is reflexive. Suppose that s,t,u ∈ S and that s (cid:54) t (cid:54) u. There exist a,b,p,q ∈ N such that a·s·b (cid:54) t and N N p·t·q (cid:54) u. Then(pa)s(bq) (cid:54) u,and(pa)s(bq)isthetraceproduct (pa)·s·(bq)since (pa)−1(pa) = a−1p−1pa = a−1tt−1a = a−1a = ss−1, and aa−1 (cid:54) tt−1. Similarly s−1s = (bq)(bq)−1. Therefore (pa)·s· (bq) (cid:54) uands (cid:54) u. N (cid:3) Corollary 2.2. The normal inverse subsemigroup N is determined by the preorder (cid:54) , and we obtain an order-preserving embedding of the poset N of normal inverse subsemigroups of S into the poset of preorders on S that containthenaturalpartialorder. Proof. Part(d)ofLemma2.1showsthat N = {s ∈ S : thereexists e ∈ E(S) with s (cid:54) e}. N (cid:3) Remark 2.3. Not every preorder containing the natural partial order arises fromanormalinversesubsemigroup. Considerthesymmetricinversemonoid I and define a preorder (cid:22) by α (cid:22) β ⇐⇒ d(α) ⊆ dβ where d(γ) is the n domain of γ ∈ I . Then α (cid:22) id for all α ∈ I , and so the normal inverse n n subsemigroup associated to (cid:22) is I itself, but (cid:22) is not the J–preorder on n I andsoisnotequalto(cid:54) . n In Wedenotethe(cid:39)–classofs ∈ S by[s] . N 5 Proposition2.4. (a) Ifn ∈ N thennn−1 (cid:39) n (cid:39) n−1 (cid:39) n−1n, N N N (b) Theequivalencerelation(cid:39) saturatesN, N (c) Theequivalencerelation(cid:39) determinesN as N (cid:91) N = [e] . N e∈E(S) (d) Ifs (cid:39) tthenss−1 (cid:39) tt−1,s−1s (cid:39) t−1t,ands−1 (cid:39) t−1. N N N N (e) The restriction of (cid:39) to E(S) coincides with Green’s J–relation N J inducedonE(S) = E(N), N (f) In the case N = S the relation (cid:39) coincides with Green’s J– S relationonS, (g) InthecaseN = E(S)therelation(cid:39) isthetrivialrelationonS. E(S) Proof. (a) If n ∈ N then n−1 ·n·n−1 = n−1 and n·n−1 ·n = n, and hence n (cid:39) n−1. Similarlynn−1·n·n−1 = nn−1 andnn−1·nn−1·n = n, N whencen (cid:39) nn−1. N (b) Suppose that s ∈ S and that for some n ∈ N we have s (cid:39) n. By N part (a) we may assume that n ∈ E(S): then there exist p,q ∈ N suchthatp·s·q (cid:54) n. Henceforsomee ∈ E(S)wehavep·s·q = e andsos = p−1 ·e·q−1 = p−1q−1 ∈ N. (c) Thisfollowsfromparts(a)and(b). (d) Suppose that s (cid:39) t, with a,b,c,d ∈ N as in (2.2). Then bb−1 = N s−1s, b−1b (cid:54) t−1t,dd−1 = t−1t,d−1d (cid:54) s−1s and so s−1s (cid:39) t−1t. N Similarlyss−1 (cid:39) tt−1. Sinceb−1·s−1·a−1 (cid:54) t−1andd−1·t−1·c−1 (cid:54) s−1,wealsohaves−1 (cid:39) t−1. (e) Ife (cid:39) f thenthereexista,b,p,q ∈ N witha·e·b (cid:54) f andp·f·q (cid:54) N e. Therefore we have a−1a = e and aa−1 (cid:54) f, and so e (cid:54) f. By JN symmetry f (cid:54) e and so e J f. Conversely, if e J f there JN N N exist m,n ∈ N with mm−1 (cid:54) f and m−1m = e,nn−1 (cid:54) e and n−1n = f. Thenm·e·m−1 (cid:54) f andn·f ·n−1 (cid:54) e,andsoe (cid:39) f. N (f) Thisfollowsfrompart(b)ofLemma2.1. (g) By Lemma 2.1(a), (cid:54) is the natural partial order , which is of E(S) courseanti-symmetric. (cid:3) However,(cid:39) neednotbeacongruenceonS. N Example2.5. 6 (a) InthesymmetricinversemonoidI ,letf : {1} → {2},letS bethe 4 inversesubsemigroup S = {id ,id ,id ,f,f−1,0} {1,3} {1} {2} of I , and let N = S. Then id = ff−1 (cid:39) f−1f = id . But 4 {1} S {2} id id = id is not (cid:39) –related to id id = 0. In this {1,3} {1} {1} S {1,3} {2} example,theposetofJ–classesisjustathree-elementchainandso isasemilattice. (b) Nowletg : {3} → {4}inI andletT betheinversesubsemigroup 4 ofI generatedby{id ,id ,f,g}. HeretheJ–classesdonot 4 {1,3} {2,4} form a semilattice, and so (cid:39) is not a congruence, and the quotient T T/ (cid:39) isnotaninversesemigroup: itistheposet T Following the notation in [1], we shall denote the quotient S/ (cid:39) by S//N N and let π : S → S//N be the quotient map. Our next result sets out the ordered groupoid structure on S//N: it is a special case of [1, Theorem 3.14],butthedescriptionissimplerforquotientsofinversesemigroupsand seemsworthstatingindetail. Theorem 2.6. For any inverse semigroup S and normal inverse subsemi- group N, the quotient set S//N is an ordered groupoid, with the following structure: (a) the identities are the classes [e] where e ∈ E(S), and a class [s] N N hasdomain[ss−1] ,range[s−1s] ,andinverse[s−1] . N N N (b) asaposet,E(S//N)isisomorphictoN/J . N (c) If s,t ∈ S and s−1s (cid:39) tt−1, then there exists a ∈ N with aa−1 (cid:54) N s−1s and a−1a = tt−1: the composition of [s] and [t] is then N N definedas[sat] . N (d) Theordering(cid:54) of(cid:39) –classesisgivenby N N [s] (cid:54) [t] ⇐⇒ thereexist a,b ∈ N suchthat a·s·b (cid:54) t. N N N Proof. Itfollowsfrompart(d)ofProposition2.4thatthedomainandrange of[s] anditsinverse[s]−1 arewell-defined. N N Supposethats,t ∈ S ands−1s (cid:39) tt−1 buthatwechooseanotherelement N z ∈ N with zz−1 (cid:54) s−1s and z−1z = tt−1. Then az−1z = att−1 = 7 aa−1a = aands−1sz = (s−1s)(zz−1)z = zz−1z = z. Hence sat = saz−1zt = saz−1s−1szt = (saz−1s−1)·szt (cid:39) szt N andsoforfixeds,tthe(cid:39) –classoftheelementsatdoesnotdependonthe N choice of a. We denote this class by s (cid:71) t. Suppose that s (cid:39) s and that N 1 we choose a ∈ N to form s (cid:71) t = [s a t] . There exist u,v ∈ N with 1 1 1 1 N u·s ·v (cid:54) s,andsovv−1 = s−1s (cid:62) a a−1. Then 1 1 1 1 1 (v−1a )(v−1a )−1 = v−1a a−1v (cid:54) v−1v (cid:54) s−1s 1 1 1 1 and (v−1a )−1(v−1a ) = a−1vv−1a = a−1a = tt−1. 1 1 1 1 1 1 Thereforewecanusetheelementv−1a toformtheclasss (cid:71) t = [sv−1a t] . 1 1 N Now sv−1s−1 = (sv−1v)(v−1s−1 = (us v)(v−1s−1 = u and since s−1s (cid:62) 1 1 1 1 v−1v,wehave sv−1a t = sv−1vv−1a t = sv−1s−1s a t = u·(s at) (cid:39) s a t 1 1 1 1 1 1 N 1 1 and so s (cid:71) t (cid:39) s (cid:71) t. Similarly, s (cid:71) t does not depend on the choice of N 1 the element t within its (cid:39) – class, and the product [s] ·[t] = [sat] is N N N N well-defined. Nowtherelations−1s (cid:39) tt−1 furnishesnotonlya ∈ N withaa−1 (cid:54) s−1s N and a−1a = tt−1 but also p ∈ N with pp−1 (cid:54) s−1s and pp−1 = tt−1. Considersaps−1 ∈ N: wehave (saps−1)(saps−1)−1 = saps−1sp−1a−1s−1 (cid:54) sapp−1a−1s−1 = (sat)(sat)−1 and (saps−1)−1(saps−1) = sp−1a−1s−1saps−1 = sp−1a−1aps−1 = sp−1ps−1 = ss−1 and, since (sat)(sat)−1 (cid:54) ss−1, we have ss−1 (cid:39) (sat)(sat)−1. There- N fore, [sat] has domain [ss−1] and range [t−1t] , and the composition N N N [s] ·[t] = [sat] doesgiveagroupoidstructureonS//N. N N N NowbyLemma2.1,(cid:54) inducesthegivenpartialorderonthe(cid:39) –classes, N N and it remains to show that this partial order makes S//N into an ordered groupoid. Now if a·s·b (cid:54) t then b−1 ·s−1 ·a−1 (cid:54) t−1 and so [s] (cid:54) [t] implies N N N that [s]−1 (cid:54) [t]−1. Now suppose that [s ] (cid:54) [s] ,[t ] (cid:54) [t] and that N n N 1 N N 1 N N the compositions [s] ·[t] and [s ]·[t ] exist. There exist m,n,u,v ∈ N N N 1 1 8 such that m·s ·m (cid:54) s and u·t ·v (cid:54) t: since [m·s ·n] = [s ] and 1 1 1 N 1 N [u·t ·v] = [t ] wemayaswellassumethats (cid:54) sandt (cid:54) t. 1 N 1 N 1 1 We now have a,p ∈ N with aa−1 (cid:54) s−1s,a−1a = tt−1 and b,q ∈ N with bb−1 (cid:54) s−1s ,b−1b = t t−1,qq−1 (cid:54) t t−1 andq−1q = s−1s . Now 1 1 1 1 1 1 1 1 s bt (cid:39) sab−1s−1 ·s bt = sab−1s−1s bt (cid:54) sat (cid:54) sat 1 1 N 1 1 1 1 1 1 andso[s ] ·[t ] = [s bt ] (cid:54) [sat] = [s] ·[b] . 1 N 1 N 1 1 N N N N Finally we suppose that [n] (cid:54) [ss−1] for some n ∈ N and s ∈ S. By N N N part (a) of Proposition 2.4 we may replace n bye = nn−1. Then there exist a,b ∈ N with a · e · b (cid:54) ss−1 and so aa−1 (cid:54) ss−1 and a−1a = e. Then the class [aa−1s] has domain [aa−1] = [e] and [aa−1s] (cid:54) [s] . We N N N N N N wishtoshowthat[aa−1s] istheunique(cid:39) –classwiththeseproperties. N N Suppose that [k] (cid:54) [s] and that [kk−1] = [e] . There exist u,v ∈ N N N N N N with u · k · v (cid:54) s and b,q ∈ N with bb−1 (cid:54) kk−1,b−1b = e,qq−1 (cid:54) e, and q−1q = kk−1. We have a ∈ N as in the previous paragraph. Then kvs−1 = u−1 andu−1uq−1 = q−1: hence k (cid:39) k ·vs−1uq−1a−1s = q−1a−1s = q−1a−1aa−1s N = q−1a−1 ·aqq−1a−1s (cid:39) = aqq−1a−1s (cid:54) aa−1s N andso[k] (cid:54) [aa−1s] . Bysymmetry,theyareequal. (cid:3) N N N Corollary 2.7. [1, Theorem 4.15] Given a homomorphism φ : S → Σ of inverse semigroups, let K = {s ∈ S : xφ ∈ E(Σ)}. Then K is a normal inversesubsemigroupofS,andφfactorisesasacomposition π κ S −→ S//K −→ Σ whereκ,definedby[s] κ = sφ,isastar-injectivefunctor. K Proof. The map κ is well-defined, since if [s] = [s(cid:48)] then, for some K K a,b ∈ K we have a · s · b (cid:54) s(cid:48). Now aφ = (a−1a)φ = (ss−1)φ and similarly, bφ = (s−1s)φ). It follows that (a · s · b)φ = sφ (cid:54) s(cid:48)φ. By symmetry,s(cid:48)φ (cid:54) sφ. To show that κ is a functor, suppose that [s] and [t] are composable in K K S//K. Thenthereexista,p ∈ K with aa−1 (cid:54) s−1s,a−1a = tt−1,pp−1 (cid:54) tt−1,p−1p = s−1s 9 and the composition of [s] and [t] is defined, as in Theorem 2.6, by K K [s] ·[t] = [sat] . Then K K K ([sat] )κ = (sat)φ = (sφ)(aφ)(tφ) K = (sφ)(a−1a)φ(tφ) (since a ∈ K) = (sφ)(tt−1)φ(tφ) = (sφ)(tφ) Now(sφ)(tφ)isatraceproduct(sφ)·(tφ)since (sφ)−1(sφ) = (s−1s)φ = (p−1p)φ = (pp−1)φ (since p ∈ K) (cid:54) (tt−1)φ = (tφ)(tφ)−1 andsimilarly (tφ)(tφ)−1 = (tt−1)φ = (a−1a)φ = (aa−1)φ (since a ∈ K) (cid:54) (s−1s)φ = (sφ)−1(sφ). Therefore (sφ)(tφ) is a trace product defined in the inductive groupoid (Σ,·)andκisafunctor. To show that κ is star-injective, suppose that for some u,v ∈ S we have [uu−1] = [vv−1] and uφ = vφ. We claim that u (cid:39) v. By symmetry, it K K K issufficienttoshowthatu (cid:54) v. Nowbypart(e)Proposition2.4thereexist K a,b ∈ K with aa−1 (cid:54) uu−1,a−1a = vv−1,bb−1 (cid:54) vv−1 and b−1b = uu−1. Then b·u·u−1b−1v = (buu−1b−1)v (cid:54) v and (u−1b−1v)φ = (u−1)φ(b−1b)φvφ (sinceb ∈ K) = (u−1b−1b)φvφ = (u−1φ)vφ = (uφ)−1vφ ∈ E(Σ) sinceuφ = vφ, andsou−1b−1v ∈ K andu (cid:54) v asrequired. (cid:3) k Corollary 2.8. The factorization of φ : S → Σ is unique, in the sense that ν if φ also factorizes as S → S//N → Σ with ν a star-injective functor, then N = K (andhenceν = κ.) Proof. If n ∈ N then by part (a) of Proposition 2.4, we have n (cid:39) nn−1 N andsonφ ∈ E(Σ). HenceN ⊆ K. 10