In this chapter we describe the methods that are available in Semigroups for determining various properties of a semigroup or monoid.
In this section we describe the properties of an arbitrary semigroup or monoid that can be determined using the Semigroups package.
‣ 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 (12.1-21).
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 size 4140, degree 4 with 4 generators> gap> M := MinimalIdeal(S); <simple bipartition *-semigroup ideal of degree 4 with 1 generator> gap> IsBand(M); true
‣ IsBlockGroup( S ) | ( property ) |
Returns: true or false.
IsBlockGroup returns true if the semigroup S is a block group and false if it is not.
A semigroup S is a block group if every L-class and every 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 := AsSemigroup(IsBlockBijectionSemigroup, S); <block bijection semigroup of degree 6 with 5 generators> gap> IsBlockGroup(T); true gap> IsBlockGroup(AsSemigroup(IsBipartitionSemigroup, 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
‣ 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
‣ 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 (12.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
‣ 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
‣ IsSurjectiveSemigroup( S ) | ( property ) |
Returns: true or false.
A semigroup is surjective if each of its elements can be written as a product of two elements in the semigroup. IsSurjectiveSemigroup(S) returns true if the semigroup S is surjective, and false if it is not.
See also IndecomposableElements (11.6-6).
Note that every monoid, and every regular semigroup, is surjective.
gap> S := FullTransformationMonoid(100); <full transformation monoid of degree 100> gap> IsSurjectiveSemigroup(S); true gap> F := FreeSemigroup(3);; gap> P := F / [[F.1, F.2 * F.1], [F.3 ^ 3, F.3]]; <fp semigroup with 3 generators and 2 relations of length 10> gap> IsSurjectiveSemigroup(P); false gap> I := SingularTransformationMonoid(5); <regular transformation semigroup ideal of degree 5 with 1 generator> gap> IsSurjectiveSemigroup(I); true gap> M := MonogenicSemigroup(IsBipartitionSemigroup, 3, 2); <commutative non-regular block bijection semigroup of size 4, degree 6 with 1 generator> gap> IsSurjectiveSemigroup(M); false
‣ 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> IsGroupAsSemigroup(G); true gap> S := AsSemigroup(IsPartialPermSemigroup, G); <partial perm group of size 120, rank 5 with 2 generators> gap> IsGroupAsSemigroup(S); true gap> G := SymmetricGroup([1, 2, 10]);; gap> T := AsSemigroup(IsBlockBijectionSemigroup, G); <inverse block bijection semigroup of size 6, degree 11 with 2 generators> gap> IsGroupAsSemigroup(T); true
‣ 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 (11.9-1) and IdempotentGeneratedSubsemigroup (11.9-3).
An inverse semigroup is idempotent-generated if and only if it is a semilattice; see IsSemilattice (12.1-21).
The terms 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
‣ IsLeftSimple( S ) | ( property ) |
‣ IsRightSimple( S ) | ( property ) |
Returns: true or false.
IsLeftSimple and IsRightSimple returns true if the semigroup S has only one L-class or one 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 (12.1-7).
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
‣ 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
‣ 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 IsMonogenicMonoid (12.1-12), IsMonogenicInverseSemigroup (12.2-9), and IsMonogenicInverseMonoid (12.2-10).
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 gap> S := FullTransformationSemigroup(5);; gap> IsMonogenicSemigroup(S); false
‣ IsMonogenicMonoid( S ) | ( property ) |
Returns: true or false.
IsMonogenicMonoid returns true if the monoid S is a monogenic monoid and it returns false if it is not.
A monoid is monogenic if it is generated as a monoid by a single element. See also IsMonogenicSemigroup (12.1-11) and IsMonogenicInverseMonoid (12.2-10).
gap> x := PartialPerm([1, 2, 3, 6, 8, 10], [2, 6, 7, 9, 1, 5]);; gap> S := Monoid(x, x ^ 2, x ^ 3);; gap> IsMonogenicSemigroup(S); false gap> IsMonogenicMonoid(S); true gap> S := FullTransformationMonoid(5);; gap> IsMonogenicMonoid(S); false
‣ 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 := AsSemigroup(IsBipartitionSemigroup, 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
‣ 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 (12.1-17) 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
‣ 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
‣ 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 := AsSemigroup(IsTransformationSemigroup, MathieuGroup(11)); <transformation group of size 7920, degree 11 with 2 generators> gap> R := RectangularBand(3, 2); <regular transformation semigroup of size 6, degree 6 with 3 generators> gap> S := DirectProduct(G, R);; gap> IsRectangularGroup(R); true gap> IsRectangularGroup(G); true gap> IsRectangularGroup(S); true gap> IsRectangularGroup(JonesMonoid(3)); false
‣ 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), IsRegularGreensClass (10.3-2), and IsRegularSemigroupElement (Reference: IsRegularSemigroupElement).
gap> IsRegularSemigroup(FullTransformationSemigroup(5)); true gap> IsRegularSemigroup(JonesMonoid(5)); true
‣ 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
‣ 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 R-relation, L-relation, H-relation, 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 R-trivial, L-trivial, D-trivial, and a semilattice are equivalent; see IsSemilattice (12.1-21).
A semigroup is aperiodic if its contains no non-trivial subgroups (equivalently, all of its group H-classes are trivial). A finite semigroup is aperiodic if and only if it is 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
‣ IsSemigroupWithAdjoinedZero( S ) | ( property ) |
Returns: true or false.
IsSemigroupWithAdjoinedZero returns true if the semigroup S can be expressed as the disjoint union of subsemigroups S ∖ { 0 } and { 0 } (where 0 is the MultiplicativeZero (11.7-3) of S).
If this is not the case, then either S lacks a multiplicative zero, or the set S ∖ { 0 } is not a subsemigroup of S, and so IsSemigroupWithAdjoinedZero returns false.
gap> S := Semigroup(Transformation([2, 3, 4, 5, 1, 6]), > Transformation([2, 1, 3, 4, 5, 6]), > Transformation([6, 6, 6, 6, 6, 6])); <transformation semigroup of degree 6 with 3 generators> gap> IsZeroGroup(S); true gap> IsSemigroupWithAdjoinedZero(S); true gap> S := FullTransformationMonoid(4);; gap> IsSemigroupWithAdjoinedZero(S); false
‣ 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 := FactorisableDualSymmetricInverseMonoid(5);; gap> S := IdempotentGeneratedSubsemigroup(S);; gap> IsSemilattice(S); true
‣ 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(())>
‣ IsSynchronizingSemigroup( S ) | ( property ) |
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] where n is the degree of the semigroup. See also ConstantTransformation (Reference: ConstantTransformation).
Note that the semigroup consisting of the identity transformation is the unique transformation semigroup with degree 0. In 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); 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); false gap> Representative(MinimalIdeal(S)); Transformation( [ 8, 7, 7, 7, 8, 8, 7, 8, 8, 8 ] )
‣ 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
‣ 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
‣ 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 H-trivial; see also IsZeroSimpleSemigroup (12.1-28) and IsHTrivial (12.1-19). An inverse semigroup is a 0-rectangular band if and only if it is a 0-group; see IsZeroGroup (12.1-25).
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
‣ 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 ] )
‣ 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 (11.7-3). An inverse semigroup is 0-simple if and only if it is a Brandt semigroup; see IsBrandtSemigroup (12.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
‣ IsSelfDualSemigroup( S ) | ( property ) |
Returns: true or false.
Returns true if the semigroup S is self dual and false otherwise.
A semigroup is self dual if it is isomorphic to its dual, that is, the semigroup T with multiplication * defined by x*y=yx where yx denotes the product in S.
gap> F := FreeSemigroup("a", "b"); <free semigroup on the generators [ a, b ]> gap> AssignGeneratorVariables(F); gap> R := [[a ^ 3, a], [b ^ 2, b], [(a * b) ^ 2, a]]; [ [ a^3, a ], [ b^2, b ], [ (a*b)^2, a ] ] gap> S := F / R; <fp semigroup with 2 generators and 3 relations of length 14> gap> IsSelfDualSemigroup(S); false gap> IsSelfDualSemigroup(FreeBand(3)); true gap> S := DualSymmetricInverseMonoid(3); <inverse block bijection monoid of degree 3 with 3 generators> gap> IsSelfDualSemigroup(S); true
In this section we describe the properties of an inverse semigroup or monoid that can be determined using the Semigroups package.
‣ 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
‣ 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 (12.1-28) 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
‣ 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 (11.9-3) and IsMajorantlyClosed (12.2-8). 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"
‣ IsFInverseSemigroup( S ) | ( property ) |
Returns: true or false.
This functions determines whether a given semigroup is an F-inverse semigroup. An F-inverse semigroup is a semigroup which satisfies IsEUnitaryInverseSemigroup (12.2-3) as well as being isomorphic to some McAlisterTripleSemigroup (8.4-2) where the McAlisterTripleSemigroupPartialOrder (8.4-4) satisfies IsJoinSemilatticeDigraph (Digraphs: IsJoinSemilatticeDigraph). McAlister triple semigroups are a representation of E-unitary inverse semigroups and more can be read about them in Chapter 8.4.
gap> S := InverseMonoid([PartialPermNC([1, 2], [1, 2]), > PartialPermNC([1, 2, 3], [1, 2, 3]), > PartialPermNC([1, 2, 4], [1, 2, 4]), > PartialPermNC([1, 2], [2, 1]), PartialPermNC([1, 2, 3], [2, 1, 3]), > PartialPermNC([1, 2, 4], [2, 1, 4])]);; gap> IsEUnitaryInverseSemigroup(S); true gap> IsFInverseSemigroup(S); false gap> IsFInverseSemigroup(IdempotentGeneratedSubsemigroup(S)); true
‣ IsFInverseMonoid( S ) | ( property ) |
Returns: true or false.
This function determines whether a given semigroup is an F-inverse monoid. A semigroup is an F-inverse monoid when it satisfies IsMonoid (Reference: IsMonoid) and IsFInverseSemigroup (12.2-4).
‣ 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 (11.8-1) and Idempotents (11.9-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 := FactorisableDualSymmetricInverseMonoid(5);; gap> IsFactorisableInverseMonoid(S); true
‣ 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 block bijection 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
‣ 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 (11.14-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 block bijection 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
‣ IsMonogenicInverseSemigroup( S ) | ( property ) |
Returns: true or false.
IsMonogenicInverseSemigroup returns true if the semigroup S is a monogenic inverse 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 (12.1-11) and IsMonogenicInverseMonoid (12.2-10).
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 gap> S := SymmetricInverseSemigroup(5);; gap> IsMonogenicInverseSemigroup(S); false
‣ IsMonogenicInverseMonoid( S ) | ( property ) |
Returns: true or false.
IsMonogenicInverseMonoid returns true if the monoid S is a monogenic inverse monoid and it returns false if it is not.
A inverse monoid is monogenic if it is generated as an inverse monoid by a single element. See also IsMonogenicInverseSemigroup (12.2-9) and IsMonogenicMonoid (12.1-12).
gap> x := PartialPerm([1, 2, 3, 6, 8, 10], [2, 6, 7, 9, 1, 5]);; gap> S := InverseMonoid(x, x ^ 2, x ^ 3);; gap> IsMonogenicMonoid(S); false gap> IsMonogenicInverseSemigroup(S); false gap> IsMonogenicInverseMonoid(S); true gap> x := RandomBlockBijection(100);; gap> S := InverseMonoid(x, x ^ 2, x ^ 20);; gap> IsMonogenicInverseMonoid(S); true gap> S := SymmetricInverseMonoid(5);; gap> IsMonogenicInverseMonoid(S); false
generated by GAPDoc2HTML