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] 

19 Congruences
 19.1 Semigroup congruence objects
 19.2 Creating congruences
 19.3 Congruence classes
 19.4 Comparing congruences
 19.5 Congruences on Rees matrix semigroups
 19.6 Congruences on inverse semigroups
 19.7 Rees congruences
 19.8 Universal congruences

19 Congruences

Congruences in Semigroups can be described in several different ways:

The operation SemigroupCongruence (19.2-1) can be used to create any of these, interpreting the arguments in a smart way. The usual way of specifying a congruence will be by giving a set of generating pairs, but a user with an ideal could instead create a Rees congruence or universal congruence.

If a congruence is specified by generating pairs on a simple, 0-simple, or inverse semigroup, then the congruence will be converted automatically to one of the last two items in the above list, to reduce the complexity of any calculations to be performed. The user need not manually specify, or even be aware of, the congruence's linked triple or kernel and trace.

We can also create left congruences and right congruences, using the LeftSemigroupCongruence (19.2-2) and RightSemigroupCongruence (19.2-3) functions.

Please note that congruence objects made in GAP before loading the Semigroups package may not behave correctly after Semigroups is loaded. If Semigroups is loaded at the beginning of the session, or before any congruence work is done, then the objects should behave correctly.

19.1 Semigroup congruence objects

19.1-1 IsSemigroupCongruence
‣ IsSemigroupCongruence( obj )( property )

A semigroup congruence cong is an equivalence relation on a semigroup S which respects left and right multiplication.

That is, if (a,b) is a pair in cong, and x is an element of S, then (ax,bx) and (xa,xb) are both in cong.

The simplest way of creating a congruence in Semigroups is by a set of generating pairs. See SemigroupCongruence (19.2-1).

gap> S:=Semigroup(Transformation( [ 2, 1, 1, 2, 1 ] ), 
>                 Transformation( [ 3, 4, 3, 4, 4 ] ), 
>                 Transformation( [ 3, 4, 3, 4, 3 ] ),  
>                 Transformation( [ 4, 3, 3, 4, 4 ] ));;
gap> pair1 := [Transformation( [ 3, 4, 3, 4, 3 ] ),
>              Transformation( [ 1, 2, 1, 2, 1 ] )];;
gap> pair2 := [Transformation( [ 4, 3, 4, 3, 4 ] ),
>              Transformation( [ 3, 4, 3, 4, 3 ] )];;
gap> cong := SemigroupCongruence(S, [pair1, pair2]);
<semigroup congruence over <simple transformation semigroup of 
 degree 5 with 4 generators> with linked triple (2,4,1)>
gap> IsSemigroupCongruence(cong);
true

19.1-2 IsLeftSemigroupCongruence
‣ IsLeftSemigroupCongruence( obj )( property )

A left semigroup congruence cong is an equivalence relation on a semigroup S which respects left multiplication.

That is, if (a,b) is a pair in cong, and x is an element of S, then (xa,xb) is also in cong.

The simplest way of creating a left congruence in Semigroups is by a set of generating pairs. See LeftSemigroupCongruence (19.2-2).

gap> S:=Semigroup(Transformation( [ 2, 1, 1, 2, 1 ] ), 
>                 Transformation( [ 3, 4, 3, 4, 4 ] ), 
>                 Transformation( [ 3, 4, 3, 4, 3 ] ),  
>                 Transformation( [ 4, 3, 3, 4, 4 ] ));;
gap> pair1 := [Transformation( [ 3, 4, 3, 4, 3 ] ),
>              Transformation( [ 1, 2, 1, 2, 1 ] )];;
gap> pair2 := [Transformation( [ 4, 3, 4, 3, 4 ] ),
>              Transformation( [ 3, 4, 3, 4, 3 ] )];;
gap> cong := LeftSemigroupCongruence(S, [pair1, pair2]);
<left semigroup congruence over <transformation semigroup of degree 5 
 with 4 generators> with 2 generating pairs>
gap> IsLeftSemigroupCongruence(cong);
true

19.1-3 IsRightSemigroupCongruence
‣ IsRightSemigroupCongruence( obj )( property )

A right semigroup congruence cong is an equivalence relation on a semigroup S which respects right multiplication.

That is, if (a,b) is a pair in cong, and x is an element of S, then (ax,bx) is also in cong.

The simplest way of creating a right congruence in Semigroups is by a set of generating pairs. See RightSemigroupCongruence (19.2-3).

gap> S:=Semigroup(Transformation( [ 2, 1, 1, 2, 1 ] ), 
>                 Transformation( [ 3, 4, 3, 4, 4 ] ), 
>                 Transformation( [ 3, 4, 3, 4, 3 ] ),  
>                 Transformation( [ 4, 3, 3, 4, 4 ] ));;
gap> pair1 := [Transformation( [ 3, 4, 3, 4, 3 ] ),
>              Transformation( [ 1, 2, 1, 2, 1 ] )];;
gap> pair2 := [Transformation( [ 4, 3, 4, 3, 4 ] ),
>              Transformation( [ 3, 4, 3, 4, 3 ] )];;
gap> RightSemigroupCongruence(S, [pair1, pair2]);
<right semigroup congruence over <transformation semigroup of 
 degree 5 with 4 generators> with 2 generating pairs>
gap> IsRightSemigroupCongruence(cong);
true

19.2 Creating congruences

19.2-1 SemigroupCongruence
‣ SemigroupCongruence( S, pairs )( function )

Returns: A semigroup congruence.

This function returns a semigroup congruence over the semigroup S.

