Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Semigroup with two elements
open-in-new
<h2 id="determination-of-semigroups-with-two-elements">Determination of semigroups with two elements</h2> <p>Choosing the set <i>A</i> = { 1, 2 } as the underlying set having two elements, sixteen <a href="/facts/Binary_operation/CYtow0bz">binary operations</a> can be defined in <i>A</i>. These operations are shown in the table below. In the table, a <a href="/facts/Matrix_(mathematics)/qa8FI4ko">matrix</a> of the form </p> <table><tbody><tr><td> <i>x</i> </td><td> <i>y</i> </td></tr><tr><td> <i>z</i> </td><td> <i>t</i> </td></tr></tbody></table> <p>indicates a binary operation on <i>A</i> having the following <a href="/facts/Cayley_table/1L05nSE7">Cayley table</a>. </p> <table><tbody><tr><th></th><th> 1 </th><th> 2 </th></tr><tr><td> 1 </td><td> <i>x</i> </td><td> <i>y</i> </td></tr><tr><td> 2 </td><td> <i>z</i> </td><td> <i>t</i> </td></tr></tbody></table> List of binary operations in { 1, 2 }<table><tbody><tr><td><table><tbody><tr><td> 1 </td><td> 1 </td></tr><tr><td> 1 </td><td> 1 </td></tr></tbody></table></td><td><table><tbody><tr><td> 1 </td><td> 1 </td></tr><tr><td> 1 </td><td> 2 </td></tr></tbody></table></td><td><table><tbody><tr><td> 1 </td><td> 1 </td></tr><tr><td> 2 </td><td> 1 </td></tr></tbody></table></td><td><table><tbody><tr><td> 1 </td><td> 1 </td></tr><tr><td> 2 </td><td> 2 </td></tr></tbody></table></td></tr><tr><td> Null semigroup O2 </td><td> ≡ Semigroup ({0,1}, ∧ {\displaystyle \wedge } ) </td><td> 2·(1·2) = 2, (2·1)·2 = 1 </td><td> Left zero semigroup LO2 </td></tr><tr><td><table><tbody><tr><td> 1 </td><td> 2 </td></tr><tr><td> 1 </td><td> 1 </td></tr></tbody></table></td><td><table><tbody><tr><td> 1 </td><td> 2 </td></tr><tr><td> 1 </td><td> 2 </td></tr></tbody></table></td><td><table><tbody><tr><td> 1 </td><td> 2 </td></tr><tr><td> 2 </td><td> 1 </td></tr></tbody></table></td><td><table><tbody><tr><td> 1 </td><td> 2 </td></tr><tr><td> 2 </td><td> 2 </td></tr></tbody></table></td></tr><tr><td> 2·(1·2) = 1, (2·1)·2 = 2 </td><td> Right zero semigroup RO2 </td><td> ≡ Group (Z2, ·2) </td><td> ≡ Semigroup ({0,1}, ∧ {\displaystyle \wedge } )</td></tr><tr><td><table><tbody><tr><td> 2 </td><td> 1 </td></tr><tr><td> 1 </td><td> 1 </td></tr></tbody></table></td><td><table><tbody><tr><td> 2 </td><td> 1 </td></tr><tr><td> 1 </td><td> 2 </td></tr></tbody></table></td><td><table><tbody><tr><td> 2 </td><td> 1 </td></tr><tr><td> 2 </td><td> 1 </td></tr></tbody></table></td><td><table><tbody><tr><td> 2 </td><td> 1 </td></tr><tr><td> 2 </td><td> 2 </td></tr></tbody></table></td></tr><tr><td> 1·(1·2) = 2, (1·1)·2 = 1 </td><td> ≡ Group (Z2, +2) </td><td> 1·(1·1) = 1, (1·1)·1 = 2 </td><td> 1·(2·1) = 1, (1·2)·1 = 2 </td></tr><tr><td><table><tbody><tr><td> 2 </td><td> 2 </td></tr><tr><td> 1 </td><td> 1 </td></tr></tbody></table></td><td><table><tbody><tr><td> 2 </td><td> 2 </td></tr><tr><td> 1 </td><td> 2 </td></tr></tbody></table></td><td><table><tbody><tr><td> 2 </td><td> 2 </td></tr><tr><td> 2 </td><td> 1 </td></tr></tbody></table></td><td><table><tbody><tr><td> 2 </td><td> 2 </td></tr><tr><td> 2 </td><td> 2 </td></tr></tbody></table></td></tr><tr><td> 1·(1·1) = 2, (1·1)·1 = 1 </td><td> 1·(2·1) = 2, (1·2)·1 = 1 </td><td> 1·(1·2) = 2, (1·1)·2 = 1 </td><td> Null semigroup O2 </td></tr></tbody></table> <p>In this table: </p> <ul><li>The semigroup ({0,1}, ∧ {\displaystyle \wedge } ) denotes the two-element semigroup containing the <a href="/facts/Null_semigroup/eyRwHwrM">zero element</a> 0 and the <a href="/facts/Unit_element/GJSBu8Y7">unit element</a> 1. The two binary operations defined by matrices in a green background are associative and pairing either with <i>A</i> creates a semigroup isomorphic to the semigroup ({0,1}, ∧ {\displaystyle \wedge } ). Every element is <a href="/facts/Idempotent/khbSpexv">idempotent</a> in this semigroup, so it is a <a href="/facts/Band_(mathematics)/CdwD3R0Y">band</a>. Furthermore, it is commutative (abelian) and thus a <a href="/facts/Semilattice/kW5po0rp">semilattice</a>. The <a href="/facts/Semilattice/kW5po0rp">order induced</a> is a <a href="/facts/Linear_order/xnTtmuYJ">linear order</a>, and so it is in fact a <a href="/facts/Lattice_(order)/5ak6ufky">lattice</a> and it is also a <a href="/facts/Distributive_lattice/97DFz1cu">distributive</a> and <a href="/facts/Complemented_lattice/KpwmsACp">complemented lattice</a>, i.e. it is actually the <a href="/facts/Two-element_Boolean_algebra/8nIWUpwd">two-element Boolean algebra</a>.</li> <li>The two binary operations defined by matrices in a blue background are associative and pairing either with <i>A</i> creates a semigroup isomorphic to the <a href="/facts/Null_semigroup/eyRwHwrM">null semigroup</a> O2 with two elements.</li> <li>The binary operation defined by the matrix in an orange background is associative and pairing it with <i>A</i> creates a semigroup. This is the <a href="/facts/Null_semigroup/eyRwHwrM">left zero semigroup</a> LO2. It is not commutative.</li> <li>The binary operation defined by the matrix in a purple background is associative and pairing it with <i>A</i> creates a semigroup. This is the <a href="/facts/Null_semigroup/eyRwHwrM">right zero semigroup</a> RO2. It is also not commutative.</li> <li>The two binary operations defined by matrices in a red background are associative and pairing either with <i>A</i> creates a semigroup isomorphic to the <a href="/facts/Group_(mathematics)/IQTYqINt">group</a> (Z2, +2).</li> <li>The remaining eight <a href="/facts/Binary_operation/CYtow0bz">binary operations</a> defined by matrices in a white background are not <a href="/facts/Associative/EQX8lV6r">associative</a> and hence none of them create a semigroup when paired with <i>A</i>.</li></ul> <h2 id="the-two-element-semigroup-01-">The two-element semigroup ({0,1}, ∧)</h2> <p>The <a href="/facts/Cayley_table/1L05nSE7">Cayley table</a> for the semigroup ({0,1}, ∧ {\displaystyle \wedge } ) is given below: </p> <table><tbody><tr><th> ∧ {\displaystyle \wedge } </th><th> 0 </th><th> 1 </th></tr><tr><td> 0 </td><td> 0 </td><td> 0 </td></tr><tr><td> 1 </td><td> 0 </td><td> 1 </td></tr></tbody></table> <p>This is the simplest non-trivial example of a semigroup that is not a group. This semigroup has an identity element, 1, making it a <a href="/facts/Monoid/6AHve7p8">monoid</a>. It is also commutative. It is not a group because the element 0 does not have an inverse, and is not even a cancellative semigroup because we cannot cancel the 0 in the equation 1·0 = 0·0. </p><p>This semigroup arises in various contexts. For instance, if we choose 1 to be the <a href="/facts/Truth_value/SY4e2w8l">truth value</a> "<a href="/facts/Truth/NyQmBtUC">true</a>" and 0 to be the <a href="/facts/Truth_value/SY4e2w8l">truth value</a> "<a href="/facts/False_(logic)/H6v5aztR">false</a>" and the operation to be the <a href="/facts/Logical_connective/VkPhUs6M">logical connective</a> "<a href="/facts/Logical_conjunction/62uyyn1d">and</a>", we obtain this semigroup in <a href="/facts/Logic/8JnpJLtt">logic</a>. It is isomorphic to the monoid {0,1} under multiplication. It is also isomorphic to the semigroup </p> S = { ( 1 0 0 1 ) , ( 1 0 0 0 ) } {\displaystyle S=\left\{{\begin{pmatrix}1&0\\0&1\end{pmatrix}},{\begin{pmatrix}1&0\\0&0\end{pmatrix}}\right\}} <p>under <a href="/facts/Matrix_multiplication/lYDB6Ro2">matrix multiplication</a>. </p> <h2 id="the-two-element-semigroup-z2-2">The two-element semigroup (Z2, +2)</h2> <p>The <a href="/facts/Cayley_table/1L05nSE7">Cayley table</a> for the semigroup (Z2, +2) is given below: </p> <table><tbody><tr><th>+2</th><th> 0 </th><th> 1 </th></tr><tr><td> 0 </td><td> 0 </td><td> 1 </td></tr><tr><td> 1 </td><td> 1 </td><td> 0 </td></tr></tbody></table> <p>This group is isomorphic to the <a href="/facts/Cyclic_group/JL5zfFuL">cyclic group</a> Z2 and the <a href="/facts/Symmetric_group/RUksK5l5">symmetric group</a> S2. </p> <h2 id="semigroups-of-order-3">Semigroups of order 3</h2> <p class="note">Main article: <a href="/facts/Semigroup_with_three_elements/Wk5mRcpr">Semigroup with three elements</a></p> <p>Let <i>A</i> be the three-element set {1, 2, 3}. Altogether, a total of 39 = 19683 different binary operations can be defined on <i>A</i>. 113 of the 19683 binary operations determine 24 nonisomorphic semigroups, or 18 non-equivalent semigroups (with equivalence being isomorphism or anti-isomorphism). <a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a> With the exception of the <a href="/facts/Cyclic_group/JL5zfFuL">group with three elements</a>, each of these has one (or more) of the above two-element semigroups as subsemigroups.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> For example, the set {−1, 0, 1} under multiplication is a semigroup of order 3, and contains both {0, 1} and {−1, 1} as subsemigroups. </p> <h2 id="finite-semigroups-of-higher-orders">Finite semigroups of higher orders</h2> <p>Algorithms and computer programs have been developed for determining nonisomorphic finite semigroups of a given order. These have been applied to determine the nonisomorphic semigroups of small order.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a><a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a><a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> The number of nonisomorphic semigroups with <i>n</i> elements, for <i>n</i> a nonnegative integer, is listed under <a href="/facts/On-Line_Encyclopedia_of_Integer_Sequences/yow6cVsU">OEIS</a>: A027851 in the <a href="/facts/On-Line_Encyclopedia_of_Integer_Sequences/yow6cVsU">On-Line Encyclopedia of Integer Sequences</a>. <a href="/facts/On-Line_Encyclopedia_of_Integer_Sequences/yow6cVsU">OEIS</a>: A001423 lists the number of non-equivalent semigroups, and <a href="/facts/On-Line_Encyclopedia_of_Integer_Sequences/yow6cVsU">OEIS</a>: A023814 the number of associative binary operations, out of a total of <i>n</i><i>n</i>2, determining a semigroup. </p> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Empty_semigroup/UKudol1V">Empty semigroup</a></li> <li><a href="/facts/Trivial_semigroup/33v5jsvX">Trivial semigroup</a> (semigroup with one element)</li> <li><a href="/facts/Semigroup_with_three_elements/Wk5mRcpr">Semigroup with three elements</a></li> <li><a href="/facts/Special_classes_of_semigroups/UPwpNRVX">Special classes of semigroups</a></li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Friðrik Diego; Kristín Halla Jónsdóttir (July 2008). "Associative Operations on a Three-Element Set" (PDF). The Montana Mathematics Enthusiast. 5 (2 & 3): 257–268. doi:10.54870/1551-3440.1106. S2CID 118704099. Retrieved 6 February 2014. <a href="http://www.math.umt.edu/tmme/vol5no2and3/TMME_vol5nos2and3_a8_pp.257_268.pdf" target="_blank">http://www.math.umt.edu/tmme/vol5no2and3/TMME_vol5nos2and3_a8_pp.257_268.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Andreas Distler, Classification and enumeration of finite semigroups Archived 2 April 2015 at the Wayback Machine, PhD thesis, University of St. Andrews <a href="http://bcc2009.mcs.st-and.ac.uk/Theses/andreasDthesis.pdf" target="_blank">http://bcc2009.mcs.st-and.ac.uk/Theses/andreasDthesis.pdf</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Andreas Distler, Classification and enumeration of finite semigroups Archived 2 April 2015 at the Wayback Machine, PhD thesis, University of St. Andrews <a href="http://bcc2009.mcs.st-and.ac.uk/Theses/andreasDthesis.pdf" target="_blank">http://bcc2009.mcs.st-and.ac.uk/Theses/andreasDthesis.pdf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Crvenković, Siniša; Stojmenović, Ivan (1993). "An algorithm for Cayley tables of algebras" (PDF). Zbornik Radova Prirodno-Matematichkog Fakulteta. Serija za Matematiku. Review of Research. Faculty of Science. Mathematics Series. 23 (2): 221–231. MR 1333549. <a href="https://www.emis.de/journals/NSJOM/Papers/23_2/NSJOM_23_2_221_231.pdf" target="_blank">https://www.emis.de/journals/NSJOM/Papers/23_2/NSJOM_23_2_221_231.pdf</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>John A Hildebrant (2001). Handbook of Finite Semigroup Programs. (Preprint).[1] <a href="http://www.math.lsu.edu/~preprint/2001/jah2001a.pdf" target="_blank">http://www.math.lsu.edu/~preprint/2001/jah2001a.pdf</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> </ol>