Login
Login

semigroup with three elements

In abstract algebra, a semigroup with three elements is an object consisting of three elements and an associative operation defined on them. The basic example would be the three integers 0, 1, and −1, together with the operation of multiplication. Multiplication of integers is associative, and the product of any two of these three integers is again one of these three integers.

There are 18 inequivalent ways to define an associative operation on three elements: while there are, altogether, a total of 39 = 19683 different binary operations that can be defined, only 113 of these are associative, and many of these are isomorphic or antiisomorphic so that there are essentially only 18 possibilities.Andreas Distler, [http://bcc2009.mcs.st-and.ac.uk/Theses/andreasDthesis.pdf Classification and enumeration of finite semigroups] {{webarchive|url=https://web.archive.org/web/20150402121217/http://bcc2009.mcs.st-and.ac.uk/Theses/andreasDthesis.pdf |date=2015-04-02 }}, PhD thesis, University of St. Andrews{{cite journal|last=Friðrik Diego|author2=Kristín Halla Jónsdóttir |title=Associative Operations on a Three-Element Set|journal=The Montana Mathematics Enthusiast|date=July 2008|volume=5|issue=2 & 3|pages=257–268|doi=10.54870/1551-3440.1106 |s2cid=118704099 |url=http://www.math.umt.edu/tmme/vol5no2and3/TMME_vol5nos2and3_a8_pp.257_268.pdf|accessdate=6 February 2014}}

One of these is C3, the cyclic group with three elements. The others all have a semigroup with two elements as subsemigroups. In the example above, the set {−1,0,1} under multiplication contains both {0,1} and {−1,1} as subsemigroups (the latter is a subgroup, C2).

Six of these are bands, meaning that all three elements are idempotent, so that the product of any element with itself is itself again. Two of these bands are commutative, therefore semilattices (one of them is the three-element totally ordered set, and the other is a three-element semilattice that is not a lattice). The other four come in anti-isomorphic pairs.

One of these non-commutative bands results from adjoining an identity element to LO2, the left zero semigroup with two elements (or, dually, to RO2, the right zero semigroup). It is sometimes called the flip-flop monoid, referring to flip-flop circuits used in electronics: the three elements can be described as "set", "reset", and "do nothing". This semigroup occurs in the Krohn–Rhodes decomposition of finite semigroups."This innocuous three-element semigroup plays an important role in what follows..." – [https://books.google.com/books?id=0ukzw5VszNwC Applications of Automata Theory and Algebra] by John L. Rhodes. The irreducible elements in this decomposition are the finite simple groups plus this three-element semigroup, and its subsemigroups.

There are two cyclic semigroups, one described by the equation x4 = x3, which has O2, the null semigroup with two elements, as a subsemigroup. The other is described by x4 = x2 and has C2, the group with two elements, as a subgroup. (The equation x4 = x describes C3, the group with three elements, already mentioned.)

There are seven other non-cyclic non-band commutative semigroups, including the initial example of {−1, 0, 1}, and O3, the null semigroup with three elements. There are also two other anti-isomorphic pairs of non-commutative non-band semigroups.

border="1" width="85%" style="margin:1em auto;"

|+List of semigroups with three elements (up to isomorphism)

|+with Cayley tables for the semigroup operation

align="center" colspan="2"|

1. Cyclic group (C3)

{| class="wikitable" border="1" style="background:#99FF99"

! x 

! y 

! z 

 x 

|  x 

|  y 

|  z 

 y 

|  y 

|  z 

|  x 

 z 

|  z 

|  x 

|  y 

|-

|align="center" colspan="2"|

2. Monogenic semigroup (index 2, period 2)

class="wikitable" border="1" style="background:#87CEEB"
! x 

! y 

! z 

 x 

|  y 

|  z 

|  y 

 y 

|  z 

|  y 

|  z 

 z 

|  y 

|  z 

|  y 

Subsemigroup: {y,z} ≈ C2

|-

|align="center" colspan="2"|

3. Aperiodic monogenic semigroup (index 3)

class="wikitable" border="1" style="background:#3FFFFF"
! x 

! y 

! z 

 x 

|  y 

|  z 

|  z 

 y 

|  z 

|  z 

|  z 

 z 

|  z 

|  z 

|  z 

Subsemigroup: {y,z} ≈ O2

|-

|align="center" colspan="2"|

4. Commutative monoid ({−1,0,1} under multiplication)

class="wikitable" border="1" style="background:#BBBBFF"
! x 

! y 

! z 

 x 

|  z 

|  y 

|  x 

 y 

|  y 

|  y 

|  y 

 z 

|  x 

|  y 

|  z 

Subsemigroups: {x,z} ≈ C2. {y,z} ≈ CH2

|-

|align="center" colspan="2"|

5. Commutative monoid

class="wikitable" border="1" style="background:#BBBBFF"
! x 

! y 

! z 

 x 

|  z 

|  x 

|  x 

 y 

|  x 

|  y 

|  z 

 z 

|  x 

|  z 

|  z 

Subsemigroups: {x,z} ≈ C2. {y,z} ≈ CH2

|-

|align="center" colspan="2"|

6. Commutative semigroup

class="wikitable" border="1" style="background:#BB77BB"
! x 

! y 

! z 

 x 

|  z 

|  x 

|  x 

 y 

|  x 

|  z 

|  z 

 z 

|  x 

|  z 

|  z 

Subsemigroups: {x,z} ≈ C2. {y,z} ≈ O2

|-

|align="center" colspan="2"|

7. Null semigroup (O3)

class="wikitable" border="1" style="background:#777777"
! x 

! y 

! z 

 x 

|  z 

|  z 

|  z 

 y 

|  z 

|  z 

|  z 

 z 

|  z 

|  z 

|  z 

Subsemigroups: {x,z} ≈ {y,z} ≈ O2

|-

|align="center" colspan="2"|

8. Commutative aperiodic semigroup

class="wikitable" border="1" style="background:#BB7777"
! x 

! y 

! z 

 x 

|  z 

|  z 

|  z 

 y 

|  z 

|  y 

|  z 

 z 

|  z 

|  z 

|  z 

Subsemigroups: {x,z} ≈ O2. {y,z} ≈ CH2

|-

|align="center" colspan="2"|

9. Commutative aperiodic semigroup

class="wikitable" border="1" style="background:#BB7777"
! x 

! y 

! z 

 x 

|  z 

|  y 

|  z 

 y 

|  y 

|  y 

|  y 

 z 

|  z 

|  y 

|  z 

Subsemigroups: {x,z} ≈ O2. {y,z} ≈ CH2

|-

|align="center" colspan="2"|

10. Commutative aperiodic monoid

class="wikitable" border="1" style="background:#9999FF"
! x 

! y 

! z 

 x 

|  z 

|  x 

|  z 

 y 

|  x 

|  y 

|  z 

 z 

|  z 

|  z 

|  z 

Subsemigroups: {x,z} ≈ O2. {y,z} ≈ CH2

|-

|align="center"|

11A. aperiodic semigroup

class="wikitable" border="1" style="background:#FF33BB"
! x 

! y 

! z 

 x 

|  z 

|  z 

|  z 

 y 

|  y 

|  y 

|  y 

 z 

|  z 

|  z 

|  z 

Subsemigroups: {x,z} ≈ O2, {y,z} ≈ LO2

|align="center"|

11B. its opposite

class="wikitable" border="1" style="background:#BB33FF"
! x 

! y 

! z 

 x 

|  z 

|  y 

|  z 

 y 

|  z 

|  y 

|  z 

 z 

|  z 

|  y 

|  z 

|-

|align="center"|

12A. aperiodic semigroup

class="wikitable" border="1" style="background:#FF33BB"
! x 

! y 

! z 

 x 

|  z 

|  z 

|  z 

 y 

|  x 

|  y 

|  z 

 z 

|  z 

|  z 

|  z 

Subsemigroups: {x,z} ≈ O2, {y,z} ≈ CH2

|align="center"|

12B. its opposite

class="wikitable" border="1" style="background:#BB33FF"
! x 

! y 

! z 

 x 

|  z 

|  x 

|  z 

 y 

|  z 

|  y 

|  z 

 z 

|  z 

|  z 

|  z 

|-

|align="center" colspan="2"|

13. Semilattice (chain)

class="wikitable" border="1" style="background:#FFBBFF"
! x 

! y 

! z 

 x 

|  x 

|  y 

|  z 

 y 

|  y 

|  y 

|  z 

 z 

|  z 

|  z 

|  z 

Subsemigroups: {x,y} ≈ {x,z} ≈ {y,z} ≈ CH2

|-

|align="center" colspan="2"|

14. Semilattice

class="wikitable" border="1" style="background:#FFBBFF"
! x 

! y 

! z 

 x 

|  x 

|  z 

|  z 

 y 

|  z 

|  y 

|  z 

 z 

|  z 

|  z 

|  z 

Subsemigroups: {x,z} ≈ {y,z} ≈ CH2

|-

|align="center"|

15A. idempotent semigroup

class="wikitable" border="1" style="background:#FF7777"
! x 

! y 

! z 

 x 

|  x 

|  x 

|  x 

 y 

|  y 

|  y 

|  y 

 z 

|  x 

|  x 

|  z 

Subsemigroups: {x,y} ≈ LO2, {x,z} ≈ CH2

|align="center"|

15B. its opposite

class="wikitable" border="1" style="background:#7777FF"
! x 

! y 

! z 

 x 

|  x 

|  y 

|  x 

 y 

|  x 

|  y 

|  x 

 z 

|  x 

|  y 

|  z 

|-

|align="center"|

16A. idempotent semigroup

class="wikitable" border="1" style="background:#FF7777"
! x 

! y 

! z 

 x 

|  x 

|  x 

|  z 

 y 

|  y 

|  y 

|  z 

 z 

|  z 

|  z 

|  z 

Subsemigroups: {x,y} ≈ LO2, {x,z} ≈ {y,z} ≈ CH2

|align="center"|

16B. its opposite

class="wikitable" border="1" style="background:#7777FF"
! x 

! y 

! z 

 x 

|  x 

|  y 

|  z 

 y 

|  x 

|  y 

|  z 

 z 

|  z 

|  z 

|  z 

|-

|align="center"|

17A. left zero semigroup (LO3)

class="wikitable" border="1" style="background:#BB3377"
! x 

! y 

! z 

 x 

|  x 

|  x 

|  x 

 y 

|  y 

|  y 

|  y 

 z 

|  z 

|  z 

|  z 

Subsemigroups: {x,y} ≈ {x,z} ≈ {y,z} ≈ LO2

|align="center"|

17B. its opposite (RO3)

class="wikitable" border="1" style="background:#7733BB"
! x 

! y 

! z 

 x 

|  x 

|  y 

|  z 

 y 

|  x 

|  y 

|  z 

 z 

|  x 

|  y 

|  z 

|-

|align="center"|

18A. idempotent semigroup (left flip-flop monoid)

class="wikitable" border="1" style="background:#FFBB77"
! x 

! y 

! z 

 x 

|  x 

|  x 

|  x 

 y 

|  y 

|  y 

|  y 

 z 

|  x 

|  y 

|  z 

Subsemigroups: {x,y} ≈ LO2, {x,z} ≈ {y,z} ≈ CH2

|align="center"|

18B. its opposite (right flip-flop monoid)

class="wikitable" border="1" style="background:#77BBFF"
! x 

! y 

! z 

 x 

|  x 

|  y 

|  x 

 y 

|  x 

|  y 

|  y 

 z 

|  x 

|  y 

|  z 

|-

|align="center" colspan="2"|

Index of two element subsemigroups: C2: cyclic group, O2: null semigroup, CH2: semilattice (chain), LO2/RO2: left/right zero semigroup.

|}

See also

References

{{Reflist}}

Category:Algebraic structures

Category:Semigroup theory