If pairs is a list of lists of size 2 with elements from S, then this function will return the semigroup congruence defined by these generating pairs. The individual pairs may instead be given as separate arguments.

gap> S := Semigroup(Transformation([2, 1, 1, 2, 1]), 
>                   Transformation([3, 4, 3, 4, 4]), 
>                   Transformation([3, 4, 3, 4, 3]),  
>                   Transformation([4, 3, 3, 4, 4]));;
gap> pair1 := [Transformation([3, 4, 3, 4, 3]),
>              Transformation([1, 2, 1, 2, 1])];;
gap> pair2 := [Transformation([4, 3, 4, 3, 4]),
>              Transformation([3, 4, 3, 4, 3])];;
gap> SemigroupCongruence(S, [pair1, pair2]);
<semigroup congruence over <simple transformation semigroup of 
 degree 5 with 4 generators> with linked triple (2,4,1)>
gap> SemigroupCongruence(S, pair1, pair2);
<semigroup congruence over <simple transformation semigroup of 
 degree 5 with 4 generators> with linked triple (2,4,1)>

19.2-2 LeftSemigroupCongruence
‣ LeftSemigroupCongruence( S, pairs )( function )

Returns: A left semigroup congruence.

This function returns a left semigroup congruence over the semigroup S.

If pairs is a list of lists of size 2 with elements from S, then this function will return the least left semigroup congruence on S which contains these generating pairs. The individual pairs may instead be given as separate arguments.

gap> S := Semigroup(Transformation([2, 1, 1, 2, 1]), 
>                   Transformation([3, 4, 3, 4, 4]), 
>                   Transformation([3, 4, 3, 4, 3]),  
>                   Transformation([4, 3, 3, 4, 4]));;
gap> pair1 := [Transformation([3, 4, 3, 4, 3]),
>              Transformation([1, 2, 1, 2, 1])];;
gap> pair2 := [Transformation([4, 3, 4, 3, 4]),
>              Transformation([3, 4, 3, 4, 3])];;
gap> LeftSemigroupCongruence(S, [pair1, pair2]);
<left semigroup congruence over <transformation semigroup of degree 5 
 with 4 generators> with 2 generating pairs>
gap> LeftSemigroupCongruence(S, pair1, pair2);
<left semigroup congruence over <transformation semigroup of degree 5 
 with 4 generators> with 2 generating pairs>

19.2-3 RightSemigroupCongruence
‣ RightSemigroupCongruence( S, pairs )( function )

Returns: A right semigroup congruence.

This function returns a right semigroup congruence over the semigroup S.

If pairs is a list of lists of size 2 with elements from S, then this function will return the least right semigroup congruence on S which contains these generating pairs. The individual pairs may instead be given as separate arguments.

gap> S := Semigroup(Transformation([2, 1, 1, 2, 1]), 
>                 Transformation([3, 4, 3, 4, 4]), 
>                 Transformation([3, 4, 3, 4, 3]),  
>                 Transformation([4, 3, 3, 4, 4]));;
gap> pair1 := [Transformation([3, 4, 3, 4, 3]),
>              Transformation([1, 2, 1, 2, 1])];;
gap> pair2 := [Transformation([4, 3, 4, 3, 4]),
>              Transformation([3, 4, 3, 4, 3])];;
gap> RightSemigroupCongruence(S, [pair1, pair2]);
<right semigroup congruence over <transformation semigroup of 
 degree 5 with 4 generators> with 2 generating pairs>
gap> RightSemigroupCongruence(S, pair1, pair2);
<right semigroup congruence over <transformation semigroup of 
 degree 5 with 4 generators> with 2 generating pairs>

19.3 Congruence classes

19.3-1 IsCongruenceClass
‣ IsCongruenceClass( obj )( category )

This category contains any object which is an equivalence class of a semigroup congruence (see IsSemigroupCongruence (19.1-1)). An object will only be in this category if the relation is known to be a semigroup congruence when the congruence class is created.

gap> S := Monoid([Transformation( [ 1, 2, 2 ] ),
>                 Transformation( [ 3, 1, 3 ] )]);;
gap> cong := SemigroupCongruence(S, [Transformation( [ 1, 2, 1 ] ), 
>                                    Transformation( [ 2, 1, 2 ] )]);;
gap> class := EquivalenceClassOfElement(cong,
>                                       Transformation([ 3, 1, 1 ] ));
<congruence class of Transformation( [ 3, 1, 1 ] )>
gap> IsCongruenceClass(class);
true

19.3-2 IsLeftCongruenceClass
‣ IsLeftCongruenceClass( obj )( category )

This category contains any object which is an equivalence class of a left semigroup congruence (see IsLeftSemigroupCongruence (19.1-2)). An object will only be in this category if the relation is known to be a left semigroup congruence when the class is created.

gap> S := Monoid([Transformation( [ 1, 2, 2 ] ),
>                 Transformation( [ 3, 1, 3 ] )]);;
gap> pairs := [Transformation( [ 1, 2, 1 ] ), 
>              Transformation( [ 2, 1, 2 ] )];;
gap> cong := LeftSemigroupCongruence(S, pairs);;
gap> class := EquivalenceClassOfElement(cong,
>                                       Transformation( [ 3, 1, 1 ] ));
<left congruence class of Transformation( [ 3, 1, 1 ] )>
gap> IsLeftCongruenceClass(class);
true

19.3-3 IsRightCongruenceClass
‣ IsRightCongruenceClass( obj )( category )

