10
Free objects

This chapter describes the functions in **Semigroups** for dealing with free inverse semigroups and free bands. This part of the manual and the functions described herein were written by Julius JonuĊĦas.

An inverse semigroup F is said to be *free* on a non-empty set X if there is a map f from F to X such that for every inverse semigroup S and a map g from X to S there exists a unique homomorphism g' from F to S such that fg' = g. Moreover, by this universal property, every inverse semigroup can be expressed as a quotient of a free inverse semigroup.

The internal representation of an element of a free inverse semigroup uses a Munn tree. A *Munn tree* is a directed tree with distinguished start and terminal vertices and where the edges are labeled by generators so that two edges labeled by the same generator are only incident to the same vertex if one of the edges is coming in and the other is leaving the vertex. For more information regarding free inverse semigroups and the Munn representations see Section 5.10 of [How95].

See also Reference: Inverse semigroups and monoids, Reference: Partial permutations and Reference: Free Groups, Monoids and Semigroups.

An element of a free inverse semigroup in **Semigroups** is displayed, by default, as a shortest word corresponding to the element. However, there might be more than one word of the minimum length. For example, if x and y are generators of a free inverse semigroups, then

xyy ^ {-1}xx ^ {-1}x ^ {-1} = xxx ^ {-1}yy ^ {-1}x ^ {-1}.

See `MinimalWord`

(10.3-2). Therefore we provide a another method for printing elements of a free inverse semigroup: a unique canonical form. Suppose an element of a free inverse semigroup is given as a Munn tree. Let L be the set of words corresponding to the shortest paths from the start vertex to the leaves of the tree. Also let w be a word corresponding to the shortest path from start to terminal vertices. The word vv ^ -1 is an idempotent for every v in L. The canonical form is given by multiplying these idempotents, in shortlex order, and then postmultiplying by w. For example, consider the word xyy ^ -1xx ^ -1x ^ -1 again. The words corresponding to the paths to the leaves are in this case xx and xy. And w is an empty word since start and terminal vertices are the same. Therefore, the canonical form is

xxx ^ {-1}x ^ {-1}xyy ^ {-1}x ^ {-1}.

See `CanonicalForm`

(10.3-1).

`‣ FreeInverseSemigroup` ( rank[, name] ) | ( function ) |

`‣ FreeInverseSemigroup` ( name1, name2, ... ) | ( function ) |

`‣ FreeInverseSemigroup` ( names ) | ( function ) |

Returns: A free inverse semigroup.

Returns a free inverse semigroup on `rank` generators, where `rank` is a positive integer. If `rank` is not specified, the number of `names` is used. If `S`

is a free inverse semigroup, then the generators can be accessed by `S.1`

, `S.2`

and so on.

gap> S := FreeInverseSemigroup(7); <free inverse semigroup on the generators [ x1, x2, x3, x4, x5, x6, x7 ]> gap> S := FreeInverseSemigroup(7, "s"); <free inverse semigroup on the generators [ s1, s2, s3, s4, s5, s6, s7 ]> gap> S := FreeInverseSemigroup("a", "b", "c"); <free inverse semigroup on the generators [ a, b, c ]> gap> S := FreeInverseSemigroup(["a", "b", "c"]); <free inverse semigroup on the generators [ a, b, c ]> gap> S.1; a gap> S.2; b

`‣ IsFreeInverseSemigroupCategory` ( obj ) | ( category ) |

Every free inverse semigroup in **GAP** created by `FreeInverseSemigroup`

(10.1-1) belongs to the category `IsFreeInverseSemigroup`

. Basic operations for a free inverse semigroup are: `GeneratorsOfInverseSemigroup`

(Reference: GeneratorsOfInverseSemigroup) and `GeneratorsOfSemigroup`

(Reference: GeneratorsOfSemigroup). Elements of a free inverse semigroup belong to the category `IsFreeInverseSemigroupElement`

(10.1-4).

`‣ IsFreeInverseSemigroup` ( S ) | ( property ) |

Returns: `true`

or `false`

Attempts to determine whether the given semigroup `S` is a free inverse semigroup.

