Fact-checked by Grok 2 weeks ago

Monoid

In abstract algebra, a monoid is a set equipped with an associative binary operation and an identity element such that for all elements a in the set, the operation with the identity yields a.^[1]^[2] This structure generalizes semigroups, which lack an identity, by adding the neutral element, while falling short of groups by not requiring inverses for every element.^[3]^[2] Monoids form a foundational algebraic structure, appearing in diverse mathematical contexts such as category theory, where a monoid is equivalent to a category with a single object whose morphisms correspond to the monoid's elements under composition.^[4] Key properties include the uniqueness of the identity element and the existence of submonoids or units (invertible elements forming a group).^[1]^[2] Common examples include the natural numbers (including zero) under addition, with identity 0; the positive integers under multiplication, with identity 1; and the set of n \times n real matrices under multiplication, which is non-commutative for n \geq 2.^[1]^[3] Another prominent example is the free monoid of finite strings over an alphabet under concatenation, with the empty string as identity, which underpins formal language theory.^[3] Beyond pure mathematics, monoids play a crucial role in computer science, particularly in functional programming languages like Haskell, where they enable efficient composition of data structures such as lists or diagrams through associative operations, supporting parallelization and optimization.^[5] In automata theory and concurrency, monoids model state transitions and resource accumulation, highlighting their versatility across theoretical and applied domains.^[6]

Fundamentals

Definition

In abstract algebra, a monoid is an algebraic structure consisting of a nonempty set M, a binary operation \cdot: M \times M \to M, and a distinguished element e \in M called the identity element, such that the operation is associative and the identity satisfies e \cdot a = a \cdot e = a for all a \in M.^[2] Formally, a monoid is a triple (M, \cdot, e) where these conditions hold.^[7] The set M serves as the underlying carrier of the structure, containing all elements on which the operation acts. The binary operation \cdot combines any two elements of M to produce another element in M, and its associativity ensures that (a \cdot b) \cdot c = a \cdot (b \cdot c) for all a, b, c \in M, allowing well-defined expressions without parentheses. The identity element e acts as a neutral component under the operation, preserving each element unchanged when combined with it from either side.^[2] Notation for monoids varies by context: multiplicative notation uses \cdot or juxtaposition for the operation with e = 1, as in the integers under multiplication where 1 serves as identity; additive notation employs + with e = 0, as in the natural numbers under addition.^[1] These conventions reflect the operation's nature but do not alter the core properties. The associativity of the operation and the identity axioms are essential, with further elaboration in the dedicated axioms section. The algebraic structure now termed a monoid was first abstracted by Arthur Cayley in his 1854 paper "On the Theory of Groups, as depending on the symbolic equation \theta^n = 1," where his definition of a "group" required closure, associativity, and identity but omitted inverses, aligning precisely with the modern monoid.^[8] The specific term "monoid," denoting a semigroup with identity, emerged in the mid-20th century, notably popularized by Claude Chevalley.

Axioms

A monoid is specified by a triple (M, \cdot, e), where M is a set, \cdot: M \times M \to M is a binary operation, and e \in M is an identity element satisfying the identity axiom.^[9]^[10] The identity axiom requires that e acts as a two-sided identity: for all a \in M, a \cdot e = e \cdot a = a.^[9]^[10] This ensures that e leaves every element unchanged under the operation, providing a neutral "starting point" for compositions within the structure. To verify this axiom, one checks that the designated e satisfies the equation for every element in M. The identity element e is unique. Suppose e' is another element satisfying a \cdot e' = e' \cdot a = a for all a \in M. Then, substituting a = e, we obtain e \cdot e' = e' and, since e' is an identity, e \cdot e' = e, so e = e'.^[11] If a left identity e_l (satisfying e_l \cdot a = a for all a \in M) and a right identity e_r (satisfying a \cdot e_r = a for all a \in M) both exist, then they coincide and serve as a two-sided identity. Indeed, e_l = e_l \cdot e_r = e_r, using the left identity property on e_r and the right identity property on e_l.^[12] The associativity axiom states that the operation is associative: for all a, b, c \in M, (a \cdot b) \cdot c = a \cdot (b \cdot c).^[9]^[10] Verification involves confirming this equality holds for arbitrary elements, often by direct computation in concrete cases or by structural properties. Associativity implies that iterated products, such as a_1 \cdot a_2 \cdot \dots \cdot a_n, are well-defined without needing parentheses, as all possible groupings yield the same result.^[10] These axioms distinguish monoids from weaker structures: a magma requires only a binary operation (with closure), while a semigroup adds associativity but lacks an identity; a monoid combines both.^[10]^[13]

Internal Structures

Submonoids

A submonoid of a monoid (M, *, e) is a subset S \subseteq M that is itself a monoid under the restriction of the operation * to S, with the same identity element e.^[14] For S to qualify as a submonoid, it must be nonempty, closed under the operation * (meaning that for all a, b \in S, a * b \in S), and contain the identity e of M.^[15] Associativity of * on S follows from the associativity in the ambient monoid M.^[14] Every monoid has two trivial submonoids: the singleton set \{e\} consisting solely of the identity element, and the entire monoid M itself.^[16] Given any subset X \subseteq M, the submonoid generated by X is the smallest submonoid of M (with respect to set inclusion) that contains X, obtained as the intersection of all submonoids of M containing X.^[17] This generated submonoid always includes e and is closed under *.^[17]