This category contains any object which is an equivalence class of a right semigroup congruence (see IsRightSemigroupCongruence (19.1-3)). An object will only be in this category if the relation is known to be a right semigroup congruence when the class is created.

gap> S := Monoid([Transformation( [ 1, 2, 2 ] ),
>                 Transformation( [ 3, 1, 3 ] )]);;
gap> pairs := [Transformation( [ 1, 2, 1 ] ),
>              Transformation( [ 2, 1, 2 ] )];;
gap> cong := RightSemigroupCongruence(S, pairs);;
gap> class := EquivalenceClassOfElement(cong,
>                                       Transformation( [ 3, 1, 1 ] ));
<right congruence class of Transformation( [ 3, 1, 1 ] )>
gap> IsRightCongruenceClass(class);
true

19.3-4 CongruenceClassOfElement
‣ CongruenceClassOfElement( cong, elm )( operation )

Returns: A congruence class.

This operation is a synonym of EquivalenceClassOfElement in the case that the argument cong is a congruence of a semigroup.

gap> S := ReesZeroMatrixSemigroup(SymmetricGroup(3), 
> [[(), (1, 3, 2)], [(1, 2), 0]]);;
gap> cong := CongruencesOfSemigroup(S)[3];;
gap> elm := ReesZeroMatrixSemigroupElement(S, 1, (1,3,2), 1);;
gap> CongruenceClassOfElement(cong, elm);
<congruence class of (1,(1,3,2),1)>

19.3-5 CongruenceClasses
‣ CongruenceClasses( cong )( operation )
‣ LeftCongruenceClasses( cong )( operation )
‣ RightCongruenceClasses( cong )( operation )

Returns: A list of equivalence classes.

These operations acts as a synonym of EquivalenceClasses in the case that the argument cong is a congruence, left congruence, or right congruence (respectively) of a semigroup.

See IsLeftSemigroupCongruence (19.1-2), IsRightSemigroupCongruence (19.1-3), and IsSemigroupCongruence (19.1-1).

gap> S := ReesZeroMatrixSemigroup(SymmetricGroup(3), 
> [[(), (1, 3, 2)], [(1, 2), 0]]);;
gap> cong := CongruencesOfSemigroup(S)[3];;
gap> elm := ReesZeroMatrixSemigroupElement(S, 1, (1,3,2), 1);;
gap> CongruenceClassOfElement(cong, elm);
<congruence class of (1,(1,3,2),1)>

19.3-6 NonTrivialEquivalenceClasses
‣ NonTrivialEquivalenceClasses( eq )( attribute )
‣ NonTrivialCongruenceClasses( cong )( operation )

Returns: A list.

If eq is an equivalence relation, then this attribute returns a list of all equivalence classes of eq which contain more than one element.

gap> S := Monoid([Transformation([1, 2, 2]),
>                 Transformation([3, 1, 3])]);;
gap> cong := SemigroupCongruence(S, [Transformation([1, 2, 1]), 
>                                    Transformation([2, 1, 2])]);;
gap> NonTrivialEquivalenceClasses(cong);
[ <congruence class of Transformation( [ 1, 2, 2 ] )>, 
  <congruence class of Transformation( [ 3, 1, 3 ] )>, 
  <congruence class of Transformation( [ 3, 1, 1 ] )>, 
  <congruence class of Transformation( [ 2, 1, 2 ] )>, 
  <congruence class of Transformation( [ 3, 3, 3 ] )> ]

19.3-7 NrEquivalenceClasses
‣ NrEquivalenceClasses( eq )( attribute )
‣ NrCongruenceClasses( cong )( operation )

Returns: A positive integer.

If eq is an equivalence relation, then this attribute describes the number of equivalence classes it has.

gap> S := ReesZeroMatrixSemigroup(SymmetricGroup(3), 
> [[(), (1,3,2)], [(1,2), 0]]);;
gap> cong := CongruencesOfSemigroup(S)[3];;
gap> NrEquivalenceClasses(cong);
9

19.3-8 CongruencesOfSemigroup
‣ CongruencesOfSemigroup( S )( attribute )

Returns: The congruences of a semigroup.

This attribute gives a list of the congruences of the semigroup S.

gap> S := ReesZeroMatrixSemigroup(SymmetricGroup(3), 
> [[(), (1,3,2)],[(1,2), 0]]);;
gap> congs := CongruencesOfSemigroup(S);
[ <universal semigroup congruence over 
    <Rees 0-matrix semigroup 2x2 over Sym( [ 1 .. 3 ] )>>, 
  <semigroup congruence over <Rees 0-matrix semigroup 2x2 over 
      Sym( [ 1 .. 3 ] )> with linked triple (1,2,2)>, 
  <semigroup congruence over <Rees 0-matrix semigroup 2x2 over 
      Sym( [ 1 .. 3 ] )> with linked triple (3,2,2)>, 
  <semigroup congruence over <Rees 0-matrix semigroup 2x2 over 
      Sym( [ 1 .. 3 ] )> with linked triple (S3,2,2)> ]

19.3-9 LatticeOfCongruences
‣ LatticeOfCongruences( S )( attribute )

Returns: A list of lists.

If S is a semigroup, then this attribute gives a list of lists showing how the congruences of S are contained in each other.

The congruence numbered i is a subcongruence of the congruence numbered j if and only if i is in the jth list.

gap> S := OrderEndomorphisms(2);;
gap> LatticeOfCongruences(S);
[ [  ], [ 1, 3 ], [ 1 ] ]

19.3-10 AsLookupTable
‣ AsLookupTable( cong )( attribute )

Returns: A list.

