|
|
|
|
Impressum chap13_mj.html
Sprache: HTML
|
|
| products/Sources/formale Sprachen/GAP/pkg/semigroups/doc/chap13_mj.html |
 |
<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<script type="text/javascript"
src="https://cdn.jsdelivr.net/npm/mathjax@2/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<title>GAP (Semigroups) - Chapter 13: Congruences</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />
<meta name="generator" content="GAPDoc2HTML" />
<link rel="stylesheet" type="text/css" href="manual.css" />
<script src="manual.js" type="text/javascript"></script>
<script type="text/javascript">overwriteStyle();</script>
</head>
<body class="chap13" onload="jscontent()">
<div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0_mj.html">Top</a> <a href="chap1_mj.html">1</a> <a href="chap2_mj.html">2</a> <a href="chap3_mj.html">3</a> <a href="chap4_mj.html">4</a> <a href="chap5_mj.html">5</a> <a href="chap6_mj.html">6</a> <a href="chap7_mj.html">7</a> <a href="chap8_mj.html">8</a> <a href="chap9_mj.html">9</a> <a href="chap10_mj.html">10</a> <a href="chap11_mj.html">11</a> <a href="chap12_mj.html">12</a> <a href="chap13_mj.html">13</a> <a href="chap14_mj.html">14</a> <a href="chap15_mj.html">15</a> <a href="chap16_mj.html">16</a> <a href="chap17_mj.html">17</a> <a href="chap18_mj.html">18</a> <a href="chapBib_mj.html">Bib</a> <a href="chapInd_mj.html">Ind</a> </div>
<div class="chlinkprevnexttop"> <a href="chap0_mj.html">[Top of Book]</a> <a href="chap0_mj.html#contents">[Contents]</a> <a href="chap12_mj.html">[Previous Chapter]</a> <a href="chap14_mj.html">[Next Chapter]</a> </div>
<p id="mathjaxlink" class="pcenter"><a href="chap13.html">[MathJax off]</a></p>
<p><a id="X82BD951079E3C349" name="X82BD951079E3C349"></a></p>
<div class="ChapSects"><a href="chap13_mj.html#X82BD951079E3C349">13 <span class="Heading">Congruences</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap13_mj.html#X784770137D98FEB9">13.1 <span class="Heading">Semigroup congruence objects</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X78E34B737F0E009F">13.1-1 IsSemigroupCongruence</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X7E909A78830D42A6">13.1-2 IsLeftSemigroupCongruence</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X839EEA797B1CCB67">13.1-3 IsRightSemigroupCongruence</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap13_mj.html#X7D49787B7B2589B2">13.2 <span class="Heading">
Creating congruences
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X85CE56AC84FA5D33">13.2-1 SemigroupCongruence</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X8757DB087BE7E55A">13.2-2 LeftSemigroupCongruence</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X7D01176B788FEE60">13.2-3 RightSemigroupCongruence</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap13_mj.html#X7D65BB067A762CD6">13.3 <span class="Heading">
Congruence classes
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X7B1F67A97E23E6A4">13.3-1 IsCongruenceClass</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X7C803E8C84E81A0B">13.3-2 IsLeftCongruenceClass</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X7D2F11C28470BC5A">13.3-3 IsRightCongruenceClass</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X86C05F31797C1D6D">13.3-4 NonTrivialEquivalenceClasses</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X7DA4BABC7891A7F1">13.3-5 EquivalenceRelationLookup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X8022B7898553F624">13.3-6 EquivalenceRelationCanonicalLookup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X842D567F79648FEB">13.3-7 EquivalenceRelationCanonicalPartition</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X85400841879E41A5">13.3-8 OnLeftCongruenceClasses</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X7D66F8607B4F0D8F">13.3-9 OnRightCongruenceClasses</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap13_mj.html#X806DEBC07E6D8FCA">13.4 <span class="Heading">
Finding the congruences of a semigroup
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X7E8D5BA27CB5A4DA">13.4-1 CongruencesOfSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X7838738987B2DB41">13.4-2 MinimalCongruencesOfSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X7986F3597F9DF7AF">13.4-3 PrincipalCongruencesOfSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X8195D6F47EE52806">13.4-4 IsCongruencePoset</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X86C9C5BA7FE93F4C">13.4-5 LatticeOfCongruences</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X784CFDE37A0B4F84">13.4-6 CayleyDigraphOfCongruences</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X83ACF2C0789F621B">13.4-7 PosetOfPrincipalCongruences</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X7B2E2CEE8626FBC3">13.4-8 CongruencesOfPoset</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X830F42B582A2FAA0">13.4-9 UnderlyingSemigroupOfCongruencePoset</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X78A91138818A4FAE">13.4-10 PosetOfCongruences</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X87CF25A178B7F1AF">13.4-11 JoinSemilatticeOfCongruences</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X7ECE04727B6A58A3">13.4-12 GeneratingCongruencesOfJoinSemilattice</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X780E2B3F8509CE32">13.4-13 MinimalCongruences</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X7AE16F237E862934">13.4-14 NumberOfRightCongruences</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X807A5FCC87661FA4">13.4-15 IteratorOfRightCongruences</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap13_mj.html#X857D750579B87DBF">13.5 <span class="Heading">
Comparing congruences
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X85075F1D878512F5">13.5-1 IsSubrelation</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X83878AED7A8E75BE">13.5-2 IsSuperrelation</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X7952A5A5789C6F60">13.5-3 MeetSemigroupCongruences</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X8262D5207DBF3C5B">13.5-4 JoinSemigroupCongruences</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap13_mj.html#X7A6478D1831DD787">13.6 <span class="Heading">Congruences on Rees matrix semigroups</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X7F4AFD7F7E163022">13.6-1 IsRMSCongruenceByLinkedTriple</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X87A475E4847D3C96">13.6-2 RMSCongruenceByLinkedTriple</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X79E4CF7B79B25AE3">13.6-3 IsRMSCongruenceClassByLinkedTriple</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X7E9AB940868FCC9D">13.6-4 RMSCongruenceClassByLinkedTriple</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X7B19CACF7A37ADBC">13.6-5 IsLinkedTriple</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X7DB7E32E865AD95D">13.6-6 AsSemigroupCongruenceByGeneratingPairs</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap13_mj.html#X7BFDC38178940AE6">13.7 <span class="Heading">
Congruences on inverse semigroups
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X8546E48E85A2A7E8">13.7-1 IsInverseSemigroupCongruenceByKernelTrace</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X7A588B737CEEB104">13.7-2 InverseSemigroupCongruenceByKernelTrace</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X87916D4E854F1F6B">13.7-3 AsInverseSemigroupCongruenceByKernelTrace</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X7D521AFF7876CBC7">13.7-4 KernelOfSemigroupCongruence</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X80972A5B82D88F89">13.7-5 TraceOfSemigroupCongruence</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X8049A0E780A7A8D9">13.7-6 IsInverseSemigroupCongruenceClassByKernelTrace</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X857495647F9A9579">13.7-7 MinimumGroupCongruence</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap13_mj.html#X8036DAA287C71CAC">13.8 <span class="Heading">
Congruences on graph inverse semigroups
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X7AEB7DA27E76145B">13.8-1 IsCongruenceByWangPair</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X7F30D10F7BEEEBB9">13.8-2 CongruenceByWangPair</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X817F4FC27E9BACD8">13.8-3 AsCongruenceByWangPair</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X858AE13379B5C380">13.8-4 GeneratingCongruencesOfLattice</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap13_mj.html#X7CE483078769A4D6">13.9 <span class="Heading">Rees congruences</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X7BC02E08840E0AF4">13.9-1 SemigroupIdealOfReesCongruence</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X7E15F66A8029C64A">13.9-2 IsReesCongruenceClass</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap13_mj.html#X7C6B4A2980BE9B03">13.10 <span class="Heading">Universal and trivial congruences</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X8751EF557A81A2B1">13.10-1 IsUniversalSemigroupCongruence</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X8646253C86AFFA29">13.10-2 IsUniversalSemigroupCongruenceClass</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X7B99C6A47F3D375F">13.10-3 UniversalSemigroupCongruence</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap13_mj.html#X7A9B483B7B4E0E27">13.10-4 TrivialCongruence</a></span>
</div></div>
</div>
<h3>13 <span class="Heading">Congruences</span></h3>
<p>Congruences in <strong class="pkg">Semigroups</strong> can be described in several different ways:</p>
<ul>
<li><p>Generating pairs -- the minimal congruence which contains these pairs</p>
</li>
<li><p>Rees congruences -- the congruence specified by a given ideal</p>
</li>
<li><p>Universal congruences -- the unique congruence with only one class</p>
</li>
<li><p>Linked triples -- only for simple or 0-simple semigroups (see below)</p>
</li>
<li><p>Kernel and trace -- only for inverse semigroups</p>
</li>
<li><p>Word graph -- only for congruences created via <code class="func">IteratorOfLeftCongruences</code> (<a href="chap13_mj.html#X807A5FCC87661FA4"><span class="RefLink">13.4-15</span></a>) or <code class="func">IteratorOfRightCongruences</code> (<a href="chap13_mj.html#X807A5FCC87661FA4"><span class="RefLink">13.4-15</span></a>)</p>
</li>
<li><p>Wang pairs -- only for graph inverse semigroup</p>
</li>
</ul>
<p>The operation <code class="func">SemigroupCongruence</code> (<a href="chap13_mj.html#X85CE56AC84FA5D33"><span class="RefLink">13.2-1</span></a>) 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.</p>
<p>If a congruence is specified by generating pairs on a simple, 0-simple, or inverse semigroup, then the congruence may 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.
<p>We can also create left congruences and right congruences, using the <code class="func">LeftSemigroupCongruence</code> (<a href="chap13_mj.html#X8757DB087BE7E55A"><span class="RefLink">13.2-2</span></a>) and <code class="func">RightSemigroupCongruence</code> (<a href="chap13_mj.html#X7D01176B788FEE60"><span class="RefLink">13.2-3</span></a>) functions.</p>
<p>Please note that congruence objects made in <strong class="pkg">GAP</strong> before loading the <strong class="pkg">Semigroups</strong> package may not behave correctly after <strong class="pkg">Semigroups</strong> is loaded. If <strong class="pkg">Semigroups</strong> is loaded at the beginning of the session, or before any congruence work is done, then the objects should behave correctly.</p>
<p><a id="X784770137D98FEB9" name="X784770137D98FEB9"></a></p>
<h4>13.1 <span class="Heading">Semigroup congruence objects</span></h4>
<p><a id="X78E34B737F0E009F" name="X78E34B737F0E009F"></a></p>
<h5>13.1-1 IsSemigroupCongruence</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsSemigroupCongruence</code>( <var class="Arg">obj</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>A semigroup congruence <code class="code">cong</code> is an equivalence relation on a semigroup <code class="code">S</code> which respects left and right multiplication.</p>
<p>That is, if <span class="SimpleMath">\((a,b)\)</span> is a pair in <code class="code">cong</code>, and <span class="SimpleMath">\(x\)</span> is an element of <code class="code">S</code>, then <span class="SimpleMath">\((ax,bx)\)</span> and <span class="SimpleMath">\((xa,xb)\)</span> are both in <code class="code">cong</code>.</p>
<p>The simplest way of creating a congruence in <strong class="pkg">Semigroups</strong> is by a set of <em>generating pairs</em>. See <code class="func">SemigroupCongruence</code> (<a href="chap13_mj.html#X85CE56AC84FA5D33"><span class="RefLink">13.2-1</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := Semigroup([</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([2, 1, 1, 2, 1]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([3, 4, 3, 4, 4]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([3, 4, 3, 4, 3]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([4, 3, 3, 4, 4])]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">pair1 := [Transformation([3, 4, 3, 4, 3]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([1, 2, 1, 2, 1])];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">pair2 := [Transformation([4, 3, 4, 3, 4]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([3, 4, 3, 4, 3])];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">cong := SemigroupCongruence(S, [pair1, pair2]);</span>
<semigroup congruence over <simple transformation semigroup of
degree 5 with 4 generators> with linked triple (2,4,1)>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSemigroupCongruence(cong);</span>
true</pre></div>
<p><a id="X7E909A78830D42A6" name="X7E909A78830D42A6"></a></p>
<h5>13.1-2 IsLeftSemigroupCongruence</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsLeftSemigroupCongruence</code>( <var class="Arg">obj</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>A left semigroup congruence <code class="code">cong</code> is an equivalence relation on a semigroup <code class="code">S</code> which respects left multiplication.</p>
<p>That is, if <span class="SimpleMath">\((a,b)\)</span> is a pair in <code class="code">cong</code>, and <span class="SimpleMath">\(x\)</span> is an element of <code class="code">S</code>, then <span class="SimpleMath">\((xa,xb)\)</span> is also in <code class="code">cong</code>.</p>
<p>The simplest way of creating a left congruence in <strong class="pkg">Semigroups</strong> is by a set of <em>generating pairs</em>. See <code class="func">LeftSemigroupCongruence</code> (<a href="chap13_mj.html#X8757DB087BE7E55A"><span class="RefLink">13.2-2</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := Semigroup([</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([2, 1, 1, 2, 1]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([3, 4, 3, 4, 4]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([3, 4, 3, 4, 3]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([4, 3, 3, 4, 4])]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">pair1 := [Transformation([3, 4, 3, 4, 3]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([1, 2, 1, 2, 1])];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">pair2 := [Transformation([4, 3, 4, 3, 4]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([3, 4, 3, 4, 3])];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">cong := LeftSemigroupCongruence(S, [pair1, pair2]);</span>
<left semigroup congruence over <transformation semigroup of degree 5
with 4 generators> with 2 generating pairs>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsLeftSemigroupCongruence(cong);</span>
true</pre></div>
<p><a id="X839EEA797B1CCB67" name="X839EEA797B1CCB67"></a></p>
<h5>13.1-3 IsRightSemigroupCongruence</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsRightSemigroupCongruence</code>( <var class="Arg">obj</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>A right semigroup congruence <code class="code">cong</code> is an equivalence relation on a semigroup <code class="code">S</code> which respects right multiplication.</p>
<p>That is, if <span class="SimpleMath">\((a,b)\)</span> is a pair in <code class="code">cong</code>, and <span class="SimpleMath">\(x\)</span> is an element of <code class="code">S</code>, then <span class="SimpleMath">\((ax,bx)\)</span> is also in <code class="code">cong</code>.</p>
<p>The simplest way of creating a right congruence in <strong class="pkg">Semigroups</strong> is by a set of <em>generating pairs</em>. See <code class="func">RightSemigroupCongruence</code> (<a href="chap13_mj.html#X7D01176B788FEE60"><span class="RefLink">13.2-3</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := Semigroup([</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([2, 1, 1, 2, 1]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([3, 4, 3, 4, 4]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([3, 4, 3, 4, 3]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([4, 3, 3, 4, 4])]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">pair1 := [Transformation([3, 4, 3, 4, 3]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([1, 2, 1, 2, 1])];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">pair2 := [Transformation([4, 3, 4, 3, 4]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([3, 4, 3, 4, 3])];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">RightSemigroupCongruence(S, [pair1, pair2]);</span>
<right semigroup congruence over <transformation semigroup of
degree 5 with 4 generators> with 2 generating pairs>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsRightSemigroupCongruence(cong);</span>
true</pre></div>
<p><a id="X7D49787B7B2589B2" name="X7D49787B7B2589B2"></a></p>
<h4>13.2 <span class="Heading">
Creating congruences
</span></h4>
<p><a id="X85CE56AC84FA5D33" name="X85CE56AC84FA5D33"></a></p>
<h5>13.2-1 SemigroupCongruence</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SemigroupCongruence</code>( <var class="Arg">S</var>, <var class="Arg">pairs</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: A semigroup congruence.</p>
<p>This function returns a semigroup congruence over the semigroup <var class="Arg">S</var>.</p>
<p>If <var class="Arg">pairs</var> is a list of lists of size 2 with elements from <var class="Arg">S</var>, then this function will return the semigroup congruence defined by these generating pairs. The individual pairs may instead be given as separate arguments.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := Semigroup([</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([2, 1, 1, 2, 1]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([3, 4, 3, 4, 4]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([3, 4, 3, 4, 3]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([4, 3, 3, 4, 4])]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">pair1 := [Transformation([3, 4, 3, 4, 3]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([1, 2, 1, 2, 1])];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">pair2 := [Transformation([4, 3, 4, 3, 4]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([3, 4, 3, 4, 3])];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">SemigroupCongruence(S, [pair1, pair2]);</span>
<semigroup congruence over <simple transformation semigroup of
degree 5 with 4 generators> with linked triple (2,4,1)>
<span class="GAPprompt">gap></span> <span class="GAPinput">SemigroupCongruence(S, pair1, pair2);</span>
<semigroup congruence over <simple transformation semigroup of
degree 5 with 4 generators> with linked triple (2,4,1)></pre></div>
<p><a id="X8757DB087BE7E55A" name="X8757DB087BE7E55A"></a></p>
<h5>13.2-2 LeftSemigroupCongruence</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ LeftSemigroupCongruence</code>( <var class="Arg">S</var>, <var class="Arg">pairs</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: A left semigroup congruence.</p>
<p>This function returns a left semigroup congruence over the semigroup <var class="Arg">S</var>.</p>
<p>If <var class="Arg">pairs</var> is a list of lists of size 2 with elements from <var class="Arg">S</var>, then this function will return the least left semigroup congruence on <var class="Arg">S</var> which contains these generating pairs. The individual pairs may instead be given as separate arguments.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := Semigroup([</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([2, 1, 1, 2, 1]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([3, 4, 3, 4, 4]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([3, 4, 3, 4, 3]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([4, 3, 3, 4, 4])]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">pair1 := [Transformation([3, 4, 3, 4, 3]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([1, 2, 1, 2, 1])];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">pair2 := [Transformation([4, 3, 4, 3, 4]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([3, 4, 3, 4, 3])];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">LeftSemigroupCongruence(S, [pair1, pair2]);</span>
<left semigroup congruence over <transformation semigroup of degree 5
with 4 generators> with 2 generating pairs>
<span class="GAPprompt">gap></span> <span class="GAPinput">LeftSemigroupCongruence(S, pair1, pair2);</span>
<left semigroup congruence over <transformation semigroup of degree 5
with 4 generators> with 2 generating pairs></pre></div>
<p><a id="X7D01176B788FEE60" name="X7D01176B788FEE60"></a></p>
<h5>13.2-3 RightSemigroupCongruence</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RightSemigroupCongruence</code>( <var class="Arg">S</var>, <var class="Arg">pairs</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: A right semigroup congruence.</p>
<p>This function returns a right semigroup congruence over the semigroup <var class="Arg">S</var>.</p>
<p>If <var class="Arg">pairs</var> is a list of lists of size 2 with elements from <var class="Arg">S</var>, then this function will return the least right semigroup congruence on <var class="Arg">S</var> which contains these generating pairs. The individual pairs may instead be given as separate arguments.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := Semigroup([</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([2, 1, 1, 2, 1]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([3, 4, 3, 4, 4]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([3, 4, 3, 4, 3]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([4, 3, 3, 4, 4])]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">pair1 := [Transformation([3, 4, 3, 4, 3]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([1, 2, 1, 2, 1])];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">pair2 := [Transformation([4, 3, 4, 3, 4]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([3, 4, 3, 4, 3])];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">RightSemigroupCongruence(S, [pair1, pair2]);</span>
<right semigroup congruence over <transformation semigroup of
degree 5 with 4 generators> with 2 generating pairs>
<span class="GAPprompt">gap></span> <span class="GAPinput">RightSemigroupCongruence(S, pair1, pair2);</span>
<right semigroup congruence over <transformation semigroup of
degree 5 with 4 generators> with 2 generating pairs></pre></div>
<p><a id="X7D65BB067A762CD6" name="X7D65BB067A762CD6"></a></p>
<h4>13.3 <span class="Heading">
Congruence classes
</span></h4>
<p>The main operations and attributes for congruences in the <strong class="pkg">GAP</strong> library are:</p>
<ul>
<li><p><code class="func">EquivalenceClasses</code> (<a href="../../../doc/ref/chap33_mj.html#X879439897EF4D728"><span class="RefLink">Reference: EquivalenceClasses attribute</span></a>)</p>
</li>
<li><p><code class="code">NrEquivalenceClasses</code></p>
</li>
<li><p><code class="func">EquivalenceClassOfElement</code> (<a href="../../../doc/ref/chap33_mj.html#X7BB985BA7FD7A82E"><span class="RefLink">Reference: EquivalenceClassOfElement</span></a>)</p>
</li>
</ul>
<p><a id="X7B1F67A97E23E6A4" name="X7B1F67A97E23E6A4"></a></p>
<h5>13.3-1 IsCongruenceClass</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsCongruenceClass</code>( <var class="Arg">obj</var> )</td><td class="tdright">( category )</td></tr></table></div>
<p>This category contains any object which is an equivalence class of a semigroup congruence (see <code class="func">IsSemigroupCongruence</code> (<a href="chap13_mj.html#X78E34B737F0E009F"><span class="RefLink">13.1-1</span></a>)). An object will only be in this category if the relation is known to be a semigroup congruence when the congruence class is created.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := Monoid([</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([1, 2, 2]), Transformation([3, 1, 3])]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">cong := SemigroupCongruence(S, [Transformation([1, 2, 1]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([2, 1, 2])]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">class := EquivalenceClassOfElement(cong,</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([3, 1, 1]));</span>
<2-sided congruence class of Transformation( [ 3, 1, 1 ] )>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsCongruenceClass(class);</span>
true</pre></div>
<p><a id="X7C803E8C84E81A0B" name="X7C803E8C84E81A0B"></a></p>
<h5>13.3-2 IsLeftCongruenceClass</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsLeftCongruenceClass</code>( <var class="Arg">obj</var> )</td><td class="tdright">( category )</td></tr></table></div>
<p>This category contains any object which is an equivalence class of a left semigroup congruence (see <code class="func">IsLeftSemigroupCongruence</code> (<a href="chap13_mj.html#X7E909A78830D42A6"><span class="RefLink">13.1-2</span></a>)). An object will only be in this category if the relation is known to be a left semigroup congruence when the class is created.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := Monoid([</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([1, 2, 2]), Transformation([3, 1, 3])]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">pairs := [Transformation([1, 2, 1]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([2, 1, 2])];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">cong := LeftSemigroupCongruence(S, pairs);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">class := EquivalenceClassOfElement(cong,</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([3, 1, 1]));</span>
<left congruence class of Transformation( [ 3, 1, 1 ] )>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsLeftCongruenceClass(class);</span>
true</pre></div>
<p><a id="X7D2F11C28470BC5A" name="X7D2F11C28470BC5A"></a></p>
<h5>13.3-3 IsRightCongruenceClass</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsRightCongruenceClass</code>( <var class="Arg">obj</var> )</td><td class="tdright">( category )</td></tr></table></div>
<p>This category contains any object which is an equivalence class of a right semigroup congruence (see <code class="func">IsRightSemigroupCongruence</code> (<a href="chap13_mj.html#X839EEA797B1CCB67"><span class="RefLink">13.1-3</span></a>)). An object will only be in this category if the relation is known to be a right semigroup congruence when the class is created.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := Monoid([</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([1, 2, 2]), Transformation([3, 1, 3])]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">pairs := [Transformation([1, 2, 1]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([2, 1, 2])];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">cong := RightSemigroupCongruence(S, pairs);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">class := EquivalenceClassOfElement(cong,</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([3, 1, 1]));</span>
<right congruence class of Transformation( [ 3, 1, 1 ] )>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsRightCongruenceClass(class);</span>
true</pre></div>
<p><a id="X86C05F31797C1D6D" name="X86C05F31797C1D6D"></a></p>
<h5>13.3-4 NonTrivialEquivalenceClasses</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NonTrivialEquivalenceClasses</code>( <var class="Arg">eq</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A list of equivalence classes.</p>
<p>If <var class="Arg">eq</var> is an equivalence relation, then this attribute returns a list of all equivalence classes of <var class="Arg">eq</var> which contain more than one element.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := Monoid([Transformation([1, 2, 2]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([3, 1, 3])]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">cong := SemigroupCongruence(S, [Transformation([1, 2, 1]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([2, 1, 2])]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">classes := NonTrivialEquivalenceClasses(cong);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Set(classes);</span>
[ <2-sided congruence class of Transformation( [ 1, 2, 2 ] )>,
<2-sided congruence class of Transformation( [ 3, 1, 3 ] )>,
<2-sided congruence class of Transformation( [ 3, 1, 1 ] )>,
<2-sided congruence class of Transformation( [ 2, 1, 2 ] )>,
<2-sided congruence class of Transformation( [ 3, 3, 3 ] )> ]
<span class="GAPprompt">gap></span> <span class="GAPinput">cong := RightSemigroupCongruence(S, [Transformation([1, 2, 1]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([2, 1, 2])]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">classes := NonTrivialEquivalenceClasses(cong);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Set(classes);</span>
[ <right congruence class of Transformation( [ 3, 1, 3 ] )>,
<right congruence class of Transformation( [ 2, 1, 2 ] )> ]</pre></div>
<p><a id="X7DA4BABC7891A7F1" name="X7DA4BABC7891A7F1"></a></p>
<h5>13.3-5 EquivalenceRelationLookup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ EquivalenceRelationLookup</code>( <var class="Arg">equiv</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A list.</p>
<p>This attribute describes the equivalence relation <var class="Arg">equiv</var>, defined over a finite semigroup, as a list of positive integers of length the size of the finite semigroup over which <var class="Arg">equiv</var> is defined.</p>
<p>Each position in the list corresponds to an element of the semigroup (in a consistent canonical order) and the integer at that position is a unique identifier for that element's equivalence class under equiv. Two elements of the semigroup on which the equivalence is defined are related in the equivalence if and only if they have the same number at their respective positions in the lookup.
<p>Note that the order in which numbers appear in the list is non-deterministic, and two equivalence relations describing the same mathematical relation might therefore have different lookups. Note also that the maximum value of the list may not be the number of classes of <var class="Arg">equiv</var>, and that any integer might not be included. However, see <code class="func">EquivalenceRelationCanonicalLookup</code> (<a href="chap13_mj.html#X8022B7898553F624"><span class="RefLink">13.3-6</span></a>).</p>
<p>See also <code class="func">EquivalenceRelationPartition</code> (<a href="../../../doc/ref/chap33_mj.html#X877389B683DD8F1A"><span class="RefLink">Reference: EquivalenceRelationPartition</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := Monoid([</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([1, 2, 2]), Transformation([3, 1, 3])]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">cong := SemigroupCongruence(S,</span>
<span class="GAPprompt">></span> <span class="GAPinput">[Transformation([1, 2, 1]), Transformation([2, 1, 2])]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">lookup := EquivalenceRelationLookup(cong);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">lookup[3] = lookup[8];</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">lookup[2] = lookup[9];</span>
false</pre></div>
<p><a id="X8022B7898553F624" name="X8022B7898553F624"></a></p>
<h5>13.3-6 EquivalenceRelationCanonicalLookup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ EquivalenceRelationCanonicalLookup</code>( <var class="Arg">equiv</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A list.</p>
<p>This attribute describes the equivalence relation <var class="Arg">equiv</var>, defined over a finite semigroup, as a list of positive integers of length the size of the semigroup.</p>
<p>Each position in the list corresponds to an element of the semigroup (in a consistent canonical order as defined by <code class="func">PositionCanonical</code> (<a href="chap11_mj.html#X7B4B10AE81602D4E"><span class="RefLink">11.1-2</span></a>)) and the integer at that position is a unique identifier for that element's equivalence class under equiv. The value of EquivalenceRelationCanonicalLookup has the property that the first appearance of the value i is strictly later than the first appearance of i-1, and that all entries in the list will be from the range [1 .. NrEquivalenceClasses(equiv)]. As such, two equivalence relations on a given semigroup are equal if and only if their canonical lookups are equal.
<p>Two elements of the semigroup on which the equivalence relation is defined are related in the equivalence relation if and only if they have the same number at their respective positions in the lookup.</p>
<p>See also <code class="func">EquivalenceRelationLookup</code> (<a href="chap13_mj.html#X7DA4BABC7891A7F1"><span class="RefLink">13.3-5</span></a>) and <code class="func">EquivalenceRelationPartition</code> (<a href="../../../doc/ref/chap33_mj.html#X877389B683DD8F1A"><span class="RefLink">Reference: EquivalenceRelationPartition</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := Monoid([</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([1, 2, 2]), Transformation([3, 1, 3])]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">cong := SemigroupCongruence(S,</span>
<span class="GAPprompt">></span> <span class="GAPinput">[Transformation([1, 2, 1]), Transformation([2, 1, 2])]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">EquivalenceRelationCanonicalLookup(cong);</span>
[ 1, 2, 3, 4, 5, 6, 2, 3, 6, 4, 5, 6 ]</pre></div>
<p><a id="X842D567F79648FEB" name="X842D567F79648FEB"></a></p>
<h5>13.3-7 EquivalenceRelationCanonicalPartition</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ EquivalenceRelationCanonicalPartition</code>( <var class="Arg">cong</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A list of lists.</p>
<p>This attribute returns a list of lists of elements of the underlying set of the semigroup congruence <var class="Arg">cong</var>. These lists are precisely the nontrivial equivalence classes of <var class="Arg">cong</var>. The order in which the classes appear is deterministic, and the order of the elements inside each class is also deterministic. Hence, two congruence objects have the same <code class="code">EquivalenceRelationCanonicalPartition</code> if and only if they describe the same relation.</p>
<p>See also <code class="func">EquivalenceRelationPartition</code> (<a href="../../../doc/ref/chap33_mj.html#X877389B683DD8F1A"><span class="RefLink">Reference: EquivalenceRelationPartition</span></a>), a similar attribute which does not have canonical ordering, but which is likely to be faster.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := Semigroup(Transformation([1, 4, 3, 3]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([2, 4, 3, 3]));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">cong := SemigroupCongruence(S, [Transformation([1, 4, 3, 3]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([1, 3, 3, 3])]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">EquivalenceRelationCanonicalPartition(cong);</span>
[ [ Transformation( [ 1, 4, 3, 3 ] ),
Transformation( [ 1, 3, 3, 3 ] ) ],
[ Transformation( [ 4, 3, 3, 3 ] ),
Transformation( [ 3, 3, 3, 3 ] ) ] ]
</pre></div>
<p><a id="X85400841879E41A5" name="X85400841879E41A5"></a></p>
<h5>13.3-8 OnLeftCongruenceClasses</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OnLeftCongruenceClasses</code>( <var class="Arg">class</var>, <var class="Arg">elm</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A left congruence class.</p>
<p>If <var class="Arg">class</var> is an equivalence class of the left semigroup congruence <code class="code">cong</code> on the semigroup <code class="code">S</code>, and <var class="Arg">elm</var> is an element of <code class="code">S</code>, then this operation returns the equivalence class of <code class="code">cong</code> containing the element <code class="code"><var class="Arg">elm</var> * x</code>, where <code class="code">x</code> is any element of <var class="Arg">class</var>. The result is well-defined by the definition of a left congruence.</p>
<p>See <code class="func">IsLeftSemigroupCongruence</code> (<a href="chap13_mj.html#X7E909A78830D42A6"><span class="RefLink">13.1-2</span></a>) and <code class="func">IsLeftCongruenceClass</code> (<a href="chap13_mj.html#X7C803E8C84E81A0B"><span class="RefLink">13.3-2</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := Semigroup([</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([2, 1, 1, 2, 1]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([3, 4, 3, 4, 4]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([3, 4, 3, 4, 3]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([4, 3, 3, 4, 4])]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">pair1 := [Transformation([3, 4, 3, 4, 3]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([1, 2, 1, 2, 1])];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">pair2 := [Transformation([4, 3, 4, 3, 4]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([3, 4, 3, 4, 3])];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">cong := LeftSemigroupCongruence(S, [pair1, pair2]);</span>
<left semigroup congruence over <transformation semigroup of degree 5
with 4 generators> with 2 generating pairs>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := Transformation([3, 4, 3, 4, 3]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">class := EquivalenceClassOfElement(cong, x);</span>
<left congruence class of Transformation( [ 3, 4, 3, 4, 3 ] )>
<span class="GAPprompt">gap></span> <span class="GAPinput">elm := Transformation([1, 2, 2, 1, 2]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">OnLeftCongruenceClasses(class, elm);</span>
<left congruence class of Transformation( [ 3, 4, 4, 3, 4 ] )>
</pre></div>
<p><a id="X7D66F8607B4F0D8F" name="X7D66F8607B4F0D8F"></a></p>
<h5>13.3-9 OnRightCongruenceClasses</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OnRightCongruenceClasses</code>( <var class="Arg">class</var>, <var class="Arg">elm</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A right congruence class.</p>
<p>If <var class="Arg">class</var> is an equivalence class of the right semigroup congruence <code class="code">cong</code> on the semigroup <code class="code">S</code>, and <var class="Arg">elm</var> is an element of <code class="code">S</code>, then this operation returns the equivalence class of <code class="code">cong</code> containing the element <code class="code">x * <var class="Arg">elm</var></code>, where <code class="code">x</code> is any element of <var class="Arg">class</var>. The result is well-defined by the definition of a right congruence.</p>
<p>See <code class="func">IsRightSemigroupCongruence</code> (<a href="chap13_mj.html#X839EEA797B1CCB67"><span class="RefLink">13.1-3</span></a>) and <code class="func">IsRightCongruenceClass</code> (<a href="chap13_mj.html#X7D2F11C28470BC5A"><span class="RefLink">13.3-3</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := Semigroup([</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([2, 1, 1, 2, 1]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([3, 4, 3, 4, 4]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([3, 4, 3, 4, 3]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([4, 3, 3, 4, 4])]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">pair1 := [Transformation([3, 4, 3, 4, 3]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([1, 2, 1, 2, 1])];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">pair2 := [Transformation([4, 3, 4, 3, 4]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([3, 4, 3, 4, 3])];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">cong := RightSemigroupCongruence(S, [pair1, pair2]);</span>
<right semigroup congruence over <transformation semigroup of
degree 5 with 4 generators> with 2 generating pairs>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := Transformation([3, 4, 3, 4, 3]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">class := EquivalenceClassOfElement(cong, x);</span>
<right congruence class of Transformation( [ 3, 4, 3, 4, 3 ] )>
<span class="GAPprompt">gap></span> <span class="GAPinput">elm := Transformation([1, 2, 2, 1, 2]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">OnRightCongruenceClasses(class, elm);</span>
<right congruence class of Transformation( [ 2, 1, 2, 1, 2 ] )>
</pre></div>
<p><a id="X806DEBC07E6D8FCA" name="X806DEBC07E6D8FCA"></a></p>
<h4>13.4 <span class="Heading">
Finding the congruences of a semigroup
</span></h4>
<p><a id="X7E8D5BA27CB5A4DA" name="X7E8D5BA27CB5A4DA"></a></p>
<h5>13.4-1 CongruencesOfSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CongruencesOfSemigroup</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ LeftCongruencesOfSemigroup</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RightCongruencesOfSemigroup</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CongruencesOfSemigroup</code>( <var class="Arg">S</var>, <var class="Arg">restriction</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ LeftCongruencesOfSemigroup</code>( <var class="Arg">S</var>, <var class="Arg">restriction</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RightCongruencesOfSemigroup</code>( <var class="Arg">S</var>, <var class="Arg">restriction</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: The congruences of a semigroup.</p>
<p>This attribute gives a list of the left, right, or 2-sided congruences of the semigroup <var class="Arg">S</var>.</p>
<p>If <var class="Arg">restriction</var> is specified and is a collection of elements from <var class="Arg">S</var>, then the result will only include congruences generated by pairs of elements from <var class="Arg">restriction</var>. Otherwise, all congruences will be calculated.</p>
<p>See also <code class="func">LatticeOfCongruences</code> (<a href="chap13_mj.html#X86C9C5BA7FE93F4C"><span class="RefLink">13.4-5</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := ReesZeroMatrixSemigroup(SymmetricGroup(3),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [[(), (1, 3, 2)], [(1, 2), 0]]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">congs := CongruencesOfSemigroup(S);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Length(congs);</span>
4
<span class="GAPprompt">gap></span> <span class="GAPinput">Set(congs, NrEquivalenceClasses);</span>
[ 1, 5, 9, 25 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">pos := Position(congs, UniversalSemigroupCongruence(S));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">congs[pos];</span>
<universal semigroup congruence over
<Rees 0-matrix semigroup 2x2 over Sym( [ 1 .. 3 ] )>></pre></div>
<p><a id="X7838738987B2DB41" name="X7838738987B2DB41"></a></p>
<h5>13.4-2 MinimalCongruencesOfSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MinimalCongruencesOfSemigroup</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MinimalLeftCongruencesOfSemigroup</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MinimalRightCongruencesOfSemigroup</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MinimalCongruencesOfSemigroup</code>( <var class="Arg">S</var>, <var class="Arg">restriction</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MinimalLeftCongruencesOfSemigroup</code>( <var class="Arg">S</var>, <var class="Arg">restriction</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MinimalRightCongruencesOfSemigroup</code>( <var class="Arg">S</var>, <var class="Arg">restriction</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: The congruences of a semigroup.</p>
<p>If <var class="Arg">S</var> is a semigroup, then the attribute <code class="code">MinimalCongruencesOfSemigroup</code> gives a list of all the congruences on <var class="Arg">S</var> which are <em>minimal</em>. A congruence is minimal iff it is non-trivial and contains no other congruences as subrelations (apart from the trivial congruence).</p>
<p><code class="code">MinimalLeftCongruencesOfSemigroup</code> and <code class="code">MinimalRightCongruencesOfSemigroup</code> do the same thing, but for left congruences and right congruences respectively. Note that any congruence is also a left congruence, but that a minimal congruence may not be a minimal left congruence.</p>
<p>If <var class="Arg">restriction</var> is specified and is a collection of elements from <var class="Arg">S</var>, then the result will only include congruences generated by pairs of elements from <var class="Arg">restriction</var>. Otherwise, all congruences will be calculated.</p>
<p>See also <code class="func">CongruencesOfSemigroup</code> (<a href="chap13_mj.html#X7E8D5BA27CB5A4DA"><span class="RefLink">13.4-1</span></a>) and <code class="func">PrincipalCongruencesOfSemigroup</code> (<a href="chap13_mj.html#X7986F3597F9DF7AF"><span class="RefLink">13.4-3</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := Semigroup(Transformation([1, 3, 2]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([3, 1, 3]));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">min := MinimalCongruencesOfSemigroup(S);</span>
[ <2-sided semigroup congruence over <transformation semigroup
of size 13, degree 3 with 2 generators> with 1 generating pairs>
]
<span class="GAPprompt">gap></span> <span class="GAPinput">minl := MinimalLeftCongruencesOfSemigroup(S);</span>
[ <left semigroup congruence over <transformation semigroup
of size 13, degree 3 with 2 generators> with 1 generating pairs>,
<left semigroup congruence over <transformation semigroup
of size 13, degree 3 with 2 generators> with 1 generating pairs>,
<left semigroup congruence over <transformation semigroup
of size 13, degree 3 with 2 generators> with 1 generating pairs>
]
</pre></div>
<p><a id="X7986F3597F9DF7AF" name="X7986F3597F9DF7AF"></a></p>
<h5>13.4-3 PrincipalCongruencesOfSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PrincipalCongruencesOfSemigroup</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PrincipalLeftCongruencesOfSemigroup</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PrincipalRightCongruencesOfSemigroup</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PrincipalCongruencesOfSemigroup</code>( <var class="Arg">S</var>, <var class="Arg">restriction</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PrincipalLeftCongruencesOfSemigroup</code>( <var class="Arg">S</var>, <var class="Arg">restriction</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PrincipalRightCongruencesOfSemigroup</code>( <var class="Arg">S</var>, <var class="Arg">restriction</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A list.</p>
<p>If <var class="Arg">S</var> is a semigroup, then the attribute <code class="code">PrincipalCongruencesOfSemigroup</code> gives a list of all the congruences on <var class="Arg">S</var> which are <em>principal</em>. A congruence is principal if and only if it is non-trivial and can be defined by a single generating pair.</p>
<p><code class="code">PrincipalLeftCongruencesOfSemigroup</code> and <code class="code">PrincipalRightCongruencesOfSemigroup</code> do the same thing, but for left congruences and right congruences respectively. Note that any congruence is a left congruence and a right congruence, but that a principal congruence may not be a principal left congruence or a principal right congruence.</p>
<p>If <var class="Arg">restriction</var> is specified and is a collection of elements from <var class="Arg">S</var>, then the result will only include congruences generated by pairs of elements from <var class="Arg">restriction</var>. Otherwise, all congruences will be calculated.</p>
<p>See also <code class="func">CongruencesOfSemigroup</code> (<a href="chap13_mj.html#X7E8D5BA27CB5A4DA"><span class="RefLink">13.4-1</span></a>) and <code class="func">MinimalCongruencesOfSemigroup</code> (<a href="chap13_mj.html#X7838738987B2DB41"><span class="RefLink">13.4-2</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := Semigroup(Transformation([1, 3, 2]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([3, 1, 3]));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">congs := PrincipalCongruencesOfSemigroup(S);</span>
[ <universal semigroup congruence over <transformation semigroup
of size 13, degree 3 with 2 generators>>,
<2-sided semigroup congruence over <transformation semigroup
of size 13, degree 3 with 2 generators> with 1 generating pairs>,
<2-sided semigroup congruence over <transformation semigroup
of size 13, degree 3 with 2 generators> with 1 generating pairs>,
<2-sided semigroup congruence over <transformation semigroup
of size 13, degree 3 with 2 generators> with 1 generating pairs>,
<2-sided semigroup congruence over <transformation semigroup
of size 13, degree 3 with 2 generators> with 1 generating pairs>
]
</pre></div>
<p><a id="X8195D6F47EE52806" name="X8195D6F47EE52806"></a></p>
<h5>13.4-4 IsCongruencePoset</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsCongruencePoset</code>( <var class="Arg">poset</var> )</td><td class="tdright">( category )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsCayleyDigraphOfCongruences</code>( <var class="Arg">poset</var> )</td><td class="tdright">( category )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>
<p>This category contains all congruence posets. A <em>congruence poset</em> is a partially ordered set of congruences over a specific semigroup, where the ordering is defined by containment according to <code class="func">IsSubrelation</code> (<a href="chap13_mj.html#X85075F1D878512F | | |
