Monoid
In abstract algebra, a monoid is a set equipped with an associative binary operation and an identity element.
≈ 6 min read
Monoid. encyclopegia.org, snapshot enwiki-001378649517. /a/monoid
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In abstract algebra, a monoid is a set equipped with an associative binary operation and an identity element. For example, the natural numbers with addition form a monoid, the identity element being . 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, 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 the history of the subject, and some other general properties of monoids. Let be a cyclic monoid of order , that is, .
Then for some . Each such gives a distinct monoid of order , and every cyclic monoid is isomorphic to one of these.
Moreover, can be considered as a function on the points given by \begin{bmatrix} 0 & 1 & 2 & \cdots & n-2 & n-1 \\ 1 & 2 & 3 & \cdots & n-1 & k\end{bmatrix} or, equivalently f(i) := \begin{cases} i+1, & \text{if } 0 \le i Multiplication of elements in is then given by function composition. When then the function is a permutation of , and gives the unique cyclic group of order .
For each nonnegative integer , one can define the product p_n = \textstyle \prod_{i=1}^n a_i of any sequence of elements of a monoid recursively: let and let for . As a special case, one can define nonnegative integer powers of an element of a monoid: and for . Then for all .
Not every monoid sits inside a group. For instance, it is perfectly possible to have a monoid in which two elements and exist such that holds even though is not the identity element (for example, take a = 0 and b = 5 in the multiplicative monoid of nonnegative integers.)
Such a monoid cannot be embedded in a group, because in the group multiplying both sides with the inverse of would get that , which is not true. A monoid has the cancellation property (or is cancellative) if for all , and in , the equality implies , and the equality implies .
A commutative monoid with the cancellation property can always be embedded in 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 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 a commutative monoid does not have the cancellation property, the homomorphism of the monoid into its Grothendieck group is not injective.
More precisely, if , then and have the same image in the Grothendieck group, even if . In particular, if the monoid has an absorbing element, then its Grothendieck group is the trivial group. \langle p,q\,\vert\; pq=1\rangle is the equational presentation for the bicyclic monoid, and \langle a,b \,\vert\; aba=baa, bba=bab\rangle is the plactic monoid of degree (it has infinite order).
Elements of this plactic monoid may be written as a^ib^j(ba)^k for integers , , , as the relations show that commutes with both and . \mathrm{fold}: M^{*} \rarr M = \ell \mapsto \begin{cases} \varepsilon & \text{if } \ell = \mathrm{nil} \\ m \bullet \mathrm{fold} \, \ell' & \text{if } \ell = \mathrm{cons} \, m \, \ell' \end{cases} In addition, any data structure can be 'folded' in a similar way, given a serialization of its elements. For instance, the result of "folding" a binary tree might differ depending on pre-order vs. post-order tree traversal. \sum_{i \in \emptyset}{m_i} = 0;\quad \sum_{i \in \{j\}}{m_i} = m_j;\quad \sum_{i \in \{j, k\}}{m_i} = m_j+m_k \quad \text{ for } j\neq k and \sum_{j \in J} {\sum_{i \in I_j}{m_i}} = \sum_{i \in I} m_i \quad \text{ if } \bigcup_{j\in J} I_j=I \text{ and } I_j \cap I_{j'} = \emptyset \quad \text{ for } j\neq j' . An ordered commutative monoid is a commutative monoid together with a partial ordering such that for every , and implies for all .
A continuous monoid is an ordered commutative monoid in which every directed subset has a least upper bound, and these least upper bounds are compatible with the monoid operation: a + \sup S = \sup(a + S) for every and directed subset of . If is a continuous monoid, then for any index set and collection of elements , one can define \sum_I a_i = \sup_{\text{finite } E \subset I} \; \sum_E a_i, and together with this infinitary sum operation is a complete monoid.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1378649517 under CC BY-SA 4.0; modifications have been made.