This attribute describes the semigroup congruence cong as a list of positive integers with length the size of the semigroup over which cong is defined.

Each position in the list corresponds to an element of the semigroup (in the order defined by SSortedList) and the integer at that position is a unique identifier for that element's congruence class under cong. Hence, two elements are congruent if and only if they have the same number at their two positions in the list.

gap> S := Monoid(Transformation([1, 2, 2]),
>                Transformation([3, 1, 3]));;
gap> cong := SemigroupCongruence(S,
> [Transformation([1, 2, 1]), Transformation([2, 1, 2])]);;
gap> AsLookupTable(cong);
[ 1, 2, 3, 4, 5, 6, 2, 3, 6, 4, 5, 6 ]

19.4 Comparing congruences

19.4-1 IsSubrelation
‣ IsSubrelation( cong1, cong2 )( operation )

Returns: True or false.

If cong1 and cong2 are congruences over the same semigroup, then this operation returns whether cong2 is a refinement of cong1, i.e. whether every pair in cong2 is contained in cong1.

gap> S := ReesZeroMatrixSemigroup(SymmetricGroup(3), 
> [[(), (1, 3, 2)], [(1, 2), 0]]);;
gap> cong1 := CongruencesOfSemigroup(S)[3];;
gap> cong2 := CongruencesOfSemigroup(S)[2];;
gap> IsSubrelation(cong1, cong2);
true

19.4-2 IsSuperrelation
‣ IsSuperrelation( cong1, cong2 )( operation )

Returns: True or false.

If cong1 and cong2 are congruences over the same semigroup, then this operation returns whether cong1 is a refinement of cong2, i.e. whether every pair in cong1 is contained in cong2.

See IsSubrelation (19.4-1).

gap> S := ReesZeroMatrixSemigroup(SymmetricGroup(3), 
> [[(), (1, 3, 2)], [(1, 2), 0]]);;
gap> cong1 := CongruencesOfSemigroup(S)[3];;
gap> cong2 := CongruencesOfSemigroup(S)[2];;
gap> IsSuperrelation(cong1, cong2);
false

19.4-3 MeetSemigroupCongruences
‣ MeetSemigroupCongruences( c1, c2 )( operation )
‣ MeetLeftSemigroupCongruences( c1, c2 )( operation )
‣ MeetRightSemigroupCongruences( c1, c2 )( operation )

Returns: A semigroup congruence.

This operation returns the meet of the two semigroup congruences c1 and c2 -- that is, the largest semigroup congruence contained in both c1 and c2.

gap> S := ReesZeroMatrixSemigroup(SymmetricGroup(3), 
> [[(), (1, 3, 2)], [(1, 2), 0]]);;
gap> congs := CongruencesOfSemigroup(S);;
gap> MeetSemigroupCongruences(congs[2], congs[3]);
<semigroup congruence over <Rees 0-matrix semigroup 2x2 over 
  Sym( [ 1 .. 3 ] )> with linked triple (1,2,2)>

19.4-4 JoinSemigroupCongruences
‣ JoinSemigroupCongruences( c1, c2 )( operation )
‣ JoinLeftSemigroupCongruences( c1, c2 )( operation )
‣ JoinRightSemigroupCongruences( c1, c2 )( operation )

Returns: A semigroup congruence.

This operation returns the join of the two semigroup congruences c1 and c2 -- that is, the smallest semigroup congruence containing all the relations in both c1 and c2.

gap> S := ReesZeroMatrixSemigroup(SymmetricGroup(3), 
> [[(), (1, 3, 2)], [(1, 2), 0]]);;
gap> congs := CongruencesOfSemigroup(S);;
gap> JoinSemigroupCongruences(congs[2], congs[3]);
<semigroup congruence over <Rees 0-matrix semigroup 2x2 over 
  Sym( [ 1 .. 3 ] )> with linked triple (3,2,2)>

19.5 Congruences on Rees matrix semigroups

This section describes the implementation of congruences of simple and 0-simple semigroups in the Semigroups package, and the functions associated with them. This code and this part of the manual were written by Michael Torpey. Most of the theorems used in this chapter are from Section 3.5 of [How95].

By the Rees Theorem, any 0-simple semigroup S is isomorphic to a Rees 0-matrix semigroup (see Reference: Rees Matrix Semigroups) over a group, with a regular sandwich matrix. That is,

S \cong \mathcal{M} ^ 0[G; I, \Lambda; P],

where G is a group, Λ and I are non-empty sets, and P is regular in the sense that it has no rows or columns consisting solely of zeroes.

The congruences of a Rees 0-matrix semigroup are in 1-1 correspondence with the linked triple, which is a triple of the form [N, S, T] where:

satisfying the following conditions:

By Theorem 3.5.9 in [How95], for any finite 0-simple Rees 0-matrix semigroup, there is a bijection between its non-universal congruences and its linked triples. In this way, we can internally represent any congruence of such a semigroup by storing its associated linked triple instead of a set of generating pairs, and thus perform many calculations on it more efficiently.

If a congruence is defined by a linked triple (N, S, T), then a single class of that congruence can be defined by a triple (Nx, i / S, k / S), where Nx is a right coset of N, i / S is the equivalence class of i in S, and k / S is the equivalence class of k in T. Thus we can internally represent any class of such a congruence as a triple simply consisting of a right coset and two positive integers.

An analogous condition exists for finite simple Rees matrix semigroups without zero.

19.5-1 IsRMSCongruenceByLinkedTriple
‣ IsRMSCongruenceByLinkedTriple( obj )( category )
‣ IsRZMSCongruenceByLinkedTriple( obj )( category )

