2.24 Monoids of Relations

There are no special functions provided for monoids generated by binary relations. The action of such a monoid on sets, however, provides a way to convert a relation monoid into a transformation monoid (see chapter Actions of Monoids). This monoid can then be used to investigate the structure of the original relation monoid.

    gap> a:= Relation( [ [  ], [  ], [ 1, 3, 4 ], [  ], [ 2, 5 ] ] );;
    gap> b:= Relation( [ [  ], [ 2 ], [ 4 ], [ 1, 2, 3 ], [ 1 ] ] );;
    gap> M:= Monoid( a, b );
    Monoid( [ Relation( [ [  ], [  ], [ 1, 3, 4 ], [  ], [ 2, 5 ] ] ), 
      Relation( [ [  ], [ 2 ], [ 4 ], [ 1, 2, 3 ], [ 1 ] ] ) ] )
    gap> # transform points into singleton sets.
    gap> one:= List( [ 1 .. 5 ], x-> [ x ] );
    [ [ 1 ], [ 2 ], [ 3 ], [ 4 ], [ 5 ] ]
    gap> # determine all reachable sets.
    gap> sets:= Union( Orbits( M, one ) ); 
    [ [  ], [ 1 ], [ 1, 2 ], [ 1, 2, 3 ], [ 1, 2, 3, 4 ], [ 1, 3, 4 ], 
      [ 2 ], [ 2, 4 ], [ 2, 5 ], [ 3 ], [ 4 ], [ 5 ] ]
    gap> # construct isomorphic transformation monoid.
    gap> act:= Action( M, sets ); 
    Monoid( [ Transformation( [ 1, 1, 1, 6, 6, 6, 1, 1, 9, 6, 1, 9 ] ), 
      Transformation( [ 1, 1, 7, 8, 5, 5, 7, 4, 3, 11, 4, 2 ] ) ] )
    gap> Size(act);
    11

  
[Index]