Goto Chapter: Top 1 2 3 4 5 6 7 8 Bib Ind

3 Homomorphisms of many-object structures

A homomorphism f from a magma with objects M to a magma with objects N consists of

• a map f_O from the objects of M to those of N,

• a map f_A from the arrows of M to those of N.

The map f_A is required to be compatible with the tail and head maps and to preserve multiplication:

f_A(a : u \to v) * f_A(b : v \to w) ~=~ f_A(a*b : u \to w)

with tail f_O(u) and head f_O(w).

When M is a monoid or group, the map f_A is required to preserve object identities and inverses.

3.1 Homomorphisms of magmas with objects

3.1-1 MagmaWithObjectsHomomorphism
 ‣ MagmaWithObjectsHomomorphism( args ) ( function )
 ‣ HomomorphismFromSinglePiece( src, rng, hom, imobs ) ( operation )
 ‣ HomomorphismToSinglePiece( src, rng, images ) ( operation )
 ‣ PieceImages( mwohom ) ( attribute )
 ‣ HomsOfMapping( mwohom ) ( attribute )
 ‣ PiecesOfMapping( mwohom ) ( attribute )
 ‣ IsomorphismNewObjects( src, objlist ) ( operation )

There are a variety of homomorphism constructors.

The simplest construction gives a homomorphism M -> N with both M and N connected. It is implemented as IsMappingToSinglePieceRep with attributes Source, Range and PieceImages. The operation requires the following information:

• a magma homomorphism f from the underlying magma of M to the underlying magma of N,

• a list imobs of the images of the objects of M.

In the first example we construct endomappings of m and M78.


gap> tup1 := [Tuple([m1,m2]), Tuple([m2,m1]), Tuple([m3,m4]), Tuple([m4,m3])];
gap> f1 := GeneralMappingByElements( m, m, tup1 );
gap> IsMagmaHomomorphism( f1 );
true
gap> hom1 := MagmaWithObjectsHomomorphism( M78, M78, f1, [-8,-7] );;
gap> Display( hom1 );
homomorphism to single piece magma: M78 -> M78
magma hom: <mapping: m -> m >, object map: [ -8, -7 ] -> [ -8, -7 ]
gap> [ Source( hom1 ), Range( hom1 ) ];
[ M78, M78 ]
gap> b87;
[m4 : -8 -> -7]
gap> im1 := ImageElm( hom1, b87 );
[m3 : -8 -> -7]
gap> i56 := IsomorphismNewObjects( M78, [-5,-6] );
magma with objects homomorphism :
[ [ IdentityMapping( m ), [ -5, -6 ] ] ]
gap> M65 := Range( i56);;
gap> SetName( M65, "M65" );
gap> j56 := InverseGeneralMapping( i56 );;
gap> ImagesOfObjects( j56 );
[ -7, -8 ]
gap> ib87 := ImageElm( i56, b87 );
[m4 : -5 -> -6]
gap> comp := j56 * hom1;
magma with objects homomorphism : M65 -> M78
[ [ <mapping: m -> m >, [ -7, -8 ] ] ]
gap> ImageElm( comp, ib87 );
[m3 : -8 -> -7]



A homomorphism to a connected magma with objects may have a source with several pieces, and so is a union of homomorphisms from single pieces.


gap> M4 := UnionOfPieces( [ M78, M65 ] );;
gap> images := [ PieceImages( hom1 )[1], PieceImages( j56 )[1] ];
[ [ <mapping: m -> m >, [ -8, -7 ] ], [ IdentityMapping( m ), [ -7, -8 ] ] ]
gap> map4 := HomomorphismToSinglePiece( M4, M78, images );
magma with objects homomorphism :
[ [ <mapping: m -> m >, [ -8, -7 ] ], [ IdentityMapping( m ), [ -7, -8 ] ] ]
gap> ImageElm( map4, b87 );
[m3 : -8 -> -7]
gap> ImageElm( map4, ib87 );
[m4 : -8 -> -7]



3.2 Homomorphisms of semigroups and monoids with objects

The next example exhibits a homomorphism between transformation semigroups with objects.


