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
In mathematics, the cardinality of a set is a measure of the number of elements of the set. For example, the set A = \ contains 3 elements, and therefore A has a cardinality of 3. Beginning in the late 19th century, this concept was generalized ...
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 set ...
is two. There are exactly five
nonisomorphic semigroups having two elements:
* O
2, the
null semigroup of order two,
* LO
2, the
left zero semigroup of order two,
* RO
2, the
right zero semigroup 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 co ...
"
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 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, usuall ...
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.
Monoids a ...
, and ultimately the
two-element Boolean algebra,
* (Z
2, +
2) (where Z
2 = and "+
2" 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
2 and RO
2 are
antiisomorphic
In category theory, a branch of mathematics, an antiisomorphism (or anti-isomorphism) between structured sets ''A'' and ''B'' is an isomorphism from ''A'' to the opposite of ''B'' (or equivalently from the opposite of ''A'' to ''B''). If there ...
. O
2, and are
commutative, and LO
2 and RO
2 are noncommutative. LO
2, RO
2 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, ...
s.
Determination of semigroups with two elements
Choosing the set as the underlying set having two elements, sixteen
binary operation
In mathematics, a binary operation or dyadic operation is a rule for combining two elements (called operands) to produce another element. More formally, a binary operation is an operation of arity two.
More specifically, an internal binary op ...
s 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'' (franchi ...
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 multiplicat ...
.
In this table:
*The semigroup 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 . 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 p ...
in this semigroup, so it is a
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, ...
. 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
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''&nb ...
, 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
2 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
2. 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
2. 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
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 ...
.
*The remaining eight
binary operation
In mathematics, a binary operation or dyadic operation is a rule for combining two elements (called operands) to produce another element. More formally, a binary operation is an operation of arity two.
More specifically, an internal binary op ...
s defined by matrices in a white background are not
associative
In mathematics, the associative property is a property of some binary operations, which means that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a valid rule of replacement ...
and hence none of them create a semigroup when paired with ''A''.
The two-element semigroup (, ∧)
The
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 multiplicat ...
for the semigroup (,
) 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
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.
Monoids 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 "
true" and 0 to be the
truth value "
false" and the operation to be 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 co ...
"
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 ...
", we obtain this semigroup in
logic. It is isomorphic to the monoid under multiplication. It is also isomorphic to the semigroup
:
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 ...
.
The two-element semigroup (Z2, +2)
The
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 multiplicat ...
for the semigroup is given below:
This group is isomorphic to the
cyclic group Z
2 and the
symmetric group S
2.
Semigroups of order 3
Let ''A'' be the three-element set . Altogether, a total of 3
9 = 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. lists the number of non-equivalent semigroups, and the number of associative binary operations, out of a total of ''n''''n''2, determining a semigroup.
See also
* Empty semigroup In mathematics, a semigroup with no elements (the empty semigroup) is a semigroup in which the underlying set is the empty set. Many authors do not admit the existence of such a semigroup. For them a semigroup is by definition a ''non-empty'' set t ...
* Trivial semigroup In mathematics, a trivial semigroup (a semigroup with one element) is a semigroup for which the cardinality of the underlying set is one. The number of distinct nonisomorphic semigroups with one element is one. If ''S'' = is a semigroup with on ...
(semigroup with one element)
* Semigroup with three elements
* Special classes of semigroups
References
{{DEFAULTSORT:Semigroup With Two Elements
Algebraic structures
Semigroup theory