Generators

In a monoid M with operation \cdot and identity e, a subset G \subseteq M is said to generate M if every element of M can be expressed as a finite product of elements from G, where the empty product is defined to be the identity e. This means that the smallest submonoid containing G is M itself, formed by closing G under the monoid operation and including e. The free monoid generated by a set X, denoted X^*, consists of all finite sequences (words) of elements from X, equipped with the concatenation operation and the empty sequence as the identity.^[18] It is freely generated by X, imposing no relations beyond associativity and the identity axioms, and satisfies the universal property: for any monoid N and any function f: X \to N, there exists a unique monoid homomorphism \overline{f}: X^* \to N extending f, defined by \overline{f}(x_1 \dots x_k) = f(x_1) \cdot \dots \cdot f(x_k) for x_i \in X.^[18] The rank of a monoid M, denoted d(M), is the minimal cardinality of a generating set for M.^[19] Finitely generated monoids are those with finite rank, but not all such monoids are free; for instance, a cyclic monoid generated by a single element a consists of the powers \{e, a, a^2, \dots \}, which may collapse under the monoid operation if a^k = a^m for some k \neq m, distinguishing it from the free monoid on one generator, which has all distinct powers.

Variants

Commutative Monoids

A commutative monoid is a monoid (M, \cdot, e) in which the binary operation satisfies the commutativity condition: for all a, b \in M, a \cdot b = b \cdot a.^[20] This ensures that the operation is symmetric, allowing elements to interact equivalently regardless of order. The commutativity property has significant implications for element interactions within the monoid. Notably, powers of distinct elements commute with each other: for any a, b \in M and nonnegative integers n, m, a^n \cdot b^m = b^m \cdot a^n. This symmetry simplifies expressions involving multiple elements and facilitates the analysis of substructures, as the order of application does not affect the result. Commutative monoids are also referred to as abelian monoids, especially when the operation is denoted additively to emphasize the group-like behavior in the commutative case.^[21] A fundamental result concerning the internal structure of these monoids is Rédei's theorem, which states that every finitely generated commutative monoid is finitely presented.^[22] This means that such a monoid can be defined by a finite set of generators and a finite set of relations among them, providing a concrete way to describe their algebraic architecture without infinite specifications. For instance, the nonnegative integers under addition form a free commutative monoid on a single generator, illustrating this finite presentation with no nontrivial relations.^[20]

Other Variants

An idempotent monoid is a monoid in which every element a satisfies the equation a \cdot a = a.^[23] This condition extends the notion of idempotence from individual elements to the entire structure, ensuring that repeated application of the operation yields the element itself. Bands, as the corresponding semigroups without requiring an identity, are precisely the idempotent semigroups where every element is idempotent, and those admitting an identity element form idempotent monoids.^[24] A cancellative monoid is one in which the operation satisfies both left and right cancellation laws: for all a, b, z in the monoid, z \cdot a = z \cdot b implies a = b, and a \cdot z = b \cdot z implies a = b.^[25] Left cancellative monoids require only the former, while right cancellative monoids require only the latter; full cancellativity combines both properties, enabling embeddings into groups under additional conditions like commutativity.^[26] Partially commutative monoids, also known as trace monoids, generalize free monoids by imposing an independence relation on the generators, allowing certain pairs of generators to commute while others do not.^[27] This relation is typically defined via a graph where generators (such as edges) commute if independent, for instance, if they share no common vertex, facilitating the study of concurrent processes or walks on graphs through equivalence classes of words under partial commutations.^[28] Monoids are distinguished as finite or infinite based on the cardinality of their underlying set: finite monoids have finitely many elements, enabling exhaustive enumeration and algorithmic analysis, whereas infinite monoids, such as the free monoid on a nonempty alphabet, possess unbounded structure.^[9] In combinatorics on words, aperiodic monoids are a significant subclass where, for every element a, there exists a positive integer n such that a^n = a^{n+1}, reflecting the absence of periodic behaviors and linking to star-free regular languages via syntactic monoids.^[29]

Examples

Algebraic Examples

