Goto Chapter: Top 1 2 3 4 5 6 7 Bib Ind
 Top of Book   Previous Chapter   Next Chapter 

5 Properties of Semigroups
 5.1 Introduction
 5.2 Property Tests
  5.2-1 IsCompletelyRegularSemigroup

  5.2-2 IsSimpleSemigroup

  5.2-3 IsGroupAsSemigroup

  5.2-4 IsCommutativeSemigroup

  5.2-5 IsRegularSemigroup

  5.2-6 IsInverseSemigroup

  5.2-7 IsCliffordSemigroup

  5.2-8 IsBand

  5.2-9 IsRectangularBand

  5.2-10 IsSemiBand

  5.2-11 IsOrthodoxSemigroup

  5.2-12 IsRightZeroSemigroup

  5.2-13 IsLeftZeroSemigroup

  5.2-14 IsZeroSemigroup

  5.2-15 IsZeroGroup

  5.2-16 MultiplicativeZero

5 Properties of Semigroups

5.1 Introduction

In this section we give the theoretical results and the corresponding GAP functions that can be used to determine whether a set of transformations generates a semigroup of a given type. Let S be a semigroup. Then

The following results provide efficient methods to determine if an arbitrary transformation semigroup is a left zero, right zero, simple, completely regular, inverse or Clifford semigroup. Proofs of these results can be found in [GM05].

Let S be a semigroup generated by a set of transformations U on a finite set. Then the following hold:

It is straightforward to verify that a transformation semigroup S generated by U is a group if and only if for all f, g in U

At first glance it might not be obvious why these conditions are an improvement over the original definitions. The main point is that it can be easily determined whether a semigroup S generated by a set U of mappings satisfies these conditions by considering the generators U and their action on the underlying set only.

5.2 Property Tests

5.2-1 IsCompletelyRegularSemigroup
> IsCompletelyRegularSemigroup( S )( property )

returns true if the transformation semigroup S is completely regular and false otherwise.

A semigroup is completely regular if every element is contained in a subgroup.

	
  gap> gens:=[ Transformation( [ 1, 2, 4, 3, 6, 5, 4 ] ), 
  >  Transformation( [ 1, 2, 5, 6, 3, 4, 5 ] ), 
  >  Transformation( [ 2, 1, 2, 2, 2, 2, 2 ] ) ];;
  gap> S:=Semigroup(gens);;
  gap> IsCompletelyRegularSemigroup(S);
  true
  gap> S:=RandomSemigroup(5,5);;
  gap> IsSimpleSemigroup(S);
  false

5.2-2 IsSimpleSemigroup
> IsSimpleSemigroup( S )( property )
> IsCompletelySimpleSemigroup( S )( property )

returns true if the transformation semigroup S is simple and false otherwise.

A semigroup is simple if it has no proper 2-sided ideals. A semigroup is completely simple if it is simple and possesses minimal left and right ideals. A finite semigroup is simple if and only if it is completely simple.

  gap> gens:=[ Transformation( [ 2, 2, 4, 4, 6, 6, 8, 8, 10, 10, 12, 12, 2 ] ), 
  >  Transformation( [ 1, 1, 3, 3, 5, 5, 7, 7, 9, 9, 11, 11, 3 ] ), 
  >  Transformation( [ 1, 7, 3, 9, 5, 11, 7, 1, 9, 3, 11, 5, 5 ] ), 
  >  Transformation( [ 7, 7, 9, 9, 11, 11, 1, 1, 3, 3, 5, 5, 7 ] ) ];;
  gap> S:=Semigroup(gens);;
  gap> IsSimpleSemigroup(S);
  true
  gap> IsCompletelySimpleSemigroup(S);
  true
  gap> S:=RandomSemigroup(5,5);;
  gap> IsSimpleSemigroup(S);
  false

5.2-3 IsGroupAsSemigroup
> IsGroupAsSemigroup( S )( property )

returns true if the transformation semigroup S is a group and false otherwise.

  gap> gens:=[ Transformation( [ 2, 4, 5, 3, 7, 8, 6, 9, 1 ] ), 
  >  Transformation( [ 3, 5, 6, 7, 8, 1, 9, 2, 4 ] ) ];;
  gap> S:=Semigroup(gens);;
  gap> IsGroupAsSemigroup(S);
  true

5.2-4 IsCommutativeSemigroup
> IsCommutativeSemigroup( S )( property )

returns true if the transformation semigroup S is commutative and false otherwise. The function IsCommutative (Reference: IsCommutative) can also be used to test if a semigroup is commutative.

