46 Semigroups

This chapter describes functions for creating semigroups and determining information about them.

  • IsSemigroup( D ) P

    A semigroup is a magma (see Magmas) with associative multiplication.

  • Semigroup( gen1, gen2... ) F
  • Semigroup( gens ) F

    In the first form, Semigroup returns the semigroup generated by the arguments gen1, gen2 ..., that is, the closure of these elements under multiplication. In the second form, Semigroup returns the semigroup generated by the elements in the homogeneous list gens; a square matrix as only argument is treated as one generator, not as a list of generators.

    It is not checked whether the underlying multiplication is associative, use Magma (see Magma) and IsAssociative (see IsAssociative) if you want to check whether a magma is in fact a semigroup.

    gap> a:= Transformation([2, 3, 4, 1]);
    Transformation( [ 2, 3, 4, 1 ] )
    gap> b:= Transformation([2, 2, 3, 4]);
    Transformation( [ 2, 2, 3, 4 ] )
    gap> s:= Semigroup(a, b);
    <semigroup with 2 generators>
    

  • Subsemigroup( S, gens ) F
  • SubsemigroupNC( S, gens ) F

    are just synonyms of Submagma and SubmagmaNC, respectively (see Submagma).

    gap> a:=GeneratorsOfSemigroup(s)[1];
    Transformation( [ 2, 3, 4, 1 ] )
    gap> t:=Subsemigroup(s,[a]);
    <semigroup with 1 generator>
    

  • SemigroupByGenerators( gens ) O

    is the underlying operation of Semigroup (see Semigroup).

  • AsSemigroup( C ) A

    If C is a collection whose elements form a semigroup (see IsSemigroup) then AsSemigroup returns this semigroup. Otherwise fail is returned.

  • AsSubsemigroup( D, C ) O

    Let D be a domain and C a collection. If C is a subset of D that forms a semigroup then AsSubsemigroup returns this semigroup, with parent D. Otherwise fail is returned.

  • GeneratorsOfSemigroup( S ) A

    Semigroup generators of a semigroup D are the same as magma generators (see GeneratorsOfMagma).

    gap> GeneratorsOfSemigroup(s);
    [ Transformation( [ 2, 3, 4, 1 ] ), Transformation( [ 2, 2, 3, 4 ] ) ]
    gap> GeneratorsOfSemigroup(t);
    [ Transformation( [ 2, 3, 4, 1 ] ) ]
    

  • FreeSemigroup( rank ) F
  • FreeSemigroup( rank, name ) F
  • FreeSemigroup( name1, name2, ... ) F
  • FreeSemigroup( names ) F
  • FreeSemigroup( infinity, name, init ) F

    Called in the first form, FreeSemigroup returns a free semigroup on rank generators. Called in the second form, FreeSemigroup returns a free semigroup on rank generators, printed as name1, name2 etc., that is, each name is the concatenation of the string name and an integer from 1 to range. Called in the third form, FreeSemigroup returns a free semigroup on as many generators as arguments, printed as name1, name2 etc. Called in the fourth form, FreeSemigroup returns a free semigroup on as many generators as the length of the list names, the i-th generator being printed as names[ i]. Called in the fifth form, FreeSemigroup returns a free semigroup on infinitely many generators, where the first generators are printed by the names in the list init, and the other generators by name and an appended number.

    gap> f1 := FreeSemigroup( 3 );
    <free semigroup on the generators [ s1, s2, s3 ]>
    gap> f2 := FreeSemigroup( 3 , "generator" );
    <free semigroup on the generators [ generator1, generator2, generator3 ]>
    gap> f3 := FreeSemigroup( "gen1" , "gen2" );
    <free semigroup on the generators [ gen1, gen2 ]>
    gap> f4 := FreeSemigroup( ["gen1" , "gen2"] );
    <free semigroup on the generators [ gen1, gen2 ]>
    

  • SemigroupByMultiplicationTable( A ) F

    returns the semigroup whose multiplication is defined by the square matrix A (see MagmaByMultiplicationTable) if such a semigroup exists. Otherwise fail is returned.

    The following functions determine information about semigroups:

  • IsRegularSemigroup( S ) P

    returns true if S is regular---i.e. if every D class of S is regular.

  • IsRegularSemigroupElement( S, x ) O

    returns true if x has a general inverse in S---i.e. there is an element y Î S such that xyx = x and yxy = y.

  • IsSimpleSemigroup( S ) P

    true if and only if the semigroup has no proper ideals.

  • IsZeroSimpleSemigroup( S ) P

    S is a semigroup with zero true if and only if the semigroup has no proper ideals except for 0. If the semigroup does not find its zero, then it breaks

  • IsZeroGroup( S ) P

    true if and only if the semigroup is a group with zero adjoined

  • IsReesCongruenceSemigroup( S ) P

    retruns true if S is a Rees Congruence semigroup, that is, if all congruences of S are Rees Congruences

    Sections

    1. Making transformation semigroups
    2. Ideals of semigroups
    3. Congruences
    4. Quotients
    5. Green's Relations
    6. Rees Matrix Semigroups

    46.1 Making transformation semigroups

    Cayley's Theorem gives special status to semigroups of transformations, and accordingly there are special functions to deal with them, and to create them from other finite semigroups.

  • IsTransformationSemigroup( obj ) P
  • IsTransformationMonoid( obj ) P

    A transformation semigroup (resp. monoid) is a subsemigroup (resp. submonoid) of the full transformation monoid. Note that for a transformation semigroup to be a transformation monoid we necessarily require the identity transformation to be an element.

  • DegreeOfTransformationSemigroup( S ) A

    The number of points the semigroup acts on.

  • IsomorphismTransformationSemigroup( S ) A
  • HomomorphismTransformationSemigroup( S, r ) O

    IsomorphismTransformationSemigroup is a generic attribute which is a transformation semigroup isomorphic to S (if such can be computed). In the case of an fp- semigroup, a todd-coxeter will be attempted. For a semigroup of endomorphisms of a finite domain of n elements, it will be to a semigroup of transformations of {1, ¼, n}. Otherwise, it will be the right regular representation on S or S1 if S has no MultiplicativeNeutralElement.

    HomomorphismTransformationSemigroup finds a representation of S as transformations of the set of equivalence classes of the right congruence r.

    46.2 Ideals of semigroups

    Ideals of semigroups are the same as ideals of the semigroup when considered as a magma. For documentation on ideals for magmas see Magma.

  • SemigroupIdealByGenerators( S, gens ) O

    S is a semigroup, gens is a list of elements of S. Returns the two-sided ideal of S generated by gens.

  • ReesCongruenceOfSemigroupIdeal( I ) A

    A two sided ideal I of a semigroup S defines a congruence on S given by DÈI ×I.

  • IsLeftSemigroupIdeal( I ) P
  • IsRightSemigroupIdeal( I ) P
  • IsSemigroupIdeal( I ) P

    Categories of semigroup ideals.

  • IsRightSemigroupIdealEnumerator C
  • IsLeftSemigroupIdealEnumerator C
  • IsSemigroupIdealEnumerator C

    Categories for generic semigroup ideal enumerators.

    46.3 Congruences

    An equivalence or a congruence on a semigroup is the equivalence or congruence on the semigroup considered as a magma. So, to deal with equivalences and congruences on semigroups, magma funtions are used. For documentation on equivalences and congruences for magmas see Magma.

  • IsSemigroupCongruence( c ) C

    a magma congruence c on a semigroup.

  • IsReesCongruence( c ) P

    returns true precisely when the congruence c has at most one nonsingleton congruence class.

    46.4 Quotients

    Given a semigroup and a congruence on the semigroup, one can construct a new semigroup: the quotient semigroup. The following funtions deal with quotient semigroups in GAP.

  • IsQuotientSemigroup( S ) C

    is the category of semigroups constructed from another semigroup and a congruence on it

    Elements of a quotient semigroup are equivalence classes of elements of QuotientSemigroupPreimage(S) under the congruence QuotientSemigroupCongruence(S).

    It is probably most useful for calculating the elements of the equivalence classes by using Elements or by looking at the images of elements of the QuotientSemigroupPreimage(S) under QuotientSemigroupHomomorphism(S):QuotientSemigroupPreimage(S) ® S.

    For intensive computations in a quotient semigroup, it is probably worthwhile finding another representation as the equality test could involve enumeration of the elements of the congruence classes being compared.

  • HomomorphismQuotientSemigroup( cong ) F

    for a congruence cong and a semigroup S. Returns the homomorphism from S to the quotient of S by cong.

  • QuotientSemigroupPreimage( S ) A
  • QuotientSemigroupCongruence( S ) A
  • QuotientSemigroupHomomorphism( S ) A

    for a quotient semigroup S.

    46.5 Green's Relations

    Green's equivalence relations play a very important role in semigroup theory. In this section we describe how they can be used in GAP.

    The five green's relations are R, L, J, H, D: two elements x, y from S are R-related if and only if xS1 = yS1, L-related if and only if S1x = S1y and J-related if and only if S1xS1 = S1yS1; finally, H = R ÙL, and D = R o L.

    Recall that relations R, L and J induce a partial order among the elements of the semigroup: for two elements x, y from S, we say that x is less than or equal to y in the order on R if xS1 Í yS1; similarly, x is less than or equal to y under L if S1x Í S1y; finally x is less than or equal to y under J if S1xS1 Í S1tS1. We extend this preorder to a partial order on equivalence classes in the natural way.

  • GreensRRelation( S ) F
  • GreensLRelation( S ) F
  • GreensDRelation( S ) F
  • GreensJRelation( S ) F
  • GreensHRelation( S ) F

    create the Green's relations.

  • IsGreensRelation( R ) P
  • IsGreensRRelation( R ) P
  • IsGreensLRelation( R ) P
  • IsGreensDRelation( R ) P
  • IsGreensJRelation( R ) P
  • IsGreensHRelation( R ) P

    returns true if the equivalence relation R is one of Green's relations.

  • IsGreensClass( C ) P
  • IsGreensRClass( C ) P
  • IsGreensLClass( C ) P
  • IsGreensDClass( C ) P
  • IsGreensJClass( C ) P
  • IsGreensHClass( C ) P

    returns true if the equivalence class C arises from one of Green's relations.

  • IsGreensLessThanOrEqual( C1, C2 ) O

    returns true if the greens class C1 is less than or equal to C2 under the respective ordering (as defined above).

  • RClassOfHClass( H ) A
  • LClassOfHClass( H ) A

    are attributes reflecting the natural ordering over the various Green's classes. RClassOfHClass and LClassOfHClass return the R and L classes respectively in which an H class is contained.

  • IsGreensRClassEnumerator( E ) C
  • IsGreensLClassEnumerator( E ) C
  • IsGreensJClassEnumerator( E ) C
  • IsGreensHClassEnumerator( E ) C
  • IsGreensDClassEnumerator( E ) C

    are categories for Enumerators of the five Green's classes.

  • EggBoxOfDClass( D ) A

    A matrix whose rows represent R classes and columns represent L classes. The entries are the H classes.

  • DisplayEggBoxOfDClass( D ) F

    A ``picture'' of the D class D, as an array of 1s and 0s. A 1 represents a group H class.

  • GreensRClassOfElement( S, a ) F
  • GreensLClassOfElement( S, a ) F
  • GreensDClassOfElement( S, a ) F
  • GreensJClassOfElement( S, a ) F
  • GreensHClassOfElement( S, a ) F

    Creates the X class of the element a in the semigroup S where X is one of L, R, D, J or H.

    Note, this checks that a in S. For more efficiency when a in S is known, you could write (for example) EquivalenceClassOfElementNC(GreensRRelation(S),a);

  • GreensRClasses( D ) A
  • GreensLClasses( D ) A
  • GreensJClasses( D ) A
  • GreensDClasses( D ) A
  • GreensHClasses( D ) A

    for a domain Return the R, L, J, D, or H classes contained in D. D might be the semigroup itself, or a class, etc

  • GroupHClassOfGreensDClass( D ) A

    for a D class of a semigroup. Returns a group H class of the D class. Or fail if there are no group H class

  • IsGroupHClass( H ) P

    returns true if the Greens H class H is a group, which in turn is true if and only if H^2 intersects H.

  • IsRegularDClass( D ) P

    returns true if the Greens D class D is regular. A D class is regular if and only if each of its elements is regular, which in turn is true if and only if any one element of D is regular. Since idempotents are clearly regular, we have that a D class is regular if and only if it contains an idempotent.

    46.6 Rees Matrix Semigroups

    In this section we describe GAP funtions for Rees matrix semigroups and Rees 0-matrix semigroups. The importance of this construction is that Rees Matrix semigroups over groups are exactly the completely simple semigroups, and Rees 0-matrix semigroups over groups are the completely 0-simple semigroups

    Recall that a Rees Matrix semigroup is constructed from a semigroup (the underlying semigroup), and a matrix. A Rees Matrix semigroup element is a triple (s, i, lambda) where s is an element of the underlying semigroup S and i, lambda are indices. This can be thought of as a matrix with zero everywhere except for an occurrence of s at row i and column lambda. The multiplication is defined by (s, i, l)*(t, j , m) = (sPljt, i, m) where P is the defining matrix of the semigroup. In the case that the underlying semigroup has a zero we can make the ReesZeroMatrixSemigroup, wherein all elements whose s entry is the zero of the underlying semigroup are identified to the unique zero of the Rees 0-matrix semigroup.

  • ReesMatrixSemigroup( S, matrix ) F

    for a semigroup S and matrix whose entries are in S. Returns the Rees Matrix semigroup with multiplication defined by matrix.

  • ReesZeroMatrixSemigroup( S, matrix ) F

    for a semigroup S with zero, and matrix over S returns the Rees 0-Matrix semigroup such that all elements (i, 0, l) are identified to zero.

    The zero in S is found automatically. If one cannot be found, an error is signalled.

  • IsReesMatrixSemigroup( T ) P

    returns true whenever we have a (whole) rees matrix semigroup.

  • IsReesZeroMatrixSemigroup( T ) P

    returns true whenever we have a (whole) rees 0-matrix semigroup.

  • ReesMatrixSemigroupElement( R, a, i, lambda ) F
  • ReesZeroMatrixSemigroupElement( R, a, i, lambda ) F

    for a Rees matrix semigroup R, a in UnderlyingSemigroup(R), i and lambda in the row (resp. column) ranges of R, returns the element of R corresponding to the matrix with zero everywhere and a in row i and column x.

  • IsReesMatrixSemigroupElement( e ) C
  • IsReesZeroMatrixSemigroupElement( e ) C

    is the category of elements of a Rees (0-) matrix semigroup. Returns true if e is an element of a Rees Matrix semigroup.

  • SandwichMatrixOfReesMatrixSemigroup( R ) A
  • SandwichMatrixOfReesZeroMatrixSemigroup( R ) A

    the defining matrix of the Rees (0-) matrix semigroup.

  • RowIndexOfReesMatrixSemigroupElement( x ) A
  • RowIndexOfReesZeroMatrixSemigroupElement( x ) A
  • ColumnIndexOfReesMatrixSemigroupElement( x ) A
  • ColumnIndexOfReesZeroMatrixSemigroupElement( x ) A
  • UnderlyingElementOfReesMatrixSemigroupElement( x ) A
  • UnderlyingElementOfReesZeroMatrixSemigroupElement( x ) A

    for an element x of a Rees Matrix semigroup, of the form (s,i,lambda), the row index is i, the column index is lambda and the underlying element is s. If we think of an element as a matrix then this corresponds to the row where the non-zero entry is, the column where the non-zero entry is and the entry at that position, respectively.

  • ReesZeroMatrixSemigroupElementIsZero( x ) P

    returns true if x is the zero of the Rees 0-matrix semigroup.

  • AssociatedReesMatrixSemigroupOfDClass( D ) A

    Given a regular D class of a finite semigroup, it can be viewed as a rees matrix semigroup by identifying products which do not lie in the D class with zero.

    Formally, let I1 be the ideal of all J classes less than or equal to D, I2 the ideal of all J classes strictly less than D, and r the rees congurence associated with I2. Then I/r is zero-simple. Then AssociatedReesMatrixSemigroupOfDClass( D ) returns this zero-simple semigroup as a Rees matrix semigroup.

  • IsomorphismReesMatrixSemigroup A

    an isomorphism to a Rees matrix semigroup over a group (resp. zero group)

    [Top] [Previous] [Up] [Next] [Index]

    GAP 4 manual
    July 1999