One prominent algebraic example of a monoid is the set of natural numbers including zero, denoted \mathbb{N}_0 = \{0, 1, 2, \dots \}, equipped with the binary operation of addition and identity element 0. This structure satisfies the monoid axioms: addition is associative, as (a + b) + c = a + (b + c) for all a, b, c \in \mathbb{N}_0, and 0 serves as the identity since a + 0 = 0 + a = a for all a \in \mathbb{N}_0.^[30] The operation is commutative, meaning a + b = b + a for all elements, and this monoid is generated by the single element 1, as every natural number can be expressed as a finite sum of 1's.^[31] Another familiar example arises from the positive integers, denoted \mathbb{Z}^+ = \{1, 2, [3, \dots](/page/3_Dots) \}, under the operation of multiplication with identity element 1. Multiplication is associative, satisfying (a \times b) \times c = a \times (b \times c) for all a, b, c \in \mathbb{Z}^+, and 1 acts as the identity because a \times 1 = 1 \times a = a for all a \in \mathbb{Z}^+.^[30] This monoid is commutative, with a \times b = b \times a, and it possesses the cancellative property: if a \times b = a \times c and a \neq 0, then b = c, which follows from the fundamental theorem of arithmetic allowing unique prime factorizations.^[32] In linear algebra, the set of all n \times n matrices over a ring R, denoted M_n(R), forms a monoid under matrix multiplication, where the identity is the n \times n identity matrix I_n. Matrix multiplication is associative, as (AB)C = A(BC) for matrices A, B, C \in M_n(R), and I_n satisfies A I_n = I_n A = A for all A \in M_n(R).^[33] However, the operation is not always commutative; for n \geq 2, there exist matrices A and B such that AB \neq BA.^[33] A further algebraic instance is the set of all functions from a set S to itself, often denoted S^S or \mathrm{End}(S), under the operation of function composition with the identity function \mathrm{id}_S (defined by \mathrm{id}_S(x) = x for all x \in S) as the identity element. Composition is associative: if f, g, h: S \to S, then (f \circ g) \circ h = f \circ (g \circ h), and f \circ \mathrm{id}_S = \mathrm{id}_S \circ f = f for all f \in S^S.^[30] This monoid is generally non-commutative when |S| > 1, as function composition does not always satisfy f \circ g = g \circ f.^[33]

Non-Algebraic Examples

One prominent non-algebraic example of a monoid arises from the collection of all finite subsets of a given set X, equipped with the operation of union and the empty set \emptyset as the identity element. This structure is associative because the union of sets is associative: (A \cup B) \cup C = A \cup (B \cup C) for any finite subsets A, B, C \subseteq X. It is commutative since A \cup B = B \cup A, and idempotent as A \cup A = A.^[34] Another example is the set of all finite strings (or words) over a nonempty alphabet \Sigma, with the operation of concatenation and the empty string \epsilon as the identity. Concatenation is associative: (uv)w = u(vw) for strings u, v, w \in \Sigma^*, but generally non-commutative, as ab \neq ba for distinct letters a, b \in \Sigma. This forms the free monoid on \Sigma, freely generated by the elements of \Sigma. The collection of all finite multisets over a set X also constitutes a monoid under multiset union, with the empty multiset \{\} serving as the identity. Union is associative and commutative: for multisets A, B, C over X, (A \uplus B) \uplus C = A \uplus (B \uplus C) and A \uplus B = B \uplus A, where \uplus denotes addition of multiplicities. This is the free commutative monoid on X. Finally, the power set \mathcal{P}(X) of any set X forms a monoid under union, with \emptyset as the identity, since union is associative and commutative, and A \cup \emptyset = A. Similarly, under intersection, \mathcal{P}(X) is a monoid with X as the identity, as intersection is associative and commutative, and A \cap X = A. Both operations yield idempotent monoids.

Properties

Operations on Elements

In a monoid (M, \cdot, e), the binary operation \cdot extends naturally to finite products of elements due to associativity. For a finite sequence of elements a_1, a_2, \dots, a_n \in M with n \geq 1, the product is defined recursively as a_1 \cdot (a_2 \cdot \dots \cdot a_n) or equivalently by any parenthesization, yielding the unambiguous notation a_1 \cdot a_2 \cdots a_n. The empty product, corresponding to the sequence of length zero, is the identity element e.^[35]^[1] Powers of an element a \in M are defined using these products: for each nonnegative integer k, a^k denotes the product of k copies of a if k \geq 1, with the convention a^0 = e. Negative powers a^{-k} for k > 0 are not defined in general monoids, as they require the existence of inverses for a.^[35]^[36] Associativity of \cdot further enables the interpretation of finite products as n-ary operations on M, where the result is independent of the order of application. This property supports iteration through repeated multiplication, such as the left translation T_a(x) = a \cdot x applied k times to yield a^k \cdot x. In monoids generated by a set S \subseteq M, every element admits an expression as a finite product of elements from S \cup \{e\}, and the length of such a product is the number of non-identity factors in the sequence.^[35]^[1]^[37]

Units

In a monoid (M, *, e), an element u \in M is called a unit if there exists an element v \in M such that u * v = v * u = e.^[38] The element v is the inverse of u, and in a monoid, this inverse is unique if it exists.^[35] An element has a left inverse if there exists some v such that v * u = e, and a right inverse if u * v = e. In a monoid, if an element has both a left inverse and a right inverse, then they coincide, making the element a two-sided unit.^[35] The set of all units in M, denoted U(M), forms a group under the restriction of the monoid operation *, known as the unit group of M.^[38] For example, in the multiplicative monoid of natural numbers (\mathbb{N}, \times, 1), the only unit is $1, as there exists no v \in \mathbb{N} such that $2 \times v = 1.^[35]

Grothendieck Group

