GAP (semigroups) - Chapter 3: Ideals

In this chapter we describe the various ways that an ideal of a semigroup can be created and manipulated in Semigroups.

The methods in the Semigroups package apply to any ideal of a transformation, partial permutation, or bipartition semigroup, or an ideal of a subsemigroup of a Rees 0-matrix semigroup or semigroup of matrices over a finite field, that is created by the function SemigroupIdeal (3.1-1) or SemigroupIdealByGenerators. Anything that can be calculated for a semigroup defined by a generating set can also be found for an ideal. This works particularly well for regular ideals, since such an ideal can be represented using a similar data structure to that used to represent a semigroup defined by a generating set but without the necessity to find a generating set for the ideal. Many methods for non-regular ideals rely on first finding a generating set for the ideal, which can be costly (but not nearly as costly as an exhaustive enumeration of the elements of the ideal). We plan to improve the functionality of Semigroups for non-regular ideals in the future.

3.1 Creating ideals

3.1-1 SemigroupIdeal

If obj1, obj2, ... are (any combination) of elements of the semigroup S or collections of elements of S (including subsemigroups and ideals of S), then SemigroupIdeal returns the 2-sided ideal of the semigroup S generated by the union of obj1, obj2, ....

gap> S := SymmetricInverseMonoid(10);
<symmetric inverse monoid of degree 10>
gap> I := SemigroupIdeal(S, PartialPerm([1,2]));
<inverse partial perm semigroup ideal of rank 10 with 1 generator>
gap> Size(I);
4151
gap> I := SemigroupIdeal(S, I, Idempotents(S));
<inverse partial perm semigroup ideal of rank 10 with 1025 generators>

3.2 Attributes of ideals

3.2-1 GeneratorsOfSemigroupIdeal

This function returns the generators of the two-sided ideal I, which were used to defined I when it was created.

If I is an ideal of a semigroup, then I is defined to be the least 2-sided ideal of a semigroup S containing a set J of elements of S. The set J is said to generate I.

The notion of the generators of an ideal is distinct from the notion of the generators of a semigroup or monoid. In particular, the semigroup generated by the generators of an ideal is not, in general, equal to that ideal. Use GeneratorsOfSemigroup (Reference: GeneratorsOfSemigroup) to obtain a semigroup generating set for an ideal, but beware that this can be very costly.

gap> S:=Semigroup(
> Bipartition( [ [ 1, 2, 3, 4, -1 ], [ -2, -4 ], [ -3 ] ] ), 
> Bipartition( [ [ 1, 2, 3, -3 ], [ 4 ], [ -1 ], [ -2, -4 ] ] ), 
> Bipartition( [ [ 1, 3, -2 ], [ 2, 4 ], [ -1, -3, -4 ] ] ), 
> Bipartition( [ [ 1 ], [ 2, 3, 4 ], [ -1, -3, -4 ], [ -2 ] ] ), 
> Bipartition( [ [ 1 ], [ 2, 4, -2 ], [ 3, -4 ], [ -1 ], [ -3 ] ] ) );;
gap> I:=SemigroupIdeal(S, S.1*S.2*S.5);
<regular bipartition semigroup ideal of degree 4 with 1 generator>
gap> GeneratorsOfSemigroupIdeal(I);
[ <bipartition: [ 1, 2, 3, 4, -4 ], [ -1 ], [ -2 ], [ -3 ]> ]
gap> I=Semigroup(GeneratorsOfSemigroupIdeal(I));
false

3.2-2 MinimalIdealGeneratingSet

This function returns a minimal set of elements of the parent of the semigroup ideal I required to generate I as an ideal.

gap> S:=Monoid( 
> Bipartition( [ [ 1, 2, 3, -2 ], [ 4 ], [ -1, -4 ], [ -3 ] ] ), 
> Bipartition( [ [ 1, 4, -2, -4 ], [ 2, -1, -3 ], [ 3 ] ] ) );;
gap> I:=SemigroupIdeal(S, S);
<non-regular bipartition semigroup ideal of degree 4 with 3 generators
 >
gap> MinimalIdealGeneratingSet(I);
[ <block bijection: [ 1, -1 ], [ 2, -2 ], [ 3, -3 ], [ 4, -4 ]> ]

3.2-3 SupersemigroupOfIdeal

The Parent (Reference: Parent) of an ideal is the semigroup in which the ideal was created, i.e. the first argument of SemigroupIdeal (3.1-1) or SemigroupByGenerators. This function returns the semigroup containing GeneratorsOfSemigroup (Reference: GeneratorsOfSemigroup) which are used to compute the ideal.

For a regular semigroup ideal, SupersemigroupOfIdeal will always be the top most semigroup used to create any of the predecessors of the current ideal. For example, if S is a semigroup, I is a regular ideal of S, and J is an ideal of I, then Parent(J) is I and SupersemigroupOfIdeal(J) is S. This is to avoid computing a generating set for I, in this example, which is expensive and unnecessary since I is regular (in which case the Green's relations of I are just restrictions of the Green's relations on S). If S is a semigroup, I is a non-regular ideal of S, J is an ideal of I, then SupersemigroupOfIdeal(J) is I, since we currently have to use GeneratorsOfSemigroup(I) to compute anything about I other than its size and membership.