`‣ IsFreeInverseSemigroupElement` | ( category ) |

Every element of a free inverse semigroup belongs to the category `IsFreeInverseSemigroupElement`

.

`‣ IsFreeInverseSemigroupElementCollection` | ( category ) |

Every collection of elements of a free inverse semigroup belongs to the category `IsFreeInverseSemigroupElementCollection`

. For example, every free inverse semigroup belongs to `IsFreeInverseSemigroupElementCollection`

.

There is a way to change how **GAP** displays free inverse semigroup elements using the user preference `FreeInverseSemigroupElementDisplay`

. See `UserPreference`

(Reference: UserPreference) for more information about user preferences.

There are two possible values for `FreeInverseSemigroupElementDisplay`

:

**minimal**With this option selected,

**GAP**will display a shortest word corresponding to the free inverse semigroup element. However, this shortest word is not unique. This is a default setting.**canonical**With this option selected,

**GAP**will display a free inverse semigroup element in the canonical form.

gap> SetUserPreference("semigroups", > "FreeInverseSemigroupElementDisplay", > "minimal"); gap> S := FreeInverseSemigroup(2); <free inverse semigroup on the generators [ x1, x2 ]> gap> S.1 * S.2; x1*x2 gap> SetUserPreference("semigroups", > "FreeInverseSemigroupElementDisplay", > "canonical"); gap> S.1 * S.2; x1x2x2^-1x1^-1x1x2

`w`^ -1returns the semigroup inverse of the free inverse semigroup element

`w`.`u`*`v`returns the product of two free inverse semigroup elements

`u`and`v`.`u`=`v`checks if two free inverse semigroup elements are equal, by comparing their canonical forms.

`‣ CanonicalForm` ( w ) | ( attribute ) |

Returns: A string.

Every element of a free inverse semigroup has a unique canonical form. If `w` is such an element, then `CanonicalForm`

returns the canonical form of `w` as a string.

gap> S := FreeInverseSemigroup(3); <free inverse semigroup on the generators [ x1, x2, x3 ]> gap> x := S.1; y := S.2; x1 x2 gap> CanonicalForm(x ^ 3 * y ^ 3); "x1x1x1x2x2x2x2^-1x2^-1x2^-1x1^-1x1^-1x1^-1x1x1x1x2x2x2"

`‣ MinimalWord` ( w ) | ( attribute ) |

Returns: A string.

For an element `w` of a free inverse semigroup `S`

, `MinimalWord`

returns a word of minimal length equal to `w` in `S`

as a string.

Note that there maybe more than one word of minimal length which is equal to `w` in `S`

.

gap> S := FreeInverseSemigroup(3); <free inverse semigroup on the generators [ x1, x2, x3 ]> gap> x := S.1; x1 gap> y := S.2; x2 gap> MinimalWord(x ^ 3 * y ^ 3); "x1*x1*x1*x2*x2*x2"

A semigroup B is a *free band* on a non-empty set X if B is a band with a map f from B to X such that for every band S and every map g from X to B there exists a unique homomorphism g' from B to S such that fg' = g. The free band on a set X is unique up to isomorphism. Moreover, by the universal property, every band can be expressed as a quotient of a free band.

For an alternative description of a free band. Suppose that X is a non-empty set and X ^ + a free semigroup on X. Also suppose that b is the smallest congurance on X ^ + containing the set

\{(w ^ 2, w) : w \in X ^ + \}.

Then the free band on X is isomorphic to the quotient of X ^ + by b. See Section 4.5 of [How95] for more information on free bands.

`‣ FreeBand` ( rank[, name] ) | ( function ) |

`‣ FreeBand` ( name1, name2, .., . ) | ( function ) |

`‣ FreeBand` ( names ) | ( function ) |

Returns: A free band.

Returns a free band on `rank` generators, for a positive integer `rank`. If `rank` is not specified, the number of `names` is used. The resulting semigroup is always finite.

