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 .
69-423: Monoids are semigroups with identity. Such algebraic structures occur in several branches of mathematics. The functions from a set into itself form a monoid with respect to function composition. More generally, in category theory , the morphisms of an object to itself form a monoid, and, conversely, a monoid may be viewed as a category with a single object. In computer science and computer programming ,
138-472: A i {\displaystyle p_{n}=\textstyle \prod _{i=1}^{n}a_{i}} of any sequence ( a 1 , ..., a n ) of n elements of a monoid recursively: let p 0 = e and let p m = p m −1 • a m for 1 ≤ m ≤ n . As a special case, one can define nonnegative integer powers of an element x of a monoid: x = 1 and x = x • x for n ≥ 1 . Then x = x • x for all m , n ≥ 0 . An element x
207-399: A i b j ( b a ) k {\displaystyle a^{i}b^{j}(ba)^{k}} for integers i , j , k , as the relations show that ba commutes with both a and b . Monoids can be viewed as a special class of categories . Indeed, the axioms required of a monoid operation are exactly those required of morphism composition when restricted to
276-459: A S b ⊆ S a ∧ b . If f is onto, the semilattice L is isomorphic to the quotient of S by the equivalence relation ~ such that x ~ y if and only if f ( x ) = f ( y ) . 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 S , there
345-428: A . This notation does not imply that it is numbers being multiplied. A monoid in which each element has an inverse is a group . A submonoid of a monoid ( M , •) is a subset N of M that is closed under the monoid operation and contains the identity element e of M . Symbolically, N is a submonoid of M if e ∈ N ⊆ M , and x • y ∈ N whenever x , y ∈ N . In this case, N
414-399: A commutative semigroup, when it exists, is a group. Green's relations , a set of five equivalence relations that characterise the elements in terms of the principal ideals 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
483-417: 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 (just notation, not necessarily the elementary arithmetic multiplication ): x ⋅ y , or simply xy , denotes the result of applying the semigroup operation to the ordered pair ( x , y ) . Associativity
552-409: A , b ∈ L has a greatest lower bound , denoted a ∧ b . The operation ∧ makes L into a semigroup that satisfies the additional idempotence law a ∧ a = a . Given a homomorphism f : S → L from an arbitrary semigroup to a semilattice, each inverse image S a = f { a } is a (possibly empty) semigroup. Moreover, S becomes graded by L , in the sense that S
621-439: 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 S / ~ . The mapping x ↦ [ x ] ~ is a semigroup homomorphism, called the quotient map , canonical surjection or projection ; if S is a monoid then quotient semigroup is a monoid with identity [1] ~ . Conversely,
690-462: A commutative monoid does not have the cancellation property, the homomorphism of the monoid into its Grothendieck group is not injective. More precisely, if a • b = a • c , then b and c have the same image in the Grothendieck group, even if b ≠ c . In particular, if the monoid has an absorbing element , then its Grothendieck group is the trivial group . An inverse monoid
759-465: A group via the Grothendieck group construction . That is how the additive group of the integers (a group with operation + ) is constructed from the additive monoid of natural numbers (a commutative monoid with operation + and cancellation property). However, a non-commutative cancellative monoid need not be embeddable in a group. If a monoid has the cancellation property and is finite , then it
SECTION 10
#1732783772922828-446: A group, because in the group multiplying both sides with the inverse of a would get that b = e , which is not true. A monoid ( M , •) has the cancellation property (or is cancellative) if for all a , b and c in M , the equality a • b = a • c implies b = c , and the equality b • a = c • a implies b = c . A commutative monoid with the cancellation property can always be embedded in
897-414: A group. Of these we mention: regular semigroups , orthodox semigroups , semigroups with involution , inverse semigroups and cancellative semigroups . There are also interesting classes of semigroups that do not contain any groups except the trivial group ; examples of the latter kind are bands and their commutative subclass – semilattices , which are also ordered algebraic structures . A semigroup
966-455: A maximal element. By Zorn's lemma , this is equivalent to saying that the ascending chain condition 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 , via the congruence ρ defined by x ρ y if either x = y , or both x and y are in I . The following notions introduce
1035-485: A meaning must be given to the exponential 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 t = 0 to the state u ( t ) = exp( tA ) u 0 at time t . The operator A is said to be the infinitesimal generator of the semigroup. The study of semigroups trailed behind that of other algebraic structures with more complex axioms such as groups or rings . A number of sources attribute
1104-407: A monoid, with the binary operation denoted by • and the identity element denoted by e . Then a (left) M -act (or left act over M ) is a set X together with an operation ⋅ : M × X → X which is compatible with the monoid structure as follows: This is the analogue in monoid theory of a (left) group action . Right M -acts are defined in a similar way. A monoid with an act
1173-441: A quasigroup need not be associative but quasigroups preserve from groups the notion of division . 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 a transformation semigroup , in which arbitrary functions replace the role of bijections in group theory. A deep result in
1242-466: A quotient of a category with one object is just a quotient monoid. Monoids, just like other algebraic structures, also form their own category, Mon , whose objects are monoids and whose morphisms are monoid homomorphisms. There is also a notion of monoid object which is an abstract definition of what is a monoid in a category. A monoid object in Set is just a monoid. Semigroup In mathematics,
1311-530: A set of generators Σ , and a set of relations on the free monoid Σ . One does this by extending (finite) binary relations on Σ to monoid congruences, and then constructing the quotient monoid, as above. Given a binary relation R ⊂ Σ × Σ , one defines its symmetric closure as R ∪ R . This can be extended to a symmetric relation E ⊂ Σ × Σ by defining x ~ E y if and only if x = sut and y = svt for some strings u , v , s , t ∈ Σ with ( u , v ) ∈ R ∪ R . Finally, one takes
1380-405: A set of two elements {a, b }, eight form semigroups whereas only four of these are monoids and only two form groups. For more on the structure of finite semigroups, see Krohn–Rhodes theory . There is a structure theorem for commutative semigroups in terms of semilattices . A semilattice (or more precisely a meet-semilattice) ( L , ≤) is a partially ordered set where every pair of elements
1449-428: Is a monoid homomorphism . But there are semigroup homomorphisms that are not monoid homomorphisms, e.g. the canonical embedding of a semigroup S without identity into S . Conditions characterizing monoid homomorphisms are discussed further. Let f : S 0 → S 1 be a semigroup homomorphism. The image of f is also a semigroup. If S 0 is a monoid with an identity element e 0 , then f ( e 0 )
SECTION 20
#17327837729221518-641: Is a set S together with a binary operation ⋅ (that is, a function ⋅ : S × S → S ) that satisfies the associative property : More succinctly, a semigroup is an associative magma . A left identity of a semigroup S (or more generally, magma ) is an element e such that for all x in S , e ⋅ x = x . Similarly, a right identity is an element f such that for all x in S , x ⋅ f = x . 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 )
1587-510: Is a finest congruence ~ such that the quotient of S by this equivalence relation is a semilattice. Denoting this semilattice by L , we get a homomorphism f from S onto L . As mentioned, S becomes graded by this semilattice. Furthermore, the components S a are all Archimedean semigroups . An Archimedean semigroup is one where given any pair of elements x , y , there exists an element z and n > 0 such that x = yz . The Archimedean property follows immediately from
1656-415: Is a monoid homomorphism, since it may not map the identity to the identity of the target monoid, even though the identity is the identity of the image of the homomorphism. For example, consider [ Z ] n , the set of residue classes modulo n equipped with multiplication. In particular, [1] n is the identity element. Function f : [ Z ] 3 → [ Z ] 6 given by [ k ] 3 ↦ [3 k ] 6
1725-411: Is a monoid under the binary operation inherited from M . On the other hand, if N is a subset of a monoid that is closed under the monoid operation, and is a monoid for this inherited operation, then N is not always a submonoid, since the identity elements may differ. For example, the singleton set {0} is closed under multiplication, and is not a submonoid of the (multiplicative) monoid of
1794-436: Is a monoid where for every a in M , there exists a unique a in M such that a = a • a • a and a = a • a • a . If an inverse monoid is cancellative, then it is a group. In the opposite direction, a zerosumfree monoid is an additively written monoid in which a + b = 0 implies that a = 0 and b = 0 : equivalently, that no element other than zero has an additive inverse. Let M be
1863-426: Is a semigroup having an identity element , 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 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 integers with addition form a commutative semigroup that
1932-445: Is a semigroup homomorphism, since [3 k ⋅ 3 l ] 6 = [9 kl ] 6 = [3 kl ] 6 . However, f ([1] 3 ) = [3] 6 ≠ [1] 6 , so a monoid homomorphism is a semigroup homomorphism between monoids that maps the identity of the first monoid to the identity of the second monoid and the latter condition cannot be omitted. In contrast, a semigroup homomorphism between groups is always a group homomorphism , as it necessarily preserves
2001-443: Is also a group is called 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
2070-538: Is also known as an operator monoid . Important examples include transition systems of semiautomata . A transformation semigroup can be made into an operator monoid by adjoining the identity transformation. A homomorphism between two monoids ( M , ∗) and ( N , •) is a function f : M → N such that where e M and e N are the identities on M and N respectively. Monoid homomorphisms are sometimes simply called monoid morphisms . Not every semigroup homomorphism between monoids
2139-404: Is an element that is both a left and right identity. Semigroups with a two-sided identity are called monoids . 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
Monoid - Misplaced Pages Continue
2208-426: 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 A . A = A holds for all elements of S , this must be true for all generators of G ( S ) as well, which is therefore the trivial group . It is clearly necessary for embeddability that S have
2277-990: Is an order-unit of G . A monoid for which the operation is commutative for some, but not all elements is a trace monoid ; trace monoids commonly occur in the theory of concurrent computation . [ 0 1 2 ⋯ n − 2 n − 1 1 2 3 ⋯ n − 1 k ] {\displaystyle {\begin{bmatrix}0&1&2&\cdots &n-2&n-1\\1&2&3&\cdots &n-1&k\end{bmatrix}}} or, equivalently f ( i ) := { i + 1 , if 0 ≤ i < n − 1 k , if i = n − 1. {\displaystyle f(i):={\begin{cases}i+1,&{\text{if }}0\leq i<n-1\\k,&{\text{if }}i=n-1.\end{cases}}} Multiplication of elements in ⟨ f ⟩
2346-457: Is called invertible if there exists an element y such that x • y = e and y • x = e . The element y is called the inverse of x . Inverses, if they exist, are unique: if y and z are inverses of x , then by associativity y = ey = ( zx ) y = z ( xy ) = ze = z . If x is invertible, say with inverse y , then one can define negative powers of x by setting x = y for each n ≥ 1 ; this makes
2415-412: Is called a zero . Analogous to the above construction, for every semigroup S , one can define S , a semigroup with 0 that embeds S . The semigroup operation induces an operation on the collection of its subsets: given subsets A and B of a semigroup S , their product A · B , written commonly as AB , is the set { ab | a in A and b in B }. (This notion is defined identically as it
2484-447: Is endowed with its algebraic preordering ≤ , defined by x ≤ y if there exists z such that x + z = y . An order-unit of a commutative monoid M is an element u of M such that for any element x of M , there exists v in the set generated by u such that x ≤ v . This is often used in case M is the positive cone of a partially ordered abelian group G , in which case we say that u
2553-464: Is for groups .) In terms of this operation, a subset A is called 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
2622-412: Is formally expressed as that ( x ⋅ y ) ⋅ z = x ⋅ ( y ⋅ z ) for all x , y and z in the semigroup. Semigroups may be considered a special case of magmas , where the operation is associative, or as a generalization of groups , without requiring the existence of an identity element or inverses. As in the case of groups or magmas, the semigroup operation need not be commutative , so x ⋅ y
2691-416: Is in fact a group. The right- and left-cancellative elements of a monoid each in turn form a submonoid (i.e. are closed under the operation and obviously include the identity). This means that the cancellative elements of any commutative monoid can be extended to a group. The cancellative property in a monoid is not necessary to perform the Grothendieck construction – commutativity is sufficient. However, if
2760-404: Is not a monoid, whereas the non-negative integers 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 quasigroups , which are generalization of groups in a different direction; the operation in
2829-426: Is not necessarily equal to y ⋅ x ; a well-known example of an operation that is associative but non-commutative is matrix multiplication . 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 is an algebraic structure intermediate between semigroups and groups, and
Monoid - Misplaced Pages Continue
2898-421: Is not necessarily the case that there are a quotient of S . Both of those relations are transitive. For any subset A of S there is a smallest subsemigroup T of S that contains A , and we say that A generates T . A single element x of S generates the subsemigroup { x | n ∈ Z } . If this is finite, then x is said to be of finite order , otherwise it is of infinite order . A semigroup
2967-461: 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 ). If a monogenic semigroup is infinite then it is isomorphic to the semigroup of positive integers with the operation of addition. If it is finite and nonempty, then it must contain at least one idempotent . It follows that every nonempty periodic semigroup has at least one idempotent. A subsemigroup that
3036-452: Is the identity element in the image of f . If S 1 is also a monoid with an identity element e 1 and e 1 belongs to the image of f , then f ( e 0 ) = e 1 , i.e. f is a monoid homomorphism. Particularly, if f is surjective , then it is a monoid homomorphism. Two semigroups S and T are said to be isomorphic if there exists a bijective semigroup homomorphism f : S → T . Isomorphic semigroups have
3105-464: Is then given by function composition. When k = 0 then the function f is a permutation of {0, 1, 2, ..., n −1} , and gives the unique cyclic group of order n . The monoid axioms imply that the identity element e is unique: If e and f are identity elements of a monoid, then e = ef = f . For each nonnegative integer n , one can define the product p n = ∏ i = 1 n
3174-418: Is unique. For this reason the identity is regarded as a constant , i. e. 0 -ary (or nullary) operation. The monoid therefore is characterized by specification of the triple ( S , • , e ) . Depending on the context, the symbol for the binary operation may be omitted, so that the operation is denoted by juxtaposition ; for example, the monoid axioms may be written ( ab ) c = a ( bc ) and ea = ae =
3243-477: The center of the semigroup. The center of a semigroup is actually a subsemigroup. A semigroup homomorphism is a function that preserves semigroup structure. A function f : S → T 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
3312-436: The cancellation property . 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 gave necessary and sufficient conditions for embeddability in 1937. Semigroup theory can be used to study some problems in
3381-413: The category of (small) monoids Mon and a full subcategory of the category of (small) categories Cat . Similarly, the category of groups is equivalent to another full subcategory of Cat . In this sense, category theory can be thought of as an extension of the concept of a monoid. Many definitions and theorems about monoids can be generalised to small categories with more than one object. For example,
3450-493: The kernel 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 that 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
3519-438: The nonnegative integers . A subset S of M is said to generate M if the smallest submonoid of M containing S is M . If there is a finite set that generates M , then M is said to be a finitely generated monoid . A monoid whose operation is commutative is called a commutative monoid (or, less commonly, an abelian monoid ). Commutative monoids are often written additively. Any commutative monoid
SECTION 50
#17327837729223588-579: The syntactic monoid . In probability theory , semigroups are associated with Markov processes . In other areas of applied mathematics , semigroups are fundamental models for linear time-invariant systems . In partial differential equations , a semigroup is associated to any equation whose spatial evolution is independent of time. There are numerous special classes of semigroups , 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
3657-499: The classification of finite semigroups is Krohn–Rhodes theory , analogous to the Jordan–Hölder decomposition for finite groups. Some other techniques for studying semigroups, like Green's relations , do not resemble anything in group theory. The theory of finite semigroups has been of particular importance in theoretical computer science since the 1950s because of the natural link between finite semigroups and finite automata via
3726-426: The corresponding generator. This has a universal property for morphisms from S to a group: given any group H and any semigroup homomorphism k : S → H , there exists a unique group homomorphism f : G → H 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
3795-416: The equation x = x • x hold for all m , n ∈ Z . The set of all invertible elements in a monoid, together with the operation •, forms a group . Not every monoid sits inside a group. For instance, it is perfectly possible to have a monoid in which two elements a and b exist such that a • b = a holds even though b is not the identity element. Such a monoid cannot be embedded in
3864-468: The field of partial differential equations . Roughly speaking, the semigroup approach is to regard a time-dependent partial differential equation as an ordinary differential equation on a function space. For example, consider the following initial/boundary value problem for the heat equation on the spatial interval (0, 1) ⊂ R and times t ≥ 0 : Let X = L ((0, 1) R ) be the L space of square-integrable real-valued functions with domain
3933-670: 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
4002-402: The history of the subject, and some other general properties of monoids. A set S equipped with a binary operation S × S → S , which we will denote • , is a monoid if it satisfies the following two axioms: In other words, a monoid is a semigroup with an identity element . It can also be thought of as a magma with associativity and identity. The identity element of a monoid
4071-472: 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, ( Z /2 Z , +) is a quotient of ( Z /4 Z , +) , using the morphism consisting of taking the remainder modulo 2 of an integer. A semigroup T divides a semigroup S , denoted T ≼ S if T is a quotient of a subsemigroup S . In particular, subsemigroups of S divides T , while it
4140-450: The identity (because, in the target group of the homomorphism, the identity element is the only element x such that x ⋅ x = x ). A bijective monoid homomorphism is called a monoid isomorphism . Two monoids are said to be isomorphic if there is a monoid isomorphism between them. Monoids may be given a presentation , much in the same way that groups can be specified by means of a group presentation . One does this by specifying
4209-401: The interval (0, 1) and let A be the second-derivative operator with domain where H is a Sobolev space . 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 u ( t ) = exp( tA ) u 0 . However, for a rigorous treatment,
SECTION 60
#17327837729224278-474: The ordering in the semilattice L , since with this ordering we have f ( x ) ≤ f ( y ) if and only if x = yz for some z and n > 0 . The group of fractions or group completion of a semigroup S is the group G = G ( S ) generated by the elements of S as generators and all equations xy = z that hold true in S as relations . There is an obvious semigroup homomorphism j : S → G ( S ) that sends each element of S to
4347-434: The reflexive and transitive closure of E , which is then a monoid congruence. In the typical situation, the relation R is simply given as a set of equations, so that R = { u 1 = v 1 , ..., u n = v n } . Thus, for example, is the equational presentation for the bicyclic monoid , and is the plactic monoid of degree 2 (it has infinite order). Elements of this plactic monoid may be written as
4416-425: The rule of unique invertibility") determined the structure of finite simple semigroups and showed that the minimal ideal (or Green's relations J-class) of a finite semigroup is simple. From that point on, the foundations of semigroup theory were further laid by David Rees , James Alexander Green , Evgenii Sergeevich Lyapin [ fr ] , Alfred H. Clifford and Gordon Preston . The latter two published
4485-406: The same structure. A semigroup congruence ~ is an equivalence relation that is compatible with the semigroup operation. That is, a subset ~ ⊆ S × S that is an equivalence relation and x ~ y and u ~ v implies xu ~ yv for every x , y , u , v in S . Like any equivalence relation, a semigroup congruence ~ induces congruence classes and the semigroup operation induces
4554-477: The set of strings built from a given set of characters is a free monoid . Transition monoids and syntactic monoids are used in describing finite-state machines . Trace monoids and history monoids provide a foundation for process calculi and concurrent computing . In theoretical computer science , the study of monoids is fundamental for automata theory ( Krohn–Rhodes theory ), and formal language theory ( star height problem ). See semigroup for
4623-436: The set of all morphisms whose source and target is a given object. That is, More precisely, given a monoid ( M , •) , one can construct a small category with only one object and whose morphisms are the elements of M . The composition of morphisms is given by the monoid operation • . Likewise, monoid homomorphisms are just functors between single object categories. So this construction gives an equivalence between
4692-436: The term maximal subgroup 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 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
4761-431: The unique one-sided identity). A semigroup S without identity may be embedded in a monoid formed by adjoining an element e ∉ S to S and defining e ⋅ s = s ⋅ e = s for all s ∈ S ∪ { e } . The notation S denotes a monoid obtained from S by adjoining an identity if necessary ( S = S for a monoid). Similarly, every magma has at most one absorbing element , which in semigroup theory
#921078