The Grothendieck group of a commutative monoid provides a canonical way to embed the monoid into an abelian group, extending the monoidal operation to a group structure while preserving the original relations. This construction, named after Alexander Grothendieck, arises naturally in algebraic contexts where one seeks to "invert" elements formally without assuming inverses exist in the monoid itself. It is particularly useful for commutative monoids, as the resulting group is abelian and satisfies a universal embedding property.^[21] Given a commutative monoid (M, +, 0), the Grothendieck group G(M) is constructed as the quotient set M \times M / \sim, where the equivalence relation \sim is defined by (a, b) \sim (c, d) if and only if a + d = b + c. The group operation on equivalence classes is induced componentwise: [(a, b)] + [(c, d)] = [(a + c, b + d)], with identity element [(0, 0)] and inverse [(a, b)]^{-1} = [(b, a)]. The monoid M embeds into G(M) via the homomorphism i: M \to G(M) given by i(m) = [(m, 0)], which preserves the addition in M. This embedding is injective if and only if M is cancellative (i.e., m + k = n + k implies m = n for all m, n, k \in M).^[21]^[39] The Grothendieck group satisfies a universal property: for any abelian group A and monoid homomorphism \phi: M \to A, there exists a unique group homomorphism \tilde{\phi}: G(M) \to A such that \tilde{\phi} \circ i = \phi, with \tilde{\phi}([(a, b)]) = \phi(a) - \phi(b). This property characterizes G(M) up to unique isomorphism among all abelian groups receiving a monoid homomorphism from M.^[21]^[39] Prominent examples include the additive monoid of non-negative integers \mathbb{N}_0, whose Grothendieck group is the integers \mathbb{Z}, with [(n, m)] corresponding to n - m. More generally, if M is the free commutative monoid on a set S (generated by formal sums of elements from S), then G(M) is the free abelian group on S. If M is already an abelian group, the construction yields G(M) \cong M, as every element already has an inverse and the equivalence relation aligns with the group structure.^[21]^[39]

Mappings and Presentations

Homomorphisms

A monoid homomorphism is a function \phi: (M, *, e) \to (N, \circ, f) between two monoids that preserves the binary operation and the identity element, satisfying \phi(a * b) = \phi(a) \circ \phi(b) for all a, b \in M and \phi(e) = f.^[40] This definition ensures that the map respects the associative structure and the neutral element of each monoid.^[41] Composition of monoid homomorphisms yields another monoid homomorphism, making the collection of monoids and their homomorphisms form a category in the algebraic sense, though the focus here remains on the mapping properties themselves.^[40] An isomorphism of monoids is a bijective homomorphism \phi: M \to N whose inverse \phi^{-1}: N \to M is also a monoid homomorphism.^[40] This bidirectional preservation implies that M and N are structurally identical as monoids, with \phi providing a one-to-one correspondence that maintains the operation and identity.^[41] Isomorphisms are equivalence relations on the class of monoids, partitioning them into isomorphism classes where elements within a class are indistinguishable up to relabeling.^[42] The kernel of a monoid homomorphism \phi: M \to N is the preimage \ker(\phi) = \{a \in M \mid \phi(a) = f\}, which forms a submonoid of M.^[40] More precisely, \ker(\phi) induces a congruence relation on M, defined as the equivalence relation \theta = \{(a, b) \in M \times M \mid \phi(a) = \phi(b)\}, which is compatible with the monoid operation in that if (a, b) \in \theta and (c, d) \in \theta, then (a * c, b * d) \in \theta.^[40] This congruence captures the fibers of \phi, partitioning M into classes where elements map to the same image, and every kernel congruence arises in this manner from some homomorphism.^[40] The image of \phi is the submonoid \phi(M) = \{\phi(a) \mid a \in M\} of N, equipped with the restricted operation \circ and identity f, since \phi preserves the structure.^[40] By the first isomorphism theorem for monoids, the quotient monoid M / \ker(\phi), formed by factoring M through the congruence \theta with operations defined on equivalence classes * = [a * b], is isomorphic to the image \phi(M).^[40] This quotient construction yields a monoid where the operation on cosets inherits associativity and the identity class $$, establishing a fundamental link between kernels, images, and structural equivalence.^[40]

Presentations

A monoid can be defined through an equational presentation, which consists of a set of generators and a set of relations specifying equalities between words formed from those generators. Formally, given a set A of generators and a set R \subseteq A^* \times A^* of relations, where A^* is the free monoid on A, the presented monoid M is the quotient A^* / \equiv_R, with \equiv_R being the smallest congruence on A^* generated by R. This congruence identifies words u and v if (u, v) \in R, and extends to all contexts via substitution and transitivity.^[43] If both the set of generators A and the set of relations R are finite, the presentation is called finite, and the monoid is said to be finitely presented, denoted M = \langle A \mid [R](/page/Relation) \rangle. Such presentations provide a compact way to describe monoids that may have infinitely many elements, as the relations impose the necessary identifications.^[43] Two presentations of the same monoid are equivalent if one can be transformed into the other via a sequence of Tietze transformations, which are elementary operations preserving the presented monoid. These include adding or removing a generator along with a defining relation, and adding or removing a relation that is derivable from the existing ones. For finite presentations, any two are connected by such transformations. A basic example is the monoid of natural numbers under addition, which is the free monoid on a single generator x with no relations, presented as \langle x \mid \rangle; here, elements are powers x^n for n \in \mathbb{N}, corresponding to multiples of the generator.

Advanced Connections

Category Theory