Returns: true or false.

These categories describe a type of semigroup congruence over a Rees matrix or 0-matrix semigroup. Externally, an object of this type may be used in the same way as any other object in the category IsSemigroupCongruence (Reference: IsSemigroupCongruence) but it is represented internally by its linked triple, and certain functions may take advantage of this information to reduce computation times.

An object of this type may be constructed with RMSCongruenceByLinkedTriple or RZMSCongruenceByLinkedTriple, or this representation may be selected automatically by SemigroupCongruence (19.2-1).

gap> G := Group([(1, 4, 5), (1, 5, 3, 4)]);;
gap> mat := [ [  0,  0, (1,4,5),     0,     0, (1,4,3,5) ],
>             [  0, (),       0,     0, (3,5),         0 ],
>             [ (),  0,       0, (3,5),     0,         0 ] ];;
gap> S := ReesZeroMatrixSemigroup(G, mat);;
gap> N := Group([ (1,4)(3,5), (1,5)(3,4) ]);;
gap> colBlocks := [[1], [2, 5], [3, 6], [4]];;
gap> rowBlocks := [[1], [2], [3]];;
gap> cong := RZMSCongruenceByLinkedTriple(S, N, colBlocks, rowBlocks);;
gap> IsRZMSCongruenceByLinkedTriple(cong);
true

19.5-2 RMSCongruenceByLinkedTriple
‣ RMSCongruenceByLinkedTriple( S, N, colBlocks, rowBlocks )( function )
‣ RZMSCongruenceByLinkedTriple( S, N, colBlocks, rowBlocks )( function )

Returns: A Rees matrix or 0-matrix semigroup congruence by linked triple.

This function returns a semigroup congruence over the Rees matrix or 0-matrix semigroup S corresponding to the linked triple (N, colBlocks, rowBlocks). The argument N should be a normal subgroup of the underlying semigroup of S; colBlocks should be a partition of the columns of the matrix of S; and rowBlocks should be a partition of the rows of the matrix of S. For example, if the matrix has 5 rows, then a possibility for rowBlocks might be [[1, 3], [2, 5], [4]].

If the arguments describe a valid linked triple on S, then an object in the category IsRZMSCongruenceByLinkedTriple is returned. This object can be used like any other semigroup congruence in GAP.

If the arguments describe a triple which is not linked in the sense described above, then this function returns an error.

gap> G := Group([(1, 4, 5), (1, 5, 3, 4)]);;
gap> mat := [[  0,  0, (1,4,5),     0,     0, (1,4,3,5)],
>            [  0, (),       0,     0, (3,5),         0],
>            [ (),  0,       0, (3,5),     0,         0]];;
gap> S := ReesZeroMatrixSemigroup(G, mat);;
gap> N := Group((1, 4)(3, 5), (1, 5)(3, 4));;
gap> colBlocks := [[1], [2, 5], [3, 6], [4]];;
gap> rowBlocks := [[1], [2], [3]];;
gap> cong := RZMSCongruenceByLinkedTriple(S, N, colBlocks, rowBlocks);
<semigroup congruence over <Rees 0-matrix semigroup 6x3 over 
  Group([ (1,4,5), (1,5,3,4) ])> with linked triple (2^2,4,3)>

19.5-3 RMSCongruenceClassByLinkedTriple
‣ RMSCongruenceClassByLinkedTriple( cong, nCoset, colClass, rowClass )( operation )
‣ RZMSCongruenceClassByLinkedTriple( cong, nCoset, colClass, rowClass )( operation )

Returns: A Rees matrix or 0-matrix semigroup congruence class by linked triple.

This operation returns one congruence class of the congruence cong, as defined by the other three parameters.

The argument cong must be a Rees matrix or 0-matrix semigroup congruence by linked triple. If the linked triple consists of the three parameters N, colBlocks and rowBlocks, then nCoset must be a right coset of N, colClass must be a positive integer corresponding to a position in the list colBlocks, and rowClass must be a positive integer corresponding to a position in the list rowBlocks.

If the arguments are valid, an IsRMSCongruenceClassByLinkedTriple or IsRZMSCongruenceClassByLinkedTriple object is returned, which can be used like any other equivalence class in GAP. Otherwise, an error is returned.

gap> G := Group([(1, 4, 5), (1, 5, 3, 4)]);;
gap> mat := [ [  0,  0, (1,4,5),     0,     0, (1,4,3,5) ],
>             [  0, (),       0,     0, (3,5),         0 ],
>             [ (),  0,       0, (3,5),     0,         0 ] ];;
gap> S := ReesZeroMatrixSemigroup(G, mat);;
gap> n := Group([ (1,4)(3,5), (1,5)(3,4) ]);;
gap> colBlocks := [[1], [2, 5], [3, 6], [4]];;
gap> rowBlocks := [[1], [2], [3]];;
gap> cong := RZMSCongruenceByLinkedTriple(S, n, colBlocks, rowBlocks);;
gap> class := RZMSCongruenceClassByLinkedTriple(cong, 
> RightCoset(n, (1, 5)), 2, 3);
<congruence class of (2,(3,4),3)>

19.5-4 IsLinkedTriple
‣ IsLinkedTriple( S, N, colBlocks, rowBlocks )( operation )

Returns: true or false.

This operation returns true if and only if the arguments (N, colBlocks, rowBlocks) describe a linked triple of the Rees matrix or 0-matrix semigroup S, as described above.

