In mathematics, a semigroup with two elements is a

semigroup In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative internal binary operation on it. The binary operation of a semigroup is most often denoted multiplicatively: ''x''·''y'', or simply ''xy'', ...

for which the cardinality of the

underlying set In mathematics, an algebraic structure consists of a nonempty set ''A'' (called the underlying set, carrier set or domain), a collection of operations on ''A'' (typically binary operations such as addition and multiplication), and a finite se ...

is two. There are exactly five nonisomorphic semigroups having two elements: * O₂, the

null semigroup In mathematics, a null semigroup (also called a zero semigroup) is a semigroup with an absorbing element, called zero, in which the product of any two elements is zero. If every element of a semigroup is a left zero then the semigroup is called a l ...

of order two, * LO₂, the left zero semigroup of order two, * RO₂, the

right zero semigroup In mathematics, a null semigroup (also called a zero semigroup) is a semigroup with an absorbing element, called zero, in which the product of any two elements is zero. If every element of a semigroup is a left zero then the semigroup is called a ...

of order two, * (, ∧) (where "∧" is the

logical connective In logic, a logical connective (also called a logical operator, sentential connective, or sentential operator) is a logical constant. They can be used to connect logical formulas. For instance in the syntax of propositional logic, the binary ...

and or AND may refer to: Logic, grammar, and computing * Conjunction (grammar), connecting two words, phrases, or clauses * Logical conjunction in mathematical logic, notated as "∧", "⋅", "&", or simple juxtaposition * Bitwise AND, a boolea ...

"), or equivalently the set under multiplication: the only

semilattice In mathematics, a join-semilattice (or upper semilattice) is a partially ordered set that has a join (a least upper bound) for any nonempty finite subset. Dually, a meet-semilattice (or lower semilattice) is a partially ordered set which has a ...

with two elements and the only non-null semigroup with

zero 0 (zero) is a number representing an empty quantity. In place-value notation such as the Hindu–Arabic numeral system, 0 also serves as a placeholder numerical digit, which works by multiplying digits to the left of 0 by the radix, usual ...

of order two, also a

monoid In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being 0. Monoid ...

, and ultimately the

two-element Boolean algebra In mathematics and abstract algebra, the two-element Boolean algebra is the Boolean algebra whose ''underlying set'' (or universe or ''carrier'') ''B'' is the Boolean domain. The elements of the Boolean domain are 1 and 0 by convention, so that ''B ...

, * (Z₂, +₂) (where Z₂ = and "+₂" is "addition modulo 2"), or equivalently (, ⊕) (where "⊕" is the logical connective " xor"), or equivalently the set under multiplication: the only

group A group is a number of persons or things that are located, gathered, or classed together. Groups of people * Cultural group, a group whose members share the same cultural identity * Ethnic group, a group whose members share the same ethnic ide ...

of order two. The semigroups LO₂ and RO₂ are antiisomorphic. O₂, and are

commutative In mathematics, a binary operation is commutative if changing the order of the operands does not change the result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it. Most familiar as the name of ...

, and LO₂ and RO₂ are noncommutative. LO₂, RO₂ and are

band Band or BAND may refer to: Places *Bánd, a village in Hungary *Band, Iran, a village in Urmia County, West Azerbaijan Province, Iran * Band, Mureș, a commune in Romania *Band-e Majid Khan, a village in Bukan County, West Azerbaijan Province, I ...

Determination of semigroups with two elements

Choosing the set 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 Matrix most commonly refers to: * ''The Matrix'' (franchise), an American media franchise ** ''The Matrix'', a 1999 science-fiction action film ** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchis ...

of the form indicates a binary operation on ''A'' having the following

Cayley table Named after the 19th century British mathematician Arthur Cayley, a Cayley table describes the structure of a finite group by arranging all the possible products of all the group's elements in a square table reminiscent of an addition or multiplic ...

. In this table: *The semigroup denotes the two-element semigroup containing the

zero element In mathematics, a zero element is one of several generalizations of the number zero to other algebraic structures. These alternate meanings may or may not reduce to the same thing, depending on the context. Additive identities An additive identi ...

0 and the

unit element In algebra, a unit of a ring is an invertible element for the multiplication of the ring. That is, an element of a ring is a unit if there exists in such that vu = uv = 1, where is the multiplicative identity; the element is unique for thi ...

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 . Every element is

idempotent Idempotence (, ) is the property of certain operations in mathematics and computer science whereby they can be applied multiple times without changing the result beyond the initial application. The concept of idempotence arises in a number of pl ...

in this semigroup, so it is a

. Furthermore, it is commutative (abelian) and thus a

. The order induced is a

linear order In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X: # a \leq a ( reflexive) ...

, and so it is in fact a

lattice Lattice may refer to: Arts and design * Latticework, an ornamental criss-crossed framework, an arrangement of crossing laths or other thin strips of material * Lattice (music), an organized grid model of pitch ratios * Lattice (pastry), an orna ...

and it is also a distributive and

complemented lattice In the mathematical discipline of order theory, a complemented lattice is a bounded lattice (with least element 0 and greatest element 1), in which every element ''a'' has a complement, i.e. an element ''b'' satisfying ''a'' ∨ ''b''& ...

, i.e. it is actually the

. *The two binary operations defined by matrices in a blue background are associative and pairing either with ''A'' creates a semigroup isomorphic to the

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

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

. *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 (, ∧)

The

for the semigroup (,

\wedge

) is given below: 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

. 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 In logic and mathematics, a truth value, sometimes called a logical value, is a value indicating the relation of a proposition to truth, which in classical logic has only two possible values ('' true'' or '' false''). Computing In some pro ...

true True most commonly refers to truth, the state of being in congruence with fact or reality. True may also refer to: Places * True, West Virginia, an unincorporated community in the United States * True, Wisconsin, a town in the United States * ...

" and 0 to be the

" false" and the operation to be the

", we obtain this semigroup in

logic Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premise ...

. It is isomorphic to the monoid under multiplication. It is also isomorphic to the semigroup :

S = \left\

under

matrix multiplication In mathematics, particularly in linear algebra, matrix multiplication is a binary operation that produces a matrix from two matrices. For matrix multiplication, the number of columns in the first matrix must be equal to the number of rows in the s ...

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

The

for the semigroup is given below: This group is isomorphic to the

cyclic group In group theory, a branch of abstract algebra in pure mathematics, a cyclic group or monogenous group is a group, denoted C''n'', that is generated by a single element. That is, it is a set of invertible elements with a single associative bina ...

Z₂ and the

symmetric group In abstract algebra, the symmetric group defined over any set is the group whose elements are all the bijections from the set to itself, and whose group operation is the composition of functions. In particular, the finite symmetric group ...

S₂.

Semigroups of order 3

Let ''A'' be the three-element set . 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). With the exception of the group with three elements, each of these has one (or more) of the above two-element semigroups as subsemigroups.Andreas Distler
Classification and enumeration of finite semigroups
, PhD thesis,

University of St. Andrews (Aien aristeuein) , motto_lang = grc , mottoeng = Ever to ExcelorEver to be the Best , established = , type = Public research university Ancient university , endowment ...

For example, the set under multiplication is a semigroup of order 3, and contains both and 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.
/ref> The number of nonisomorphic semigroups with ''n'' elements, for ''n'' a nonnegative integer, is listed under in the

On-Line Encyclopedia of Integer Sequences The On-Line Encyclopedia of Integer Sequences (OEIS) is an online database of integer sequences. It was created and maintained by Neil Sloane while researching at AT&T Labs. He transferred the intellectual property and hosting of the OEIS to t ...

. lists the number of non-equivalent semigroups, and the number of associative binary operations, out of a total of ''n''^''n''², determining a semigroup.

References

{{DEFAULTSORT:Semigroup With Two Elements Algebraic structures Semigroup theory