| Quellcodebibliothek Statistik Leitseite products/Sources/formale Sprachen/GAP/pkg/semigroups/doc/ (Algebra von RWTH Aachen Version 4.15.1©) Datei vom 29.7.2025 mit Größe 164 kB |
|
Quelle chap13.htmlSprache: 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> <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.html">Top</a> <a <div class="chlinkprevnexttop"> <a href="chap0.html">[Top of Book]</a> <a href="chap0.html#con <p id="mathjaxlink" class="pcenter"><a href="chap13_mj.html">[MathJax on]</a></p> <p><a id="X82BD951079E3C349" name="X82BD951079E3C349"></a></p> <div class="ChapSects"><a href="chap13.html#X82BD951079E3C349">13 <span class="Heading">Co <div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap13.html#X </span> <div class="ContSSBlock"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X78E34B737F0E009F"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X7E909A78830D42A6"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X839EEA797B1CCB67"> </div></div> <div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap13.html#X Creating congruences </span></a> </span> <div class="ContSSBlock"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X85CE56AC84FA5D33"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X8757DB087BE7E55A"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X7D01176B788FEE60"> </div></div> <div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap13.html#X Congruence classes </span></a> </span> <div class="ContSSBlock"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X7B1F67A97E23E6A4"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X7C803E8C84E81A0B"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X7D2F11C28470BC5A"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X86C05F31797C1D6D"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X7DA4BABC7891A7F1"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X8022B7898553F624"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X842D567F79648FEB"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X85400841879E41A5"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X7D66F8607B4F0D8F"> </div></div> <div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap13.html#X Finding the congruences of a semigroup </span></a> </span> <div class="ContSSBlock"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X7E8D5BA27CB5A4DA"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X7838738987B2DB41"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X7986F3597F9DF7AF"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X8195D6F47EE52806"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X86C9C5BA7FE93F4C"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X784CFDE37A0B4F84"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X83ACF2C0789F621B"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X7B2E2CEE8626FBC3"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X830F42B582A2FAA0"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X78A91138818A4FAE"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X87CF25A178B7F1AF"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X7ECE04727B6A58A3"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X780E2B3F8509CE32"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X7AE16F237E862934"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X807A5FCC87661FA4"> </div></div> <div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap13.html#X Comparing congruences </span></a> </span> <div class="ContSSBlock"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X85075F1D878512F5"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X83878AED7A8E75BE"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X7952A5A5789C6F60"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X8262D5207DBF3C5B"> </div></div> <div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap13.html#X </span> <div class="ContSSBlock"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X7F4AFD7F7E163022"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X87A475E4847D3C96"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X79E4CF7B79B25AE3"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X7E9AB940868FCC9D"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X7B19CACF7A37ADBC"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X7DB7E32E865AD95D"> </div></div> <div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap13.html#X Congruences on inverse semigroups </span></a> </span> <div class="ContSSBlock"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X8546E48E85A2A7E8"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X7A588B737CEEB104"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X87916D4E854F1F6B"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X7D521AFF7876CBC7"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X80972A5B82D88F89"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X8049A0E780A7A8D9"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X857495647F9A9579"> </div></div> <div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap13.html#X Congruences on graph inverse semigroups </span></a> </span> <div class="ContSSBlock"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X7AEB7DA27E76145B"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X7F30D10F7BEEEBB9"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X817F4FC27E9BACD8"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X858AE13379B5C380"> </div></div> <div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap13.html#X </span> <div class="ContSSBlock"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X7BC02E08840E0AF4"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X7E15F66A8029C64A"> </div></div> <div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap13.html#X </span> <div class="ContSSBlock"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X8751EF557A81A2B1"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X8646253C86AFFA29"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X7B99C6A47F3D375F"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap13.html#X7A9B483B7B4E0E27"> </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 <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">IteratorOfLeftCongruen </li> <li><p>Wang pairs -- only for graph inverse semigroup</p> </li> </ul> <p>The operation <code class="func">SemigroupCongruence</code> (<a href="chap13.html#X85CE56 <p>If a congruence is specified by generating pairs on a simple, 0-simple, or inverse semigroup, <p>We can also create left congruences and right congruences, using the <code class="func">LeftS <p>Please note that congruence objects made in <strong class="pkg">GAP</strong> before loading th <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">‣ Is <p>A semigroup congruence <code class="code">cong</code> is an equivalence relation on a semigrou <p>That is, if <span class="SimpleMath">(a,b)</span> is a pair in <code class="code">cong</code>, and < <p>The simplest way of creating a congruence in <strong class="pkg">Semigroups</strong> is by a set <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])]);;</sp <span class="GAPprompt">gap></span> <span class="GAPinput">pair1 := [Transformation([3, 4, 3, 4 <span class="GAPprompt">></span> <span class="GAPinput"> Transformation([1, 2, 1, 2, 1])];;</spa <span class="GAPprompt">gap></span> <span class="GAPinput">pair2 := [Transformation([4, 3, 4, 3 <span class="GAPprompt">></span> <span class="GAPinput"> Transformation([3, 4, 3, 4, 3])];;</spa <span class="GAPprompt">gap></span> <span class="GAPinput">cong := SemigroupCongruence(S, [pa <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);</sp 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">‣ Is <p>A left semigroup congruence <code class="code">cong</code> is an equivalence relation on a semi <p>That is, if <span class="SimpleMath">(a,b)</span> is a pair in <code class="code">cong</code>, and < <p>The simplest way of creating a left congruence in <strong class="pkg">Semigroups</strong> is by <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])]);;</sp <span class="GAPprompt">gap></span> <span class="GAPinput">pair1 := [Transformation([3, 4, 3, 4 <span class="GAPprompt">></span> <span class="GAPinput"> Transformation([1, 2, 1, 2, 1])];;</spa <span class="GAPprompt">gap></span> <span class="GAPinput">pair2 := [Transformation([4, 3, 4, 3 <span class="GAPprompt">></span> <span class="GAPinput"> Transformation([3, 4, 3, 4, 3])];;</spa <span class="GAPprompt">gap></span> <span class="GAPinput">cong := LeftSemigroupCongruence(S <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) 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">‣ Is <p>A right semigroup congruence <code class="code">cong</code> is an equivalence relation on a sem <p>That is, if <span class="SimpleMath">(a,b)</span> is a pair in <code class="code">cong</code>, and < <p>The simplest way of creating a right congruence in <strong class="pkg">Semigroups</strong> is b <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])]);;</sp <span class="GAPprompt">gap></span> <span class="GAPinput">pair1 := [Transformation([3, 4, 3, 4 <span class="GAPprompt">></span> <span class="GAPinput"> Transformation([1, 2, 1, 2, 1])];;</spa <span class="GAPprompt">gap></span> <span class="GAPinput">pair2 := [Transformation([4, 3, 4, 3 <span class="GAPprompt">></span> <span class="GAPinput"> Transformation([3, 4, 3, 4, 3])];;</spa <span class="GAPprompt">gap></span> <span class="GAPinput">RightSemigroupCongruence(S, [pai <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 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">‣ Se <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</v <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])]);;</sp <span class="GAPprompt">gap></span> <span class="GAPinput">pair1 := [Transformation([3, 4, 3, 4 <span class="GAPprompt">></span> <span class="GAPinput"> Transformation([1, 2, 1, 2, 1])];;</spa <span class="GAPprompt">gap></span> <span class="GAPinput">pair2 := [Transformation([4, 3, 4, 3 <span class="GAPprompt">></span> <span class="GAPinput"> Transformation([3, 4, 3, 4, 3])];;</spa <span class="GAPprompt">gap></span> <span class="GAPinput">SemigroupCongruence(S, [pair1, pa <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, pai <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">‣ Le <p>Returns: A left semigroup congruence.</p> <p>This function returns a left semigroup congruence over the semigroup <var class="Arg">S</var>.< <p>If <var class="Arg">pairs</var> is a list of lists of size 2 with elements from <var class="Arg">S</v <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])]);;</sp <span class="GAPprompt">gap></span> <span class="GAPinput">pair1 := [Transformation([3, 4, 3, 4 <span class="GAPprompt">></span> <span class="GAPinput"> Transformation([1, 2, 1, 2, 1])];;</spa <span class="GAPprompt">gap></span> <span class="GAPinput">pair2 := [Transformation([4, 3, 4, 3 <span class="GAPprompt">></span> <span class="GAPinput"> Transformation([3, 4, 3, 4, 3])];;</spa <span class="GAPprompt">gap></span> <span class="GAPinput">LeftSemigroupCongruence(S, [pair <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 <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">‣ Ri <p>Returns: A right semigroup congruence.</p> <p>This function returns a right semigroup congruence over the semigroup <var class="Arg">S</var> <p>If <var class="Arg">pairs</var> is a list of lists of size 2 with elements from <var class="Arg">S</v <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])]);;</sp <span class="GAPprompt">gap></span> <span class="GAPinput">pair1 := [Transformation([3, 4, 3, 4 <span class="GAPprompt">></span> <span class="GAPinput"> Transformation([1, 2, 1, 2, 1])];;</spa <span class="GAPprompt">gap></span> <span class="GAPinput">pair2 := [Transformation([4, 3, 4, 3 <span class="GAPprompt">></span> <span class="GAPinput"> Transformation([3, 4, 3, 4, 3])];;</spa <span class="GAPprompt">gap></span> <span class="GAPinput">RightSemigroupCongruence(S, [pai <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, pair <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> lib <ul> <li><p><code class="func">EquivalenceClasses</code> (<a href="../../../doc/ref/chap33_mj.htm </li> <li><p><code class="code">NrEquivalenceClasses</code></p> </li> <li><p><code class="func">EquivalenceClassOfElement</code> (<a href="../../../doc/ref/chap33 </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">‣ Is <p>This category contains any object which is an equivalence class of a semigroup congruence (se <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]), Transforma <span class="GAPprompt">gap></span> <span class="GAPinput">cong := SemigroupCongruence(S, [Tr <span class="GAPprompt">></span> <span class="GAPinput"> Transformation([2, 1, 2])]);;</span> <span class="GAPprompt">gap></span> <span class="GAPinput">class := EquivalenceClassOfElemen <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">‣ Is <p>This category contains any object which is an equivalence class of a left semigroup congruenc <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]), Transforma <span class="GAPprompt">gap></span> <span class="GAPinput">pairs := [Transformation([1, 2, 1]) <span class="GAPprompt">></span> <span class="GAPinput"> Transformation([2, 1, 2])];;</span> <span class="GAPprompt">gap></span> <span class="GAPinput">cong := LeftSemigroupCongruence(S <span class="GAPprompt">gap></span> <span class="GAPinput">class := EquivalenceClassOfElemen <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);</s 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">‣ Is <p>This category contains any object which is an equivalence class of a right semigroup congruen <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]), Transforma <span class="GAPprompt">gap></span> <span class="GAPinput">pairs := [Transformation([1, 2, 1]) <span class="GAPprompt">></span> <span class="GAPinput"> Transformation([2, 1, 2])];;</span> <span class="GAPprompt">gap></span> <span class="GAPinput">cong := RightSemigroupCongruence( <span class="GAPprompt">gap></span> <span class="GAPinput">class := EquivalenceClassOfElemen <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);</ 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">‣ No <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 al <div class="example"><pre> <span class="GAPprompt">gap></span> <span class="GAPinput">S := Monoid([Transformation([1, 2, <span class="GAPprompt">></span> <span class="GAPinput"> Transformation([3, 1, 3])]);;</span> <span class="GAPprompt">gap></span> <span class="GAPinput">cong := SemigroupCongruence(S, [Tr <span class="GAPprompt">></span> <span class="GAPinput"> Transformation([2, 1, 2])]);;</span> <span class="GAPprompt">gap></span> <span class="GAPinput">classes := NonTrivialEquivalenceC <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( <span class="GAPprompt">></span> <span class="GAPinput"> Transformation([2, 1, 2])]);;</span> <span class="GAPprompt">gap></span> <span class="GAPinput">classes := NonTrivialEquivalenceC <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">‣ Eq <p>Returns: A list.</p> <p>This attribute describes the equivalence relation <var class="Arg">equiv</var>, defined over <p>Each position in the list corresponds to an element of the semigroup (in a consistent canonica <p>Note that the order in which numbers appear in the list is non-deterministic, and two equivale <p>See also <code class="func">EquivalenceRelationPartition</code> (<a href="../../../doc/re <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]), Transforma <span class="GAPprompt">gap></span> <span class="GAPinput">cong := SemigroupCongruence(S,</sp <span class="GAPprompt">></span> <span class="GAPinput">[Transformation([1, 2, 1]), Transform <span class="GAPprompt">gap></span> <span class="GAPinput">lookup := EquivalenceRelationLook <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">‣ Eq <p>Returns: A list.</p> <p>This attribute describes the equivalence relation <var class="Arg">equiv</var>, defined over <p>Each position in the list corresponds to an element of the semigroup (in a consistent canonica <p>Two elements of the semigroup on which the equivalence relation is defined are related in the e <p>See also <code class="func">EquivalenceRelationLookup</code> (<a href="chap13.html#X7DA4B <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]), Transforma <span class="GAPprompt">gap></span> <span class="GAPinput">cong := SemigroupCongruence(S,</sp <span class="GAPprompt">></span> <span class="GAPinput">[Transformation([1, 2, 1]), Transform <span class="GAPprompt">gap></span> <span class="GAPinput">EquivalenceRelationCanonicalLoo [ 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">‣ Eq <p>Returns: A list of lists.</p> <p>This attribute returns a list of lists of elements of the underlying set of the semigroup congr <p>See also <code class="func">EquivalenceRelationPartition</code> (<a href="../../../doc/re <div class="example"><pre> <span class="GAPprompt">gap></span> <span class="GAPinput">S := Semigroup(Transformation([1, <span class="GAPprompt">></span> <span class="GAPinput"> Transformation([2, 4, 3, 3]));;</span> <span class="GAPprompt">gap></span> <span class="GAPinput">cong := SemigroupCongruence(S, [Tr <span class="GAPprompt">></span> <span class="GAPinput"> Transformation([1, 3, 3, 3])]);;</span> <span class="GAPprompt">gap></span> <span class="GAPinput">EquivalenceRelationCanonicalPar [ [ 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">‣ On <p>Returns: A left congruence class.</p> <p>If <var class="Arg">class</var> is an equivalence class of the left semigroup congruence <code cl <p>See <code class="func">IsLeftSemigroupCongruence</code> (<a href="chap13.html#X7E909A788 <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])]);;</sp <span class="GAPprompt">gap></span> <span class="GAPinput">pair1 := [Transformation([3, 4, 3, 4 <span class="GAPprompt">></span> <span class="GAPinput"> Transformation([1, 2, 1, 2, 1])];;</spa <span class="GAPprompt">gap></span> <span class="GAPinput">pair2 := [Transformation([4, 3, 4, 3 <span class="GAPprompt">></span> <span class="GAPinput"> Transformation([3, 4, 3, 4, 3])];;</spa <span class="GAPprompt">gap></span> <span class="GAPinput">cong := LeftSemigroupCongruence(S <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 class="GAPprompt">gap></span> <span class="GAPinput">class := EquivalenceClassOfElemen <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 class="GAPprompt">gap></span> <span class="GAPinput">OnLeftCongruenceClasses(class, e <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">‣ On <p>Returns: A right congruence class.</p> <p>If <var class="Arg">class</var> is an equivalence class of the right semigroup congruence <code c <p>See <code class="func">IsRightSemigroupCongruence</code> (<a href="chap13.html#X839EEA79 <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])]);;</sp <span class="GAPprompt">gap></span> <span class="GAPinput">pair1 := [Transformation([3, 4, 3, 4 <span class="GAPprompt">></span> <span class="GAPinput"> Transformation([1, 2, 1, 2, 1])];;</spa <span class="GAPprompt">gap></span> <span class="GAPinput">pair2 := [Transformation([4, 3, 4, 3 <span class="GAPprompt">></span> <span class="GAPinput"> Transformation([3, 4, 3, 4, 3])];;</spa <span class="GAPprompt">gap></span> <span class="GAPinput">cong := RightSemigroupCongruence( <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 class="GAPprompt">gap></span> <span class="GAPinput">class := EquivalenceClassOfElemen <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 class="GAPprompt">gap></span> <span class="GAPinput">OnRightCongruenceClasses(class, <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">‣ Co <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Le <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Ri <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Co <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Le <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Ri <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 cla <p>If <var class="Arg">restriction</var> is specified and is a collection of elements from <var clas <p>See also <code class="func">LatticeOfCongruences</code> (<a href="chap13.html#X86C9C5BA7F <div class="example"><pre> <span class="GAPprompt">gap></span> <span class="GAPinput">S := ReesZeroMatrixSemigroup(Symm <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 class="GAPprompt">gap></span> <span class="GAPinput">Length(congs);</span> 4 <span class="GAPprompt">gap></span> <span class="GAPinput">Set(congs, NrEquivalenceClasses) [ 1, 5, 9, 25 ] <span class="GAPprompt">gap></span> <span class="GAPinput">pos := Position(congs, UniversalSe <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">‣ Mi <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Mi <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Mi <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Mi <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Mi <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Mi |