gap> G := Group([(1,4,5), (1,5,3,4)]);;
gap> mat := [ [  0,  0, (1,4,5),     0,     0, (1,4,3,5) ],
>             [  0, (),       0,     0, (3,5),         0 ],
>             [ (),  0,       0, (3,5),     0,         0 ] ];;
gap> S := ReesZeroMatrixSemigroup(G, mat);;
gap> N := Group([ (1,4)(3,5), (1,5)(3,4) ]);;
gap> colBlocks := [[1], [2, 5], [3, 6], [4]];;
gap> rowBlocks := [[1], [2], [3]];;
gap> IsLinkedTriple(S, N, colBlocks, rowBlocks);
true

19.5-5 CanonicalRepresentative
‣ CanonicalRepresentative( class )( attribute )

Returns: A congruence class.

This attribute gives a canonical representative for the semigroup congruence class class. This representative can be used to identify a class uniquely.

At present this only works for simple and 0-simple semigroups.

gap> S := ReesZeroMatrixSemigroup(SymmetricGroup(3), 
> [[(), (1, 3, 2)], [(1, 2), 0]]);;
gap> cong := CongruencesOfSemigroup(S)[3];;
gap> class := CongruenceClasses(cong)[3];;
gap> CanonicalRepresentative(class);
(1,(1,2,3),2)

19.5-6 AsSemigroupCongruenceByGeneratingPairs
‣ AsSemigroupCongruenceByGeneratingPairs( cong )( operation )

Returns: A semigroup congruence.

This operation takes cong, a semigroup congruence, and returns the same congruence relation, but described by GAP's default method of defining semigroup congruences: a set of generating pairs for the congruence.

gap> S := ReesZeroMatrixSemigroup(SymmetricGroup(3), 
> [[(), (1,3,2)], [(1,2), 0]]);;
gap> cong := CongruencesOfSemigroup(S)[3];;
gap> AsSemigroupCongruenceByGeneratingPairs(cong);
<semigroup congruence over <Rees 0-matrix semigroup 2x2 over 
  Sym( [ 1 .. 3 ] )> with 3 generating pairs>

19.5-7 AsRMSCongruenceByLinkedTriple
‣ AsRMSCongruenceByLinkedTriple( cong )( operation )
‣ AsRZMSCongruenceByLinkedTriple( cong )( operation )

Returns: A Rees matrix or 0-matrix semigroup congruence by linked triple.

This operation takes a semigroup congruence cong over a finite simple or 0-simple Rees 0-matrix semigroup, and returns that congruence relation in a new form: as either a congruence by linked triple, or a universal congruence.

If the congruence is not defined over an appropriate type of semigroup, then this function returns an error.

gap> S := ReesZeroMatrixSemigroup(SymmetricGroup(3), 
> [[(), (1, 3, 2)], [(1, 2), 0]]);;
gap> x := ReesZeroMatrixSemigroupElement(S, 1, (1,3,2), 1);;
gap> y := ReesZeroMatrixSemigroupElement(S, 1, (), 1);;
gap> cong := SemigroupCongruenceByGeneratingPairs(S, [[x, y]]);;
gap> AsRZMSCongruenceByLinkedTriple(cong);
<semigroup congruence over <Rees 0-matrix semigroup 2x2 over 
  Sym( [ 1 .. 3 ] )> with linked triple (3,2,2)>

19.6 Congruences on inverse semigroups

This section describes the implementation of congruences of inverse semigroups in the Semigroups package, and the functions associated with them. This code and this part of the manual were written by Michael Torpey. Most of the theorems used in this chapter are from Section 5.3 of [How95].

The congruences of an inverse semigroup are in 1-1 correspondence with its congruence pairs. A congruence pair is a pair (N, t) such that:

satisfying the following conditions:

By Theorem 5.3.3 in [How95], for any inverse semigroup, there is a bijection between its congruences and its congruence pairs. In this way, we can internally represent any congruence of such a semigroup by storing its associated congruence pair instead of a set of generating pairs, and thus perform many calculations on it more efficiently.

If we have a congruence C with congruence pair (N, t), it turns out that N is its kernel (that is, the set of all elements congruent to an idempotent) and that t is its trace (that is, the restriction of C to the idempotents). Hence, we refer to a congruence stored in this format as a "congruence by kernel and trace".

19.6-1 IsInverseSemigroupCongruenceByKernelTrace
‣ IsInverseSemigroupCongruenceByKernelTrace( cong )( category )

Returns: true or false.

This category contains any inverse semigroup congruence cong which is represented internally by its kernel and trace. The SemigroupCongruence (19.2-1) function will almost always create an object of this category if its first argument S is an inverse semigroup.

See [How95] Section 5.3 for more details. See also InverseSemigroupCongruenceByKernelTrace (19.6-2).

gap> i := InverseSemigroup([
> PartialPerm([1, 2], [2, 3]),
> PartialPerm([1, 3], [2, 3])]);;
gap> cong := SemigroupCongruence(i,
> [[PartialPerm([2, 3], [1, 3]),
>   PartialPerm([2], [1])],
>  [PartialPerm([], []),
>   PartialPerm([1, 2], [1, 2])]]);
<semigroup congruence over <inverse partial perm semigroup of rank 3 
 with 2 generators> with congruence pair (19,1)>
gap> IsInverseSemigroupCongruenceByKernelTrace(cong);
true

19.6-2 InverseSemigroupCongruenceByKernelTrace
‣ InverseSemigroupCongruenceByKernelTrace( S, kernel, traceBlocks )( function )

Returns: An inverse semigroup congruence by kernel and trace.

