Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 Bib Ind
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 

51 Semigroups
 51.1 IsSemigroup (Filter)
 51.2 Properties of Semigroups
 51.3 Making transformation semigroups
 51.4 Ideals of semigroups
 51.5 Congruences for semigroups
 51.6 Quotients
 51.7 Green's Relations
 51.8 Rees Matrix Semigroups

51 Semigroups

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

51.1 IsSemigroup (Filter)

51.1-1 IsSemigroup
‣ IsSemigroup( D )( property )

returns true if the object D is a semigroup. A semigroup is a magma (see 35) with associative multiplication.

51.1-2 Semigroup
‣ Semigroup( gen1, gen2, ... )( function )
‣ Semigroup( gens )( function )

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 (35.2-1) and IsAssociative (35.4-7) 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>

51.1-3 Subsemigroup
‣ Subsemigroup( S, gens )( function )
‣ SubsemigroupNC( S, gens )( function )

are just synonyms of Submagma (35.2-7) and SubmagmaNC (35.2-7), respectively.

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

51.1-4 SemigroupByGenerators
‣ SemigroupByGenerators( gens )( operation )

is the underlying operation of Semigroup (51.1-2).

51.1-5 AsSemigroup
‣ AsSemigroup( C )( attribute )

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

51.1-6 AsSubsemigroup
‣ AsSubsemigroup( D, C )( operation )

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.

51.1-7 GeneratorsOfSemigroup
‣ GeneratorsOfSemigroup( S )( attribute )

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

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

51.1-8 FreeSemigroup
‣ FreeSemigroup( [wfilt, ]rank[, name] )( function )
‣ FreeSemigroup( [wfilt, ]name1, name2, ... )( function )
‣ FreeSemigroup( [wfilt, ]names )( function )
‣ FreeSemigroup( [wfilt, ]infinity, name, init )( function )

Called with a positive integer rank, FreeSemigroup returns a free semigroup on rank generators. If the optional argument name is given then the generators are printed as name1, name2 etc., that is, each name is the concatenation of the string name and an integer from 1 to range. The default for name is the string "s".

Called in the second form, FreeSemigroup returns a free semigroup on as many generators as arguments, printed as name1, name2 etc.

Called in the third 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 fourth 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.

If the extra argument wfilt is given, it must be either IsSyllableWordsFamily (37.6-6) or IsLetterWordsFamily (37.6-2) or IsWLetterWordsFamily (37.6-4) or IsBLetterWordsFamily (37.6-4). This filter then specifies the representation used for the elements of the free semigroup (see 37.6). If no such filter is given, a letter representation is used.

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 ]>

Also see Chapter 51.

Each free object defines a unique alphabet (and a unique family of words). Its generators are the letters of this alphabet, thus words of length one.

gap> FreeGroup( 5 );
<free group on the generators [ f1, f2, f3, f4, f5 ]>
gap> FreeGroup( "a", "b" );
<free group on the generators [ a, b ]>
gap> FreeGroup( infinity );
<free group with infinity generators>
gap> FreeSemigroup( "x", "y" );
<free semigroup on the generators [ x, y ]>
gap> FreeMonoid( 7 );
<free monoid on the generators [ m1, m2, m3, m4, m5, m6, m7 ]>

Remember that names are just a help for printing and do not necessarily distinguish letters. It is possible to create arbitrarily weird situations by choosing strange names for the letters.

gap> f:= FreeGroup( "x", "x" );  gens:= GeneratorsOfGroup( f );;
<free group on the generators [ x, x ]>
gap> gens[1] = gens[2];
false
gap> f:= FreeGroup( "f1*f2", "f2^-1", "Group( [ f1, f2 ] )" );
<free group on the generators [ f1*f2, f2^-1, Group( [ f1, f2 ] ) ]>
gap> gens:= GeneratorsOfGroup( f );;
gap> gens[1]*gens[2];
f1*f2*f2^-1
gap> gens[1]/gens[3];
f1*f2*Group( [ f1, f2 ] )^-1
gap> gens[3]/gens[1]/gens[2];
Group( [ f1, f2 ] )*f1*f2^-1*f2^-1^-1

