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', so we use the term single piece.
The simplest form for a single piece groupoid is the direct product of a group and a complete digraph, and so is determined by a set of objects obs = Ω (the least of which is the root object), and a root group grp = G. Then the elements of the groupoid are arrows g : o_1 -> o_2, stored as triples [g,o1,o2], where g ∈ G and o_1,o_2 ∈ Ω. The objects will generally be chosen to be consecutive negative integers, but any suitable ordered set is acceptable, and `consecutive' is not a requirement. The root group will usually be taken to be a permutation group, but pc-groups, fp-groups and matrix groups are also supported.
A group may be considered as 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.
The underlying digraph of a single piece groupoid is a regular, complete digraph on the object set Ω with |G| arrows from any one object to any other object. It will be convenient to specify a set of rays consisting of |Ω| arrows r_i : o_1 -> o_i, where o_1 is the root object and r_1 is the identity in G. In the simplest examples all the r_i will be identity elements, but rays are useful when forming subgroupoids (see SubgroupoidWithRays (4.3-2)).
A groupoid is homogeneous if it has two of more isomorphic pieces, with identical groups. The special case of homogeneous, discrete groupoids, where each piece has a single object, is given its own representation. These are used in the XMod package as the source of a crossed modules of groupoids.
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].
‣ SinglePieceGroupoid( grp, obs ) | ( operation ) |
‣ Groupoid( args ) | ( function ) |
‣ DomainWithSingleObject( gp, obj ) | ( operation ) |
The simplest construction of a groupoid is as the direct product of a group and a complete digraph. Such a groupoid will be called a standard groupoid. Many subgroupoids of such a groupoid do not have this simple form, and will be considered in section 4.3. The global function Groupoid will normally find the appropriate constructor to call, the options being:
the object group, a set of objects;
a group being converted to a groupoid, a single object;
a list of groupoids which have already been constructed (see 4.1-4).
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" );
‣ ObjectList( gpd ) | ( attribute ) |
‣ RootObject( gpd ) | ( attribute ) |
‣ RootGroup( gpd ) | ( attribute ) |
‣ ObjectGroup( gpd, obj ) | ( operation ) |
The ObjectList of a groupoid is the sorted list of its objects. The RootObject in a single-piece groupoid is the object with the least label. A loop is an arrow of the form g : o -> o, and the loops at a particular object o form a group, the ObjectGroup at o. The RootGroup is the ObjectGroup at the RootObject.
In the example, the groupoids Gf2c6 and Gabc illustrate that the objects need not be integers.
gap> ObjectList( Gs4 ); [ -15 .. -11 ] gap> f2 := FreeGroup(2);; gap> Gf2c6 := Groupoid( c6, GeneratorsOfGroup(f2) ); single piece groupoid: < c6, [ f1, f2 ] > gap> Arrow( Gf2c6, (5,7,6), f2.1, f2.2 ); [(5,7,6) : f1 -> f2] gap> Gabc := Groupoid( d8, [ "a", "b", "c" ] ); single piece groupoid: < d8, [ "a", "b", "c" ] > gap> Arrow( Gabc, (2,4), "c", "b" ); [(2,4) : c -> b]
‣ IsPermGroupoid( gpd ) | ( property ) |
‣ IsPcGroupoid( gpd ) | ( property ) |
‣ IsFpGroupoid( gpd ) | ( property ) |
‣ IsMatrixGroupoid( gpd ) | ( property ) |
‣ IsFreeGroupoid( gpd ) | ( property ) |
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 and also a free groupoid, Gq8 is a pc-groupoid, and Ggl43 is a matrix groupoid. See section 5.7 for matrix representations of groupoids.
gap> f2 := FreeGroup( 2 );; gap> Gf2 := Groupoid( f2, -22 );; gap> SetName( f2, "f2" ); SetName( Gf2, "Gf2" ); gap> q8 := QuaternionGroup( 8 );; gap> Gq8 := Groupoid( q8, [ -18, -17 ] );; gap> SetName( q8, "q8" ); SetName( Gq8, "Gq8" ); gap> gl43 := SpecialLinearGroup( 4, 3 );; gap> Ggl43 := SinglePieceGroupoid( gl43, [ -25..-21 ] );; gap> SetName( gl43, "gl43" ); SetName( Ggl43, "Ggl43" ); gap> [ IsMatrixGroupoid( Ggl43 ), IsFpGroupoid( Gf2 ), IsFreeGroupoid( Gf2 ), > IsPcGroupoid( Gq8 ), IsPermGroupoid( Gs4 ) ]; [ true, true, true, true, true ]
‣ UnionOfPieces( pieces ) | ( operation ) |
‣ Pieces( gpd ) | ( attribute ) |
‣ Size( gpd ) | ( attribute ) |
‣ ReplaceOnePieceInUnion( U, old_piece, new_piece ) | ( operation ) |
When a groupoid consists of two or more pieces, we require their object lists to be disjoint. The operation UnionOfPieces and the attribute Pieces, introduced in section 2.5, are also used for groupoids. The pieces are sorted by the least object in their object lists. The ObjectList is the sorted concatenation of the objects in the pieces.
The Size of a groupoid is the number of its arrows. For a single piece groupoid, this is the product of the size of the group with the square of the number of objects. For a non-connected groupoid, the size is the sum of the sizes of its pieces.
One of the pieces in a groupoid may be replaced by an alternative piece using the operation ReplaceOnePieceInUnion. The old_piece may be either the position of the piece to be replaced, or one of the pieces in U. The objects in the new piece may or may not overlap the objects in the piece being removed -- we just require that the object lists in the new union are disjoint.
gap> U3 := UnionOfPieces( [ Gc6, Gd8, Gs4 ] );; 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) ]; [ 600, 72, 6, 678 ] gap> [ Size(Gf2), Size(Gq8), Size(U2) ]; [ infinity, 32, infinity ] gap> U5 := UnionOfPieces( [ U3, U2 ] ); groupoid with 5 pieces: [ Gf2, Gq8, Gs4, Gd8, Gc6 ] gap> Display( U5 ); groupoid with 5 pieces: < objects: [ -22 ] group: f2 = <[ f1, f2 ]> > < objects: [ -18, -17 ] group: q8 = <[ x, y, y2 ]> > < 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> ## in the next example the object lists are not disjoint gap> UnionOfPieces( [ Gf2, Ggl43 ] ); fail gap> V3 := ReplaceOnePieceInUnion( U3, Gd8, Gq8 ); groupoid with 3 pieces: [ Gq8, Gs4, Gc6 ] gap> ObjectList( V3 ); [ -18, -17, -15, -14, -13, -12, -11, -6 ] gap> U3 = V3; false gap> V2 := ReplaceOnePieceInUnion( U2, 2, Gd8 ); groupoid with 2 pieces: [ Gf2, Gd8 ]
‣ HomogeneousGroupoid( gpd, oblist ) | ( operation ) |
‣ HomogeneousDiscreteGroupoid( gp, obs ) | ( operation ) |
‣ PieceIsomorphisms( hgpd ) | ( attribute ) |
Special functions are provided for the case where a groupoid has more than one connected component, and when these components are identical except for their object sets. Such groupoids are said to be homogeneous.
The operation HomogeneousGroupoid is used when the components each contain more than one object. The arguments consist of a single piece groupoid gpd and a list of lists of objects oblist, each of whose lists has the same length as the object list obs of gpd. Note that gpd is not included as one of the pieces in the output unless obs is included as one of the lists in oblist.
The operation HomogeneousDiscreteGroupoid is used when the components each have a single object. In this case the first argument is just a group -- the root group for each component. These groupoids are used in the XMod package as the source of many crossed modules of groupoids.
Both types of groupoid have the property IsHomogeneousDomainWithObjects. In the latter case a separate representation IsHomogeneousDiscreteGroupoidRep is used.
gap> Hd8 := HomogeneousGroupoid( Gd8, > [ [-20,-19,-18], [-12,-11,-10], [-16,-15,-14] ] ); homogeneous groupoid with 3 pieces: 1: single piece groupoid: < d8, [ -20, -19, -18 ] > 2: single piece groupoid: < d8, [ -16, -15, -14 ] > 3: single piece groupoid: < d8, [ -12, -11, -10 ] > gap> Size(Hd8); ## 8x3x3 + 8x3x3 216 gap> IsHomogeneousDomainWithObjects( Hd8 ); true gap> PieceIsomorphisms( Hd8 ); [ groupoid homomorphism : [ [ [(1,2,3,4) : -20 -> -20], [(1,3) : -20 -> -20], [() : -20 -> -19], [() : -20 -> -18] ], [ [(1,2,3,4) : -16 -> -16], [(1,3) : -16 -> -16], [() : -16 -> -15], [() : -16 -> -14] ] ], groupoid homomorphism : [ [ [(1,2,3,4) : -20 -> -20], [(1,3) : -20 -> -20], [() : -20 -> -19], [() : -20 -> -18] ], [ [(1,2,3,4) : -12 -> -12], [(1,3) : -12 -> -12], [() : -12 -> -11], [() : -12 -> -10] ] ] ] gap> Hc6 := HomogeneousDiscreteGroupoid( c6, [-7..-4] ); homogeneous, discrete groupoid: < c6, [ -7 .. -4 ] > gap> Size( Hc6 ); ## 6x4 24 gap> RepresentationsOfObject( Gd8 ); [ "IsComponentObjectRep", "IsAttributeStoringRep", "IsMWOSinglePieceRep" ] gap> RepresentationsOfObject( Hd8 ); [ "IsComponentObjectRep", "IsAttributeStoringRep", "IsPiecesRep" ] gap> RepresentationsOfObject( Hc6 ); [ "IsComponentObjectRep", "IsAttributeStoringRep", "IsHomogeneousDiscreteGroupoidRep" ] gap> ktpo := KnownTruePropertiesOfObject( Hc6 );; gap> ans := > [ "IsDuplicateFree", "IsAssociative", "IsCommutative", > "IsDiscreteDomainWithObjects", "IsHomogeneousDomainWithObjects" ];; gap> ForAll( ans, a -> ( a in ktpo ) ); true
‣ DirectProductOp( list, gpd ) | ( operation ) |
‣ Projection( gpd, pos ) | ( operation ) |
‣ Embedding( gpd, pos ) | ( operation ) |
The direct product of groupoids G,H has as group the direct product of the groups in G and H and as object list the cartesian product of their object lists. As usual with DirectProductOp the two parameters are a list of groupoids followed by the first entry in the list.
gap> prod := DirectProductOp( [Gd8,Gc6], Gd8 ); single piece groupoid: < Group( [ (1,2,3,4), (1,3), (5,6,7)(8,9) ] ), [ [ -9, -6 ], [ -8, -6 ], [ -7, -6 ] ] > gap> Projection( prod, 1 ); groupoid homomorphism : [ [ [(1,2,3,4) : [ -9, -6 ] -> [ -9, -6 ]], [(1,3) : [ -9, -6 ] -> [ -9, -6 ]] , [(5,6,7)(8,9) : [ -9, -6 ] -> [ -9, -6 ]], [() : [ -9, -6 ] -> [ -8, -6 ]], [() : [ -9, -6 ] -> [ -7, -6 ]] ], [ [(1,2,3,4) : -9 -> -9], [(1,3) : -9 -> -9], [() : -9 -> -9], [() : -9 -> -8], [() : -9 -> -7] ] ] gap> Embedding( prod, 2 ); groupoid homomorphism : [ [ [(5,6,7)(8,9) : -6 -> -6] ], [ [(5,6,7)(8,9) : [ -9, -6 ] -> [ -9, -6 ]] ] ] gap> DirectProductInfo( prod ); rec( embeddings := [ , groupoid homomorphism : [ [ [(5,6,7)(8,9) : -6 -> -6] ], [ [(5,6,7)(8,9) : [ -9, -6 ] -> [ -9, -6 ]] ] ] ], first := Gd8, groupoids := [ Gd8, Gc6 ], groups := [ d8, c6 ], objectlists := [ [ -9, -8, -7 ], [ -6 ] ], projections := [ groupoid homomorphism : [ [ [(1,2,3,4) : [ -9, -6 ] -> [ -9, -6 ]], [(1,3) : [ -9, -6 ] -> [ -9, -6 ]], [(5,6,7)(8,9) : [ -9, -6 ] -> [ -9, -6 ]], [() : [ -9, -6 ] -> [ -8, -6 ]], [() : [ -9, -6 ] -> [ -7, -6 ]] ], [ [(1,2,3,4) : -9 -> -9], [(1,3) : -9 -> -9], [() : -9 -> -9], [() : -9 -> -8], [() : -9 -> -7] ] ] ] )
‣ GroupoidElement( gpd, elt, tail, head ) | ( operation ) |
‣ ElementOfArrow( elt ) | ( operation ) |
‣ TailOfArrow( elt ) | ( operation ) |
‣ HeadOfArrow( elt ) | ( operation ) |
The operation GroupoidElement is a synonym for the operation Arrow, as described in subsection 2.1-3. To recapitulate, an arrow e consists of a group element, ElementOfArrow(e); the tail (source) object, TailOfArrow(e); and the head (target) object, HeadOfArrow(e). Arrows have a partial composition: two arrows may be multiplied when the head of the first coincides with the tail of the second. If an attempt is made to multiply arrows where this condition does not hold, then the value fail is returned.
gap> e1 := GroupoidElement( Gd8, (1,2,3,4), -9, -8 ); [(1,2,3,4) : -9 -> -8] gap> e2 := Arrow( Gd8, (1,3), -8, -7 ); [(1,3) : -8 -> -7] gap> Print( [ ElementOfArrow(e1), TailOfArrow(e1), HeadOfArrow(e1) ], "\n" ); [ (1,2,3,4), -9, -8 ] gap> e1e2 := e1*e2; [(1,2)(3,4) : -9 -> -7] gap> e2*e1; fail gap> e3 := Arrow( Gd8, (2,4), -7, -9 );; gap> loop := e1e2*e3; [(1,4,3,2) : -9 -> -9] gap> loop^2; [(1,3)(2,4) : -9 -> -9]
‣ IdentityArrow( gpd, obj ) | ( operation ) |
The identity arrow 1_o of G at object o is (e:o -> o) where e is the identity element in the object group. The inverse arrow 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 := IdentityArrow( Gd8, -8 ); [() : -8 -> -8] gap> [ e1*i8, i8*e1, e1^-1]; [ [(1,2,3,4) : -9 -> -8], fail, [(1,4,3,2) : -8 -> -9] ]
‣ Order( arr ) | ( attribute ) |
A groupoid element is a loop when the tail and head coincide. In this case the order of the element is defined to be the order of its group element.
gap> [ i8, loop ]; [ [() : -8 -> -8], [(1,4,3,2) : -9 -> -9] ] gap> [ Order( i8 ), Order(loop) ]; [ 1, 4 ]
‣ ObjectStar( gpd, obj ) | ( operation ) |
‣ ObjectCostar( gpd, obj ) | ( operation ) |
‣ Homset( gpd, tail, head ) | ( operation ) |
The star at obj is the set of arrows which have obj as tail, while the costar is the set of arrows which have obj as head. The homset from obj1 to obj2 is the set of arrows with the specified tail and head, and so is bijective with the elements of the object groups. Thus every star and every costar is a union of homsets. The identity arrow 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 unneccessarily 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 vertex group d8> gap> Size( star9 ); 24 gap> ## PrintSelection( star9, 19, 1 ); gap> iter := Iterator( star9 );; gap> for i in [1..18] do a := NextIterator( iter ); od; gap> for i in [19..24] do Print( i, " : ", NextIterator( iter ), "\n" ); od; 19 : [(1,2,3,4) : -9 -> -9] 20 : [(1,2,3,4) : -9 -> -8] 21 : [(1,2,3,4) : -9 -> -7] 22 : [(1,2)(3,4) : -9 -> -9] 23 : [(1,2)(3,4) : -9 -> -8] 24 : [(1,2)(3,4) : -9 -> -7] gap> costar6 := ObjectCostar( Gc6, -6 ); <costar at -6 with vertex group c6> gap> Size( costar6 ); 6 gap> hsetq8 := Homset( Gq8, -18, -17 ); <homset -18 -> -17 with head group q8> gap> Perform( hsetq8, Display ); [<identity> of ... : -18 -> -17] [y2 : -18 -> -17] [y : -18 -> -17] [y*y2 : -18 -> -17] [x : -18 -> -17] [x*y2 : -18 -> -17] [x*y : -18 -> -17] [x*y*y2 : -18 -> -17]
‣ Subgroupoid( args ) | ( function ) |
‣ IsSubgroupoid( gpd, sgpd ) | ( operation ) |
‣ IsWideSubgroupoid( gpd, sgpd ) | ( operation ) |
A subgroupoid S of a groupoid G has as objects some subset of the objects of G. It is wide in G if both groupoids have the same object set. It is full if, for any two objects in S, the Homset is the same as that in G. The arrows of S are a subset of those of G, closed under multiplication and with tail and head in the chosen object set.
There are a variety of constructors for a subgroupoid of a standard groupoid, as described in for following sections. The global function Subgroupoid should call the operation appropriate to the parameters provided.
‣ SubgroupoidWithRays( gpd, sgp, rays ) | ( operation ) |
‣ RaysOfGroupoid( gpd ) | ( operation ) |
‣ RayArrowsOfGroupoid( gpd ) | ( operation ) |
If groupoid G is of type IsDirectProductWithCompleteDigraph with group g and n objects, then a typical wide subgroupoid H of G is formed by choosing a subgroup h of g to be the object group at the root object q, and an arrow r : q -> p for each of the objects p. The chosen loop arrow at q must be the identity arrow. These n arrows are called the ray arrows of the subgroupoid. The arrows in the homset from p to p' have the form r^-1xr' where r,r' are the rays from q to p,p' respectively, and x ∈ h.
The operation RayArrowsOfGroupoid returns a list of arrows, one for each object, while the operation RaysOfGroupoid returns the list of group elements in these arrows.
Note that it is also possible to construct a subgroupoid with rays of a subgroupoid with rays.
In the following example we construct a subgroupoid Ua4 of the groupoid Gs4, and then a second subgroupoid Uc3. The initial standard groupoid Gs4 is set as the parent for both Ua4 and Uc3.
gap> a4 := Subgroup( s4, [ (1,2,3), (2,3,4) ] );; gap> SetName( a4, "a4" ); gap> Ua4 := SubgroupoidWithRays( Gs4, a4, [(),(1,2),(2,3),(3,4),(1,4)] ); single piece groupoid with rays: < a4, [ -15 .. -11 ], [ (), (1,2), (2,3), (3,4), (1,4) ] > gap> IsSubgroupoid( Gs4, Ua4 ); true gap> IsWideSubgroupoid( Gs4, Ua4 ); true gap> RaysOfGroupoid( Ua4 ); [ (), (1,2), (2,3), (3,4), (1,4) ] gap> RayArrowsOfGroupoid( Ua4 ); [ [() : -15 -> -15], [(1,2) : -15 -> -14], [(2,3) : -15 -> -13], [(3,4) : -15 -> -12], [(1,4) : -15 -> -11] ] gap> c3 := Subgroup( a4, [ (1,2,3) ] );; gap> SetName( c3, "c3" ); gap> Uc3 := SubgroupoidWithRays( Ua4, c3, > [ (), (1,2,3,4), (1,3), (2,4), (1,4,3,2) ] ); single piece groupoid with rays: < c3, [ -15 .. -11 ], [ (), (1,2,3,4), (1,3), (2,4), (1,4,3,2) ] > gap> ObjectGroup( Uc3, -14 ); Group([ (2,3,4) ]) gap> Ha4 := HomogeneousGroupoid( Ua4, [ [-25..-21], [-35..-31] ] ); homogeneous groupoid with 2 pieces: 1: single piece groupoid with rays: < a4, [ -35 .. -31 ], [ (), (1,2), (2,3), (3,4), (1,4) ] > 2: single piece groupoid with rays: < a4, [ -25 .. -21 ], [ (), (1,2), (2,3), (3,4), (1,4) ] >
‣ SubgroupoidByObjects( gpd, obs ) | ( operation ) |
‣ SubgroupoidBySubgroup( gpd, sgp ) | ( attribute ) |
The SubgroupoidByObjects of a groupoid gpd on a subset obs of its objects contains all the arrows of gpd with tail and head in obs.
The SubgroupoidBySubgroup of a connected groupoid gpd determinded by a subgroup sgp of the root group is the wide subgroupoid with root group sgp and containing the rays of gpd.
gap> Va4 := SubgroupoidByObjects( Ua4, [-14,-13,-12] ); single piece groupoid with rays: < Group( [ (1,3,2), (1,3,4) ] ), [ -14, -13, -12 ], [ (), (1,3,2), (1,2)(3,4) ] > gap> Vc3 := SubgroupoidBySubgroup( Va4, c3 ); single piece groupoid with rays: < c3, [ -14, -13, -12 ], [ (), (1,3,2), (1,2)(3,4) ] >
‣ SubgroupoidByPieces( gpd, pieces ) | ( operation ) |
The most general way to construct a subgroupoid is to use the operation SubgroupoidByPieces. Its two parameters are a groupoid and a list of pieces, each piece being specified either as a list [sgp,obs], where sgp is a subgroup of the root group in that piece, and obs is a subset of the objects in that piece, or as a list [sgp,obs,rays] when a set of rays is required.
gap> Display(Gd8); single piece groupoid: Gd8 objects: [ -9, -8, -7 ] group: d8 = <[ (1,2,3,4), (1,3) ]> gap> c4 := Subgroup( d8, [ (1,2,3,4) ] );; gap> k4 := Subgroup( d8, [ (1,3), (2,4) ] );; gap> SetName( c4, "c4" ); SetName( k4, "k4" ); gap> Ud8 := Subgroupoid( Gd8, [ [ k4, [-9] ], [ c4, [-8,-7] ] ] );; gap> SetName( Ud8, "Ud8" ); gap> Display( Ud8 ); groupoid with 2 pieces: < objects: [ -9 ] group: k4 = <[ (1,3), (2,4) ]> > < objects: [ -8, -7 ] group: c4 = <[ (1,2,3,4) ]> > gap> [ Parent( Ud8 ), IsWideSubgroupoid( Gd8, Ud8 ) ]; [ Gd8, true ] gap> U2; groupoid with 2 pieces: [ Gf2, Gq8 ] gap> genf2b := List( GeneratorsOfGroup(f2), g -> g^2 ); [ f1^2, f2^2 ] gap> f2b := Subgroup( f2, genf2b );; gap> SU2 := SubgroupoidByPieces( U2, [ [q8,[-17]], [f2b,[-22]] ] ); groupoid with 2 pieces: 1: single piece groupoid: < Group( [ f1^2, f2^2 ] ), [ -22 ] > 2: single piece groupoid: < q8, [ -17 ] > gap> IsWideSubgroupoid( U2, SU2 ); false gap> IsSubgroupoid( Gf2, Groupoid( f2b, [-22] ) ); true
‣ FullTrivialSubgroupoid( gpd ) | ( attribute ) |
‣ DiscreteTrivialSubgroupoid( gpd ) | ( attribute ) |
A trivial subgroupoid has trivial object groups, but need not be discrete. A single piece trivial groupoid is sometimes called a tree groupoid. (The term identity subgroupoid was used in versions up to 1.14.)
gap> FullTrivialSubgroupoid( Ud8 ); groupoid with 2 pieces: 1: single piece groupoid: < id(k4), [ -9 ] > 2: single piece groupoid: < id(c4), [ -8, -7 ] > gap> DiscreteTrivialSubgroupoid( Ud8 ); groupoid with 3 pieces: 1: single piece groupoid: < id(k4), [ -9 ] > 2: single piece groupoid: < id(c4), [ -8 ] > 3: single piece groupoid: < id(c4), [ -7 ] >
‣ DiscreteSubgroupoid( gpd, sgps, obs ) | ( operation ) |
‣ MaximalDiscreteSubgroupoid( gpd ) | ( attribute ) |
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.
gap> U3; groupoid with 3 pieces: [ Gs4, Gd8, Gc6 ] gap> DiscreteSubgroupoid( U3, [ a4, a4, c4, k4 ], [-15,-11,-9,-7] ); groupoid with 4 pieces: 1: single piece groupoid: < a4, [ -15 ] > 2: single piece groupoid: < a4, [ -11 ] > 3: single piece groupoid: < c4, [ -9 ] > 4: single piece groupoid: < k4, [ -7 ] > gap> MaximalDiscreteSubgroupoid( Vc3 ); groupoid with 3 pieces: 1: single piece groupoid: < c3, [ -14 ] > 2: single piece groupoid: < Group( [ (1,2,3) ] ), [ -13 ] > 3: single piece groupoid: < Group( [ (1,4,2) ] ), [ -12 ] >
‣ SinglePieceSubgroupoidByGenerators( parent, gens ) | ( operation ) |
A set of arrows 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 together with 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 digraph, should be provided. This is the case needed for ConjugateGroupoid in section 4.5-2. Other cases will be added as time permits.
gap> a1 := Arrow( Ua4, (2,3,4), -15, -15 ); gap> a2 := Arrow( Ua4, (1,2,3,4), -15, -13 ); gap> a3 := Arrow( Ua4, (2,3), -15, -11 ); gap> SinglePieceSubgroupoidByGenerators( Ua4, [a1,a2,a3] ); single piece groupoid with rays: < Group( [ (2,3,4) ] ), [ -15, -13, -11 ], [ (), (1,2,3,4), (2,3) ] >
‣ RightCoset( G, U, elt ) | ( operation ) |
‣ RightCosetRepresentatives( G, U ) | ( operation ) |
‣ RightCosets( G, U ) | ( operation ) |
‣ LeftCoset( G, U, elt ) | ( operation ) |
‣ LeftCosetRepresentatives( G, U ) | ( operation ) |
‣ LeftCosetRepresentativesFromObject( G, U, obj ) | ( operation ) |
‣ LeftCosets( G, U ) | ( operation ) |
‣ DoubleCoset( G, U, V, elt ) | ( operation ) |
‣ DoubleCosetRepresentatives( G, U, V ) | ( operation ) |
‣ DoubleCosets( G, U, V ) | ( operation ) |
If U is a subgroupoid of G, the right cosets Ug of U in G are the equivalence classes for the relation on the arrows of G where g1 is related to g2 if and only if g2 = u*g1 for some arrow 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 object o. So (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 arrow 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 and right cosets. The operation LeftCosetRepresentativesFromObject( G, U, obj ) is used in Chapter 6 , 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.
In the example the representative for the right coset re2 is the tenth one in the printed list rcrd8, namely [(2,4):-7->-7].
Note that operations for double cosets are a recent addition, and may need further work.
gap> re2 := RightCoset( Gd8, Ud8, e2 ); <right coset of single piece groupoid: < c4, [ -8, -7 ] > with representative [(1,3) : -8 -> -7]> gap> Perform( re2, Display ); [(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], [(1,4,3,2) : -9 -> -9], [() : -9 -> -8], [(1,4,3,2) : -9 -> -8], [() : -9 -> -7], [(1,4,3,2) : -9 -> -7], [() : -8 -> -8], [(2,4) : -8 -> -8], [() : -7 -> -7], [(2,4) : -7 -> -7], [() : -8 -> -9], [(2,4) : -8 -> -9] ] gap> le2 := LeftCoset( Gd8, Ud8, e2 ); <left coset of single piece groupoid: < c4, [ -8, -7 ] > with representative [ (1,3) : -8 -> -8]> gap> Perform( le2, Display ); [(1,3) : -8 -> -8] [(1,3) : -8 -> -7] [(2,4) : -8 -> -8] [(2,4) : -8 -> -7] [(1,4)(2,3) : -8 -> -8] [(1,4)(2,3) : -8 -> -7] [(1,2)(3,4) : -8 -> -8] [(1,2)(3,4) : -8 -> -7] gap> lcrd8 := LeftCosetRepresentatives( Gd8, Ud8 ); [ [() : -9 -> -9], [(1,2,3,4) : -9 -> -9], [() : -8 -> -9], [(1,2,3,4) : -8 -> -9], [() : -7 -> -9], [(1,2,3,4) : -7 -> -9], [() : -8 -> -8], [(2,4) : -8 -> -8], [() : -7 -> -7], [(2,4) : -7 -> -7], [() : -9 -> -8], [(2,4) : -9 -> -8] ] gap> lcr7 := LeftCosetRepresentativesFromObject( Gd8, Ud8, -7 ); [ [() : -7 -> -9], [(1,2,3,4) : -7 -> -9], [() : -7 -> -7], [(2,4) : -7 -> -7] ] gap> de2 := DoubleCoset( Gd8, Ud8, Ud8, e2 ); <double coset of [ single piece groupoid: < c4, [ -8, -7 ] >, single piece groupoid: < c4, [ -8, -7 ] > ] with representative [(1,3) : -8 -> -8]> gap> Perform( de2, Display ); [(2,4) : -8 -> -8] [(2,4) : -8 -> -7] [(2,4) : -7 -> -8] [(2,4) : -7 -> -7] [(1,3) : -8 -> -8] [(1,3) : -8 -> -7] [(1,3) : -7 -> -8] [(1,3) : -7 -> -7] [(1,2)(3,4) : -8 -> -8] [(1,2)(3,4) : -8 -> -7] [(1,2)(3,4) : -7 -> -8] [(1,2)(3,4) : -7 -> -7] [(1,4)(2,3) : -8 -> -8] [(1,4)(2,3) : -8 -> -7] [(1,4)(2,3) : -7 -> -8] [(1,4)(2,3) : -7 -> -7] gap> dcrd8 := DoubleCosetRepresentatives( Gd8, Ud8, Ud8 ); [ [() : -9 -> -9], [(1,4,3,2) : -9 -> -9], [() : -9 -> -8], [() : -8 -> -9], [() : -8 -> -8], [(2,4) : -8 -> -8] ]
4.5-1 \^‣ \^( e1, e ) | ( operation ) |
Conjugation by an arrow e = (c : p -> q) is the groupoid inner automorphism (see section 5.6) defined as follows. There are two cases to consider. In the case p ≠ q,
objects p,q are interchanged, and the remaining objects are fixed;
loops at p,q: (b: p -> p) ↦ (b^c : q -> q) and (b: q -> q) ↦ (b^c^-1} : p -> p);
arrows between p and q: (b : p -> q) ↦ (c^-1bc^-1 : q -> p) and (b : q -> p) ↦ (cbc : p -> q);
costars at p,q: (b : r -> p) ↦ (bc : r -> q) and (b : r -> q) ↦ (bc^-1 : r -> p);
stars at p,q: (b : p -> r) ↦ (c^-1b : -> q) and (b : q -> r) ↦ (cb : p -> r);
the remaining arrows are unchanged.
In the case p=q,
all the objects are fixed;
loops at p are conjugated by c, so (b : p -> p) ↦ (b^c : p -> p);
the rest of the costar and star at p are permuted,
(b : r \to p) \mapsto (bc : r \to p) \quad\mbox{and}\quad (b : p \to r) \mapsto (c^{-1}b : p \to r);
the remaining arrows are unchanged.
The details of this construction may be found in section 3.2 of [AW10].
gap> x := Arrow( Gd8, (1,3), -9, -9 );; gap> y := Arrow( Gd8, (1,2,3,4), -8, -9 );; gap> z := Arrow( Gd8, (1,2)(3,4), -9, -7 );; gap> w := Arrow( Gd8, (1,2,3,4), -7, -8 );; gap> ## conjugation with elements x, y, and z in Gd8: gap> x^y; [(2,4) : -8 -> -8] gap> x^z; [(2,4) : -7 -> -7] gap> y^x; [() : -8 -> -9] gap> y^z; [(2,4) : -8 -> -7] gap> z^x; [(1,4,3,2) : -9 -> -7] gap> z^y; [(2,4) : -8 -> -7] gap> w^z [(1,3) : -9 -> -8]
‣ ConjugateGroupoid( gpd, e ) | ( operation ) |
When H is a subgroupoid of a groupoid G and a is an arrow of G, then the conjugate of H by a is the subgroupoid generated by the conjugates of the generators of H.
gap> Kd8 := SubgroupoidWithRays( Gs4, d8, [(),(1,2),(2,3),(3,4),(1,4)] ); single piece groupoid with rays: < d8, [ -15 .. -11 ], [ (), (1,2), (2,3), (3,4), (1,4) ] > gap> u := Arrow( Gs4, (1,2,3), -15, -14 ); [(1,2,3) : -15 -> -14] gap> ConjugateGroupoid( Kd8, u ); single piece groupoid with rays: < Group( [ (1,3,2,4), (1,2) ] ), [ -15, -14, -13, -12, -11 ], [ (), (1,2), (), (2,4,3), (1,4)(2,3) ] >
Here we describe an alternative way of constructing a connected groupoid. This section has been introduced in version 1.66 of the package, and so should be considered very experimental, and liable to change.
Object groups in a connected groupoid are isomorphic, so we may use a collection of isomorphisms to form a groupoid. Let G_1,G_2,...,G_n be isomorphic groups and, for 2 leqslant i leqslant n, let μ_i : G_1 -> G_i be isomorphisms. Then μ_ij = μ_i^-1*μ_j is an isomorphism from G_i to G_j. If we take {u_1,...,u_n} to be our set of objects, with G_i the object group at u_i, we may consider the arrows in the groupoid to have the form [[g_i,g_j] : u_i -> u_j] where g_i ∈ G_i and g_j = μ_ij(g_i) ∈ G_j. The product of [[g_i,g_j] : u_i -> u_j] and [[g'_j,g_k] : u_j -> u_k] is [[μ_ij^-1(g_jg'_j), μ_jk(g_jg'_j)] : u_i -> u_k].
‣ GroupoidByIsomorphisms( gp, obs, isos ) | ( operation ) |
‣ IsGroupoidByIsomorphisms( gpd ) | ( property ) |
The operation GroupoidByIsomorphisms takes a group G1 as root group; a set of n objects; and a set of n isomorphisms from the root group, where the first isomorphism should be the identity mapping on G1. The output is a single piece groupoid of type IsGroupoidByIsomorphisms. Its rays have the form [One(G1),One(Gi)] where Gi is the image of the i-th isomorphism.
In the example we first take three permutation groups isomorphic to the symmetric group S_3. There follows an isomorphic groupoid whose object groups are a permutation group; a pc-group and an fp-group.
gap> s3a := Group( (1,2), (2,3) );; gap> s3b := Group( (4,6,8)(5,7,9), (4,9)(5,8)(6,7) );; gap> s3c := Group( (4,6,8)(5,7,9), (5,9)(6,8) );; gap> SetName( s3a, "s3a" ); gap> ida := IdentityMapping( s3a );; gap> isoab := IsomorphismGroups( s3a, s3b );; gap> isoac := IsomorphismGroups( s3a, s3c );; gap> isos1 := [ ida, isoab, isoac ];; gap> G1 := GroupoidByIsomorphisms( s3a, [-3,-2,-1], isos1 );; gap> gens1 := GeneratorsOfGroupoid( G1 ); [ [[ (1,2), (1,2) ] : -3 -> -3], [[ (2,3), (2,3) ] : -3 -> -3], [[ (), () ] : -3 -> -2], [[ (), () ] : -3 -> -1] ] gap> x1 := ImageElm( isos1[2], (1,2) );; gap> a1 := Arrow( G1, [ (1,2), x1 ], -3, -2 ); [[ (1,2), (4,5)(6,9)(7,8) ] : -3 -> -2] gap> a1^-1; [[ (4,5)(6,9)(7,8), (1,2) ] : -2 -> -3] gap> y1 := ImageElm( isos1[2], (2,3) );; gap> z1 := ImageElm( isos1[3], (2,3) );; gap> b1 := Arrow( G1, [ y1, z1 ], -2, -1 ); [[ (4,9)(5,8)(6,7), (5,9)(6,8) ] : -2 -> -1] gap> c1 := a1*b1; [[ (1,3,2), (4,8,6)(5,9,7) ] : -3 -> -1] gap> isopc := IsomorphismPcGroup( s3a );; gap> s3p := Image( isopc );; gap> f2 := FreeGroup( 2 );; gap> s3f := f2/[ f2.1^3, f2.2^2, (f2.1*f2.2)^2 ];; gap> isofp := GroupHomomorphismByImages(s3a,s3f,[(1,2,3),(2,3)],[s3f.1,s3f.2]);; gap> isos2 := [ ida, isopc, isofp ];; gap> G2 := GroupoidByIsomorphisms( s3a, [-7,-6,-5], isos2 );; gap> gens2 := GeneratorsOfGroupoid( G2 ); [ [[ (1,2), (1,2) ] : -7 -> -7], [[ (2,3), (2,3) ] : -7 -> -7], [[ (), <identity> of ... ] : -7 -> -6], [[ (), <identity ...> ] : -7 -> -5] ] gap> x2 := ImageElm( isos2[2], (1,2) );; gap> a2 := Arrow( G2, [ (1,2), x2 ], -7, -6 ); [[ (1,2), f1*f2 ] : -7 -> -6] gap> a2^-1; [[ f1*f2, (1,2) ] : -6 -> -7] gap> y2 := ImageElm( isos2[2], (2,3) );; gap> z2 := ImageElm( isos2[3], (2,3) );; gap> b2 := Arrow( G2, [ y2, z2 ], -6, -5 ); [[ f1, f2^-1 ] : -6 -> -5] gap> c2 := a2*b2; [[ (1,3,2), f1^2 ] : -7 -> -5]
Let M be a monoid with G its maximal subgroup. We may form a groupoid with the elements of M as its objects and with arrows t -> t*g for all t ∈ M and g ∈ G.
This construction is used in the XMod package to construct the group-groupoid which corresponds to a crossed module or cat2-group.
‣ SinglePieceGroupoidWithRays( gp, obs, rays ) | ( operation ) |
When M is a group, G=M and the groupoid so constructed is a single piece which represents the regular representation of G. The ray from 1 to g is just g since 1*g=g.
gap> d8 := Group( (1,2,3,4), (1,3) );; gap> ed8 := Elements( d8 );; gap> rd8 := SinglePieceGroupoidWithRays( d8, ed8, ed8 ); single piece groupoid with rays: < Group( [ (1,2,3,4), (1,3) ] ), [ (), (2,4), (1,2)(3,4), (1,2,3,4), (1,3), (1,3)(2,4), (1,4,3,2), (1,4)(2,3) ], [ (), (2,4), (1,2)(3,4), (1,2,3,4), (1,3), (1,3)(2,4), (1,4,3,2), (1,4)(2,3) ] > gap> Display( Homset( rd8, (2,4), (1,3) ) ); [(1,3)(2,4) : (2,4) -> (1,3)] [(1,3) : (2,4) -> (1,3)] [() : (2,4) -> (1,3)] [(2,4) : (2,4) -> (1,3)] [(1,4,3,2) : (2,4) -> (1,3)] [(1,4)(2,3) : (2,4) -> (1,3)] [(1,2,3,4) : (2,4) -> (1,3)] [(1,2)(3,4) : (2,4) -> (1,3)]
‣ RightActionGroupoid( mon ) | ( operation ) |
‣ IsGroupoidWithMonoidObjects( gpd ) | ( property ) |
When M is a monoid, rather than a group, this construction produces several components. One of these has as objects the elements of the group G.
When M is a group, this operation gives the same result as SinglePieceGroupoidWithRays.
As a simple example we take a monoid M generated by two transformations of degree 4. The groupoid has 8 components, of which 3 have a single object and group C_2, while 5 have two objects and trivial group.
gap> t := Transformation( [1,1,2,3] );; u := Transformation( [1,2,4,3] );; gap> M := Monoid( t, u );; gap> rag := RightActionGroupoid( M ); groupoid with 8 pieces: 1: single piece groupoid with rays: < Group( [ IdentityTransformation, Transformation( [ 1, 2, 4, 3 ] ) ] ), [ Transformation( [ 1, 1, 1, 1 ] ) ], [ IdentityTransformation ] > 2: single piece groupoid with rays: < Group( [ IdentityTransformation, Transformation( [ 1, 2, 4, 3 ] ) ] ), [ Transformation( [ 1, 1, 1, 2 ] ) ], [ IdentityTransformation ] > 3: single piece groupoid with rays: < Group( [ IdentityTransformation ] ), [ Transformation( [ 1, 1, 1, 3 ] ), Transformation( [ 1, 1, 1 ] ) ], [ IdentityTransformation, Transformation( [ 1, 2, 4, 3 ] ) ] > 4: single piece groupoid with rays: < Group( [ IdentityTransformation, Transformation( [ 1, 2, 4, 3 ] ) ] ), [ Transformation( [ 1, 1, 2, 1 ] ) ], [ IdentityTransformation ] > 5: single piece groupoid with rays: < Group( [ IdentityTransformation ] ), [ Transformation( [ 1, 1, 2, 3 ] ), Transformation( [ 1, 1, 2 ] ) ], [ IdentityTransformation, Transformation( [ 1, 2, 4, 3 ] ) ] > 6: single piece groupoid with rays: < Group( [ IdentityTransformation ] ), [ Transformation( [ 1, 1, 3, 1 ] ), Transformation( [ 1, 1, 4, 1 ] ) ], [ IdentityTransformation, Transformation( [ 1, 2, 4, 3 ] ) ] > 7: single piece groupoid with rays: < Group( [ IdentityTransformation ] ), [ Transformation( [ 1, 1, 3, 2 ] ), Transformation( [ 1, 1, 4, 2 ] ) ], [ IdentityTransformation, Transformation( [ 1, 2, 4, 3 ] ) ] > 8: single piece groupoid with rays: < Group( [ IdentityTransformation ] ), [ IdentityTransformation, Transformation( [ 1, 2, 4, 3 ] ) ], [ IdentityTransformation, Transformation( [ 1, 2, 4, 3 ] ) ] > gap> IsGroupoidWithMonoidObjects( rag ); true gap> orag := ObjectList( rag );; gap> hs := Homset( rag, orag[3], orag[4] );; gap> Display( hs ); <homset Transformation( [ 1, 1, 1, 3 ] ) -> Transformation( [ 1, 1, 1 ] ) with elements: [Transformation( [ 1, 2, 4, 3 ] ) : Transformation( [ 1, 1, 1, 3 ] ) -> Transformation( [ 1, 1, 1 ] )]
generated by GAPDoc2HTML