If S is an inverse semigroup, kernel is a subsemigroup of S, traceBlocks is a list of lists describing a congruence on the idempotents of S, and (kernel, trace) describes a valid congruence pair for S (see [How95] Section 5.3) then this function returns the semigroup congruence defined by that congruence pair.

See also KernelOfSemigroupCongruence (19.6-4) and TraceOfSemigroupCongruence (19.6-5).

gap> S := InverseSemigroup([
> PartialPerm([1, 2], [2, 3]),
> PartialPerm([1, 3], [2, 3])]);;
gap> kernel := InverseSemigroup([
> PartialPerm([1, 3], [1, 3]),
> PartialPerm([2, 3], [2, 3]),
> PartialPerm([1, 2], [1, 2]), 
> PartialPerm([1], [3]),
> PartialPerm([1], [2])]);;
gap> trace := [[PartialPerm([2, 3], [2, 3])], 
>              [PartialPerm([1, 2], [1, 2])], 
>              [PartialPerm([1, 3], [1, 3])], 
>              [PartialPerm([3], [3]),
>               PartialPerm([2], [2]), 
>               PartialPerm([1], [1]),
>               PartialPerm([], [])]];;
gap> cong := InverseSemigroupCongruenceByKernelTrace(S, kernel, trace);
<semigroup congruence over <inverse partial perm semigroup of rank 3 
 with 2 generators> with congruence pair (13,4)>

19.6-3 AsInverseSemigroupCongruenceByKernelTrace
‣ AsInverseSemigroupCongruenceByKernelTrace( cong )( attribute )

Returns: An inverse semigroup congruence by kernel and trace.

If cong is a semigroup congruence over an inverse semigroup, then this attribute returns an object which describes the same congruence, but with an internal representation defined by that congruence's kernel and trace.

See [How95] section 5.3 for more details.

gap> i := InverseSemigroup([
> PartialPerm([1, 2], [2, 3]),
> PartialPerm([1, 3], [2, 3])]);;
gap> cong := SemigroupCongruenceByGeneratingPairs(i,
> [[PartialPerm([2, 3], [1, 3]),
>    PartialPerm([2], [1])],
>  [PartialPerm([], []),
>    PartialPerm([1, 2], [1, 2])]]);
<semigroup congruence over <inverse partial perm semigroup of rank 3 
 with 2 generators> with 2 generating pairs>
gap> cong2 := AsInverseSemigroupCongruenceByKernelTrace(cong);
<semigroup congruence over <inverse partial perm semigroup of rank 3 
 with 2 generators> with congruence pair (19,1)>

19.6-4 KernelOfSemigroupCongruence
‣ KernelOfSemigroupCongruence( cong )( attribute )

Returns: An inverse semigroup.

If cong is an inverse semigroup congruence by kernel and trace, then this attribute returns the kernel of that congruence; that is, the inverse subsemigroup consisting of all elements which are related to an idempotent by cong.

gap> i := InverseSemigroup(
> PartialPerm([1, 2], [2, 3]),
> PartialPerm([1, 3], [2, 3]));;
gap> cong := SemigroupCongruence(i,
> [[PartialPerm([2, 3], [1, 3]),
>   PartialPerm([2], [1])],
>  [PartialPerm([], []),
>   PartialPerm([1, 2], [1, 2])]]);
<semigroup congruence over <inverse partial perm semigroup of rank 3 
 with 2 generators> with congruence pair (19,1)>
gap> KernelOfSemigroupCongruence(cong);
<inverse partial perm semigroup of size 19, rank 3 with 5 generators>

19.6-5 TraceOfSemigroupCongruence
‣ TraceOfSemigroupCongruence( cong )( attribute )

Returns: A list of lists.

If cong is an inverse semigroup congruence by kernel and trace, then this attribute returns the restriction of cong to the idempotents of the semigroup. This is in block form: each idempotent will appear in precisely one list, and two idempotents will be in the same list if and only if they are related by cong.

gap> i := InverseSemigroup(
> PartialPerm([1, 2], [2, 3]),
> PartialPerm([1, 3], [2, 3]));;
gap> cong := SemigroupCongruence(i,
> [[PartialPerm([2, 3], [1, 3]),
>   PartialPerm([2], [1])],
>  [PartialPerm([], []),
>   PartialPerm([1, 2], [1, 2])]]);
<semigroup congruence over <inverse partial perm semigroup of rank 3 
 with 2 generators> with congruence pair (19,1)>
gap> TraceOfSemigroupCongruence(cong);
[ [ <empty partial perm>, <identity partial perm on [ 1 ]>, 
      <identity partial perm on [ 2 ]>, 
      <identity partial perm on [ 1, 2 ]>, 
      <identity partial perm on [ 3 ]>, 
      <identity partial perm on [ 2, 3 ]>, 
      <identity partial perm on [ 1, 3 ]> ] ]

19.6-6 IsInverseSemigroupCongruenceClassByKernelTrace
‣ IsInverseSemigroupCongruenceClassByKernelTrace( obj )( category )

Returns: true or false.

This category contains any congruence class which belongs to a congruence which is represented internally by its kernel and trace. See InverseSemigroupCongruenceByKernelTrace (19.6-2).

See [How95] Section 5.3 for more details.

gap> i := InverseSemigroup([
> PartialPerm([1, 2], [2, 3]),
> PartialPerm([1, 3], [2, 3])]);;
gap> cong := SemigroupCongruence(i,
> [[PartialPerm([2, 3], [1, 3]),
>   PartialPerm([2], [1])],
>  [PartialPerm([], []),
>   PartialPerm([1, 2], [1, 2])]]);;
gap> class := CongruenceClassOfElement(cong,
>                                      PartialPerm([1, 2], [2, 3]));;
gap> IsInverseSemigroupCongruenceClassByKernelTrace(class);
true