51.1-9 SemigroupByMultiplicationTable
‣ SemigroupByMultiplicationTable( A )( function )

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

51.2 Properties of Semigroups

The following functions determine information about semigroups.

51.2-1 IsRegularSemigroup
‣ IsRegularSemigroup( S )( property )

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

51.2-2 IsRegularSemigroupElement
‣ IsRegularSemigroupElement( S, x )( operation )

returns true if x has a general inverse in S, i.e., there is an element y ∈ S such that x y x = x and y x y = y.

51.2-3 IsSimpleSemigroup
‣ IsSimpleSemigroup( S )( property )

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

51.2-4 IsZeroSimpleSemigroup
‣ IsZeroSimpleSemigroup( S )( property )

is true if and only if the semigroup has no proper ideals except for 0, where S is a semigroup with zero. If the semigroup does not find its zero, then a break-loop is entered.

51.2-5 IsZeroGroup
‣ IsZeroGroup( S )( property )

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

51.2-6 IsReesCongruenceSemigroup
‣ IsReesCongruenceSemigroup( S )( property )

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

51.3 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.

51.3-1 IsTransformationSemigroup
‣ IsTransformationSemigroup( obj )( property )
‣ IsTransformationMonoid( obj )( property )

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.

51.3-2 DegreeOfTransformationSemigroup
‣ DegreeOfTransformationSemigroup( S )( attribute )

The number of points the semigroup S acts on.

51.3-3 IsomorphismTransformationSemigroup
‣ IsomorphismTransformationSemigroup( S )( attribute )
‣ HomomorphismTransformationSemigroup( S, r )( operation )

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 approach 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, 2, ..., n }. Otherwise, it will be the right regular representation on S or S^1 if S has no multiplicative neutral element, see MultiplicativeNeutralElement (35.4-10).

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

51.3-4 IsFullTransformationSemigroup
‣ IsFullTransformationSemigroup( obj )( property )

checks whether obj is a full transformation semigroup.

51.3-5 FullTransformationSemigroup
‣ FullTransformationSemigroup( degree )( function )

Returns the full transformation semigroup of degree degree.

51.4 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 (35.2-1).

51.4-1 SemigroupIdealByGenerators
‣ SemigroupIdealByGenerators( S, gens )( operation )

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

51.4-2 ReesCongruenceOfSemigroupIdeal
‣ ReesCongruenceOfSemigroupIdeal( I )( attribute )

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

51.4-3 IsLeftSemigroupIdeal
‣ IsLeftSemigroupIdeal( I )( property )
‣ IsRightSemigroupIdeal( I )( property )
‣ IsSemigroupIdeal( I )( property )

Categories of semigroup ideals.

51.5 Congruences for semigroups

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 functions are used. For documentation on equivalences and congruences for magmas, see Magma (35.2-1).

51.5-1 IsSemigroupCongruence
‣ IsSemigroupCongruence( c )( property )

a magma congruence c on a semigroup.

51.5-2 IsReesCongruence
‣ IsReesCongruence( c )( property )

returns true if and only if the congruence c has at most one nonsingleton congruence class.

51.6 Quotients

Given a semigroup and a congruence on the semigroup, one can construct a new semigroup: the quotient semigroup. The following functions deal with quotient semigroups in GAP. For a semigroup S, elements of a quotient semigroup are equivalence classes of elements of the QuotientSemigroupPreimage (51.6-3) value under the congruence given by the value of QuotientSemigroupCongruence (51.6-3).

It is probably most useful for calculating the elements of the equivalence classes by using Elements (30.3-11) or by looking at the images of elements of QuotientSemigroupPreimage (51.6-3) under the map returned by QuotientSemigroupHomomorphism (51.6-3), which maps the QuotientSemigroupPreimage (51.6-3) value to 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.

51.6-1 IsQuotientSemigroup
‣ IsQuotientSemigroup( S )( category )

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