In category theory, a monoid (M, \cdot, e) is equivalent to a category with exactly one object, say \bullet, whose morphisms are the elements of M, whose composition is the monoid multiplication \cdot, and whose identity morphism is the monoid unit e.^[44] This perspective identifies the monoid operation with categorical composition and the unit with the identity arrow.^[10] Consequently, monoid homomorphisms correspond to functors between such one-object categories.^[10] This construction induces an equivalence of categories between the category of monoids, denoted \mathbf{Mon}, and the category of one-object categories equipped with identity-preserving functors.^[10] Under this equivalence, the forgetful functor from one-object categories to the category of sets (sending the category to its hom-set) aligns with the underlying-set functor on monoids.^[10] Monoidal categories provide a broader generalization of monoids, where the role of the single-object category is played by an arbitrary category \mathcal{C}, the multiplication by a bifunctor \otimes: \mathcal{C} \times \mathcal{C} \to \mathcal{C}, and the unit by an object I \in \mathcal{C}, subject to coherence conditions expressed via natural isomorphisms for associativity and unit laws (the pentagon and triangle identities).^[45] Specifically, a strict monoidal category with a single object recovers the structure of a monoid exactly, with \otimes as the multiplication and I as the unit.^[45] The category \mathbf{Mon} of monoids and monoid homomorphisms admits a forgetful functor U: \mathbf{Mon} \to \mathbf{Set} that maps each monoid to its underlying set and each homomorphism to its underlying function.^[46] This forgetful functor has a left adjoint F: \mathbf{Set} \to \mathbf{Mon}, known as the free monoid functor, which sends a set X to the free monoid on X—the set of all finite words (including the empty word) over the alphabet X, with concatenation as multiplication and the empty word as unit.^[46] The unit of this adjunction provides the canonical inclusion of generators, while the counit projects onto the underlying set via the monoid structure.^[46]

Acts

In abstract algebra, a right act over a monoid M, or right M-act, consists of a nonempty set X together with a map X \times M \to X, denoted (x, a) \mapsto x \cdot a, satisfying the axioms (x \cdot a) \cdot b = x \cdot (a b) for all x \in X and a, b \in M, and x \cdot e = x for all x \in X, where e is the identity of M. This structure generalizes the notion of a module over a ring to the setting of monoids, capturing how elements of M transform elements of X while preserving the monoid's associative operation.^[47] Symmetrically, a left M-act is a nonempty set X with a map M \times X \to X, denoted (a, x) \mapsto a \cdot x, that obeys (a b) \cdot x = a \cdot (b \cdot x) for all a, b \in M and x \in X, along with e \cdot x = x for all x \in X. These definitions ensure compatibility with the monoid structure, allowing monoids to "act" on sets in a controlled manner.^[48] A monoid action on a set X is faithful if the induced monoid homomorphism M \to T_X, where T_X denotes the full transformation monoid on X (the set of all functions X \to X under composition), is injective; equivalently, for distinct a, b \in M, there exists some x \in X such that x \cdot a \neq x \cdot b (or a \cdot x \neq b \cdot x for left actions). This injectivity embeds M as a submonoid of T_X, ensuring the action distinguishes elements of M. Faithful actions are fundamental in representation theory for monoids, as they realize M concretely via transformations.^[49] An operator monoid arises when a monoid M acts on a set X, forming a submonoid of the full transformation monoid T_X generated by the maps x \mapsto x \cdot m for m \in M (or left variants); this views M as a collection of operators on X. Such structures are central to the study of monoid representations by transformations and appear in applications like automata theory, where transition functions form operator monoids.

Applications

Computer Science

In computer science, monoids play a foundational role in formal language theory, where the free monoid generated by a finite alphabet \Sigma consists of all finite strings (words) over \Sigma, including the empty string as the identity element, with concatenation as the associative operation.^[50] This structure captures the essence of string manipulation, as every word is a unique sequence without relations imposed beyond associativity, enabling the definition of languages as subsets of this monoid.^[50] Regular languages, a core class in this theory, are precisely those subsets recognizable by finite automata and closed under monoid operations like union, concatenation, and Kleene star, which generates powers within the free monoid.^[51] In automata theory, monoids provide an algebraic framework for understanding language recognition through transition monoids. For a deterministic finite automaton accepting a regular language, the transition monoid is the finite monoid generated by the transition functions under composition, where each generator corresponds to a letter in the alphabet and acts on the state set.^[52] This monoid determines the language up to equivalence, as two automata recognize the same language if and only if their transition monoids are isomorphic; moreover, Eilenberg's variety theorem establishes a correspondence between varieties of regular languages and pseudovarieties of finite monoids, linking syntactic properties of languages to monoid structures.^[51] Such algebraic characterizations facilitate decidability results and complexity analyses in language processing. Monads in functional programming draw inspiration from monoids via category theory, where a monad on a category can be viewed as a monoid in the category of endofunctors, equipped with composition as the operation and the identity functor as the unit.^[36] In languages like Haskell, monads structure computations with effects (e.g., state, I/O) through return (unit) and bind (multiplication), enabling Kleisli composition to chain functions that produce wrapped values associatively, much like monoid operations but generalized to handle computational contexts.^[53] This abstraction promotes modular code reuse, as seen in do-notation for sequencing operations, while preserving referential transparency. Monoids underpin efficient parallel computation by allowing associative combination of partial results in divide-and-conquer paradigms, such as tree-based reductions for operations like sum or max.^[54] For instance, computing the sum of an array can be parallelized by recursively summing subarrays and merging via the additive monoid of numbers, ensuring correctness regardless of evaluation order due to associativity and the existence of a neutral element (zero).^[54] This pattern extends to scan (prefix sum) algorithms, where monoid structure enables work-efficient parallel implementations on architectures like GPUs, reducing synchronization overhead and scaling to large datasets.^[54]

