2 Many-object structures

A magma with objects M consists of a set of objects Ob(M), and a set of arrows Arr(M) together with tail and head maps t,h : Arr(M) -> Ob(M), and a partial multiplication * : Arr(M) -> Arr(M), with a*b defined precisely when the head of a coincides with the tail of b. We write an arrow a with tail u and head v as (a : u -> v).

When this multiplication is associative we obtain a semigroup with objects.

A loop is an arrow whose tail and head are the same object. An identity arrow at object u is a loop (1_u : u -> u) such that a*1_u=a and 1_u*b=b whenever u is the head of a and the tail of b. When M is a semigroup with objects and every object has an identity arrow, we obtain a monoid with objects, which is just the usual notion of mathematical category.

An arrow (a : u -> v) in a monoid with objects has inverse (a^-1 : v -> u) provided a*a^-1 = 1_u and a^-1*a = 1_v. A monoid with objects in which every arrow has an inverse is a group with objects, usually called a groupoid.

For the definitions of the standard properties of groupoids we refer to P. Higgins' book ``Categories and Groupoids'' [Hig05] (originally published in 1971, reprinted by TAC in 2005), and to R. Brown's book ``Topology'' [Bro88], recently revised and reissued as ``Topology and Groupoids'' [Bro06].

2.1 Magmas with objects

2.1-1 MagmaWithObjects

The simplest construction for a magma with objects is to take a magma m and form arrows (u,x,v) for every x in m and every pair of objects (u,v). Multiplication is defined by (u,x,v)*(v,y,w) = (u,x*y,w). Any finite, ordered set is in principle acceptable as the object list of M, but we find it convenient to restrict ourselves to sets of negative integers.

This is the only construction implemented here for magmas, semigroups, and monoids with objects, and these all have the property IsDirectProductWithComlpleteGraph. There are other constructions implemented for groupoids.

The output from function MagmaWithObjects lies in the categories IsDomainWithObjects, IsMagmaWithObjects, CategoryCollections(IsMultiplicativeElementWithObjects) and IsMagma.

gap> tm := [[1,2,4,3],[1,2,4,3],[3,4,2,1],[3,4,2,1]];;  Display( tm );
[ [  1,  2,  4,  3 ],
  [  1,  2,  4,  3 ],
  [  3,  4,  2,  1 ],
  [  3,  4,  2,  1 ] ]
gap> m := MagmaByMultiplicationTable( tm ); 
<magma with 4 generators>
gap> SetName( m, "m" ); 
gap> m1 := MagmaElement(m,1);; 
gap> m2 := MagmaElement(m,2);; 
gap> m3 := MagmaElement(m,3);; 
gap> m4 := MagmaElement(m,4);; 
gap> One(m); 
fail
gap> M78 := MagmaWithObjects( [-8,-7], m ); 
magma with objects :-
    magma = m
  objects = [ -8, -7 ]
gap> SetName( M78, "M78" );
gap> [ IsAssociative(M78), IsCommutative(M78), IsDomainWithObjects(M78) ]; 
[ false, false, true ]

2.1-2 MultiplicativeElementWithObjects

Elements in a magma with objects lie in the category IsMultiplicativeElementWithObjects. An attempt to multiply two arrows which do not compose resuts in fail being returned.

gap> a78 := MultiplicativeElementWithObjects( M78, m4, -7, -8 ); 
[m2 : -7 -> -8]
gap> b87 := MultiplicativeElementWithObjects( M78, m3, -8, -7 );; 
gap> [ Arrowelt(b87), Arrowtail(b87), Arrowhead(b87) ];
[ m3, -8, -7 ] 
gap> ba := b87*a78; 
[m4 : -8 -> -8]
gap> ab := a78*b87;
[m4 : -7 -> -7]
gap> a78^2; 
fail
gap> [ ba^2, ba^3, ba^4=ba^2 ];
[ [m1 : -8 -> -8], [m3 : -8 -> -8], true ] 

2.1-3 IsSinglePiece

If the partial composition is forgotten, then what remains is a digraph (usually with multiple edges and loops). Thus the notion of connected component may be inherited by magmas with objects from digraphs. Unfortunately the terms Component and Constituent are already in considerable use elsewhere in GAP, so (and this may change if a more suitable word is suggested) we use the term IsSinglePiece to describe a connected magma with objects. When each connected component has a single object, the magma with objects is discrete.

gap> IsSinglePiece( M78 ); 
true
gap> IsDirectProductWithCompleteGraph( M78 );
true
gasp> IsDiscrete( M78 ); 
false

2.2 Semigroups with objects

2.2-1 SemigroupWithObjects

When the magma is a semigroup we obtain a SinglePieceSemigroupWithObjects. In tyhe example we use a transformation semigroup.

