4 Groupoids

A groupoid is a (mathematical) category in which every element is invertible. It consists of a set of pieces, each of which is a connected groupoid. (The usual terminology is `connected component', but in GAP `component' is used for `record component'.)

A single piece groupoid is determined by a set of objects obs and an object group grp. The objects of a single piece groupoid are generally chosen to be consecutive negative integers, but any suitable ordered set is acceptable, and `consecutive' is not a requirement. The object groups will usually be taken to be permutation groups, but pc-groups and fp-groups are also supported.

A group is a single piece groupoid with one object.

A groupoid is a set of one or more single piece groupoids, its pieces, and is represented as IsGroupoidRep, with attribute PiecesOfGroupoid.

For the definitions of the standard properties of groupoids we refer to R. Brown's book ``Topology'' [Bro88], recently revised and reissued as ``Topology and Groupoids'' [Bro06].

4.1 Groupoids: their properties and attributes

4.1-1 SinglePieceGroupoid

As for magmas with objects, the simplest construction of a groupoid is as the direct product of a group and a complete graph. Some subgroups of such a groupoid do not have this simple form, and will be considered in a later section. The global function Groupoid will normally find the appropriate constructor to call, the options being:

• the object group, a list of objects;

• a group being converted to a groupoid, a single object;

• a list of groupoids which have already been constructed.

Methods for ViewObj, PrintObj and Display are provided for groupoids and the other types of object in this package. Users are advised to supply names for all the groups and groupoids they construct.

gap> s4 := Group( (1,2,3,4), (3,4) );; 
gap> d8 := Subgroup( s4, [ (1,2,3,4), (1,3) ] );;
gap> SetName( s4, "s4" );  SetName( d8, "d8" ); 
gap> Gs4 := SinglePieceGroupoid( s4, [-15 .. -11] ); 
single piece groupoid: < s4, [ -15 .. -11 ] >
gap> Gd8 := Groupoid( d8, [-9,-8,-7] );
single piece groupoid: < d8, [ -9, -8, -7 ] >
gap> c6 := Group( (5,6,7)(8,9) );;
gap> SetName( c6, "c6" );
gap> Gc6 := DomainWithSingleObject( c6, -6 );
single piece groupoid: < c6, [ -6 ] >
gap> SetName( Gs4, "Gs4" );  SetName( Gd8, "Gd8" );  SetName( Gc6, "Gc6" );  

4.1-2 IsPermGroupoid

A groupoid is a permutation groupoid if all its pieces have permutation groups. Most of the examples in this chapter are permutation groupoids, but in principle any type of group known to GAP may be used. In the following example Gf2 is an fp-groupoid, while Gq8 is a pc-groupoid.

gap> f2 := FreeGroup( 2 );;
gap> Gf2 := Groupoid( f2, -22 );;
gap> SetName( f2, "f2" );  SetName( Gf2, "Gf2" ); 
gap> q8 := SmallGroup( 8, 4 );;
gap> Gq8 := Groupoid( q8, [ -28, -27 ] );;
gap> SetName( q8, "q8" );  SetName( Gq8, "Gq8" );
gap> [ IsFpGroupoid( Gf2 ), IsPcGroupoid( Gq8 ), IsPermGroupoid( Gs4 ) ]; 
[ true, true, true ]

4.1-3 UnionOfPieces

When a groupoid consists of two or more pieces, we require their object lists to be disjoint. The operation UnionOfPieces in section 2.4 is also used for groupoids. The pieces are sorted by the first object in their object lists. The ObjectList of a groupoid is the sorted concatenation of the objects in the pieces.

gap> U3 := UnionOfPieces( [ Gs4, Gd8, Gc6 ] );;
gap> SetName( U3, "Gs4+Gd8+Gc6" );
gap> Display( U3 );
groupoid with 3 pieces:
< objects: [ -15 .. -11 ]
    group: s4 = <[ (1,2,3,4), (3,4) ]> >
< objects: [ -9, -8, -7 ]
    group: d8 = <[ (1,2,3,4), (1,3) ]> >
< objects: [ -6 ]
    group: c6 = <[ (5,6,7)(8,9) ]> >

gap> Pieces( U3 );
[ Gs4, Gd8, Gc6 ]
gap> ObjectList( U3 );
[ -15, -14, -13, -12, -11, -9, -8, -7, -6 ]
gap> U2 := Groupoid( [ Gf2, Gq8 ] );;
gap> [ Size(Gs4), Size(Gd8), Size(Gc6), Size(U3), Size(U2) ];
[ 600, 72, 6, 678, infinity ]
gap> U5 := UnionOfPieces( [ U3, Gf2, Gq8 ] );
groupoid with 5 pieces:
1:  Gq8
2:  Gf2
3:  Gs4
4:  Gd8
5:  Gc6

gap> Display( U5 );
groupoid with 5 pieces:
< objects: [ -28, -27 ]
    group: q8 = <[ f1, f2, f3 ]> >
< objects: [ -22 ]
    group: f2 = <[ f1, f2 ]> >
< objects: [ -15 .. -11 ]
    group: s4 = <[ (1,2,3,4), (3,4) ]> >
< objects: [ -9, -8, -7 ]
    group: d8 = <[ (1,2,3,4), (1,3) ]> >
< objects: [ -6 ]
    group: c6 = <[ (5,6,7)(8,9) ]> >
gap> V5 := Groupoid( [ Gq8, Gf2, U3 ] );;
gap> U5 = V5;
true
gap> W5 := ReplaceOnePieceInUnion( U5, Gs4, Groupoid( s4, [-20,-19] ) ); 
groupoid with 5 pieces:
1:  Gq8
2:  Gf2
3:  single piece groupoid: < s4, [ -20, -19 ] >
4:  Gd8
5:  Gc6

4.2 Groupoid elements; stars; costars and homsets

4.2-1 GroupoidElement

A groupoid element e is a triple consisting of a group element, Arrowelt(e) or e![1]; the tail (source) object, Arrowtail(e) or e![2]; and the head (target) object, Arrowhead(e) or e![3]. Note that GroupoidElement is essentially a synonym, in the groupoid case, for MultiplicativeElementWithObjects.

The Size of a groupoid is the number of its elements which, for a single piece groupoid, is the product of the size of the group with the square of the number of objects.

As for elements in any magma with objects, groupoid elements have a partial composition: two elements may be multiplied when the head of the first coincides with the tail of the second.

gap> e1 := GroupoidElement( Gd8, (1,2,3,4), -9, -8 );
[(1,2,3,4) : -9 -> -8]
gap> e2 := GroupoidElement( Gd8, (1,3), -8, -7 );;
gap> Print( [ Arrowelt(e2), Arrowtail(e2), Arrowhead(e2) ], "\n" );
[ (1,3), -8, -7 ]
gap> prod := e1*e2;
[(1,2)(3,4) : -9 -> -7]
gap> e3 := GroupoidElement( Gd8, (2,4), -7, -9 );;
gap> cycle := prod*e3;
[(1,4,3,2) : -9 -> -9]
gap> cycle^2;
[(1,3)(2,4) : -9 -> -9]
gap> Order(cycle);
4

4.2-2 IdentityElement

The identity groupoid element 1_o of G at object o is (e:o -> o) where e is the identity element in the object group. The inverse e^-1 of e = (c : p -> q) is (c^-1 : q -> p), so that e*e^-1=1_p and e^-1*e = 1_q.

gap> i8 := IdentityElement( Gd8, -8 );
[() : -8 -> -8]
gap> [ e1*i8, i8*e1, e1^-1]; 
[ [(1,2,3,4) : -9 -> -8], fail, [(1,4,3,2) : -8 -> -9] ]

4.2-3 ObjectStar

The star at obj is the set of groupoid elements which have obj as tail, while the costar is the set of elements which have obj as head. The homset from obj1 to obj2 is the set of elements with the specified tail and head, and so is bijective with the elements of the group. Thus every star and every costar is a union of homsets. The identity element at an object is a left identity for the star and a right identity for the costar at that object.

In order not to create unneccessary long lists, these operations return objects of type IsHomsetCosetsRep for which an Iterator is provided. (An Enumerator is not yet implemented.)

gap> star9 := ObjectStar( Gd8, -9 );
<star at [ -9 ] with group d8>
gap> Size( star9 ); 
24
gap> for e in star9 do
>      if ( Order( e![1] ) = 4 ) then Print( e, "\n" ); fi;
>    od;
[(1,4,3,2) : -9 -> -9]
[(1,4,3,2) : -9 -> -8]
[(1,4,3,2) : -9 -> -7]
[(1,2,3,4) : -9 -> -9]
[(1,2,3,4) : -9 -> -8]
[(1,2,3,4) : -9 -> -7]
gap> costar6 := ObjectCostar( Gc6, -6 );
<costar at [ -6 ] with group c6>
gap> Size( costar6 ); 
6
gap> hsetq8 := Homset( Gq8, -28, -27 );
<homset -28 -> -27 with group q8>
gap> for e in hsetq8 do Print(e,"\n"); od;
[<identity> of ... : -28 -> -27]
[f3 : -28 -> -27]
[f2 : -28 -> -27]
[f2*f3 : -28 -> -27]
[f1 : -28 -> -27]
[f1*f3 : -28 -> -27]
[f1*f2 : -28 -> -27]
[f1*f2*f3 : -28 -> -27]

4.3 Subgroupoids

4.3-1 Subgroupoid

A subgroupoid sgpd of gpd has as objects some subset of the objects of gpd. It is wide if all the objects are included. It is full if, for any two objects in sgpd, the Homset is the same as that in gpd. The elements of sgpd are a subset of those of gpd, closed under multiplication and with tail and head in the chosen object set.

There are a variety of constructors for a subgroupoid of a groupoid, and the most general is the operation SubgroupoidByPieces. Its two parameters are a groupoid and a list of pieces, each piece being specified as a list [sgp,obs], where sgp is a subgroup of the group in that piece, and obs is a subset of the objects in one of the pieces of gpd.

The FullSubgroupoid of a groupoid gpd on a subset obs of its objects contains all the elements of gpd with tail and head in obs.

A subgroupoid is discrete if it is a union of groups. The MaximalDiscreteSubgroupoid of gpd is the union of all the single-object full subgroupoids of gpd.

An identity subgroupoid has trivial object groups, but need not be discrete. A single piece identity groupoid is sometimes called a tree groupoid.

The global function Subgroupoid should call the appropriate operation.

gap> c4 := Subgroup( d8, [ (1,2,3,4) ] );;
gap> k4 := Subgroup( d8, [ (1,2)(3,4), (1,3)(2,4) ] );;
gap> SetName( c4, "c4" );  SetName( k4, "k4" );
gap> Ud8 := Subgroupoid( Gd8, [ [ k4,[-9] ], [ c4, [-7,-5] ] ] );;
gap> SetName( Ud8, "Ud8" );
gap> Display( Ud8 );
Perm Groupoid with 2 pieces:
< objects: [ -9 ]
    group: k4 = <[ (1,2)(3,4), (1,3)(2,4) ]> >
< objects: [ -7, -5 ]
    group: c4 = <[ (1,2,3,4) ]> >

gap> Parent( Ud8 ); 
Gd8
gap> IsWide( Gd8, Ud8 ); 
true
gap> genf2b := List( GeneratorsOfGroup(f2), g -> g^2 );
[ f1^2, f2^2 ]
gap> f2b := Subgroup( f2, genf2b );;
gap> SubgroupoidByPieces( U2, [ [q8,[-27]], [f2b,[-22]] ] );
groupoid with 2 pieces:
1:  single piece groupoid: < q8, [ -27 ] >
2:  single piece groupoid: < Group( [ f1^2, f2^2 ] ), [ -22 ] >

gap> IsSubgroupoid( Gf2, Groupoid( f2b, [-22] ) );
true
gap> FullSubgroupoid( U3, [-7,-6] );
groupoid with 2 pieces:
1:  single piece groupoid: < d8, [ -7 ] >
2:  single piece groupoid: < c6, [ -6 ] >
gap> DiscreteSubgroupoid( U3, [ c4, k4 ], [-9,-7] );
groupoid with 2 pieces:
1:  single piece groupoid: < c4, [ -9 ] >
2:  single piece groupoid: < k4, [ -7 ] >
gap> FullIdentitySubgroupoid( Ud8 );
groupoid with 2 pieces:
1:  single piece groupoid: < id(k4), [ -9 ] >
2:  single piece groupoid: < id(c4), [ -8, -7 ] >
gap> MaximalDiscreteSubgroupoid(U2);
groupoid with 3 pieces:
1:  single piece groupoid: < q8, [ -28 ] >
2:  single piece groupoid: < q8, [ -27 ] >
3:  single piece groupoid: < f2, [ -22 ] >

4.3-2 SubgroupoidWithRays

If groupoid G is of type IsDirectProductWithCompleteGraph with group g and n objects, then a typical wide subgroupoid Hof G is formed by choosing a subgroup h of g to be the object group at the root object q, and an element r : q -> p for each of the objects p. The chosen loop element at q must be the identity element. These n elements are called the rays of the subgroupoid.

In the following example a subgroupoid with rays is to be constructed on four of the five objects. It is therefore necessary to construct the full subgroupoid on these four objects first.

It is also possible to construct a subgroupoid with rays of a subgroupoid with rays.

Note that the function Ancestor provides an iteration of Parent.

gap> Hs4 := FullSubgroupoid( Gs4, [-14,-13,-12] );; 
gap> SetName( Hs4, "Hs4" ); 
gap> Hd8a := SubgroupoidWithRays( Hs4, d8, [(),(2,3),(3,4)] );
single piece groupoid with rays: < d8, [ -14, -13, -12 ], [ (), (2,3), (3,4)
 ] >
gap> hs1413 := Homset( Hd8a, -14, -13 );
<homset -14 -> -13 with group d8>
gap> for e in hs1413 do  Print(e,", "); od;  Print( "\n");
[(2,3) : -14 -> -13], [(1,2,4,3) : -14 -> -13], [(1,4,2) : -14 -> -13], [
(1,3,4) : -14 -> -13], [(2,4,3) : -14 -> -13], [(1,2,3) : -14 -> -13], [
(1,4) : -14 -> -13], [(1,3,4,2) : -14 -> -13], 
gap> Hd8b := SubgroupoidWithRays( Hs4, d8, [(),(1,2,3),(1,2,4)] );
single piece groupoid with rays: < d8, [ -14, -13, -12 ],
[ (), (1,2,3), (1,2,4) ] >
gap> Hd8a = Hd8b; 
true
gap> RaysOfGroupoid( Hd8b ); 
[ (), (1,2,3), (1,2,4) ]
gap> Parent( Hd8a );
Hs4
gap> Ancestor( Hd8a ); 
Gs4
gap> Fd8a := FullSubgroupoid( Hd8a, [-14,-13]);
single piece groupoid with rays: < d8, [ -14, -13 ], [ (), (2,3) ] >
gap> Fd8b := FullSubgroupoid( Hd8a, [-13,-12]);
single piece groupoid with rays: < Group( [ (1,3,2,4), (1,2) ] ), 
[ -13, -12 ], [ (), (2,4,3) ] >
gap> Fd8a := FullSubgroupoid( Hd8a, [-13,-12] );            
single piece groupoid with rays: < Group( [ (1,3,2,4), (1,2) ] ), 
[ -13, -12 ], [ (), (2,4,3) ] >
gap> Kd8a := SubgroupoidWithRays( Fd8a, k4, [ (), (1,3) ] ); 
single piece groupoid with rays: < k4, [ -13, -12 ], [ (), (1,3) ] >

4.4 Left, right and double cosets

4.4-1 RightCoset

If U is a wide subgroupoid of G, the right cosets Ug of U in G are the equivalence classes for the relation on the elements of G where g1 is related to g2 if and only if g2 = u*g1 for some element u of U. The right coset containing g is written Ug. These right cosets partition the costars of G and, in particular, the costar U1_o of U at o, so that (unlike groups) U is itself a coset only when G has a single object.

The right coset representatives for U in G form a list containing one groupoid element for each coset where, in a particular piece of U, the group element chosen is the right coset representative of the group of U in the group of G.

Similarly, the left cosets gU refine the stars of G, while double cosets are unions of left cosets and of right cosets. The operation LeftCosetRepresentativesFromObject( G, U, obj ) is used in Chapter 4, and returns only those representatives which have tail at obj.

As with stars and homsets, these cosets are implemented with representation IsHomsetCosetsRep and provided with an iterator. Note that, when U has more than one piece, cosets may have differing lengths.

gap> re2 := RightCoset( Gd8, Ud8, e2 );
RightCoset(single piece groupoid: < c4, [ -8, -7 ] >,[(1,3) : -8 -> -7])
gap> for x in re2 do Print( x, "\n" ); od;
[(1,3) : -8 -> -7]
[(1,3) : -7 -> -7]
[(2,4) : -8 -> -7]
[(2,4) : -7 -> -7]
[(1,4)(2,3) : -8 -> -7]
[(1,4)(2,3) : -7 -> -7]
[(1,2)(3,4) : -8 -> -7]
[(1,2)(3,4) : -7 -> -7]
gap> rcrd8 := RightCosetRepresentatives( Gd8, Ud8 );
[ [() : -9 -> -9], [() : -9 -> -8], [() : -9 -> -7], [(2,4) : -9 -> -9],
  [(2,4) : -9 -> -8], [(2,4) : -9 -> -7], [() : -8 -> -9], [() : -8 -> -8],
  [() : -8 -> -7], [(2,4) : -8 -> -9], [(2,4) : -8 -> -8], [(2,4) : -8 -> -7]
 ]
gap> lcr7 := LeftCosetRepresentativesFromObject( Gd8, Ud8, -7 );
[ [() : -7 -> -9], [(2,4) : -7 -> -9], [() : -7 -> -8], [(2,4) : -7 -> -8] ]

4.5 Conjugation

4.5-1 ConjugateGroupoidElement

When e2 = c : p -> q and e1 has group element b, the conjugate e1^e2 has a complicated definition, but may be remembered as follows. All objects are fixed except p,q, which are interchanged. For p,q as source, multiply b on the left by c^-1,c respectively; and for p,q as target, multiply b on the right by c,c^-1. This product gives the group element of the conjugate. The details of this construction may be found in [AW10].

(Note that it is more desirable to use the command e1^e2, but it has not yet been possible to get this to work!)

gap> x := GroupoidElement( Gd8, (1,3), -9, -9 );; 
gap> y := GroupoidElement( Gd8, (1,2,3,4), -8, -9 );; 
gap> z := GroupoidElement( Gd8, (1,2)(3,4), -9, -7 );; 
gap> ##  conjugation with elements x, y, and z in Gd8: 
gap> ConjugateGroupoidElement(x,y);
[(2,4) : -8 -> -8]
gap> ConjugateGroupoidElement(x,z);
[(2,4) : -7 -> -7]
gap> ConjugateGroupoidElement(y,x);
[() : -8 -> -9]
gap> ConjugateGroupoidElement(y,z);
[(2,4) : -8 -> -7]
gap> ConjugateGroupoidElement(z,x);
[(1,4,3,2) : -9 -> -7]
gap> ConjugateGroupoidElement(z,y);
[(2,4) : -8 -> -7]

4.5-2 SinglePieceGroupoidByGenerators

A set of groupoid elements generates a groupoid by taking all possible products and inverses. So far, the only implementation is for the case of loops generating a group at an object o andf a set of rays from o, where o is not the least object. A suitably large supergroupoid, which must be a direct product with a complete graph, should be provided. This is the case needed for ConjugateGroupoid in the following section. Other cases will be added as time permits.

gap> u := GroupoidElement( Gs4, (1,2,3), -15, -13 ); 
[(1,2,3) : -15 -> -13]
gap> gensa := GeneratorsOfGroupoid( Hd8a );
[ [(1,2,3,4) : -14 -> -14], [(1,3) : -14 -> -14], [(2,3) : -14 -> -13], 
  [(3,4) : -14 -> -12] ]
gap> imsa := List( gensa, g -> ConjugateGroupoidElement( g, u ) ); 
[ [(1,2,3,4) : -14 -> -14], [(1,3) : -14 -> -14], [(1,3) : -14 -> -15], 
  [(3,4) : -14 -> -12] ]
gap> C := SinglePieceGroupoidByGenerators( Gs4, imsa ); 
single piece groupoid with rays: < Group( [ (1,4,3,2), (1,3) ] ), 
[ -15, -14, -12 ], [ (), (1,3), (1,4,3) ] >

4.5-3 ConjugateGroupoid

When H is a subgroupoid of a groupoid G and e is an element of G, then the conjugate of H by e is th4e subgroupoid generated by the conjugates of the generators of H.

gap> ConjugateGroupoid( Hd8a, u^-1 ); 
single piece groupoid with rays: < Group( [ (1,4,3,2), (1,3) ] ), 
[ -15, -14, -12 ], [ (), (1,3), (1,4,3) ] >

More examples of all these operations may be found in the example file gpd/examples/gpd.g.

generated by GAPDoc2HTML