Specialized Uses

In distributed computing frameworks such as MapReduce, monoids provide the algebraic foundation for associative reduction operations that enable efficient parallel processing of large datasets. The combiner step in MapReduce leverages the associativity of the monoid operation to partially aggregate key-value pairs locally before shuffling, reducing network overhead; for instance, the monoid of lists under concatenation, with the empty list as the identity, allows appending values associatively across mappers. This design principle generalizes to various aggregation tasks, where the monoid's binary operation combines intermediate results without dependency on order, ensuring correctness in distributed environments.^[55] Complete monoids extend commutative monoids by incorporating an infinitary summation operation that assigns a supremum to every subset, forming a structure integral to lattice theory where it supports the analysis of infinite joins and meets. In such monoids, the finitary sum coincides with the infinitary operation restricted to finite index sets, enabling the modeling of continuous processes in ordered structures. Applications in optimization arise in contexts like dynamic programming over lattices, where complete monoids facilitate the computation of fixed points and suprema in weighted lattice frameworks for sparse signal representation and variational problems.^[56] Semirings, which consist of two monoids (one additive and one multiplicative) satisfying distributive laws, find specialized use in graph algorithms by generalizing shortest path computations beyond traditional metrics. The min-plus semiring, where addition is minimization and multiplication is addition (with infinity as the additive identity and zero as the multiplicative identity), underpins algorithms like Floyd-Warshall for all-pairs shortest paths, treating edge weights as "distances" combined associatively. This framework allows uniform treatment of problems such as minimum cost paths or Viterbi decoding in hidden Markov models, with the monoid structure ensuring efficient matrix operations over the semiring.^[57] In cryptography, monoids serve as underlying structures for protocols requiring non-commutative operations, particularly in key exchange and digital signatures. Stickel's protocol was proposed using a non-commutative monoid to compute "exponentiations" via repeated applications of the monoid operation for key agreement without relying on commutative groups like those in Diffie-Hellman, but it has been subject to cryptanalytic attacks such as linear algebra methods.^[58]^[59] Similarly, monoid-based knapsack protocols construct hard problems from subset sums in monoids, resisting linear algebra attacks through the representation gap in finite monoids derived from monoidal categories. These applications highlight monoids' role in post-quantum cryptography, where their algebraic properties support efficient yet secure computations in resource-constrained settings.^[60]

References