gap> t2 := Transformation( [2,2,4,1] );;
gap> s2 := Transformation( [1,1,4,4] );;
gap> r2 := Transformation( [4,1,3,3] );;
gap> sgp2 := Semigroup( [ t2, s2, r2 ] );;
gap> SetName( sgp2, "sgp<t2,s2,r2>" );
gap> ##  apparently no method for transformation semigroups available for:
gap> ##  nat := NaturalHomomorphismByGenerators( sgp, sgp2 );  so we use:
gap> ##  in the function flip below t is a transformation on [1..n]
gap> flip := function( t )
>     local i, j, k, L, L2, n;
>     n := DegreeOfTransformation( t );
>     L := ImageListOfTransformation( t );
>     if IsOddInt(n) then n:=n+1; L1:=Concatenation(L,[n]);
>                    else L1:=L; fi;
>     L2 := ShallowCopy( L1 );
>     for i in [1..n] do
>         if IsOddInt(i) then j:=i+1; else j:=i-1; fi;
>         k := L1[j];
>         if IsOddInt(k) then L2[i]:=k+1; else L2[i]:=k-1; fi;
>     od;
>     return( Transformation( L2 ) );
> end;;
gap> smap := MappingByFunction( sgp, sgp2, flip );;
gap> ok := RespectsMultiplication( smap );
true
gap> [ t, ImageElm( smap, t ) ];
[ Transformation( [ 1, 1, 2, 3 ] ), Transformation( [ 2, 2, 4, 1 ] ) ]
gap> [ s, ImageElm( smap, s ) ];
[ Transformation( [ 2, 2, 3, 3 ] ), Transformation( [ 1, 1, 4, 4 ] ) ]
gap> [ r, ImageElm( smap, r ) ];
[ Transformation( [ 2, 3, 4, 4 ] ), Transformation( [ 4, 1, 3, 3 ] ) ]
gap> SetName( smap, "smap" );
gap> T123 := SemigroupWithObjects( sgp2, [-13,-12,-11] );;
gap> shom := MagmaWithObjectsHomomorphism( S123, T123, smap, [-11,-12,-13] );;
gap> it12 := ImageElm( shom, t12 );;  [ t12, it12 ];
[ [Transformation( [ 1, 1, 2, 3 ] ) : -1 -> -2],
[Transformation( [ 2, 2, 4, 1 ] ) : -13 -> -12] ]
gap> is23 := ImageElm( shom, s23 );;  [ s23, is23 ];
[ [Transformation( [ 2, 2, 3, 3 ] ) : -2 -> -3],
[Transformation( [ 1, 1, 4, 4 ] ) : -12 -> -11] ]
gap> ir31 := ImageElm( shom, r31 );;  [ r31, ir31 ];
[ [Transformation( [ 2, 3, 4, 4 ] ) : -3 -> -1],
[Transformation( [ 4, 1, 3, 3 ] ) : -11 -> -13] ]



3.3 Homomorphisms to more than one piece

3.3-1 HomomorphismByUnion
 ‣ HomomorphismByUnion( src, rng, homs ) ( operation )
 ‣ IsInjectiveOnObjects( mwohom ) ( property )
 ‣ IsSurjectiveOnObjects( mwohom ) ( property )
 ‣ IsBijectiveOnObjects( mwohom ) ( property )
 ‣ IsEndomorphismWithObjects( mwohom ) ( property )
 ‣ IsAutomorphismWithObjects( mwohom ) ( property )

When f : M -> N and N has more than one connected component, then f is a union of homomorphisms, one for each piece in the range.


gap> N4 := UnionOfPieces( [ M78, T123 ] );
magma with objects having 2 pieces :-
1: semigroup with objects :-
magma = sgp<t2,s2,r2>
objects = [ -13, -12, -11 ]
2: M78
gap> h14 := HomomorphismByUnionNC( N1, N4, [ hom1, shom ] );
magma with objects homomorphism :
[ magma with objects homomorphism : M78 -> M78
[ [ <mapping: m -> m >, [ -8, -7 ] ] ], magma with objects homomorphism :
[ [ smap, [ -11, -12, -13 ] ] ] ]
gap> IsInjectiveOnObjects( h14 );
true
gap> IsSurjectiveOnObjects( h14 );
true
gap> IsBijectiveOnObjects( h14 );
true
gap> ImageElm( h14, t12 );
[Transformation( [ 2, 2, 4, 1 ] ) : -13 -> -12]
gap> h45 := IsomorphismNewObjects( N4, [ [-103,-102,-101], [-108,-107] ] );
magma with objects homomorphism :
[ magma with objects homomorphism :
[ [ IdentityMapping( m ), [ -108, -107 ] ] ],
magma with objects homomorphism :
[ [ IdentityMapping( sgp<t2,s2,r2> ), [ -103, -102, -101 ] ] ] ]
gap> N5 := Range( h45 );;  SetName( N5, "N5" );
gap> h15 := h14 * h45;
magma with objects homomorphism :
[ magma with objects homomorphism : [ [ <mapping: m -> m >, [ -108, -107 ] ] ]
, magma with objects homomorphism : [ [ smap, [ -101, -102, -103 ] ] ] ]
gap> ImageElm( h15, t12 );
[Transformation( [ 2, 2, 4, 1 ] ) : -103 -> -102]


Goto Chapter: Top 1 2 3 4 5 6 7 8 Bib Ind

generated by GAPDoc2HTML