19.6-7 MinimumGroupCongruence
‣ MinimumGroupCongruence( S )( attribute )

Returns: An inverse semigroup congruence by kernel and trace.

If S is an inverse semigroup, then this function returns the least congruence on S whose quotient is a group.

gap> S := InverseSemigroup(
>       [PartialPerm([1,2,5,6], [5,2,1,4]),
>        PartialPerm([1,2,3,4,5,7], [1,4,6,3,5,2])]);;
gap> cong := MinimumGroupCongruence(S);
<semigroup congruence over <inverse partial perm semigroup of rank 7 
 with 2 generators> with congruence pair (59,1)>
gap> IsGroupAsSemigroup(S / cong);
true

19.7 Rees congruences

A Rees congruence is defined by a semigroup ideal. It is a congruence on a semigroup S which has one congruence class equal to a semigroup ideal I of S, and every other congruence class being a singleton.

19.7-1 SemigroupIdealOfReesCongruence
‣ SemigroupIdealOfReesCongruence( cong )( attribute )

Returns: A semigroup ideal.

If cong is a rees congruence (see IsReesCongruence (Reference: IsReesCongruence)) then this attribute returns the two-sided ideal that was used to define it, i.e.~the ideal of elements in the only non-trivial congruence class of cong.

gap> S := Semigroup([
> Transformation([2, 3, 4, 3, 1, 1]),
> Transformation([6, 4, 4, 4, 6, 1])]);;
gap> I := SemigroupIdeal(S,
> Transformation([4, 4, 4, 4, 4, 2]),
> Transformation([3, 3, 3, 3, 3, 2]));;
gap> cong := ReesCongruenceOfSemigroupIdeal(I);;
gap> SemigroupIdealOfReesCongruence(cong);
<non-regular transformation semigroup ideal of degree 6 with
  2 generators>

19.7-2 IsReesCongruenceClass
‣ IsReesCongruenceClass( obj )( category )

Returns: true or false.

This category describes a congruence class of a Rees congruence. A congruence class of a Rees congruence either contains all the elements of an ideal, or is a singleton (see IsReesCongruence (Reference: IsReesCongruence)).

An object of this type may be used in the same way as any other congruence class object.

gap> S := Semigroup(
> Transformation([2, 3, 4, 3, 1, 1]),
> Transformation([6, 4, 4, 4, 6, 1]));;
gap> I := SemigroupIdeal(S,
> Transformation([4, 4, 4, 4, 4, 2]),
> Transformation([3, 3, 3, 3, 3, 2]));;
gap> cong := ReesCongruenceOfSemigroupIdeal(I);;
gap> classes := CongruenceClasses(cong);;
gap> IsReesCongruenceClass(classes[1]);
true

19.8 Universal congruences

The linked triples of a completely 0-simple Rees 0-matrix semigroup describe only its non-universal congruences. In any one of these, the zero element of the semigroup is related only to itself. However, for any semigroup S the universal relation S × S is a congruence; called the universal congruence. The universal congruence on a semigroup has its own unique representation.

Since many things we want to calculate about congruences are trivial in the case of the universal congruence, this package contains a category specifically designed for it, IsUniversalSemigroupCongruence. We also define IsUniversalSemigroupCongruenceClass, which represents the single congruence class of the universal congruence.

19.8-1 IsUniversalSemigroupCongruence
‣ IsUniversalSemigroupCongruence( obj )( category )

Returns: true or false.

This category describes a type of semigroup congruence, which must refer to the universal semigroup congruence S × S. Externally, an object of this type may be used in the same way as any other object in the category IsSemigroupCongruence (Reference: IsSemigroupCongruence).

An object of this type may be constructed with UniversalSemigroupCongruence or this representation may be selected automatically as an alternative to an IsRZMSCongruenceByLinkedTriple object (since the universal congruence cannot be represented by a linked triple).

gap> S := Semigroup([Transformation([3, 2, 3])]);;
gap> U := UniversalSemigroupCongruence(S);;
gap> IsUniversalSemigroupCongruence(U);
true

19.8-2 IsUniversalSemigroupCongruenceClass
‣ IsUniversalSemigroupCongruenceClass( obj )( category )

Returns: true or false.

This category describes a class of the universal semigroup congruence (see IsUniversalSemigroupCongruence (19.8-1)). A universal semigroup congruence by definition has precisely one congruence class, which contains all of the elements of the semigroup in question.

gap> S := Semigroup([Transformation([3, 2, 3])]);;
gap> U := UniversalSemigroupCongruence(S);;
gap> classes := CongruenceClasses(U);;
gap> IsUniversalSemigroupCongruenceClass(classes[1]);
true

19.8-3 UniversalSemigroupCongruence
‣ UniversalSemigroupCongruence( S )( operation )

Returns: A universal semigroup congruence.

This operation returns the universal semigroup congruence for the semigroup S. It can be used in the same way as any other semigroup congruence object.

gap> S := ReesZeroMatrixSemigroup(SymmetricGroup(3), 
> [[(), (1, 3, 2)], [(1, 2), 0]]);;
gap> UniversalSemigroupCongruence(S);
<universal semigroup congruence over 
<Rees 0-matrix semigroup 2x2 over Sym( [ 1 .. 3 ] )>>
 [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