A semigroup S is commutative if xy=yx for all x,y in S.

  gap> gens:=[ Transformation( [ 2, 4, 5, 3, 7, 8, 6, 9, 1 ] ), 
  >  Transformation( [ 3, 5, 6, 7, 8, 1, 9, 2, 4 ] ) ];;
  gap> S:=Semigroup(gens);;
  gap> IsCommutativeSemigroup(S);
  true
  gap> IsCommutative(S);
  true

5.2-5 IsRegularSemigroup
> IsRegularSemigroup( S )( property )

returns true if the transformation semigroup S is a regular semigroup and false otherwise. The algorithm used here is essentially the same algorithm as that used for GreensRClasses (Reference: GreensRClasses) in MONOID. If S is regular, then S will have the attribute GreensRClasses after IsRegularSemigroup is invoked.

A semigroup S is regular if for all x in S there exists y in S such that xyx=x.

  gap> IsRegularSemigroup(FullTransformationSemigroup(5));
  true

5.2-6 IsInverseSemigroup
> IsInverseSemigroup( S )( property )

returns true if the transformation semigroup S is an inverse semigroup and false otherwise.

A semigroup S is an inverse semigroup if every element x in S has a unique semigroup inverse, that is, a unique element y such that xyx=x and yxy=y.

  gap> gens:=[Transformation([1,2,4,5,6,3,7,8]),
  > Transformation([3,3,4,5,6,2,7,8]),
  >Transformation([1,2,5,3,6,8,4,4])];;
  gap> S:=Semigroup(gens);;
  gap> IsInverseSemigroup(S);
  true

5.2-7 IsCliffordSemigroup
> IsCliffordSemigroup( S )( property )

returns true if the transformation semigroup S is a Clifford semigroup and false otherwise.

A semigroup S is a Clifford semigroup if it is a regular semigroup whose idempotents are central, that is, for all e in S with e^2=e and x in S we have that ex=xe.

  gap> gens:=[Transformation([1,2,4,5,6,3,7,8]),
  > Transformation([3,3,4,5,6,2,7,8]),
  >Transformation([1,2,5,3,6,8,4,4])];;
  gap> S:=Semigroup(gens);;
  gap> IsCliffordSemigroup(S);
  true

5.2-8 IsBand
> IsBand( S )( property )

returns true if the transformation semigroup S is a band and false otherwise.

A semigroup S is a band if every element is an idempotent, that is, x^2=x for all x in S.

  gap> gens:=[ Transformation( [ 1, 1, 1, 4, 4, 4, 7, 7, 7, 1 ] ), 
  > Transformation( [ 2, 2, 2, 5, 5, 5, 8, 8, 8, 2 ] ), 
  > Transformation( [ 3, 3, 3, 6, 6, 6, 9, 9, 9, 3 ] ), 
  > Transformation( [ 1, 1, 1, 4, 4, 4, 7, 7, 7, 4 ] ), 
  > Transformation( [ 1, 1, 1, 4, 4, 4, 7, 7, 7, 7 ] ) ];;
  gap> S:=Semigroup(gens);;
  gap> IsBand(S);
  true

5.2-9 IsRectangularBand
> IsRectangularBand( S )( property )

returns true if the transformation semigroup S is a rectangular band and false otherwise.

A semigroup S is a rectangular band if for all x,y,z in S we have that x^2=x and xyz=xz.

  gap> gens:=[ Transformation( [ 1, 1, 1, 4, 4, 4, 7, 7, 7, 1 ] ), 
  > Transformation( [ 2, 2, 2, 5, 5, 5, 8, 8, 8, 2 ] ), 
  > Transformation( [ 3, 3, 3, 6, 6, 6, 9, 9, 9, 3 ] ), 
  > Transformation( [ 1, 1, 1, 4, 4, 4, 7, 7, 7, 4 ] ), 
  > Transformation( [ 1, 1, 1, 4, 4, 4, 7, 7, 7, 7 ] ) ];;
  gap> S:=Semigroup(gens);;
  gap> IsRectangularBand(S);
  true

5.2-10 IsSemiBand
> IsSemiBand( S )( property )

returns true if the transformation semigroup S is a semiband and false otherwise.

A semigroup S is a semiband if it is generated by its idempotent elements, that is, elements satisfying x^2=x.

  gap> S:=FullTransformationSemigroup(4);;
  gap> x:=Transformation( [ 1, 2, 3, 1 ] );;
  gap> D:=GreensDClassOfElement(S, x);;
  gap> T:=Semigroup(Elements(D));;
  gap> IsSemiBand(T);
  true

5.2-11 IsOrthodoxSemigroup
> IsOrthodoxSemigroup( S )( property )

