Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 Bib Ind
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 

17 Properties of semigroups and inverse semigroups
 17.1 Properties of semigroups
 17.2 Properties of inverse semigroups

17 Properties of semigroups and inverse semigroups

In this chapter we decribe the methods that are available in Semigroups for determining various properties of a semigroup.

17.1 Properties of semigroups

In this section we describe the properties of a semigroup that can be determined using the Semigroups package.

17.1-1 IsBand
‣ IsBand( S )( property )

Returns: true or false.

IsBand returns true if every element of the semigroup S is an idempotent and false if it is not. An inverse semigroup is band if and only if it is a semilattice; see IsSemilattice (17.1-18).

gap> S := Semigroup(
> 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> IsBand(S);
true
gap> S := InverseSemigroup(
> PartialPerm([1, 2, 3, 4, 8, 9], [5, 8, 7, 6, 9, 1]),
> PartialPerm([1, 3, 4, 7, 8, 9, 10], [2, 3, 8, 7, 10, 6, 1]));;
gap> IsBand(S);
false
gap> IsBand(IdempotentGeneratedSubsemigroup(S));
true
gap> S := PartitionMonoid(4);
<regular bipartition monoid of degree 4 with 4 generators>
gap> M := MinimalIdeal(S);
<simple bipartition semigroup ideal of degree 4 with 1 generator>
gap> IsBand(M);
true

17.1-2 IsBlockGroup
‣ IsBlockGroup( S )( property )
‣ IsSemigroupWithCommutingIdempotents( S )( property )

Returns: true or false.

IsBlockGroup and IsSemigroupWithCommutingIdempotents return true if the semigroup S is a block group and false if it is not.

A semigroup S is a block group if every \(\mathscr{L}\)-class and every \(\mathscr{R}\)-class of S contains at most one idempotent. Every semigroup of partial permutations is a block group.

gap> S := Semigroup(Transformation([5, 6, 7, 3, 1, 4, 2, 8]),
>                   Transformation([3, 6, 8, 5, 7, 4, 2, 8]));;
gap> IsBlockGroup(S);
true
gap> S := Semigroup(
> Transformation([2, 1, 10, 4, 5, 9, 7, 4, 8, 4]),
> Transformation([10, 7, 5, 6, 1, 3, 9, 7, 10, 2]));;
gap> IsBlockGroup(S);
false
gap> S := Semigroup(
> PartialPerm([1, 2], [5, 4]), 
> PartialPerm([1, 2, 3], [1, 2, 5]), 
> PartialPerm([1, 2, 3], [2, 1, 5]), 
> PartialPerm([1, 3, 4], [3, 1, 2]), 
> PartialPerm([1, 3, 4, 5], [5, 4, 3, 2]));;
gap> T := Range(IsomorphismBlockBijectionSemigroup(S));
<bipartition semigroup of degree 6 with 5 generators>
gap> IsBlockGroup(T);
true
gap> IsBlockGroup(Range(IsomorphismBipartitionSemigroup(S)));
true
gap> S := Semigroup(
> Bipartition([[1, -2], [2, -3], [3, -4], [4, -1]]), 
> Bipartition([[1, -2], [2, -1], [3, -3], [4, -4]]), 
> Bipartition([[1, 2, -3], [3, -1, -2], [4, -4]]), 
> Bipartition([[1, -1], [2, -2], [3, -3], [4, -4]]));;
gap> IsBlockGroup(S);
true

17.1-3 IsCommutativeSemigroup
‣ IsCommutativeSemigroup( S )( property )

Returns: true or false.

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

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

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

17.1-4 IsCompletelyRegularSemigroup
‣ IsCompletelyRegularSemigroup( S )( property )

Returns: true or false.

IsCompletelyRegularSemigroup returns true if every element of the semigroup S is contained in a subgroup of S.

An inverse semigroup is completely regular if and only if it is a Clifford semigroup; see IsCliffordSemigroup (17.2-1).

gap> S := Semigroup(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> IsCompletelyRegularSemigroup(S);
true
gap> IsInverseSemigroup(S);
true
gap> T := Range(IsomorphismPartialPermSemigroup(S));;
gap> IsCompletelyRegularSemigroup(T);
true
gap> IsCliffordSemigroup(T);         
true
gap> S := Semigroup(
> Bipartition([[1, 3, -4], [2, 4, -1, -2], [-3]]), 
> Bipartition([[1, -1], [2, 3, 4, -3], [-2, -4]]));;
gap> IsCompletelyRegularSemigroup(S);
false

17.1-5 IsCongruenceFreeSemigroup
‣ IsCongruenceFreeSemigroup( S )( property )

Returns: true or false.

IsCongruenceFreeSemigroup returns true if the semigroup S is a congruence-free semigroup and false if it is not.

A semigroup S is congruence-free if it has no non-trivial proper congruences.

A semigroup with zero is congruence-free if and only if it is isomorphic to a regular Rees 0-matrix semigroup R whose underlying semigroup is the trivial group, no two rows of the matrix of R are identical, and no two columns are identical; see Theorem 3.7.1 in [How95].

A semigroup without zero is congruence-free if and only if it is a simple group or has order 2; see Theorem 3.7.2 in [How95].

gap> S := Semigroup(Transformation([4, 2, 3, 3, 4]));;
gap> IsCongruenceFreeSemigroup(S);
true
gap> S := Semigroup(Transformation([2, 2, 4, 4]),
>                   Transformation([5, 3, 4, 4, 6, 6]));;
gap> IsCongruenceFreeSemigroup(S);
false

17.1-6 IsGroupAsSemigroup
‣ IsGroupAsSemigroup( S )( property )

Returns: true or false.

IsGroupAsSemigroup returns true if and only if the semigroup S is mathematically a group.

gap> S := Semigroup(Transformation([2, 4, 5, 3, 7, 8, 6, 9, 1]), 
>                   Transformation([3, 5, 6, 7, 8, 1, 9, 2, 4]));;
gap> IsGroupAsSemigroup(S);
true
gap> G := SymmetricGroup(5);;
gap> S := Range(IsomorphismPartialPermSemigroup(G));
<inverse partial perm semigroup of rank 5 with 2 generators>
gap> IsGroupAsSemigroup(S);
true
gap> S := SymmetricGroup([1, 2, 10]);;
gap> T := Range(IsomorphismBlockBijectionSemigroup(
> Range(IsomorphismPartialPermSemigroup(S))));
<inverse bipartition semigroup of degree 11 with 2 generators>
gap> IsGroupAsSemigroup(T);
true

17.1-7 IsIdempotentGenerated
‣ IsIdempotentGenerated( S )( property )
‣ IsSemiBand( S )( property )

Returns: true or false.

IsIdempotentGenerated and IsSemiBand return true if the semigroup S is generated by its idempotents and false if it is not. See also Idempotents (15.6-1) and IdempotentGeneratedSubsemigroup (15.6-3).

An inverse semigroup is idempotent-generated if and only if it is a semilattice; see IsSemilattice (17.1-18).

Semiband and idempotent-generated are synonymous in this context.

gap> S := SingularTransformationSemigroup(4);
<regular transformation semigroup ideal of degree 4 with 1 generator>
gap> IsIdempotentGenerated(S);
true
gap> S := SingularBrauerMonoid(5);
<regular bipartition semigroup ideal of degree 5 with 1 generator>
gap> IsIdempotentGenerated(S);
true

17.1-8 IsLeftSimple
‣ IsLeftSimple( S )( property )
‣ IsRightSimple( S )( property )

Returns: true or false.

IsLeftSimple and IsRightSimple returns true if the semigroup S has only one \(\mathscr{L}\)-class or one \(\mathscr{R}\)-class, respectively, and returns false if it has more than one.

An inverse semigroup is left simple if and only if it is right simple if and only if it is a group; see IsGroupAsSemigroup (17.1-6).

gap> S := Semigroup(Transformation([6, 7, 9, 6, 8, 9, 8, 7, 6]), 
>                   Transformation([6, 8, 9, 6, 8, 8, 7, 9, 6]), 
>                   Transformation([6, 8, 9, 7, 8, 8, 7, 9, 6]), 
>                   Transformation([6, 9, 8, 6, 7, 9, 7, 8, 6]), 
>                   Transformation([6, 9, 9, 6, 8, 8, 7, 9, 6]), 
>                   Transformation([6, 9, 9, 7, 8, 8, 6, 9, 7]), 
>                   Transformation([7, 8, 8, 7, 9, 9, 7, 8, 6]), 
>                   Transformation([7, 9, 9, 7, 6, 9, 6, 8, 7]), 
>                   Transformation([8, 7, 6, 9, 8, 6, 8, 7, 9]), 
>                   Transformation([9, 6, 6, 7, 8, 8, 7, 6, 9]), 
>                   Transformation([9, 6, 6, 7, 9, 6, 9, 8, 7]), 
>                   Transformation([9, 6, 7, 9, 6, 6, 9, 7, 8]), 
>                   Transformation([9, 6, 8, 7, 9, 6, 9, 8, 7]), 
>                   Transformation([9, 7, 6, 8, 7, 7, 9, 6, 8]), 
>                   Transformation([9, 7, 7, 8, 9, 6, 9, 7, 8]), 
>                   Transformation([9, 8, 8, 9, 6, 7, 6, 8, 9]));;
gap> IsRightSimple(S);
false
gap> IsLeftSimple(S);
true
gap> IsGroupAsSemigroup(S);
false
gap> NrRClasses(S);
16
gap> S := BrauerMonoid(6);;
gap> S := Semigroup(RClass(S, Random(MinimalDClass(S))));;
gap> IsLeftSimple(S);
false
gap> IsRightSimple(S);
true

17.1-9 IsLeftZeroSemigroup
‣ IsLeftZeroSemigroup( S )( property )

Returns: true or false.

IsLeftZeroSemigroup returns true if the semigroup S is a left zero semigroup and false if it is not.

A semigroup is a left zero semigroup if x*y=x for all x,y. An inverse semigroup is a left zero semigroup if and only if it is trivial.

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

17.1-10 IsMonogenicSemigroup
‣ IsMonogenicSemigroup( S )( property )

Returns: true or false.

IsMonogenicSemigroup returns true if the semigroup S is monogenic and it returns false if it is not.

A semigroup is monogenic if it is generated by a single element. See also IsMonogenicInverseSemigroup (17.2-7) and IndexPeriodOfTransformation (Reference: IndexPeriodOfTransformation).

gap> S := Semigroup(
> Transformation(
>  [2, 2, 2, 11, 10, 8, 10, 11, 2, 11, 10, 2, 11, 11, 10]),
> Transformation(
>  [2, 2, 2, 8, 11, 15, 11, 10, 2, 10, 11, 2, 10, 4, 7]), 
> Transformation(
>  [2, 2, 2, 11, 10, 8, 10, 11, 2, 11, 10, 2, 11, 11, 10]),
> Transformation(
>  [2, 2, 12, 7, 8, 14, 8, 11, 2, 11, 10, 2, 11, 15, 4]));;
gap> IsMonogenicSemigroup(S);
true
gap> S := Semigroup(
> Bipartition([[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, -2, -5, -7, -9], 
>              [-1, -10], [-3, -4, -6, -8]]), 
>  Bipartition([[1, 4, 7, 8, -2], [2, 3, 5, 10, -5], 
>               [6, 9, -7, -9], [-1, -10], [-3, -4, -6, -8]]));;
gap> IsMonogenicSemigroup(S);
true

17.1-11 IsMonoidAsSemigroup
‣ IsMonoidAsSemigroup( S )( property )

Returns: true or false.

IsMonoidAsSemigroup returns true if and only if the semigroup S is mathematically a monoid, i.e. if and only if it contains a MultiplicativeNeutralElement (Reference: MultiplicativeNeutralElement).

It is possible that a semigroup which satisfies IsMonoidAsSemigroup is not in the GAP category IsMonoid (Reference: IsMonoid). This is possible if the MultiplicativeNeutralElement (Reference: MultiplicativeNeutralElement) of S is not equal to the One (Reference: One) of any element in S. Therefore a semigroup satisfying IsMonoidAsSemigroup may not possess the attributes of a monoid (such as, GeneratorsOfMonoid (Reference: GeneratorsOfMonoid)).

See also One (Reference: One), IsInverseMonoid (Reference: IsInverseMonoid) and IsomorphismTransformationMonoid (Reference: IsomorphismTransformationMonoid).

gap> S := Semigroup(Transformation([1, 4, 6, 2, 5, 3, 7, 8, 9, 9]),
>                   Transformation([6, 3, 2, 7, 5, 1, 8, 8, 9, 9]));;
gap> IsMonoidAsSemigroup(S);
true
gap> IsMonoid(S);
false
gap> MultiplicativeNeutralElement(S);
Transformation( [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 9 ] )
gap> T := Range(IsomorphismBipartitionSemigroup(S));;
gap> IsMonoidAsSemigroup(T);
true
gap> IsMonoid(T);
false
gap> One(T);
fail
gap> S := Monoid(Transformation([8, 2, 8, 9, 10, 6, 2, 8, 7, 8]),
>                Transformation([9, 2, 6, 3, 6, 4, 5, 5, 3, 2]));;
gap> IsMonoidAsSemigroup(S);
true

17.1-12 IsOrthodoxSemigroup
‣ IsOrthodoxSemigroup( S )( property )

Returns: true or false.

IsOrthodoxSemigroup returns true if the semigroup S is orthodox and false if it is not.

A semigroup is orthodox if it is regular and its idempotent elements form a subsemigroup. Every inverse semigroup is also an orthodox semigroup.

See also IsRegularSemigroup (17.1-15) and IsRegularSemigroup (Reference: IsRegularSemigroup).

gap> S := Semigroup(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> IsOrthodoxSemigroup(S);
true
gap> S := DualSymmetricInverseMonoid(5);;
gap> S := Semigroup(GeneratorsOfSemigroup(S));;
gap> IsOrthodoxSemigroup(S);
true

17.1-13 IsRectangularBand
‣ IsRectangularBand( S )( property )

Returns: true or false.

IsRectangularBand returns true if the semigroup S is a rectangular band and false if it is not.

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

Equivalently, S is a rectangular band if S is isomorphic to a semigroup of the form I × Λ with multiplication (i, λ)(j, μ) = (i, μ). In this case, S is called an |I| × |Λ| rectangular band.

An inverse semigroup is a rectangular band if and only if it is a group.

gap> S := Semigroup(
> 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> IsRectangularBand(S);
true
gap> IsRectangularBand(MinimalIdeal(PartitionMonoid(4)));
true

17.1-14 IsRectangularGroup
‣ IsRectangularGroup( S )( property )

Returns: true or false.

A semigroup is rectangular group if it is the direct product of a group and a rectangular band. Or equivalently, if it is orthodox and simple.

gap> G := AsTransformationSemigroup(MathieuGroup(11));
<transformation semigroup of size 7920, degree 11 with 2 generators>
gap> R := RectangularBand(3, 2);
<regular transformation semigroup of size 6, degree 7 with 3 generators>
gap> S := DirectProduct(G, R);
<transformation semigroup of size 47520, degree 18 with 4 generators>
gap> IsRectangularGroup(R);
true
gap> IsRectangularGroup(G);
true
gap> IsRectangularGroup(S);
true
gap> IsRectangularGroup(JonesMonoid(3));
false

17.1-15 IsRegularSemigroup
‣ IsRegularSemigroup( S )( property )

Returns: true or false.

IsRegularSemigroup returns true if the semigroup S is regular and false if it is not.

A semigroup S is regular if for all x in S there exists y in S such that x * y * x = x. Every inverse semigroup is regular, and a semigroup of partial permutations is regular if and only if it is an inverse semigroup.

See also IsRegularDClass (Reference: IsRegularDClass), IsRegularClass (14.3-2), and IsRegularSemigroupElement (Reference: IsRegularSemigroupElement).

gap> IsRegularSemigroup(FullTransformationSemigroup(5));
true
gap> IsRegularSemigroup(JonesMonoid(5));
true

17.1-16 IsRightZeroSemigroup
‣ IsRightZeroSemigroup( S )( property )

Returns: true or false.

IsRightZeroSemigroup returns true if the S is a right zero semigroup and false if it is not.

A semigroup S is a right zero semigroup if x * y = y for all x, y in S. An inverse semigroup is a right zero semigroup if and only if it is trivial.

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

17.1-17 IsXTrivial
‣ IsRTrivial( S )( property )
‣ IsLTrivial( S )( property )
‣ IsHTrivial( S )( property )
‣ IsDTrivial( S )( property )
‣ IsAperiodicSemigroup( S )( property )
‣ IsCombinatorialSemigroup( S )( property )

Returns: true or false.

IsXTrivial returns true if Green's \(\mathscr{R}\)-relation, \(\mathscr{L}\)-relation, \(\mathscr{H}\)-relation, \(\mathscr{D}\)-relation, respectively, on the semigroup S is trivial and false if it is not. These properties can also be applied to a Green's class instead of a semigroup where applicable.

For inverse semigroups, the properties of being \(\mathscr{R}\)-trivial, \(\mathscr{L}\)-trivial, \(\mathscr{D}\)-trivial, and a semilattice are equivalent; see IsSemilattice (17.1-18).

A semigroup is aperiodic if its contains no non-trivial subgroups (equivalently, all of its group \(\mathscr{H}\)-classes are trivial). A finite semigroup is aperiodic if and only if it is \(\mathscr{H}\)-trivial.

Combinatorial is a synonym for aperiodic in this context.

gap> S := Semigroup(
>  Transformation([1, 5, 1, 3, 7, 10, 6, 2, 7, 10]), 
>  Transformation([4, 4, 5, 6, 7, 7, 7, 4, 3, 10]));;
gap> IsHTrivial(S);
true
gap> Size(S);
108
gap> IsRTrivial(S);
false
gap> IsLTrivial(S);
false

17.1-18 IsSemilattice
‣ IsSemilattice( S )( property )

Returns: true or false.

IsSemilattice returns true if the semigroup S is a semilattice and false if it is not.

A semigroup is a semilattice if it is commutative and every element is an idempotent. The idempotents of an inverse semigroup form a semilattice.

gap> S := Semigroup(Transformation([2, 5, 1, 7, 3, 7, 7]), 
>                   Transformation([3, 6, 5, 7, 2, 1, 7]));;
gap> Size(S);
631
gap> IsInverseSemigroup(S);
true
gap> A := Semigroup(Idempotents(S)); 
<transformation semigroup of degree 7 with 32 generators>
gap> IsSemilattice(A);
true
gap> S := FactorisableDualSymmetricInverseSemigroup(5);;
gap> S := IdempotentGeneratedSubsemigroup(S);;
gap> IsSemilattice(S);
true

17.1-19 IsSimpleSemigroup
‣ IsSimpleSemigroup( S )( property )
‣ IsCompletelySimpleSemigroup( S )( property )

Returns: true or false.

IsSimpleSemigroup returns true if the semigroup S is simple and false if it is not.

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. An inverse semigroup is simple if and only if it is a group.

gap> S := Semigroup(
>  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> IsSimpleSemigroup(S);
true
gap> IsCompletelySimpleSemigroup(S);
true
gap> IsSimpleSemigroup(MinimalIdeal(BrauerMonoid(6)));
true
gap> R := Range(IsomorphismReesMatrixSemigroup(
> MinimalIdeal(BrauerMonoid(6))));
<Rees matrix semigroup 15x15 over Group(())>

17.1-20 IsSynchronizingSemigroup
‣ IsSynchronizingSemigroup( S[, n] )( operation )
‣ IsSynchronizingTransformationCollection( coll[, n] )( operation )

Returns: true or false.

For a positive integer n, IsSynchronizingSemigroup returns true if the semigroup of transformations S contains a transformation with constant value on [1 .. n]. Note that this function will return true whenever n = 1. See also ConstantTransformation (Reference: ConstantTransformation).

If the optional second argument is not specified, then n will be taken to be the value of DegreeOfTransformationSemigroup (Reference: DegreeOfTransformationSemigroup) for S.

The operation IsSynchronizingTransformationCollection behaves in the same way as IsSynchronizingSemigroup but can be applied to any collection of transformations and not only semigroups.

Note that the semigroup consisting of the identity transformation has degree 0, and for this special case the function IsSynchronizingSemigroup will return false.

gap> S := Semigroup(
> Transformation([1, 1, 8, 7, 6, 6, 4, 1, 8, 9]), 
> Transformation([5, 8, 7, 6, 10, 8, 7, 6, 9, 7]));;
gap> IsSynchronizingSemigroup(S, 10);
true
gap> S := Semigroup(
> Transformation([3, 8, 1, 1, 9, 9, 8, 7, 9, 6]), 
> Transformation([7, 6, 8, 7, 5, 6, 8, 7, 8, 9]));;
gap> IsSynchronizingSemigroup(S, 10);
false
gap> Representative(MinimalIdeal(S));
Transformation( [ 7, 8, 8, 7, 8, 8, 8, 7, 8, 8 ] )

17.1-21 IsUnitRegularMonoid
‣ IsUnitRegularMonoid( S )( property )

Returns: true if the semigroup S is unit regular and false if it is not.

A monoid is unit regular if and only if for every >x in S there exists an element y in the group of units of S such that x*y*x=x.

gap> IsUnitRegularMonoid(FullTransformationMonoid(3));
true

17.1-22 IsZeroGroup
‣ IsZeroGroup( S )( property )

Returns: true or false.

IsZeroGroup returns true if the semigroup S is a zero group and false if it is not.

A semigroup S is a zero group if there exists an element z in S such that S without z is a group and x*z=z*x=z for all x in S. Every zero group is an inverse semigroup.

gap> S := Semigroup(Transformation([2, 2, 3, 4, 6, 8, 5, 5, 9]),
>                   Transformation([3, 3, 8, 2, 5, 6, 4, 4, 9]),
>                   ConstantTransformation(9, 9));;
gap> IsZeroGroup(S);
true
gap> T := Range(IsomorphismPartialPermSemigroup(S));;
gap> IsZeroGroup(T);
true
gap> IsZeroGroup(JonesMonoid(2));
true

17.1-23 IsZeroRectangularBand
‣ IsZeroRectangularBand( S )( property )

Returns: true or false.

IsZeroRectangularBand returns true if the semigroup S is a zero rectangular band and false if it is not.

A semigroup is a 0-rectangular band if it is 0-simple and \(\mathscr{H}\)-trivial; see also IsZeroSimpleSemigroup (17.1-25) and IsHTrivial (17.1-17). An inverse semigroup is a 0-rectangular band if and only if it is a 0-group; see IsZeroGroup (17.1-22).

gap> S := Semigroup(
>  Transformation([1, 3, 7, 9, 1, 12, 13, 1, 15, 9, 1, 18, 1, 1, 13, 
>                  1, 1, 21, 1, 1, 1, 1, 1, 25, 26, 1]),
> Transformation([1, 5, 1, 5, 11, 1, 1, 14, 1, 16, 17, 1, 1, 19, 1, 
>                 11, 1, 1, 1, 23, 1, 16, 19, 1, 1, 1]),
> Transformation([1, 4, 8, 1, 10, 1, 8, 1, 1, 1, 10, 1, 8, 10, 1, 1, 
>                 20, 1, 22, 1, 8, 1, 1, 1, 1, 1]),
> Transformation([1, 6, 6, 1, 1, 1, 6, 1, 1, 1, 1, 1, 6, 1, 6, 1, 1, 
>                 6, 1, 1, 24, 1, 1, 1, 1, 6]));;
gap> D := DClass(S, 
> Transformation([1, 8, 1, 1, 8, 1, 1, 1, 1, 1, 8, 1, 1, 8, 1, 1, 1,
>                 1, 1, 1, 1, 1, 1, 1, 1, 1]));;
gap> IsZeroRectangularBand(Semigroup(D)); 
true
gap> IsZeroRectangularBand(Semigroup(GreensDClasses(S)[1]));
false

17.1-24 IsZeroSemigroup
‣ IsZeroSemigroup( S )( property )

Returns: true or false.

IsZeroSemigroup returns true if the semigroup S is a zero semigroup and false if it is not.

A semigroup S is a zero semigroup if there exists an element z in S such that x*y=z for all x,y in S. An inverse semigroup is a zero semigroup if and only if it is trivial.

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

17.1-25 IsZeroSimpleSemigroup
‣ IsZeroSimpleSemigroup( S )( property )

Returns: true or false.

IsZeroSimpleSemigroup returns true if the semigroup S is 0-simple and false if it is not.

A semigroup is a 0-simple if it has no two-sided ideals other than itself and the set containing the zero element; see also MultiplicativeZero (15.4-3). An inverse semigroup is 0-simple if and only if it is a Brandt semigroup; see IsBrandtSemigroup (17.2-2).

gap> S := Semigroup(
>  Transformation([1, 17, 17, 17, 17, 17, 17, 17, 17, 17, 5, 17, 
>                  17, 17, 17, 17, 17]), 
>  Transformation([1, 17, 17, 17, 11, 17, 17, 17, 17, 17, 17, 17, 
>                  17, 17, 17, 17, 17]), 
>  Transformation([1, 17, 17, 17, 17, 17, 17, 17, 17, 17, 4, 17, 
>                  17, 17, 17, 17, 17]), 
>  Transformation([1, 17, 17, 5, 17, 17, 17, 17, 17, 17, 17, 17, 
>                  17, 17, 17, 17, 17]));;
gap> IsZeroSimpleSemigroup(S);
true
gap> S := Semigroup(
> Transformation([2, 3, 4, 5, 1, 8, 7, 6, 2, 7]),
> Transformation([2, 3, 4, 5, 6, 8, 7, 1, 2, 2]));;
gap> IsZeroSimpleSemigroup(S);
false

17.2 Properties of inverse semigroups

17.2-1 IsCliffordSemigroup
‣ IsCliffordSemigroup( S )( property )

Returns: true or false.

IsCliffordSemigroup returns true if the semigroup S is regular and its idempotents are central, and false if it is not.

gap> S := Semigroup(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> IsCliffordSemigroup(S);
true
gap> T := Range(IsomorphismPartialPermSemigroup(S));;
gap> IsCliffordSemigroup(S);
true
gap> S := DualSymmetricInverseMonoid(5);;
gap> T := IdempotentGeneratedSubsemigroup(S);;
gap> IsCliffordSemigroup(T);
true

17.2-2 IsBrandtSemigroup
‣ IsBrandtSemigroup( S )( property )

Returns: true or false.

IsBrandtSemigroup return true if the semigroup S is a finite 0-simple inverse semigroup, and false if it is not. See also IsZeroSimpleSemigroup (17.1-25) and IsInverseSemigroup (Reference: IsInverseSemigroup).

gap> S := Semigroup(
> Transformation([2, 8, 8, 8, 8, 8, 8, 8]),
> Transformation([5, 8, 8, 8, 8, 8, 8, 8]),
> Transformation([8, 3, 8, 8, 8, 8, 8, 8]),
> Transformation([8, 6, 8, 8, 8, 8, 8, 8]),
> Transformation([8, 8, 1, 8, 8, 8, 8, 8]),
> Transformation([8, 8, 8, 1, 8, 8, 8, 8]),
> Transformation([8, 8, 8, 8, 4, 8, 8, 8]),
> Transformation([8, 8, 8, 8, 8, 7, 8, 8]),
> Transformation([8, 8, 8, 8, 8, 8, 2, 8]));;
gap> IsBrandtSemigroup(S);
true
gap> T := Range(IsomorphismPartialPermSemigroup(S));;
gap> IsBrandtSemigroup(T);
true
gap> S := DualSymmetricInverseMonoid(4);;
gap> D := DClass(S, 
> Bipartition( [ [ 1, 2, 3, -1, -2, -3 ], [ 4, -4 ] ] ));;
gap> R := InjectionPrincipalFactor(D);;
gap> S := Semigroup(PreImages(R, GeneratorsOfSemigroup(Range(R))));;
gap> IsBrandtSemigroup(S);
true

17.2-3 IsEUnitaryInverseSemigroup
‣ IsEUnitaryInverseSemigroup( S )( property )

Returns: true or false.

As described in Section 5.9 of [How95], an inverse semigroup S with semilattice of idempotents E is E-unitary if for

s \in S\textrm{ and }e \in E\textrm{: }es \in E \Rightarrow s \in E.

Equivalently, S is E-unitary if E is closed in the natural partial order (see Proposition 5.9.1 in [How95]):

\textrm{for } s \in S\textrm{ and }e \in E\textrm{: }e \le s \Rightarrow s \in E.

This condition is equivalent to E being majorantly closed in S. See IdempotentGeneratedSubsemigroup (15.6-3) and IsMajorantlyClosed (17.2-6). Hence an inverse semigroup of partial permutations, block bijections or partial permutation bipartitions is E-unitary if and only if the idempotent semilattice is majorantly closed.

gap> S := InverseSemigroup(
>  PartialPerm([1, 2, 3, 4], [2, 3, 1, 6]),
>  PartialPerm([1, 2, 3, 5], [3, 2, 1, 6]));;
gap> IsEUnitaryInverseSemigroup(S);
true
gap> e := IdempotentGeneratedSubsemigroup(S);;
gap> ForAll(Difference(S, e), x -> not ForAny(e, y -> y * x in e));
true
gap> T := InverseSemigroup([
>  PartialPerm([1, 3, 4, 6, 8], [2, 5, 10, 7, 9]),
>  PartialPerm([1, 2, 3, 5, 6, 7, 8], [5, 8, 9, 2, 10, 1, 3]),
>  PartialPerm([1, 2, 3, 5, 6, 7, 9], [9, 8, 4, 1, 6, 7, 2])]);;
gap> IsEUnitaryInverseSemigroup(T);
false
gap> U := InverseSemigroup([
>  PartialPerm([1, 2, 3, 4, 5], [2, 3, 4, 5, 1]),
>  PartialPerm([1, 2, 3, 4, 5], [2, 1, 3, 4, 5])]);;
gap> IsEUnitaryInverseSemigroup(U);
true
gap> IsGroupAsSemigroup(U);
true
gap> StructureDescription(U);
"S5"

17.2-4 IsFactorisableInverseMonoid
‣ IsFactorisableInverseMonoid( S )( property )

Returns: true or false.

An inverse monoid is factorisable if every element is the product of an element of the group of units and an idempotent; see also GroupOfUnits (15.5-1) and Idempotents (15.6-1). Hence an inverse semigroup of partial permutations is factorisable if and only if each of its generators is the restriction of some element in the group of units.

gap> S := InverseSemigroup(
> PartialPerm([1, 2, 4], [3, 1, 4]),
> PartialPerm([1, 2, 3, 5], [4, 1, 5, 2]));;
gap> IsFactorisableInverseMonoid(S);
false
gap> IsFactorisableInverseMonoid(SymmetricInverseSemigroup(5)); 
true
gap> IsFactorisableInverseMonoid(DualSymmetricInverseMonoid(5));
false
gap> S := FactorisableDualSymmetricInverseSemigroup(5);;
gap> IsFactorisableInverseMonoid(S);
true

17.2-5 IsJoinIrreducible
‣ IsJoinIrreducible( S, x )( operation )

Returns: true or false.

IsJoinIrreducible determines whether an element x of an inverse semigroup S of partial permutations, block bijections or partial permutation bipartitions is join irreducible.

An element x is join irreducible when it is not the least upper bound (with respect to the natural partial order NaturalLeqPartialPerm (Reference: NaturalLeqPartialPerm)) of any subset of S not containing x.

gap> S := SymmetricInverseSemigroup(3);
<symmetric inverse monoid of degree 3>
gap> x := PartialPerm([1, 2, 3]);
<identity partial perm on [ 1, 2, 3 ]>
gap> IsJoinIrreducible(S, x);
false
gap> T := InverseSemigroup(PartialPerm([1, 2, 4, 3]), 
>                          PartialPerm([1]),
>                          PartialPerm([0, 2]));
<inverse partial perm semigroup of rank 4 with 3 generators>
gap> y := PartialPerm([1, 2, 3, 4]);
<identity partial perm on [ 1, 2, 3, 4 ]>
gap> IsJoinIrreducible(T, y);
true
gap> B := InverseSemigroup([
>  Bipartition([[1, -5], [2, -2], 
>    [3, 5, 6, 7, -1, -4, -6, -7], [4, -3]]),
>  Bipartition([[1, -1], [2, -3], [3, -4], 
>    [4, 5, 7, -2, -6, -7], [6, -5]]),
>  Bipartition([[1, -2], [2, -4], [3, -6], 
>    [4, -1], [5, 7, -3, -7], [6, -5]]),
>  Bipartition([[1, -5], [2, -1], [3, -6], 
>    [4, 5, 7, -2, -4, -7], [6, -3]])]);
<inverse bipartition semigroup of degree 7 with 4 generators>
gap> x := Bipartition( [ [ 1, 2, 3, 5, 6, 7, -2, -3, -4, -5, -6, -7 ], 
> [ 4, -1 ] ] );
<block bijection: [ 1, 2, 3, 5, 6, 7, -2, -3, -4, -5, -6, -7 ], 
 [ 4, -1 ]>
gap> IsJoinIrreducible(B, x);
true
gap> IsJoinIrreducible(B, B.1);
false

17.2-6 IsMajorantlyClosed
‣ IsMajorantlyClosed( S, T )( operation )

Returns: true or false.

IsMajorantlyClosed determines whether the subset T of the inverse semigroup of partial permutations, block bijections or partial permutation bipartitions S is majorantly closed in S. See also MajorantClosure (16.1-3).

We say that T is majorantly closed in S if it contains all elements of S which are greater than or equal to any element of T, with respect to the natural partial order. See NaturalLeqPartialPerm (Reference: NaturalLeqPartialPerm).

Note that T can be a subset of S or a subsemigroup of S.

gap> S := SymmetricInverseSemigroup(2);
<symmetric inverse monoid of degree 2>
gap> T := [Elements(S)[2]];
[ <identity partial perm on [ 1 ]> ]
gap> IsMajorantlyClosed(S, T);
false
gap> U := [Elements(S)[2],Elements(S)[6]];
[ <identity partial perm on [ 1 ]>, <identity partial perm on [ 1, 2 ]
    > ]
gap> IsMajorantlyClosed(S,U);
true
gap> D := DualSymmetricInverseSemigroup(3);
<inverse bipartition monoid of degree 3 with 3 generators>
gap> x := Bipartition([[1, -2], [2, -3], [3, -1]]);;
gap> IsMajorantlyClosed(D, [x]);
true
gap> y := Bipartition([[1, 2, -1, -2], [3, -3]]);;
gap> IsMajorantlyClosed(D, [x, y]);
false

17.2-7 IsMonogenicInverseSemigroup
‣ IsMonogenicInverseSemigroup( S )( property )

Returns: true or false.

IsMonogenicInverseSemigroup returns true if the semigroup S is an inverse monogenic semigroup and it returns false if it is not.

A inverse semigroup is monogenic if it is generated as an inverse semigroup by a single element. See also IsMonogenicSemigroup (17.1-10) and IndexPeriodOfTransformation (Reference: IndexPeriodOfTransformation).

gap> x := PartialPerm([1, 2, 3, 6, 8, 10], [2, 6, 7, 9, 1, 5]);;
gap> S := InverseSemigroup(x, x ^ 2, x ^ 3);;
gap> IsMonogenicSemigroup(S);
false
gap> IsMonogenicInverseSemigroup(S);
true
gap> x := RandomBlockBijection(100);;
gap> S := InverseSemigroup(x, x ^ 2, x ^ 20);;
gap> IsMonogenicInverseSemigroup(S);
true
 [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 Bib Ind

generated by GAPDoc2HTML