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
S
is a left zero semigroup if xy=x
for all x,y
in S
.
S
is a right zero semigroup if xy=y
for all x,y
in S
.
S
is commutative if xy=yx
for all x,y
in S
.
S
is simple if it has no proper two-sided ideals.
S
is regular if for all x
in S
there exists y
in S
such that xyx=x
.
S
is completely regular if every element of S
lies in a subgroup.
S
is an inverse semigroup if for all elements x
in S
there exists a unique semigroup inverse, that is, a unique element y
such that xyx=x
and yxy=y
.
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
.
S
is a band if every element is an idempotent, that is, x^2=x
for all x
in S
.
S
is a rectangular band if for all x,y,z
in S
we have that x^2=x
and xyz=xz
.
S
is a semiband if it is generated by its idempotent elements, that is, elements satisfying x^2=x
.
S
is an orthodox semigroup if its idempotents (elements satisfying x^2=x
) form a subsemigroup.
S
is a zero semigroup if there exists an element 0
in S
such that xy=0
for all x,y
in 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
.
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:
S
is a left zero semigroup if and only if for all f, g
in U
the image of f
equals the image of g
and f^2=f
.
S
is a right zero semigroup if and only if for all f, g
in U
the kernel of f
equals the kernel of g
and f^2=f
.
S
is simple if and only if for all f, g
in U
every class of the kernel of f
contains exactly 1
element of the image of g
.
S
is completely regular if and only if for all f
in U
and g
in S
, every class of the kernel of f
contains at most 1
element of the set found by applying g
to the image of f
.
S
is inverse if and only if it is regular and there is a bijection \phi
from the set of kernels of elements of S
to the set of images of elements of S
such that every class of a kernel K
contains exactly 1
element in (K)\phi
.
S
is a Clifford semigroup if and only if for all f, g
in U
f
permutes its image
f
commutes with the power of g
that acts as the identity on its image.
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
the kernel of f
equals the kernel of g
.
the image of f
equals the image of g
.
f
permutes its image.
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.
> 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 |
> 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 |
> 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 |
> 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 |
> 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 |
> 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 |
> 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 |
> 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 |
> 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 |
> 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 |
> 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 |
> 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 |
> 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 |
> 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 |
> 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 |
> 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 ] ) |
generated by GAPDoc2HTML