[1]
[PDF] 2. Groups 2.1. Groups and monoids. Let's start out with the basic ...
(b) A monoid is a semigroup M that has an identity (or neutral ele- ment): there exists e ∈ M such that ea = ae = a for all a ∈ M.
[2]
[PDF] Section I.1. Semigroups, Monoids, and Groups
Feb 5, 2022 · The order of a semigroup/monoid/group is the cardinality of set G, denoted |G|. If |G| < ∞, then the semigroup/monoid/group is said to be ...
[3]
AlgebraicStructures - Department of Computer Science
A semigroup (S,*) is a monoid if it has an identity element e, that is, if there is an element e such that e*x = x and x*e = x for all x. In algebraic terms, we ...Missing: abstract | Show results with:abstract
[4]
[PDF] Introduction to Category Theory∗ OPLSS 2023 - Computer Science
We can equivalently think of a monoid as a category with just one object, ∗, where the arrows are the elements of the monoid, the identity the unit element 1M ...
[5]
[PDF] Monoids: theme and variations <i>(functional pearl)</i> - Testing!
Abstract. The monoid is a humble algebraic structure, at first glance even downright boring. However, there's much more to monoids than meets the eye.
[6]
"Applications of automata theory to presentations of monoids and ...
In this work we construct certain automata and exploit the characteristics of these automata to derive information about monoids. A monoid is a semigroup with ...
[7]
[PDF] Algebraic Monoids and Renner Monoids
A Zariski closed submonoid of Mn is called a linear algebraic monoid. The following theorem shows that every affine algebraic monoid is isomorphic to a linear.
[8]
a study in early twentieth-century group axiomatics - PMC
... Cayley had laid down. Cayley's 'group', as defined, was merely a monoid. The additional structure that emerges upon multiplication by a 'further or nearer ...
[9]
Monoid -- from Wolfram MathWorld
A monoid is a set that is closed under an associative binary operation and has an identity element I in S such that for all a in S, Ia=aI=a.Missing: axioms | Show results with:axioms
[10]
monoid in nLab
Jul 10, 2024 · In algebra, by a monoid one means a collection (set) of elements equipped with a binary operation (a “multiplication operation”) which is associative and has a ...
[11]
identity element is unique - PlanetMath.org
Mar 22, 2013 · Proof. Let e e and e′ e ′ be identity elements of a monoid (G,⋅) ( G , ⋅ ) . Since e e is an identity element, one has e⋅e′=e′ e ⋅ e ′ = e ′ ...
[12]
Left and right identity - abstract algebra - Math Stack Exchange
Feb 2, 2012 · You showed that if g is a left identity and h is a right identity, then g=h. This means that g is a 2-sided identity, and that it is unique, ...
[13]
Group identities and inverses - Mathematics Stack Exchange
Apr 25, 2012 · If a semigroup has a left identity and a right identity, then they are the same and it is a two-sided identity. (Note that no inverses are ...
[14]
Submonoid -- from Wolfram MathWorld
A submonoid is a subset of the elements of a monoid that are themselves a monoid under the same monoid operation. For example, consider the monoid formed by ...Missing: "abstract | Show results with:"abstract
[15]
[PDF] Introduction to Algebra - UC Berkeley Mathematics
Mar 7, 2019 · of a monoid M a submonoid ... Exercise 66 Prove that (101) is a partition of set G if and only if the coset aH which contains the identity element ...
[16]
[PDF] Closure operations on the submonoids of the natural numbers
Feb 1, 2012 · A submonoid will be a subset of a monoid in which the operation + ... [7] Herstein, I.N., Abstract Algebra. John Wiley and Sons, Inc ...
[17]
[PDF] Lecture 1. Monoids: General algebraic aspects Definition.
Given a subset X ⊆ M, the submonoid generated by X, denoted XM , is the intersection of all submonoids of M that contain X. We say M is finitely generated ...
[18]
Minimal generating sets for matrix monoids - ScienceDirect.com
(1998). The least cardinality of a generating set for a semigroup S is often called the rank of S and is denoted by d ...
[19]
Commutative Monoid -- from Wolfram MathWorld
A monoid that is commutative i.e., a monoid M such that for every two elements a and b in M, ab=ba. This means that commutative monoids are commutative, ...Missing: properties | Show results with:properties
[20]
[PDF] Some Algebraic Definitions and Constructions
As a convention, it is convenient to say that a commutative monoid is “Abelian” when we choose to think of its product as “addition”, but to use the word “ ...<|separator|>
[21]
[PDF] factorization theory in commutative monoids - Uni Graz
By Redei's Theorem, every finitely generated commutative semigroup is finitely presented. ... finitely generated commutative cancellative monoids, Manuscr.
[22]
Hemirings and Semirings: Definitions and Examples - SpringerLink
An element m of M idempotent if and only if m * m = m. A semigroup (M, *) is commutative if and only if m * M′ = M′ * m for all m.m′ ∈ M.
[23]
band in nLab
Jun 14, 2025 · 1. Definition. A band is a semigroup in which every element is idempotent. 2. Order structures on bands. There are two distinct order structures ...
[24]
cancellative monoid in nLab
### Definition of Cancellative Monoid
[25]
Cancellative monoids
A \emph{cancellative monoid} is a monoid M=⟨M,⋅,e⟩ M = ⟨ M , ⋅ , e ⟩ such that. ⋅ ⋅ is left cancellative: z⋅x=z⋅y⟹x=y z ⋅ x = z ⋅ y ⟹ x = y.Cancellative monoids · Definition · Properties · Finite members
[26]
Algebraic Combinatorics on Trace Monoids: Extending Number ...
Partially commutative monoids provide a powerful tool to study graphs, viewing walks as words whose letters, the edges of the graph, obey a specific ...
[27]
Algebraic combinatorics on trace monoids: extending number theory ...
Jan 8, 2016 · Partially commutative monoids provide a powerful tool to study graphs, viewingwalks as words whose letters, the edges of the graph, obey a specific commutation ...
[28]
https://arxiv.org/abs/1601.01780
[29]
[PDF] Examples of monoids (1) N = {0,1,2,...} is a monoid with respect to ...
(1) N = {0,1,2,...} is a monoid with respect to addition. Simi- larly, N+ = N − {0} and N are both monoids with respect to multiplication.Missing: abstract | Show results with:abstract
[30]
Commutative monoids
Definition. A \emph{commutative monoid} is a structure M=⟨M,⋅,e⟩ M = ⟨ M , ⋅ , e ⟩ , where ⋅ is an infix binary operation, called the \emph{monoid product}, ...
[31]
[PDF] Factorization in monoids and rings - arXiv
May 4, 2020 · By the fundamental theorem of arithmetic, every positive integer other than 1 can be expressed as a non-empty product of primes in an ...<|control11|><|separator|>
[32]
https://arxiv.org/pdf/2005.01681
[33]
[PDF] LINEAR LOGIC : ITS SYNTAX AND SEMANTICS - Jean-Yves GIRARD
will be replaced by the monoid of finite subsets of X, and sum will be replaced by union. The web of !X will be the set Xfin of all finite cliques of X.
[34]
[PDF] Binary Operations, Monoids, and Groups - CSUSM
This document covers ideas related to the concept of binary operations. This includes examples, various properties (commutative, associative) that binary op- ...
[35]
[PDF] maclane-categories.pdf - MIT Mathematics
... monoid-a set with a binary operation of multiplication that is associa- tive ... Powers. If the factors in a product are all equal (aj = bEe for all j).
[36]
[PDF] Minimal Generating Sets of the Monoid of Partial Order-Preserving ...
Aug 6, 2020 · Abstract - Monoids arise in such fields as computer science, physics, and numerous branches of mathematics including abstract algebra, ...
[37]
Monoids - an overview | ScienceDirect Topics
A monoid is defined as a set equipped with an associative binary operation and an identity element. In the context of the source, a specific example of a ...
[38]
[PDF] the grothendieck group k0
An (abelian) cancellation monoid is an abelian monoid M such that for all m ... The exterior powers Λi(V ) of a representation V are also G- modules ...
[39]
None
Below is a merged summary of monoid-related content from "A Course in Universal Algebra" and the provided sections of the document at https://www.math.hawaii.edu/~ralph/Classes/619/univ-algebra.pdf. To retain all information in a dense and organized manner, I will use a table in CSV format for key concepts, followed by a concise narrative summary that integrates additional details not suitable for the table. The table will cover definitions, examples, and page references across all segments, while the narrative will address broader context, specific examples, and any additional notes.
[40]
[PDF] Introduction to Abstract Algebra (Math 113)
The central idea behind abstract algebra is to define a larger class of objects (sets with extra structure), of which Z and Q are definitive members.
[41]
[PDF] Group Theory - James Milne
The only prerequisite is an undergraduate course in abstract algebra. There ... (ℤ∕𝑛ℤ)× = {units in the ring ℤ∕𝑛ℤ}={𝑚 + 𝑛ℤ ∣ gcd(𝑚, 𝑛) = 1 ...
[42]
[PDF] presentation of monoids by generators and relations
PRESENTATION OF MONOIDS BY GENERATORS AND. RELATIONS. NACER GHADBANE* AND DOUADI MIHOUB. Abstract. Let A be the free monoid over a finite alphabet A and R a.
[43]
[PDF] Saunders Mac Lane - Categories for the Working Mathematician
Monoids. A monoid is a category with one object. Each monoid is thus determined by the set of all its arrows, by the identity arrow, and.
[44]
monoidal category in nLab
### Definition of Monoidal Category and Relation to Monoids
[45]
category of monoids in nLab
### Summary of Forgetful Functor and Free Monoid Functor from Mon to Set
[46]
[PDF] The Flat Cover Conjecture for Monoid Acts - arXiv
Our terminology agrees with the standard reference for monoid acts (Kilp et al. [17]). A monoid is a nonempty set S together with an associative binary.
[47]
[PDF] monoid actions and ultrafilter methods in ramsey theory
Let M be a monoid. By a located word over M we understand a function from a finite non-empty subset of N to M. For two such words w1 and w2, we write w1 ...
[48]
[PDF] Faithful and Transitive Monoid Actions - AMS - EMS
Any transitive and faithful action of a monoid M on a set Ω is equivalent to the action of M on eM/≡ where e is an idempo- tent in I(M) and ≡ is a right ...
[49]
[PDF] 1.1 words and languages - UCLA Department of Mathematics
free monoid and free semigroup generated by Σ. = The reader should keep ... Subsets of Σ* are referred to as (formal) languages over Σ. Thus,. L1. = {a ...
[50]
[PDF] Algebraic Approach to Automata Theory - CSA – IISc Bangalore
Let A≡L = (Q,s, δ,F) be the canonical automaton for a language L ⊆ A∗. The transition monoid of A≡L is called the syntactic monoid of L, we write M(L) rather ...<|control11|><|separator|>
[51]
[PDF] On Deterministic Finite Automata and Syntactic Monoid Size
In order to compute the syntactic monoid of a language it is convenient to consider the transition monoid induced by a finite automaton. Let A = (Q, Σ, δ, q0,F) ...
[52]
[PDF] Monads for functional programming - The University of Edinburgh
These notes describe one, the use of monads to integrate impure effects into pure functional languages. The concept of a monad, which arises from category ...
[53]
Functional Parallels of Sequential Imperatives (Short Paper)
Reduce-phase expressions are (with few exceptions) monoid operations, so that we obtain static guarantees that the programs can be parallelized with determin- ...
[54]
Monoidify! Monoids as a Design Principle for Efficient MapReduce ...
Apr 29, 2013 · This short paper represents an attempt to more clearly articulate this design principle in terms of monoids, which generalizes the use of combiners and the in- ...Missing: associative processing
[55]
[PDF] Toward a Sparsity Theory on Weighted Lattices - CVSP - NTUA
This paper studies issues of sparse representation in nonlinear vector spaces. In particular, we focus on complete weighted lattices Maragos (Math. Control ...
[56]
[PDF] Semiring Frameworks and Algorithms for Shortest-Distance Problems
The semi- ring (R+ ∪ {∞}, min, +, ∞, 0) is the underlying algebraic structure of many classical shortest-paths algorithms and is called the tropical semiring.
[57]
[PDF] Algebraic Structures, Stickel's Protocol, and Monoid Investigations
May 22, 2024 · This thesis examines cryptographic key-exchange protocols using algebraic structures, focusing on Stickel's protocol, and explores monoids.
[58]
[PDF] Monoidal categories, representation gap and cryptography - arXiv
(a) As explained above, monoid-based protocols such as SU or St and many others often admit efficient attacks based on linear algebra [MR15].