gap> FreeBand(6); <free band on the generators [ x1, x2, x3, x4, x5, x6 ]> gap> FreeBand(6, "b"); <free band on the generators [ b1, b2, b3, b4, b5, b6 ]> gap> FreeBand("a", "b", "c"); <free band on the generators [ a, b, c ]> gap> FreeBand("a", "b", "c"); <free band on the generators [ a, b, c ]> gap> S := FreeBand(["a", "b", "c"]); <free band on the generators [ a, b, c ]> gap> Size(S); 159 gap> gens := Generators(S); [ a, b, c ] gap> S.1 * S.2; ab

`‣ IsFreeBandCategory` | ( category ) |

`IsFreeBandCategory`

is the category of semigroups created using `FreeBand`

(10.4-1).

gap> IsFreeBandCategory(FreeBand(3)); true gap> IsFreeBand(SymmetricGroup(6)); false

`‣ IsFreeBand` ( S ) | ( property ) |

Returns: `true`

or `false`

.

`IsFreeBand`

returns `true`

if the given semigroup `S` is a free band.

gap> IsFreeBand(FreeBand(3)); true gap> IsFreeBand(SymmetricGroup(6)); false gap> IsFreeBand(FullTransformationMonoid(7)); false

`‣ IsFreeBandElement` | ( category ) |

`IsFreeBandElement`

is a `Category`

containing the elements of a free band.

gap> IsFreeBandElement(Generators(FreeBand(4))[1]); true gap> IsFreeBandElement(Transformation([1, 3, 4, 1])); false gap> IsFreeBandElement((1, 2, 3, 4)); false

`‣ IsFreeBandElementCollection` | ( category ) |

Every collection of elements of a free band belongs to the category `IsFreeBandElementCollection`

. For example, every free band belongs to `IsFreeBandElementCollection`

.

`‣ IsFreeBandSubsemigroup` | ( filter ) |

`IsFreeBandSubsemigroup`

is a synonym for `IsSemigroup`

and `IsFreeBandElementCollection`

.

gap> S := FreeBand(2); <free band on the generators [ x1, x2 ]> gap> x := S.1; x1 gap> y := S.2; x2 gap> new := Semigroup([x * y, x]); <semigroup with 2 generators> gap> IsFreeBand(new); false gap> IsFreeBandSubsemigroup(new); true

`‣ ContentOfFreeBandElement` ( x ) | ( attribute ) |

`‣ ContentOfFreeBandElementCollection` ( coll ) | ( attribute ) |

Returns: A list of integers

The content of a free band element `x` is the set of generators appearing in the word representing the element `x` of the free band.

The function `ContentOfFreeBandElement`

returns the content of free band element `x` represented as a list of integers, where `1`

represents the first generator, `2`

the second generator, and so on.

The function `ContentOfFreeBandElementCollection`

returns the the least list `C`

for the collection of free band elements `coll` such that the content of every element in `coll` is contained in `C`

.

gap> S := FreeBand(2); <free band on the generators [ x1, x2 ]> gap> x := S.1; x1 gap> y := S.2; x2 gap> ContentOfFreeBandElement(x); [ 1 ] gap> ContentOfFreeBandElement(x * y); [ 1, 2 ] gap> ContentOfFreeBandElement(x * y * x); [ 1, 2 ] gap> ContentOfFreeBandElementCollection([x, y]); [ 1, 2 ]

`u`*`v`returns the product of two free band elements

`u`and`v`.`u`=`v`checks if two free band elements are equal.

`u`<`v`compares the sizes of the internal representations of two free band elements.

`‣ GreensDClassOfElement` ( S, x ) | ( operation ) |

Returns: A Green's \(\mathscr{D}\)-class

Let `S` be a free band. Two elements of ` S ` are \(\mathscr{D}\)-related if and only if they have the same content i.e. the set of generators appearing in any factorization of the elements. Therefore, a \(\mathscr{D}\)-class of a free band element ` x ` is the set of elements of ` S ` which have the same content as ` x `.

gap> S := FreeBand(3, "b"); <free band on the generators [ b1, b2, b3 ]> gap> x := S.1 * S.2; b1b2 gap> D := GreensDClassOfElement(S, x); <Green's D-class: b1b2> gap> IsGreensDClass(D); true

generated by GAPDoc2HTML