51.6-2 HomomorphismQuotientSemigroup
‣ HomomorphismQuotientSemigroup( cong )( function )

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

51.6-3 QuotientSemigroupPreimage
‣ QuotientSemigroupPreimage( S )( attribute )
‣ QuotientSemigroupCongruence( S )( attribute )
‣ QuotientSemigroupHomomorphism( S )( attribute )

for a quotient semigroup S.

51.7 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 a semigroup S are R-related if and only if xS^1 = yS^1, L-related if and only if S^1 x = S^1 y and J-related if and only if S^1 xS^1 = S^1 yS^1; finally, H = R ∧ L, and D = R ∘ L.

Recall that relations R, L and J induce a partial order among the elements of the semigroup S: for two elements x, y from S, we say that x is less than or equal to y in the order on R if xS^1 ⊆ yS^1; similarly, x is less than or equal to y under L if S^1x ⊆ S^1y; finally x is less than or equal to y under J if S^1 xS^1 ⊆ S^1 tS^1. We extend this preorder to a partial order on equivalence classes in the natural way.

51.7-1 GreensRRelation
‣ GreensRRelation( semigroup )( attribute )
‣ GreensLRelation( semigroup )( attribute )
‣ GreensJRelation( semigroup )( attribute )
‣ GreensDRelation( semigroup )( attribute )
‣ GreensHRelation( semigroup )( attribute )

The Green's relations (which are equivalence relations) are attributes of the semigroup semigroup.

51.7-2 IsGreensRelation
‣ IsGreensRelation( bin-relation )( property )
‣ IsGreensRRelation( equiv-relation )( property )
‣ IsGreensLRelation( equiv-relation )( property )
‣ IsGreensJRelation( equiv-relation )( property )
‣ IsGreensHRelation( equiv-relation )( property )
‣ IsGreensDRelation( equiv-relation )( property )

Categories for the Green's relations.

51.7-3 IsGreensClass
‣ IsGreensClass( equiv-class )( property )
‣ IsGreensRClass( equiv-class )( property )
‣ IsGreensLClass( equiv-class )( property )
‣ IsGreensJClass( equiv-class )( property )
‣ IsGreensHClass( equiv-class )( property )
‣ IsGreensDClass( equiv-class )( property )

return true if the equivalence class equiv-class is a Green's class of any type, or of R, L, J, H, D type, respectively, or false otherwise.

51.7-4 IsGreensLessThanOrEqual
‣ IsGreensLessThanOrEqual( C1, C2 )( operation )

returns true if the Green's class C1 is less than or equal to C2 under the respective ordering (as defined above), and false otherwise.

Only defined for R, L and J classes.

51.7-5 RClassOfHClass
‣ RClassOfHClass( H )( attribute )
‣ LClassOfHClass( H )( attribute )

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.

51.7-6 EggBoxOfDClass
‣ EggBoxOfDClass( Dclass )( attribute )

returns for a Green's D class Dclass a matrix whose rows represent R classes and columns represent L classes. The entries are the H classes.

51.7-7 DisplayEggBoxOfDClass
‣ DisplayEggBoxOfDClass( Dclass )( function )

displays a "picture" of the D class Dclass, as an array of 1s and 0s. A 1 represents a group H class.

51.7-8 GreensRClassOfElement
‣ GreensRClassOfElement( S, a )( operation )
‣ GreensLClassOfElement( S, a )( operation )
‣ GreensDClassOfElement( S, a )( operation )
‣ GreensJClassOfElement( S, a )( operation )
‣ GreensHClassOfElement( S, a )( operation )

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

51.7-9 GreensRClasses
‣ GreensRClasses( semigroup )( attribute )
‣ GreensLClasses( semigroup )( attribute )
‣ GreensJClasses( semigroup )( attribute )
‣ GreensDClasses( semigroup )( attribute )
‣ GreensHClasses( semigroup )( attribute )

return the R, L, J, H, or D Green's classes, respectively for semigroup semigroup. EquivalenceClasses (33.7-3) for a Green's relation lead to one of these functions.

