In this chapter we describe some standard ways of constructing semigroups and monoids from other semigroups that are available in the Semigroups package.
In this section, we describe the functions in Semigroups that can be used to create various products of semigroups.
‣ DirectProduct( S[, T, ...] ) | ( function ) |
‣ DirectProductOp( list, S ) | ( operation ) |
Returns: A transformation semigroup.
The function DirectProduct takes an arbitrary positive number of finite semigroups, and returns a semigroup that is isomorphic to their direct product.
If these finite semigroups are all partial perm semigroups, all bipartition semigroups, or all PBR semigroups, then DirectProduct returns a semigroup of the same type. Otherwise, DirectProduct returns a transformation semigroup.
The operation DirectProductOp is included for consistency with the GAP library (see DirectProductOp (Reference: DirectProductOp)). It takes exactly two arguments, namely a non-empty list list of semigroups and one of these semigroups, S, and returns the same result as CallFuncList(DirectProduct, list).
If D is the direct product of a collection of semigroups, then an embedding of the ith factor into D can be accessed with the command Embedding(D, i), and a projection of D onto its ith factor can be accessed with the command Projection(D, i); see Embedding (Reference: Embedding) and Projection (Reference: Projection) for more information.
gap> S := InverseMonoid([PartialPerm([2, 1])]);; gap> T := InverseMonoid([PartialPerm([1, 2, 3])]);; gap> D := DirectProduct(S, T); <commutative inverse partial perm monoid of rank 5 with 1 generator> gap> Elements(D); [ <identity partial perm on [ 1, 2, 3, 4, 5 ]>, (1,2)(3)(4)(5) ] gap> S := PartitionMonoid(2);; gap> D := DirectProduct(S, S, S);; IsRegularSemigroup(D);; D; <regular bipartition monoid of size 3375, degree 6 with 9 generators> gap> S := Semigroup([PartialPerm([2, 5, 0, 1, 3]), > PartialPerm([5, 2, 4, 3])]);; gap> T := Semigroup([Bipartition([[1, -2], [2], [3, -1, -3]])]);; gap> D := DirectProduct(S, T); <transformation semigroup of size 122, degree 9 with 63 generators> gap> Size(D) = Size(S) * Size(T); true
‣ WreathProduct( M, S ) | ( operation ) |
Returns: A transformation semigroup.
If M is a transformation monoid (or a permutation group) of degree m, and S is a transformation semigroup (or permutation group) of degree s, the operation WreathProduct(M, S) returns the wreath product of M and S, in terms of an embedding in the full transformation monoid of degree m * s.
gap> T := FullTransformationMonoid(3);; gap> C := Group((1, 3));; gap> W := WreathProduct(T, C);; gap> Size(W); 39366 gap> WW := WreathProduct(C, T);; gap> Size(WW); 216
The dual semigroup of a semigroup S is the semigroup with the same underlying set of elements but with reversed multiplication; this is anti-isomorphic to S. In Semigroups a semigroup and its dual are represented with disjoint sets of elements.
‣ DualSemigroup( S ) | ( attribute ) |
Returns: The dual semigroup of the given semigroup.
The dual semigroup of a semigroup S is the semigroup with the same underlying set as S, but with multiplication reversed; this is anti-isomorphic to S. This attribute returns a semigroup isomorphic to the dual semigroup of S.
gap> S := Semigroup([Transformation([1, 4, 3, 2, 2]), > Transformation([5, 4, 4, 1, 2])]);; gap> D := DualSemigroup(S); <dual semigroup of <transformation semigroup of degree 5 with 2 generators>> gap> Size(S) = Size(D); true gap> NrDClasses(S) = NrDClasses(D); true
‣ IsDualSemigroupRep( sgrp ) | ( category ) |
Returns: Returns true if sgrp lies in the category of dual semigroups.
Semigroups created using DualSemigroup (8.2-1) normally lie in this category. The exception is semigroups which are the dual of semigroups already lying in this category. That is, a semigroup lies in the category IsDualSemigroupRep if and only if the corresponding dual semigroup does not. Note that this is not a Representation in the GAP sense, and will likely be renamed in a future major release of the package.
gap> S := Semigroup([Transformation([3, 5, 1, 1, 2]), > Transformation([1, 2, 4, 4, 3])]); <transformation semigroup of degree 5 with 2 generators> gap> D := DualSemigroup(S); <dual semigroup of <transformation semigroup of degree 5 with 2 generators>> gap> IsDualSemigroupRep(D); true gap> R := DualSemigroup(D); <transformation semigroup of degree 5 with 2 generators> gap> IsDualSemigroupRep(R); false gap> R = S; true gap> T := Range(IsomorphismTransformationSemigroup(D)); <transformation semigroup of size 16, degree 17 with 2 generators> gap> IsDualSemigroupRep(T); false gap> x := Representative(D); <Transformation( [ 3, 5, 1, 1, 2 ] ) in the dual semigroup> gap> V := Semigroup(x); <dual semigroup of <commutative transformation semigroup of degree 5 with 1 generator>> gap> IsDualSemigroupRep(V); true
‣ IsDualSemigroupElement( elt ) | ( category ) |
Returns: Returns true if elt has the representation of a dual semigroup element.
Elements of a dual semigroup obtained using AntiIsomorphismDualSemigroup (8.2-4) normally lie in this category. The exception is elements obtained by applying the map AntiIsomorphismDualSemigroup (8.2-4) to elements already in this category. That is, the elements of a semigroup lie in the category IsDualSemigroupElement if and only if the elements of the corresponding dual semigroup do not.
gap> S := SingularPartitionMonoid(4);; gap> D := DualSemigroup(S);; gap> s := GeneratorsOfSemigroup(S)[1];; gap> map := AntiIsomorphismDualSemigroup(S);; gap> t := s ^ map; <<block bijection: [ 1, 2, -1, -2 ], [ 3, -3 ], [ 4, -4 ]> in the dual semigroup> gap> IsDualSemigroupElement(t); true gap> inv := InverseGeneralMapping(map);; gap> x := t ^ inv; <block bijection: [ 1, 2, -1, -2 ], [ 3, -3 ], [ 4, -4 ]> gap> IsDualSemigroupElement(x); false
‣ AntiIsomorphismDualSemigroup( S ) | ( attribute ) |
Returns: An anti-isomorphism from S to the corresponding dual semigroup.
The dual semigroup of S mathematically has the same underlying set as S, but is represented with a different set of elements in Semigroups. This function returns a mapping which is an anti-isomorphism from S to its dual.
gap> S := PartitionMonoid(3); <regular bipartition *-monoid of size 203, degree 3 with 4 generators> gap> map := AntiIsomorphismDualSemigroup(S); MappingByFunction( <regular bipartition *-monoid of size 203, degree 3 with 4 generators>, <dual semigroup of <regular bipartition *-monoid of size 203, degree 3 with 4 generators> >, function( x ) ... end, function( x ) ... end ) gap> inv := InverseGeneralMapping(map);; gap> x := Bipartition([[1, -2], [2, -3], [3, -1]]); <block bijection: [ 1, -2 ], [ 2, -3 ], [ 3, -1 ]> gap> y := Bipartition([[1], [2, -2], [3, -3], [-1]]); <bipartition: [ 1 ], [ 2, -2 ], [ 3, -3 ], [ -1 ]> gap> (x ^ map) * (y ^ map) = (y * x) ^ map; true gap> x ^ map; <<block bijection: [ 1, -2 ], [ 2, -3 ], [ 3, -1 ]> in the dual semigroup>
In this section, we describe how Semigroups can be used to create and manipulate strong semilattices of semigroups (SSSs). Strong semilattices of semigroups are described, for example, in Section 4.1 of [How95]. They consist of a meet-semilattice \(Y\) along with a collection of semigroups \(S_a\) for each \(a\) in \(Y\), and a collection of homomorphisms \(f_{ab} : S_a \rightarrow S_b\) for each \(a\) and \(b\) in \(Y\) such that \(a \geq b\).
The product of two elements \(x \in S_a, y \in S_b\) is defined to lie in the semigroup \(S_c\), corresponding to the meet \(c\) of \(a, b \in Y\). The exact element of \(S_c\) equal to the product is obtained using the homomorphisms of the SSS: \(xy = (x f_{ac}) (y f_{bc})\).
‣ StrongSemilatticeOfSemigroups( D, L, H ) | ( operation ) |
Returns: A strong semilattice of semigroups.
If D is a digraph, L is a list of semigroups, and H is a list of lists of maps, then this function returns a corresponding IsStrongSemilatticeOfSemigroups object. The format of the arguments is not required to be exactly analogous to Howie's description above, but consistency amongst the arguments is required:
D must be a digraph whose DigraphReflexiveTransitiveClosure (Digraphs: DigraphReflexiveTransitiveClosure) is a meet-semilattice. For example, Digraph([2, 3], [4], [4], []]) is valid and produces a semilattice where the meet of 2 and 3 is 1. See IsMeetSemilatticeDigraph (Digraphs: IsMeetSemilatticeDigraph).
L must contain as many semigroups as there are vertices in D.
H must be a list with as many elements as there are vertices in D. Each element of H must itself be a (possibly empty) list with as many entries as the corresponding vertex of D has out-edges. The entries of each sublist must be the corresponding homomorphisms: for example, if D is entered as above, then H[1][2] must be the homomorphism \(f_31\), i.e. H[1][2] is an IsMapping object whose domain is a superset of L[3] and whose range is a subset of L[1].
Note that in the example above, the edge \(1 \rightarrow 4\) is not entered as part of the argument D, but it is still an edge in the reflexive transitive closure of D. When creating the object, GAP creates the homomorphism \(f_{41}\) by composing the mappings along paths that lead from 4 to 1, and checks that composing along all possible paths produces the same result.
‣ SSSE( SSS, n, x ) | ( operation ) |
Returns: An element of a strong semilattice of semigroups.
If n is a vertex of the underlying semilattice of the strong semilattice of semigroups SSS, and if x is an element of the nth semigroup of SSS, then this function returns the element of SSS which lies in semigroup number n and which corresponds to the element x in that semigroup.
This function returns an IsSSSE (8.3-3) object. SSSEs from the same strong semilattice of semigroups can be compared and multiplied.
gap> D := Digraph([[2, 3], [4], [4], []]);; gap> S4 := FullTransformationMonoid(2);; gap> S3 := FullTransformationMonoid(3);; gap> pairs := [[Transformation([1, 2]), Transformation([2, 1])]];; gap> cong := SemigroupCongruence(S4, pairs);; gap> S2 := S4 / cong;; gap> S1 := TrivialSemigroup();; gap> L := [S1, S2, S3, S4];; gap> idfn := t -> IdentityTransformation;; gap> f21 := SemigroupHomomorphismByFunction(S2, S1, idfn);; gap> f31 := SemigroupHomomorphismByFunction(S3, S1, idfn);; gap> f42 := HomomorphismQuotientSemigroup(cong);; gap> f43 := SemigroupHomomorphismByFunction(S4, S3, IdFunc);; gap> H := [[f21, f31], [f42], [f43], []];; gap> SSS := StrongSemilatticeOfSemigroups(D, L, H); <strong semilattice of 4 semigroups> gap> Size(SSS); 34 gap> x := SSSE(SSS, 3, Elements(S3)[10]); SSSE(3, Transformation( [ 2, 1, 1 ] )) gap> y := SSSE(SSS, 4, Elements(S4)[1]); SSSE(4, Transformation( [ 1, 1 ] )) gap> x * y; SSSE(3, Transformation( [ 1, 1, 1 ] ))
‣ IsSSSE( obj ) | ( filter ) |
Returns: true or false.
All elements of an SSS belong in the category IsSSSE (for "Strong Semilattice of Semigroups Element").
‣ IsStrongSemilatticeOfSemigroups( obj ) | ( filter ) |
Returns: true or false.
Every Strong Semilattice of Semigroups in GAP belongs to the category IsStrongSemilatticeOfSemigroups. Basic operations in this category allow the user to recover the three essential elements of an SSS object: SemilatticeOfStrongSemilatticeOfSemigroups (8.3-5), SemigroupsOfStrongSemilatticeOfSemigroups (8.3-6), and HomomorphismsOfStrongSemilatticeOfSemigroups (8.3-7).
‣ SemilatticeOfStrongSemilatticeOfSemigroups( SSS ) | ( attribute ) |
Returns: A meet-semilattice digraph.
If SSS is a strong semilattice of semigroups, this function returns the underlying semilattice structure as a digraph. Note that this may not be equal to the digraph passed as input when SSS was created: rather, it is the reflexive transitive closure of the input digraph.
‣ SemigroupsOfStrongSemilatticeOfSemigroups( SSS ) | ( attribute ) |
Returns: A list of semigroups.
If SSS is a strong semilattice of semigroups, this function returns the list of semigroups that make up SSS. The position of a semigroup in the list corresponds to the node of the semilattice where that semigroup lies.
‣ HomomorphismsOfStrongSemilatticeOfSemigroups( SSS ) | ( attribute ) |
Returns: A list of lists of mappings.
If SSS is a strong semilattice of \(n\) semigroups, this function returns an \(n \times n\) list where the \((i, j)\)th entry of the list is the homomorphism \(f_{ji}\), provided \(i \leq j\) in the semilattice. If this last condition is not true, then the entry is fail.
In this section, we describe the functions in GAP for creating and computing with McAlister triple semigroups and their subsemigroups. This implementation is based on the section in Chapter 5 of [How95] but differs from the treatment in Howie by using right actions instead of left. Some definitions found in the documentation are changed for this reason.
The importance of the McAlister triple semigroups lies in the fact that they are exactly the E-unitary inverse semigroups, which are an important class in the study of inverse semigroups.
First we define E-unitary inverse semigroups. It is standard to denote the subsemigroup of a semigroup consisting of its idempotents by E. A semigroup S is said to be E-unitary if for all e in E and for all s in S:
es \(\in\) E implies s \(\in\) E,
se \(\in\) E implies s \(\in\) E.
For inverse semigroups these two conditions are equivalent. We are only interested in E-unitary inverse semigroups. Before defining McAlister triple semigroups we define a McAlister triple. A McAlister triple is a triple (G,X,Y) which consists of:
a partial order X,
a subset Y of X,
a group G which acts on X, on the right, by order automorphisms. That means for all A,B \(\in\) X and for all g \(\in\) G: A \(\leq\) B if and only if Ag \(\leq\) Bg.
Furthermore, (G,X,Y) must satisfy the following four properties to be a McAlister triple:
Y is a subset of X which is a join-semilattice together with the restriction of the order relation of X to Y.
Y is an order ideal of X. That is to say, for all A \(\in\) X and for all B \(\in\) Y: if A \(\leq\) B, then A \(\in\) Y.
Every element of X is the image of some element in Y moved by an element of G. That is to say, for every A \(\in\) X, there exists some B \(\in\) Y and there exists g \(\in\) G such that A = Bg.
Finally, for all g \(\in\) G, the intersection {yg : y \(\in\) Y} \(\cap\) Y is non-empty.
We may define an E-unitary inverse semigroup using a McAlister triple. Given (G,X,Y) let M(G,X,Y) be the set of all pairs (A,g) in Y x G such that A acted on by the inverse of g is in Y together with multiplication defined by
(A,g)*(B,h) = (Join(A,Bg^-1),hg)
where Join is the natural join operation of the semilattice and Bg^-1 is B acted on by the inverse of g. With this operation, M(G,X,Y) is a semigroup which we call a McAlister triple semigroup over (G,X,Y). In fact every McAlister triple semigroup is an E-unitary inverse semigroup and every E-unitary inverse semigroup is isomorphic to some McAlister triple semigroup. Note that there need not be a unique McAlister triple semigroup for a particular McAlister triple because in general there is more than one way for a group to act on a partial order.
‣ IsMcAlisterTripleSemigroup( S ) | ( filter ) |
Returns: true or false.
This function returns true if S is a McAlister triple semigroup. A McAlister triple semigroup is a special representation of an E-unitary inverse semigroup IsEUnitaryInverseSemigroup (12.2-3) created by McAlisterTripleSemigroup (8.4-2).
‣ McAlisterTripleSemigroup( G, X, Y[, act] ) | ( operation ) |
Returns: A McAlister triple semigroup.
The following documentation covers the technical information needed to create McAlister triple semigroups in GAP, the underlying theory can be read in the introduction to Chapter 8.4.
In this implementation the partial order X of a McAlister triple is represented by a Digraph (Digraphs: Digraph) object X. The digraph represents a partial order in the sense that vertices are the elements of the partial order and the order relation is defined by A \(\leq\) B if and only if there is an edge from B to A. The semilattice Y of the McAlister triple should be an induced subdigraph Y of X and the DigraphVertexLabels (Digraphs: DigraphVertexLabels) must correspond to the vertices of X on which Y is induced. That means that the following:
Y = InducedSubdigraph(X, DigraphVertexLabels(Y))
must return true. Herein if we say that a vertex A of X is 'in' Y then we mean there is a vertex of Y whose label is A. Alternatively the user may choose to give the argument Y as the vertices of X on which Y is the induced subdigraph.
A McAlister triple semigroup is created from a quadruple (G, X, Y, act) where:
G is a finite group.
X is a digraph satisfying IsPartialOrderDigraph (Digraphs: IsPartialOrderDigraph).
Y is a digraph satisfying IsJoinSemilatticeDigraph (Digraphs: IsJoinSemilatticeDigraph) which is an induced subdigraph of X satisfying the aforementioned labeling criteria. Furthermore the OutNeighbours (Digraphs: OutNeighbours) of each vertex of X which is in Y must contain only vertices which are in Y.
act is a function which takes as its first argument a vertex of the digraph X, its second argument should be an element of G, and it must return a vertex of X. act must be a right action, meaning that act(A,gh)=act(act(A,g),h) holds for all A in X and g,h \(\in\) G. Furthermore the permutation representation of this action must be a subgroup of the automorphism group of X. That means we require the following to return true:
IsSubgroup(AutomorphismGroup(X), Image(ActionHomomorphism(G, DigraphVertices(X), act));
Furthermore every vertex of X must be in the orbit of some vertex of X which is in Y. Finally, act must fix the vertex of X which is the minimal vertex of Y, i.e. the unique vertex of Y whose only out-neighbour is itself.
For user convenience, there are multiple versions of McAlisterTripleSemigroup. When the argument act is omitted it is assumed to be OnPoints (Reference: OnPoints). Additionally, the semilattice argument Y may be replaced by a homogeneous list sub_ver of vertices of X. When sub_ver is provided, McAlisterTripleSemigroup is called with Y equalling InducedSubdigraph(X, sub_ver) with the appropriate labels.
gap> x := Digraph([[1], [1, 2], [1, 2, 3], [1, 4], [1, 4, 5]]); <immutable digraph with 5 vertices, 11 edges> gap> y := InducedSubdigraph(x, [1, 4, 5]); <immutable digraph with 3 vertices, 6 edges> gap> DigraphVertexLabels(y); [ 1, 4, 5 ] gap> A := AutomorphismGroup(x); Group([ (2,4)(3,5) ]) gap> S := McAlisterTripleSemigroup(A, x, y, OnPoints); <McAlister triple semigroup over Group([ (2,4)(3,5) ])> gap> T := McAlisterTripleSemigroup(A, x, y); <McAlister triple semigroup over Group([ (2,4)(3,5) ])> gap> S = T; false gap> IsIsomorphicSemigroup(S, T); true
‣ McAlisterTripleSemigroupGroup( S ) | ( attribute ) |
Returns: A group.
Returns the group used to create the McAlister triple semigroup S via McAlisterTripleSemigroup (8.4-2).
‣ McAlisterTripleSemigroupPartialOrder( S ) | ( attribute ) |
Returns: A partial order digraph.
Returns the IsPartialOrderDigraph (Digraphs: IsPartialOrderDigraph) used to create the McAlister triple semigroup S via McAlisterTripleSemigroup (8.4-2).
‣ McAlisterTripleSemigroupSemilattice( S ) | ( attribute ) |
Returns: A join-semilattice digraph.
Returns the IsJoinSemilatticeDigraph (Digraphs: IsJoinSemilatticeDigraph) used to create the McAlister triple semigroup S via McAlisterTripleSemigroup (8.4-2).
‣ McAlisterTripleSemigroupAction( S ) | ( attribute ) |
Returns: A function.
Returns the action used to create the McAlister triple semigroup S via McAlisterTripleSemigroup (8.4-2).
‣ IsMcAlisterTripleSemigroupElement( x ) | ( filter ) |
‣ IsMTSE( x ) | ( filter ) |
Returns: true or false.
Returns true if x is an element of a McAlister triple semigroup; in particular, this returns true if x has been created by McAlisterTripleSemigroupElement (8.4-8). The functions IsMTSE and IsMcAlisterTripleSemigroupElement are synonyms. The mathematical description of these objects can be found in the introduction to Chapter 8.4.
‣ McAlisterTripleSemigroupElement( S, A, g ) | ( operation ) |
‣ MTSE( S, A, g ) | ( operation ) |
Returns: A McAlister triple semigroup element.
Returns the McAlister triple semigroup element of the McAlister triple semigroup S which corresponds to a label A of a vertex from the McAlisterTripleSemigroupSemilattice (8.4-5) of S and a group element g of the McAlisterTripleSemigroupGroup (8.4-3) of S. The pair (A,g) only represents an element of S if the following holds: A acted on by the inverse of g (via McAlisterTripleSemigroupAction (8.4-6)) is a vertex of the join-semilattice of S.
The functions MTSE and McAlisterTripleSemigroupElement are synonyms.
gap> x := Digraph([[1], [1, 2], [1, 2, 3], [1, 4], [1, 4, 5]]); <immutable digraph with 5 vertices, 11 edges> gap> y := InducedSubdigraph(x, [1, 2, 3]); <immutable digraph with 3 vertices, 6 edges> gap> A := AutomorphismGroup(x); Group([ (2,4)(3,5) ]) gap> S := McAlisterTripleSemigroup(A, x, y, OnPoints); <McAlister triple semigroup over Group([ (2,4)(3,5) ])> gap> T := McAlisterTripleSemigroup(A, x, y); <McAlister triple semigroup over Group([ (2,4)(3,5) ])> gap> S = T; false gap> IsIsomorphicSemigroup(S, T); true gap> a := MTSE(S, 1, (2, 4)(3, 5)); (1, (2,4)(3,5)) gap> b := MTSE(S, 2, ()); (2, ()) gap> a * a; (1, ()) gap> IsMTSE(a * a); true gap> a = MTSE(T, 1, (2, 4)(3, 5)); false gap> a * b; (1, (2,4)(3,5))
generated by GAPDoc2HTML