returns true if the transformation semigroup S is orthodox and false otherwise.

A semigroup is an orthodox semigroup if its idempotent elements form a subsemigroup.

  gap> gens:=[ Transformation( [ 1, 1, 1, 4, 5, 4 ] ), 
  >  Transformation( [ 1, 2, 3, 1, 1, 2 ] ), 
  >  Transformation( [ 1, 2, 3, 1, 1, 3 ] ), 
  >  Transformation( [ 5, 5, 5, 5, 5, 5 ] ) ];;
  gap> S:=Semigroup(gens);;
  gap> IsOrthodoxSemigroup(S);
  true

5.2-12 IsRightZeroSemigroup
> IsRightZeroSemigroup( S )( property )

returns true if the transformation semigroup S is a right zero semigroup and false otherwise.

A semigroup S is a right zero semigroup if xy=y for all x,y in S.

  gap> gens:=[ Transformation( [ 2, 1, 4, 3, 5 ] ), 
  >  Transformation( [ 3, 2, 3, 1, 1 ] ) ];;
  gap> S:=Semigroup(gens);;
  gap> IsRightZeroSemigroup(S);
  false
  gap> gens:=[Transformation( [ 1, 2, 3, 3, 1 ] ), 
  >  Transformation( [ 1, 2, 4, 4, 1 ] )];;
  gap> S:=Semigroup(gens);;
  gap> IsRightZeroSemigroup(S);
  true

5.2-13 IsLeftZeroSemigroup
> IsLeftZeroSemigroup( S )( property )

returns true if the transformation semigroup S is a left zero semigroup and false otherwise.

A semigroup S is a left zero semigroup if xy=x for all x,y in S.

  gap> gens:=[ Transformation( [ 2, 1, 4, 3, 5 ] ), 
  >  Transformation( [ 3, 2, 3, 1, 1 ] ) ];;
  gap> S:=Semigroup(gens);;
  gap> IsRightZeroSemigroup(S);
  false
  gap> gens:=[Transformation( [ 1, 2, 3, 3, 1 ] ), 
  > Transformation( [ 1, 2, 3, 3, 3 ] ) ];;
  gap> S:=Semigroup(gens);;
  gap> IsLeftZeroSemigroup(S);
  true

5.2-14 IsZeroSemigroup
> IsZeroSemigroup( S )( property )

returns true if the transformation semigroup S is a zero semigroup or if S was created using the ZeroSemigroup (6.2-1) command. Otherwise false is returned.

A semigroup S is a zero semigroup if there exists an element 0 in S such that xy=0 for all x,y in S.

  gap> gens:=[ Transformation( [ 4, 7, 6, 3, 1, 5, 3, 6, 5, 9 ] ), 
  > Transformation( [ 5, 3, 5, 1, 9, 3, 8, 7, 4, 3 ] ), 
  > Transformation( [ 5, 10, 10, 1, 7, 6, 6, 8, 7, 7 ] ), 
  > Transformation( [ 7, 4, 3, 3, 2, 2, 3, 2, 9, 3 ] ), 
  > Transformation( [ 8, 1, 3, 4, 9, 6, 3, 7, 1, 6 ] ) ];;
  gap> S:=Semigroup(gens);;
  gap> IsZeroSemigroup(S);
  false

5.2-15 IsZeroGroup
> IsZeroGroup( S )( property )

returns true if the transformation semigroup S is a zero group or if S was created using the ZeroGroup (6.2-3) command. Otherwise false is returned.

A semigroup S S is a zero group if there exists an element 0 in S such that S without 0 is a group and for all x in S we have that x0=0x=0.

  gap> S:=ZeroGroup(DihedralGroup(10));;
  gap> iso:=IsomorphismTransformationSemigroup(S);;
  gap> T:=Range(iso);;
  gap> IsZeroGroup(T);
  true

5.2-16 MultiplicativeZero
> MultiplicativeZero( S )( property )

returns the multiplicative zero of the transformation semigroup S if it has one and returns fail otherwise.

  gap> gens:=[ Transformation( [ 1, 4, 2, 6, 6, 5, 2 ] ), 
  > Transformation( [ 1, 6, 3, 6, 2, 1, 6 ] ) ];;
  gap> S:=Semigroup(gens);;
  gap> MultiplicativeZero(S);
  Transformation( [ 1, 1, 1, 1, 1, 1, 1 ] )
 Top of Book   Previous Chapter   Next Chapter 
Goto Chapter: Top 1 2 3 4 5 6 7 Bib Ind

generated by GAPDoc2HTML