![Magma to group4](https://upload.wikimedia.org/wikipedia/commons/3/3f/Magma_to_group4.svg)
In mathematics, a semigroup is an
algebraic structure consisting of a
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
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'', denotes the result of applying the semigroup operation to the
ordered pair . Associativity is formally expressed as that for all ''x'', ''y'' and ''z'' in the semigroup.
Semigroups may be considered a special case of
magmas
Magma () is the molten or semi-molten natural material from which all igneous rocks are formed. Magma is found beneath the surface of the Earth, and evidence of magmatism has also been discovered on other terrestrial planets and some natural sa ...
, where the operation is associative, or as a generalization of
groups
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 ...
, without requiring the existence of an identity element or inverses.
[ The closure axiom is implied by the definition of a binary operation on a set. Some authors thus omit it and specify three axioms for a group and only one axiom (associativity) for a semigroup.] As in the case of groups or magmas, the semigroup operation need not be
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 ...
, so ''x''·''y'' is not necessarily equal to ''y''·''x''; a well-known example of an operation that is associative but non-commutative is
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 ...
. If the semigroup operation is commutative, then the semigroup is called a ''commutative semigroup'' or (less often than in the
analogous case of groups) it may be called an ''abelian semigroup''.
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 ...
is an algebraic structure intermediate between semigroups and groups, and is a semigroup having an
identity element
In mathematics, an identity element, or neutral element, of a binary operation operating on a set is an element of the set that leaves unchanged every element of the set when the operation is applied. This concept is used in algebraic structures su ...
, thus obeying all but one of the axioms of a group: existence of inverses is not required of a monoid. A natural example is
strings with
concatenation
In formal language theory and computer programming, string concatenation is the operation of joining character strings end-to-end. For example, the concatenation of "snow" and "ball" is "snowball". In certain formalisations of concatenat ...
as the binary operation, and the empty string as the identity element. Restricting to non-empty
strings gives an example of a semigroup that is not a monoid. Positive
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
s with addition form a commutative semigroup that is not a monoid, whereas the non-negative
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
s do form a monoid. A semigroup without an identity element can be easily turned into a monoid by just adding an identity element. Consequently, monoids are studied in the theory of semigroups rather than in group theory. Semigroups should not be confused with
quasigroup
In mathematics, especially in abstract algebra, a quasigroup is an algebraic structure resembling a group in the sense that " division" is always possible. Quasigroups differ from groups mainly in that they need not be associative and need not have ...
s, which are a generalization of groups in a different direction; the operation in a quasigroup need not be associative but quasigroups
preserve from groups a notion of
division
Division or divider may refer to:
Mathematics
*Division (mathematics), the inverse of multiplication
*Division algorithm, a method for computing the result of mathematical division
Military
*Division (military), a formation typically consisting ...
. Division in semigroups (or in monoids) is not possible in general.
The formal study of semigroups began in the early 20th century. Early results include
a Cayley theorem for semigroups realizing any semigroup as
transformation semigroup In algebra, a transformation semigroup (or composition semigroup) is a collection of transformations ( functions from a set to itself) that is closed under function composition. If it includes the identity function, it is a monoid, called a transfo ...
, in which arbitrary functions replace the role of bijections from group theory. A deep result in the classification of finite semigroups is
Krohn–Rhodes theory In mathematics and computer science, the Krohn–Rhodes theory (or algebraic automata theory) is an approach to the study of finite semigroups and automata that seeks to decompose them in terms of elementary components. These components correspond ...
, analogous to the
Jordan–Hölder decomposition In abstract algebra, a composition series provides a way to break up an algebraic structure, such as a group or a module, into simple pieces. The need for considering composition series in the context of modules arises from the fact that many nat ...
for finite groups. Some other techniques for studying semigroups, like
Green's relations In mathematics, Green's relations are five equivalence relations that characterise the elements of a semigroup in terms of the principal ideals they generate. The relations are named for James Alexander Green, who introduced them in a paper of 1951 ...
, do not resemble anything in group theory.
The theory of finite semigroups has been of particular importance in
theoretical computer science
computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory.
It is difficult to circumscribe the ...
since the 1950s because of the natural link between finite semigroups and
finite automata
A finite-state machine (FSM) or finite-state automaton (FSA, plural: ''automata''), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number o ...
via the
syntactic monoid In mathematics and computer science, the syntactic monoid M(L) of a formal language L is the smallest monoid that recognizes the language L.
Syntactic quotient
The free monoid on a given set is the monoid whose elements are all the strings of ze ...
. In
probability theory
Probability theory is the branch of mathematics concerned with probability. Although there are several different probability interpretations, probability theory treats the concept in a rigorous mathematical manner by expressing it through a set ...
, semigroups are associated with
Markov process
A Markov chain or Markov process is a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. Informally, this may be thought of as, "What happe ...
es. In other areas of
applied mathematics
Applied mathematics is the application of mathematical methods by different fields such as physics, engineering, medicine, biology, finance, business, computer science, and industry. Thus, applied mathematics is a combination of mathemati ...
, semigroups are fundamental models for
linear time-invariant systems. In
partial differential equations
In mathematics, a partial differential equation (PDE) is an equation which imposes relations between the various partial derivatives of a multivariable function.
The function is often thought of as an "unknown" to be solved for, similarly to ...
, a semigroup is associated to any equation whose spatial evolution is independent of time.
There are numerous
special classes of semigroups
In mathematics, a semigroup is a nonempty set together with an associative binary operation. A special class of semigroups is a class of semigroups satisfying additional properties or conditions. Thus the class of commutative semigroups consis ...
, semigroups with additional properties, which appear in particular applications. Some of these classes are even closer to groups by exhibiting some additional but not all properties of a group. Of these we mention:
regular semigroup In mathematics, a regular semigroup is a semigroup ''S'' in which every element is regular, i.e., for each element ''a'' in ''S'' there exists an element ''x'' in ''S'' such that . Regular semigroups are one of the most-studied classes of semigroup ...
s,
orthodox semigroup In mathematics, an orthodox semigroup is a regular semigroup whose set of idempotents forms a subsemigroup. In more recent terminology, an orthodox semigroup is a regular ''E''-semigroup. The term ''orthodox semigroup'' was coined by T. E. Hall and ...
s,
semigroups with involution,
inverse semigroup In group (mathematics), group theory, an inverse semigroup (occasionally called an inversion semigroup) ''S'' is a semigroup in which every element ''x'' in ''S'' has a unique ''inverse'' ''y'' in ''S'' in the sense that ''x = xyx'' and ''y = yxy'', ...
s and
cancellative semigroup In mathematics, a cancellative semigroup (also called a cancellation semigroup) is a semigroup having the cancellation property. In intuitive terms, the cancellation property asserts that from an equality of the form ''a''·''b'' = ''a''·''c'', w ...
s. There are also interesting classes of semigroups that do not contain any groups except the
trivial group
In mathematics, a trivial group or zero group is a group consisting of a single element. All such groups are isomorphic, so one often speaks of the trivial group. The single element of the trivial group is the identity element and so it is usuall ...
; examples of the latter kind are
bands and their commutative subclass—
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 ...
s, which are also
ordered algebraic structures.
Definition
A semigroup is a
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
together with a
binary operation "
" (that is, a
function
Function or functionality may refer to:
Computing
* Function key, a type of key on computer keyboards
* Function model, a structured representation of processes in a system
* Function object or functor or functionoid, a concept of object-oriente ...
) that satisfies the
associative property
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 replacemen ...
:
:For all
, the equation
holds.
More succinctly, a semigroup is an associative
magma
Magma () is the molten or semi-molten natural material from which all igneous rocks are formed. Magma is found beneath the surface of the Earth, and evidence of magmatism has also been discovered on other terrestrial planets and some natural sa ...
.
Examples of semigroups
*
Empty semigroup: the
empty set forms a semigroup with the
empty function
In mathematics, a function from a set to a set assigns to each element of exactly one element of .; the words map, mapping, transformation, correspondence, and operator are often used synonymously. The set is called the domain of the functi ...
as the binary operation.
*
Semigroup with one element: there is essentially only one (specifically, only one
up to isomorphism
In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word i ...
), the singleton with operation .
*
Semigroup with two elements: there are five which are essentially different.
* The "flip-flop" monoid: a
semigroup with three elements representing the three operations on a switch - set, reset, and do nothing.
* The set of positive
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
s with addition. (With 0 included, this becomes 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 ...
.)
* The set of
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
s with minimum or maximum. (With positive/negative infinity included, this becomes a monoid.)
* Square
nonnegative matrices
In mathematics, the sign of a real number is its property of being either positive, negative, or zero. Depending on local conventions, zero may be considered as being neither positive nor negative (having no sign or a unique third sign), or it ...
of a given size with matrix multiplication.
* Any
ideal
Ideal may refer to:
Philosophy
* Ideal (ethics), values that one actively pursues as goals
* Platonic ideal, a philosophical idea of trueness of form, associated with Plato
Mathematics
* Ideal (ring theory), special subsets of a ring considere ...
of a
ring
Ring may refer to:
* Ring (jewellery), a round band, usually made of metal, worn as ornamental jewelry
* To make a sound with a bell, and the sound made by a bell
:(hence) to initiate a telephone connection
Arts, entertainment and media Film and ...
with the multiplication of the ring.
* The set of all finite
strings over a fixed alphabet Σ with
concatenation
In formal language theory and computer programming, string concatenation is the operation of joining character strings end-to-end. For example, the concatenation of "snow" and "ball" is "snowball". In certain formalisations of concatenat ...
of strings as the semigroup operation — the so-called "
free semigroup In abstract algebra, the free monoid on a set is the monoid whose elements are all the finite sequences (or strings) of zero or more elements from that set, with string concatenation as the monoid operation and with the unique sequence of zero ele ...
over Σ". With the empty string included, this semigroup becomes the
free monoid In abstract algebra, the free monoid on a set is the monoid whose elements are all the finite sequences (or strings) of zero or more elements from that set, with string concatenation as the monoid operation and with the unique sequence of zero ele ...
over Σ.
* A
probability distribution F together with all
convolution powers of F, with convolution as the operation. This is called a convolution semigroup.
*
Transformation semigroup In algebra, a transformation semigroup (or composition semigroup) is a collection of transformations ( functions from a set to itself) that is closed under function composition. If it includes the identity function, it is a monoid, called a transfo ...
s and
monoids
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 ...
.
* The set of
continuous functions from a
topological space
In mathematics, a topological space is, roughly speaking, a geometrical space in which closeness is defined but cannot necessarily be measured by a numeric distance. More specifically, a topological space is a set whose elements are called po ...
to itself with composition of functions forms a monoid with the
identity function
Graph of the identity function on the real numbers
In mathematics, an identity function, also called an identity relation, identity map or identity transformation, is a function that always returns the value that was used as its argument, un ...
acting as the identity. More generally, the
endomorphisms of any object of a
category
Category, plural categories, may refer to:
Philosophy and general uses
*Categorization, categories in cognitive science, information science and generally
* Category of being
* ''Categories'' (Aristotle)
* Category (Kant)
* Categories (Peirce) ...
form a monoid under composition.
* The product of faces of an
arrangement of hyperplanes
In geometry and combinatorics, an arrangement of hyperplanes is an arrangement of a finite set ''A'' of hyperplanes in a linear, affine, or projective space ''S''.
Questions about a hyperplane arrangement ''A'' generally concern geometrical, ...
.
Basic concepts
Identity and zero
A
left identity of a semigroup
(or more generally,
magma
Magma () is the molten or semi-molten natural material from which all igneous rocks are formed. Magma is found beneath the surface of the Earth, and evidence of magmatism has also been discovered on other terrestrial planets and some natural sa ...
) is an element
such that for all
in
,
. Similarly, a
right identity is an element
such that for all
in
,
. Left and right identities are both called one-sided identities. A semigroup may have one or more left identities but no right identity, and vice versa.
A two-sided identity (or just identity) is an element that is both a left and right identity. Semigroups with a two-sided identity are called
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 ...
s. A semigroup may have at most one two-sided identity. If a semigroup has a two-sided identity, then the two-sided identity is the only one-sided identity in the semigroup. If a semigroup has both a left identity and a right identity, then it has a two-sided identity (which is therefore the unique one-sided identity).
A semigroup
without identity may be
embedded in a monoid formed by adjoining an element
to
and defining
for all
.
The notation
denotes a monoid obtained from
by adjoining an identity ''if necessary'' (
for a monoid).
Similarly, every magma has at most one
absorbing element In mathematics, an absorbing element (or annihilating element) is a special type of element of a set with respect to a binary operation on that set. The result of combining an absorbing element with any element of the set is the absorbing element i ...
, which in semigroup theory is called a zero. Analogous to the above construction, for every semigroup
, one can define
, a semigroup with 0 that embeds
.
Subsemigroups and ideals
The semigroup operation induces an operation on the collection of its subsets: given subsets ''A'' and ''B'' of a semigroup ''S'', their product , written commonly as ''AB'', is the set (This notion is defined identically as
it is for groups.) In terms of this operation, a subset ''A'' is called
* a subsemigroup if ''AA'' is a subset of ''A'',
* a right ideal if ''AS'' is a subset of ''A'', and
* a left ideal if ''SA'' is a subset of ''A''.
If ''A'' is both a left ideal and a right ideal then it is called an ideal (or a two-sided ideal).
If ''S'' is a semigroup, then the intersection of any collection of subsemigroups of ''S'' is also a subsemigroup of ''S''.
So the subsemigroups of ''S'' form a
complete lattice.
An example of a semigroup with no minimal ideal is the set of positive integers under addition. The minimal ideal of a
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 ...
semigroup, when it exists, is a group.
Green's relations In mathematics, Green's relations are five equivalence relations that characterise the elements of a semigroup in terms of the principal ideals they generate. The relations are named for James Alexander Green, who introduced them in a paper of 1951 ...
, a set of five
equivalence relations that characterise the elements in terms of the
principal ideal
In mathematics, specifically ring theory, a principal ideal is an ideal I in a ring R that is generated by a single element a of R through multiplication by every element of R. The term also has another, similar meaning in order theory, where ...
s they generate, are important tools for analysing the ideals of a semigroup and related notions of structure.
The subset with the property that every element commutes with any other element of the semigroup is called the
center
Center or centre may refer to:
Mathematics
*Center (geometry), the middle of an object
* Center (algebra), used in various contexts
** Center (group theory)
** Center (ring theory)
* Graph center, the set of all vertices of minimum eccentrici ...
of the semigroup.
The center of a semigroup is actually a subsemigroup.
Homomorphisms and congruences
A semigroup
homomorphism
In algebra, a homomorphism is a structure-preserving map between two algebraic structures of the same type (such as two groups, two rings, or two vector spaces). The word ''homomorphism'' comes from the Ancient Greek language: () meaning "same" ...
is a function that preserves semigroup structure. A function between two semigroups is a homomorphism if the equation
:.
holds for all elements ''a'', ''b'' in ''S'', i.e. the result is the same when performing the semigroup operation after or before applying the map ''f''.
A semigroup homomorphism between monoids preserves identity if it is a
monoid homomorphism
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 ar ...
. But there are semigroup homomorphisms which are not monoid homomorphisms, e.g. the canonical embedding of a semigroup
without identity into
. Conditions characterizing monoid homomorphisms are discussed further. Let
be a semigroup homomorphism. The image of
is also a semigroup. If
is a monoid with an identity element
, then
is the identity element in the image of
. If
is also a monoid with an identity element
and
belongs to the image of
, then
, i.e.
is a monoid homomorphism. Particularly, if
is
surjective, then it is a monoid homomorphism.
Two semigroups ''S'' and ''T'' are said to be
isomorphic if there exists a
bijective
In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other ...
semigroup homomorphism . Isomorphic semigroups have the same structure.
A semigroup congruence
is an
equivalence relation that is compatible with the semigroup operation. That is, a subset
that is an equivalence relation and
and
implies
for every
in ''S''. Like any equivalence relation, a semigroup congruence
induces
congruence class
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book ...
es
:
and the semigroup operation induces a binary operation
on the congruence classes:
:
Because
is a congruence, the set of all congruence classes of
forms a semigroup with
, called the quotient semigroup or factor semigroup, and denoted
. The mapping
is a semigroup homomorphism, called the quotient map, canonical
surjection
In mathematics, a surjective function (also known as surjection, or onto function) is a function that every element can be mapped from element so that . In other words, every element of the function's codomain is the image of one element of ...
or projection; if ''S'' is a monoid then quotient semigroup is a monoid with identity
. Conversely, the
kernel
Kernel may refer to:
Computing
* Kernel (operating system), the central component of most operating systems
* Kernel (image processing), a matrix used for image convolution
* Compute kernel, in GPGPU programming
* Kernel method, in machine learn ...
of any semigroup homomorphism is a semigroup congruence. These results are nothing more than a particularization of the
first isomorphism theorem in universal algebra. Congruence classes and factor monoids are the objects of study in
string rewriting systems.
A nuclear congruence on ''S'' is one which is the kernel of an endomorphism of ''S''.
A semigroup ''S'' satisfies the maximal condition on congruences if any family of congruences on ''S'', ordered by inclusion, has a maximal element. By
Zorn's lemma, this is equivalent to saying that the
ascending chain condition In mathematics, the ascending chain condition (ACC) and descending chain condition (DCC) are finiteness properties satisfied by some algebraic structures, most importantly ideals in certain commutative rings.Jacobson (2009), p. 142 and 147 These con ...
holds: there is no infinite strictly ascending chain of congruences on ''S''.
Every ideal ''I'' of a semigroup induces a factor semigroup, the
Rees factor semigroup In mathematics, in semigroup theory, a Rees factor semigroup (also called Rees quotient semigroup or just Rees factor), named after David Rees, is a certain semigroup constructed using a semigroup and an ideal of the semigroup.
Let ''S'' be a sem ...
, via the congruence ρ defined by if either , or both ''x'' and ''y'' are in ''I''.
Quotients and divisions
The following notions introduce the idea that a semigroup is contained in another one.
A semigroup T is a quotient of a semigroup S if there is a surjective semigroup morphism from S to T. For example,
is a quotient of
, using the morphism consisting of taking the remainder modulo 2 of an integer.
A semigroup T divides a semigroup S, noted
if T is a quotient of a subsemigroup S. In particular, subsemigroups of S divides T, while it is not necessarily the case that there are a quotient of S.
Both of those relation are transitive.
Structure of semigroups
For any subset ''A'' of ''S'' there is a smallest subsemigroup ''T'' of ''S'' which contains ''A'', and we say that ''A'' generates ''T''. A single element ''x'' of ''S'' generates the subsemigroup . If this is finite, then ''x'' is said to be of finite order, otherwise it is of infinite order.
A semigroup is said to be periodic if all of its elements are of finite order.
A semigroup generated by a single element is said to be
monogenic (or
cyclic
Cycle, cycles, or cyclic may refer to:
Anthropology and social sciences
* Cyclic history, a theory of history
* Cyclical theory, a theory of American political history associated with Arthur Schlesinger, Sr.
* Social cycle, various cycles in s ...
). If a monogenic semigroup is infinite then it is isomorphic to the semigroup of positive
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
s with the operation of addition.
If it is finite and nonempty, then it must contain at least one
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 ...
.
It follows that every nonempty periodic semigroup has at least one idempotent.
A subsemigroup which is also a group is called a
subgroup
In group theory, a branch of mathematics, given a group ''G'' under a binary operation ∗, a subset ''H'' of ''G'' is called a subgroup of ''G'' if ''H'' also forms a group under the operation ∗. More precisely, ''H'' is a subgroup ...
. There is a close relationship between the subgroups of a semigroup and its idempotents. Each subgroup contains exactly one idempotent, namely the identity element of the subgroup. For each idempotent ''e'' of the semigroup there is a unique maximal subgroup containing ''e''. Each maximal subgroup arises in this way, so there is a one-to-one correspondence between idempotents and maximal subgroups. Here the term ''
maximal subgroup
In mathematics, the term maximal subgroup is used to mean slightly different things in different areas of algebra.
In group theory, a maximal subgroup ''H'' of a group ''G'' is a proper subgroup, such that no proper subgroup ''K'' contains ''H'' ...
'' differs from its standard use in group theory.
More can often be said when the order is finite. For example, every nonempty finite semigroup is periodic, and has a minimal
ideal
Ideal may refer to:
Philosophy
* Ideal (ethics), values that one actively pursues as goals
* Platonic ideal, a philosophical idea of trueness of form, associated with Plato
Mathematics
* Ideal (ring theory), special subsets of a ring considere ...
and at least one idempotent. The number of finite semigroups of a given size (greater than 1) is (obviously) larger than the number of groups of the same size. For example, of the sixteen possible "multiplication tables" for a set of two elements eight form semigroups
[Namely: the trivial semigroup in which (for all ''x'' and ''y'') and its counterpart in which , the semigroups based on multiplication modulo 2 (choosing a or b as the identity element 1), the groups equivalent to addition modulo 2 (choosing a or b to be the identity element 0), and the semigroups in which the elements are either both left identities or both right identities.] whereas only four of these are monoids and only two form groups. For more on the structure of finite semigroups, see
Krohn–Rhodes theory In mathematics and computer science, the Krohn–Rhodes theory (or algebraic automata theory) is an approach to the study of finite semigroups and automata that seeks to decompose them in terms of elementary components. These components correspond ...
.
Special classes of semigroups
* 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 ...
is a semigroup with an
identity element
In mathematics, an identity element, or neutral element, of a binary operation operating on a set is an element of the set that leaves unchanged every element of the set when the operation is applied. This concept is used in algebraic structures su ...
.
* A
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 ...
is a monoid in which every element has an
inverse element
In mathematics, the concept of an inverse element generalises the concepts of opposite () and reciprocal () of numbers.
Given an operation denoted here , and an identity element denoted , if , one says that is a left inverse of , and that is ...
.
* A subsemigroup is a
subset of a semigroup that is closed under the semigroup operation.
* A
cancellative semigroup In mathematics, a cancellative semigroup (also called a cancellation semigroup) is a semigroup having the cancellation property. In intuitive terms, the cancellation property asserts that from an equality of the form ''a''·''b'' = ''a''·''c'', w ...
is one having the
cancellation property
In mathematics, the notion of cancellative is a generalization of the notion of invertible.
An element ''a'' in a magma has the left cancellation property (or is left-cancellative) if for all ''b'' and ''c'' in ''M'', always implies that .
An ...
: implies and similarly for . Every group is a cancellative semigroup, and every finite cancellative semigroup is a group.
* 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, I ...
is a semigroup whose operation 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 ...
.
* A
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 ...
is a semigroup whose operation is idempotent and
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 ...
.
*
0-simple semigroups.
*
Transformation semigroup In algebra, a transformation semigroup (or composition semigroup) is a collection of transformations ( functions from a set to itself) that is closed under function composition. If it includes the identity function, it is a monoid, called a transfo ...
s: any finite semigroup ''S'' can be represented by transformations of a (state-) set ''Q'' of at most states. Each element ''x'' of ''S'' then maps ''Q'' into itself and sequence ''xy'' is defined by for each ''q'' in ''Q''. Sequencing clearly is an associative operation, here equivalent to
function composition. This representation is basic for any
automaton
An automaton (; plural: automata or automatons) is a relatively self-operating machine, or control mechanism designed to automatically follow a sequence of operations, or respond to predetermined instructions.Automaton – Definition and More ...
or
finite-state machine
A finite-state machine (FSM) or finite-state automaton (FSA, plural: ''automata''), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number o ...
(FSM).
* The
bicyclic semigroup In mathematics, the bicyclic semigroup is an algebraic object important for the structure theory of semigroups. Although it is in fact a monoid, it is usually referred to as simply a semigroup. It is perhaps most easily understood as the syntactic ...
is in fact a monoid, which can be described as the
free semigroup In abstract algebra, the free monoid on a set is the monoid whose elements are all the finite sequences (or strings) of zero or more elements from that set, with string concatenation as the monoid operation and with the unique sequence of zero ele ...
on two generators ''p'' and ''q'', under the relation .
*
C0-semigroups.
*
Regular semigroup In mathematics, a regular semigroup is a semigroup ''S'' in which every element is regular, i.e., for each element ''a'' in ''S'' there exists an element ''x'' in ''S'' such that . Regular semigroups are one of the most-studied classes of semigroup ...
s. Every element ''x'' has at least one inverse ''y'' satisfying and ; the elements ''x'' and ''y'' are sometimes called "mutually inverse".
*
Inverse semigroup In group (mathematics), group theory, an inverse semigroup (occasionally called an inversion semigroup) ''S'' is a semigroup in which every element ''x'' in ''S'' has a unique ''inverse'' ''y'' in ''S'' in the sense that ''x = xyx'' and ''y = yxy'', ...
s are regular semigroups where every element has exactly one inverse. Alternatively, a regular semigroup is inverse if and only if any two idempotents commute.
* Affine semigroup: a semigroup that is isomorphic to a finitely-generated subsemigroup of Z
d. These semigroups have applications to
commutative algebra
Commutative algebra, first known as ideal theory, is the branch of algebra that studies commutative rings, their ideals, and modules over such rings. Both algebraic geometry and algebraic number theory build on commutative algebra. Prom ...
.
Structure theorem for commutative semigroups
There is a structure theorem for commutative semigroups in terms of
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 ...
s. A semilattice (or more precisely a meet-semilattice)
is a
partially ordered set
In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a bina ...
where every pair of elements
has a
greatest lower bound, denoted
. The operation
makes
into a semigroup satisfying the additional
idempotence
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 ...
law
.
Given a homomorphism
from an arbitrary semigroup to a semilattice, each inverse image
is a (possibly empty) semigroup. Moreover,
becomes graded by
, in the sense that
:
If
is onto, the semilattice
is isomorphic to the
quotient
In arithmetic, a quotient (from lat, quotiens 'how many times', pronounced ) is a quantity produced by the division of two numbers. The quotient has widespread use throughout mathematics, and is commonly referred to as the integer part of a ...
of
by the equivalence relation
such that
if and only if
. This equivalence relation is a semigroup congruence, as defined above.
Whenever we take the quotient of a commutative semigroup by a congruence, we get another commutative semigroup. The structure theorem says that for any commutative semigroup
, there is a finest congruence
such that the quotient of
by this equivalence relation is a semilattice. Denoting this semilattice by
, we get a homomorphism
from
onto
. As mentioned,
becomes graded by this semilattice.
Furthermore, the components
are all
Archimedean semigroups. An Archimedean semigroup is one where given any pair of elements
, there exists an element
and
such that
.
The Archimedean property follows immediately from the ordering in the semilattice
, since with this ordering we have
if and only if
for some
and
.
Group of fractions
The group of fractions or group completion of a semigroup ''S'' is 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 ...
generated by the elements of ''S'' as generators and all equations which hold true in ''S'' as
relations. There is an obvious semigroup homomorphism which sends each element of ''S'' to the corresponding generator. This has a
universal property
In mathematics, more specifically in category theory, a universal property is a property that characterizes up to an isomorphism the result of some constructions. Thus, universal properties can be used for defining some objects independently fr ...
for morphisms from ''S'' to a group: given any group ''H'' and any semigroup homomorphism , there exists a unique
group homomorphism
In mathematics, given two groups, (''G'', ∗) and (''H'', ·), a group homomorphism from (''G'', ∗) to (''H'', ·) is a function ''h'' : ''G'' → ''H'' such that for all ''u'' and ''v'' in ''G'' it holds that
: h(u*v) = h(u) \cdot h(v)
w ...
with ''k''=''fj''. We may think of ''G'' as the "most general" group that contains a homomorphic image of ''S''.
An important question is to characterize those semigroups for which this map is an embedding. This need not always be the case: for example, take ''S'' to be the semigroup of subsets of some set ''X'' with
set-theoretic intersection as the binary operation (this is an example of a semilattice). Since holds for all elements of ''S'', this must be true for all generators of ''G''(''S'') as well: which is therefore the
trivial group
In mathematics, a trivial group or zero group is a group consisting of a single element. All such groups are isomorphic, so one often speaks of the trivial group. The single element of the trivial group is the identity element and so it is usuall ...
. It is clearly necessary for embeddability that ''S'' have the
cancellation property
In mathematics, the notion of cancellative is a generalization of the notion of invertible.
An element ''a'' in a magma has the left cancellation property (or is left-cancellative) if for all ''b'' and ''c'' in ''M'', always implies that .
An ...
. When ''S'' is commutative this condition is also sufficient and the
Grothendieck group of the semigroup provides a construction of the group of fractions. The problem for non-commutative semigroups can be traced to the first substantial paper on semigroups.
Anatoly Maltsev Anatoly Ivanovich Maltsev (also: Malcev, Mal'cev; Russian: Анато́лий Ива́нович Ма́льцев; 27 November N.S./14 November O.S. 1909, Moscow Governorate – 7 June 1967, Novosibirsk) was born in Misheronsky, near Moscow, an ...
gave necessary and sufficient conditions for embeddability in 1937.
Semigroup methods in partial differential equations
Semigroup theory can be used to study some problems in the field of
partial differential equations
In mathematics, a partial differential equation (PDE) is an equation which imposes relations between the various partial derivatives of a multivariable function.
The function is often thought of as an "unknown" to be solved for, similarly to ...
. Roughly speaking, the semigroup approach is to regard a time-dependent partial differential equation as an
ordinary differential equation
In mathematics, an ordinary differential equation (ODE) is a differential equation whose unknown(s) consists of one (or more) function(s) of one variable and involves the derivatives of those functions. The term ''ordinary'' is used in contrast ...
on a function space. For example, consider the following initial/boundary value problem for the
heat equation on the spatial
interval and times :
:
Let be the
''L''''p'' space of square-integrable real-valued functions with domain the interval and let ''A'' be the second-derivative operator with
domain
:
where ''H''
2 is a
Sobolev space
In mathematics, a Sobolev space is a vector space of functions equipped with a norm that is a combination of ''Lp''-norms of the function together with its derivatives up to a given order. The derivatives are understood in a suitable weak sense ...
. Then the above initial/boundary value problem can be interpreted as an initial value problem for an ordinary differential equation on the space ''X'':
:
On an heuristic level, the solution to this problem "ought" to be . However, for a rigorous treatment, a meaning must be given to the
exponential
Exponential may refer to any of several mathematical topics related to exponentiation, including:
*Exponential function, also:
**Matrix exponential, the matrix analogue to the above
*Exponential decay, decrease at a rate proportional to value
*Expo ...
of ''tA''. As a function of ''t'', exp(''tA'') is a semigroup of operators from ''X'' to itself, taking the initial state ''u''
0 at time to the state at time ''t''. The operator ''A'' is said to be the
infinitesimal generator of the semigroup.
History
The study of semigroups trailed behind that of other algebraic structures with more complex axioms such as
groups
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 ...
or
rings
Ring may refer to:
* Ring (jewellery), a round band, usually made of metal, worn as ornamental jewelry
* To make a sound with a bell, and the sound made by a bell
:(hence) to initiate a telephone connection
Arts, entertainment and media Film and ...
. A number of sources
attribute the first use of the term (in French) to J.-A. de Séguier in ''Élements de la Théorie des Groupes Abstraits'' (Elements of the Theory of Abstract Groups) in 1904. The term is used in English in 1908 in Harold Hinton's ''Theory of Groups of Finite Order''.
Anton Sushkevich obtained the first non-trivial results about semigroups. His 1928 paper "Über die endlichen Gruppen ohne das Gesetz der eindeutigen Umkehrbarkeit" ("On finite groups without the rule of unique invertibility") determined the structure of finite
simple semigroups and showed that the minimal ideal (or
Green's relations In mathematics, Green's relations are five equivalence relations that characterise the elements of a semigroup in terms of the principal ideals they generate. The relations are named for James Alexander Green, who introduced them in a paper of 1951 ...
J-class) of a finite semigroup is simple.
[ From that point on, the foundations of semigroup theory were further laid by ]David Rees David or Dai Rees may refer to:
Entertainment
* David Rees (author) (1936–1993), British children's author
* Dave Rees (born 1969), American drummer for SNFU and Wheat Chiefs
* David Rees (cartoonist) (born 1972), American cartoonist and televis ...
, James Alexander Green
James Alexander "Sandy" Green FRS (26 February 1926 – 7 April 2014) was a mathematician and Professor at the Mathematics Institute at the University of Warwick, who worked in the field of representation theory.
Early life
Sandy Green was bor ...
, Evgenii Sergeevich Lyapin, Alfred H. Clifford and Gordon Preston. The latter two published a two-volume monograph on semigroup theory in 1961 and 1967 respectively. In 1970, a new periodical called ''Semigroup Forum
Semigroup Forum (print , electronic ) is a mathematics research journal published by Springer. The journal serves as a platform for the speedy and efficient transmission of information on current research in semigroup theory. Coverage in the jour ...
'' (currently edited by Springer Verlag) became one of the few mathematical journals devoted entirely to semigroup theory.
The representation theory
Representation theory is a branch of mathematics that studies abstract algebraic structures by ''representing'' their elements as linear transformations of vector spaces, and studies modules over these abstract algebraic structures. In essen ...
of semigroups was developed in 1963 by Boris Schein using binary relations on a set ''A'' and composition of relations for the semigroup product. At an algebraic conference in 1972 Schein surveyed the literature on B''A'', the semigroup of relations on ''A''. In 1997 Schein and Ralph McKenzie proved that every semigroup is isomorphic to a transitive semigroup of binary relations.
In recent years researchers in the field have become more specialized with dedicated monographs appearing on important classes of semigroups, like inverse semigroup In group (mathematics), group theory, an inverse semigroup (occasionally called an inversion semigroup) ''S'' is a semigroup in which every element ''x'' in ''S'' has a unique ''inverse'' ''y'' in ''S'' in the sense that ''x = xyx'' and ''y = yxy'', ...
s, as well as monographs focusing on applications in algebraic automata theory, particularly for finite automata, and also in functional analysis
Functional analysis is a branch of mathematical analysis, the core of which is formed by the study of vector spaces endowed with some kind of limit-related structure (e.g. inner product, norm, topology, etc.) and the linear functions defined o ...
.
Generalizations
If the associativity axiom of a semigroup is dropped, the result is a magma
Magma () is the molten or semi-molten natural material from which all igneous rocks are formed. Magma is found beneath the surface of the Earth, and evidence of magmatism has also been discovered on other terrestrial planets and some natural sa ...
, which is nothing more than a set ''M'' equipped with a binary operation that is closed .
Generalizing in a different direction, an ''n''-ary semigroup (also ''n''-semigroup, polyadic semigroup or multiary semigroup) is a generalization of a semigroup to a set ''G'' with a ''n''-ary operation instead of a binary operation. The associative law is generalized as follows: ternary associativity is , i.e. the string ''abcde'' with any three adjacent elements bracketed. ''N''-ary associativity is a string of length with any ''n'' adjacent elements bracketed. A 2-ary semigroup is just a semigroup. Further axioms lead to an ''n''-ary group.
A third generalization is the semigroupoid
In mathematics, a semigroupoid (also called semicategory, naked category or precategory) is a partial algebra that satisfies the axioms for a smallSee e.g. , which requires the objects of a semigroupoid to form a set. category, except possibly for ...
, in which the requirement that the binary relation be total is lifted. As categories generalize monoids in the same way, a semigroupoid behaves much like a category but lacks identities.
Infinitary generalizations of commutative semigroups have sometimes been considered by various authors.[See references in Udo Hebisch and Hanns Joachim Weinert, ''Semirings and Semifields'', in particular, Section 10, ''Semirings with infinite sums'', in M. Hazewinkel, Handbook of Algebra, Vol. 1, Elsevier, 1996. Notice that in this context the authors use the term ''semimodule'' in place of ''semigroup''.]
See also
* Absorbing element In mathematics, an absorbing element (or annihilating element) is a special type of element of a set with respect to a binary operation on that set. The result of combining an absorbing element with any element of the set is the absorbing element i ...
* Biordered set A biordered set (otherwise known as boset) is a mathematical object that occurs in the description of the structure of the set of idempotents in a semigroup.
The set of idempotents in a semigroup is a biordered set and every biordered set is the s ...
* Empty semigroup
* Generalized inverse
In mathematics, and in particular, algebra, a generalized inverse (or, g-inverse) of an element ''x'' is an element ''y'' that has some properties of an inverse element but not necessarily all of them. The purpose of constructing a generalized in ...
* Identity element
In mathematics, an identity element, or neutral element, of a binary operation operating on a set is an element of the set that leaves unchanged every element of the set when the operation is applied. This concept is used in algebraic structures su ...
* Light's associativity test In mathematics, Light's associativity test is a procedure invented by F. W. Light for testing whether a binary operation defined in a finite set by a Cayley multiplication table is associative. The naive procedure for verification of the associa ...
* Quantum dynamical semigroup
* Semigroup ring
* Weak inverse
In mathematics, the term weak inverse is used with several meanings.
Theory of semigroups
In the theory of semigroups, a weak inverse of an element ''x'' in a semigroup is an element ''y'' such that . If every element has a weak inverse, the s ...
Notes
Citations
References
General references
*
*
*
*
*
*
*
*
Specific references
*
*
*
*
*
*
* {{Cite book, last=Lothaire , first=M. , author-link=M. Lothaire , title=Algebraic combinatorics on words , orig-year=2002 , series=Encyclopedia of Mathematics and Its Applications , volume=90, publisher=Cambridge University Press , year=2011 , isbn=978-0-521-18071-9 , zbl=1221.68183
Semigroup theory
Algebraic structures