51.7-10 GroupHClassOfGreensDClass
‣ GroupHClassOfGreensDClass( Dclass )( attribute )

for a D class Dclass of a semigroup, returns a group H class of the D class, or fail if there is no group H class.

51.7-11 IsGroupHClass
‣ IsGroupHClass( Hclass )( property )

returns true if the Green's H class Hclass is a group, which in turn is true if and only if Hclass^2 intersects Hclass.

51.7-12 IsRegularDClass
‣ IsRegularDClass( Dclass )( property )

returns true if the Greens D class Dclass 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 Dclass is regular. Idempotents are regular since eee = e so it follows that a Green's D class containing an idempotent is regular. Conversely, it is true that a regular D class must contain at least one idempotent. (See [How76, Prop. 3.2].)

51.8 Rees Matrix Semigroups

In this section we describe GAP functions 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, λ) where s is an element of the underlying semigroup S and i, λ are indices. This can be thought of as a matrix with zero everywhere except for an occurrence of s at row i and column λ. The multiplication is defined by (i, s, λ)*(j, t, μ) = (i, s P_{λ j} t, μ) where P is the defining matrix of the semigroup. In the case that the underlying semigroup has a zero we can create the ReesZeroMatrixSemigroup (51.8-2) value, 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.

51.8-1 ReesMatrixSemigroup
‣ ReesMatrixSemigroup( S, matrix )( function )

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

51.8-2 ReesZeroMatrixSemigroup
‣ ReesZeroMatrixSemigroup( S, matrix )( function )

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

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

51.8-3 IsReesMatrixSemigroup
‣ IsReesMatrixSemigroup( T )( property )

returns true if the object T is a (whole) Rees matrix semigroup.

51.8-4 IsReesZeroMatrixSemigroup
‣ IsReesZeroMatrixSemigroup( T )( property )

returns true if the object T is a (whole) Rees 0-matrix semigroup.

51.8-5 ReesMatrixSemigroupElement
‣ ReesMatrixSemigroupElement( R, i, a, lambda )( function )
‣ ReesZeroMatrixSemigroupElement( R, i, a, lambda )( function )

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.

51.8-6 IsReesMatrixSemigroupElement
‣ IsReesMatrixSemigroupElement( e )( category )
‣ IsReesZeroMatrixSemigroupElement( e )( category )

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

51.8-7 SandwichMatrixOfReesMatrixSemigroup
‣ SandwichMatrixOfReesMatrixSemigroup( R )( attribute )
‣ SandwichMatrixOfReesZeroMatrixSemigroup( R )( attribute )

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

51.8-8 RowIndexOfReesMatrixSemigroupElement
‣ RowIndexOfReesMatrixSemigroupElement( x )( attribute )
‣ RowIndexOfReesZeroMatrixSemigroupElement( x )( attribute )
‣ ColumnIndexOfReesMatrixSemigroupElement( x )( attribute )
‣ ColumnIndexOfReesZeroMatrixSemigroupElement( x )( attribute )
‣ UnderlyingElementOfReesMatrixSemigroupElement( x )( attribute )
‣ UnderlyingElementOfReesZeroMatrixSemigroupElement( x )( attribute )

For an element x of a Rees Matrix semigroup, of the form (i, s, λ), the row index is i, the column index is λ 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.

51.8-9 ReesZeroMatrixSemigroupElementIsZero
‣ ReesZeroMatrixSemigroupElementIsZero( x )( property )

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

51.8-10 AssociatedReesMatrixSemigroupOfDClass
‣ AssociatedReesMatrixSemigroupOfDClass( D )( attribute )

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, and this is what it is returned.

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

51.8-11 IsomorphismReesMatrixSemigroup
‣ IsomorphismReesMatrixSemigroup( obj )( attribute )

If S is a completely simple (resp. zero simple) semigroup, returns an isomorphism to a Rees matrix semigroup over a group (resp. zero group).

 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 
Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 Bib Ind

generated by GAPDoc2HTML