Semigroup with two elements

In mathematics, a semigroup with two elements is a semigroup for which the cardinality of the underlying set is two. There are exactly five nonisomorphic semigroups having two elements:

O₂, the null semigroup of order two.
LO₂, the left zero semigroup of order two.
RO₂, the right zero semigroup of order two.
({0,1}, ∧) (where "∧" is the logical connective "and"), or equivalently the set {0,1} under multiplication: the only semilattice with two elements and the only non-null semigroup with zero of order two, also a monoid, and ultimately the two-element Boolean algebra; this is also isomorphic to (Z₂, ·₂), the multiplicative group of {0,1} modulo 2.
(Z₂, +₂) (where Z₂ = {0,1} and "+₂" is "addition modulo 2"), or equivalently ({0,1}, ⊕) (where "⊕" is the logical connective "xor"), or equivalently the set {−1,1} under multiplication: the only group of order two.

The semigroups LO₂ and RO₂ are antiisomorphic. O₂, ({0,1}, ∧) and (Z₂, +₂) are commutative, and LO₂ and RO₂ are noncommutative. LO₂, RO₂ and ({0,1}, ∧) are bands.

Determination of semigroups with two elements

Choosing the set A = { 1, 2 } as the underlying set having two elements, sixteen binary operations can be defined in A. These operations are shown in the table below. In the table, a matrix of the form

x	y
z	t

indicates a binary operation on A having the following Cayley table.

	1	2
1	x	y
2	z	t

List of binary operations in { 1, 2 }

1	1
1	1

1	1
1	2

1	1
2	1

1	1
2	2

Null semigroup O₂

≡ Semigroup ({0,1},

\wedge

)

2·(1·2) = 2, (2·1)·2 = 1

Left zero semigroup LO₂

1	2
1	1

1	2
1	2

1	2
2	1

1	2
2	2

2·(1·2) = 1, (2·1)·2 = 2

Right zero semigroup RO₂

≡ Group (Z₂, ·₂)

≡ Semigroup ({0,1},

\wedge

)

2	1
1	1

2	1
1	2

2	1
2	1

2	1
2	2

1·(1·2) = 2, (1·1)·2 = 1

≡ Group (Z₂, +₂)

1·(1·1) = 1, (1·1)·1 = 2

1·(2·1) = 1, (1·2)·1 = 2

2	2
1	1

2	2
1	2

2	2
2	1

2	2
2	2

1·(1·1) = 2, (1·1)·1 = 1

1·(2·1) = 2, (1·2)·1 = 1

1·(1·2) = 2, (1·1)·2 = 1

Null semigroup O₂

In this table:

The semigroup ({0,1}, $\wedge$ ) denotes the two-element semigroup containing the zero element 0 and the unit element 1. The two binary operations defined by matrices in a green background are associative and pairing either with A creates a semigroup isomorphic to the semigroup ({0,1}, $\wedge$ ). Every element is idempotent in this semigroup, so it is a band. Furthermore, it is commutative (abelian) and thus a semilattice. The order induced is a linear order, and so it is in fact a lattice and it is also a distributive and complemented lattice, i.e. it is actually the two-element Boolean algebra.
The two binary operations defined by matrices in a blue background are associative and pairing either with A creates a semigroup isomorphic to the null semigroup O₂ with two elements.
The binary operation defined by the matrix in an orange background is associative and pairing it with A creates a semigroup. This is the left zero semigroup LO₂. It is not commutative.
The binary operation defined by the matrix in a purple background is associative and pairing it with A creates a semigroup. This is the right zero semigroup RO₂. It is also not commutative.
The two binary operations defined by matrices in a red background are associative and pairing either with A creates a semigroup isomorphic to the group (Z₂, +₂).
The remaining eight binary operations defined by matrices in a white background are not associative and hence none of them create a semigroup when paired with A.

The two-element semigroup ({0,1}, ∧)

The Cayley table for the semigroup ({0,1}, $\wedge$ ) is given below:

$\wedge$	0	1
0	0	0
1	0	1

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 monoid. 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.

This semigroup arises in various contexts. For instance, if we choose 1 to be the truth value "true" and 0 to be the truth value "false" and the operation to be the logical connective "and", we obtain this semigroup in logic. It is isomorphic to the monoid {0,1} under multiplication. It is also isomorphic to the semigroup

S=\left\{{\begin{pmatrix}1&0\\0&1\end{pmatrix}},{\begin{pmatrix}1&0\\0&0\end{pmatrix}}\right\}

under matrix multiplication.

The two-element semigroup (Z₂, +₂)

The Cayley table for the semigroup (Z₂, +₂) is given below:

+₂	0	1
0	0	1
1	1	0

This group is isomorphic to the cyclic group Z₂ and the symmetric group S₂.

Semigroups of order 3

Let A be the three-element set {1, 2, 3}. Altogether, a total of 3⁹ = 19683 different binary operations can be defined on A. 113 of the 19683 binary operations determine 24 nonisomorphic semigroups, or 18 non-equivalent semigroups (with equivalence being isomorphism or anti-isomorphism). ^[1] With the exception of the group with three elements, each of these has one (or more) of the above two-element semigroups as subsemigroups.^[2] 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.

Finite semigroups of higher orders

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.^[2]^[3]^[4] The number of nonisomorphic semigroups with n elements, for n a nonnegative integer, is listed under OEIS: A027851 in the On-Line Encyclopedia of Integer Sequences. OEIS: A001423 lists the number of non-equivalent semigroups, and OEIS: A023814 the number of associative binary operations, out of a total of n^n², determining a semigroup.

References

^ 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 ^b Andreas Distler, Classification and enumeration of finite semigroups Archived 2 April 2015 at the Wayback Machine, PhD thesis, University of St. Andrews
^ 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.
^ John A Hildebrant (2001). Handbook of Finite Semigroup Programs. (Preprint).[1]

[1] 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.

[distler-2] Andreas Distler, Classification and enumeration of finite semigroups Archived 2 April 2015 at the Wayback Machine, PhD thesis, University of St. Andrews

[3] 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.

[4] John A Hildebrant (2001). Handbook of Finite Semigroup Programs. (Preprint).[1]

[1]

[2]

[3]

[4]