gap> t := Transformation( [1,1,2,3] );;
gap> s := Transformation( [2,2,3,3] );;
gap> r := Transformation( [2,3,4,4] );;
gap> sgp := Semigroup( t, s, r );; 
gap> SetName( sgp, "sgp<t,s,r>" ); 
gap> S123 := SemigroupWithObjects( sgp, [-3,-2,-1] ); 
semigroup with objects :-
    magma = sgp<t,s,r>
  objects = [ -3, -2, -1 ]
gap> [ IsAssociative(S123), IsCommutative(S123) ];
[ true, false ]
gap> t12 := MultiplicativeElementWithObjects( S123, t, -1, -2 );
[Transformation( [ 1, 1, 2, 3 ] ) : -1 -> -2]
gap> s23 := MultiplicativeElementWithObjects( S123, s, -2, -3 );; 
gap> r31 := MultiplicativeElementWithObjects( S123, r, -3, -1 );; 
gap> ts13 := t12 * s23;
[Transformation( [ 2, 2, 2, 3 ] ) : -1 -> -3]
gap> sr21 := s23 * r31;
[Transformation( [ 3, 3, 4, 4 ] ) : -2 -> -1]
gap> rt32 := r31 * t12;
[Transformation( [ 1, 2, 3, 3 ] ) : -3 -> -2]
gap> tsr1 := ts13 * r31;
[Transformation( [ 3, 3, 3, 4 ] ) : -1 -> -1]

2.3 Monoids with objects

2.3-1 MonoidWithObjects

When the magma is a monoid we obtain a SinglePieceMonoidWithObjects. The example uses a finitely presented monoid.

gap> fm := FreeMonoid( 2, "f" );;
gap> em := Identity( fm );;
gap> gm := GeneratorsOfMonoid( fm );;
gap> mon := fm/[ [gm[1]^3,em], [gm[1]*gm[2],gm[2]] ];; 
gap> M49 := MonoidWithObjects( mon, [-9,-4] ); 
monoid with objects :-
    magma = Monoid( [ f1, f2 ], ... )
  objects = [ -9, -4 ]
gap> genM : GeneratorsOfMagmaWithOne( M49 );
[ [<identity ...> : -9 -> -9], [f1 : -9 -> -9], [f2 : -9 -> -9],
  [<identity ...> : -9 -> -4], [<identity ...> : -4 -> -9] ]
gap> g2:=genM[2];; g3:=genM[3];; g4:=genM[4];; g5:=genM[5];; 
gap> g5*g2*g4;
[f1 : -4 -> -4]

2.4 Structures with one or more pieces

2.4-1 DomainWithSingleObject

A magma, semigroup, monoid, or group with a single object is algebraically isomorphic to the same structure without the object, but is implemented with the extra structure of a single object.

gap> d8 := Group( (1,2,3,4), (1,3) );;
gap> SetName( d8, "d8" );
gap> D0 := DomainWithSingleObject( d8, 0 );
single piece groupoid: < d8, [ 0 ] >
gap> GeneratorsOfMagmaWithInverses( D0 );
[ [(1,2,3,4) : 0 -> 0], [(1,3) : 0 -> 0] ]
gap> Size( D0 );
8

2.4-2 UnionOfPieces

A magma with objects whose underlying digraph has two or more connected components can be constructed by taking the union of two or more connected structures and these, in turn, can be combined together. The only requirement is that all the object lists should be disjoint.

We have formed structures S123, M46, D0 which have, respectively, GeneratorsOfMagma, GeneratorsOfMagmaWithOne and GeneratorsOfMagmaWithInverses. The generators of a structure with several pieces is the union of the generators of the individual pieces.

gap> U1 := UnionOfPieces( [ M78, S123 ] );;
gap> ObjectList( U1 );
[ -8, -7, -3, -2, -1 ]
gap U2 := UnionOfPieces( [ M49, D0 ] );;
gap> Pieces( U2 );
[ monoid with objects :-
        magma = Monoid( [ f1, f2 ], ... )
      objects = [ -9, -4 ]
    , single piece groupoid: < d8, [ 0 ] > ]
gap> U3 := UnionOfPieces( [ U1, U2 ] );
magma with objects having 4 pieces :-
1: monoid with objects :-
    magma = Monoid( [ f1, f2 ], ... )
  objects = [ -9, -4 ]
2: M78
3: semigroup with objects :-
    magma = sgp<t,s,r>
  objects = [ -3, -2, -1 ]
4: single piece groupoid: < d8, [ 0 ] >
gap> ObjectList( U3 ); 
[ -9, -8, -7, -4, -3, -2, -1, 0 ]
gap> Length( GeneratorsOfMagmaWithObjects( U3 ) ); 
50
gap> ## this should fail since the object sets are not disjoint: 
gap> U4 := UnionOfPieces( [ S123, DomainWithSingleObject( d8, -2 ) ] );  
fail

generated by GAPDoc2HTML