Monoid
Operation
Identity Element
definition a monoid is a semigroup that has an identity element
definition a monoid is a set equipped with a closed associative binary operation and an identity element --- Wikipedia
definition
a monoid is a set \(S\) equipped with a binary operator \(\cdot\) that satisfies the following axioms for some \(e \in S\) for all \(a, b, c \in S\):
associativity \((a \cdot b) \cdot c = a \cdot (b \cdot c)\)
identity \(a \cdot e = e \cdot a = a\)
closure \(a \cdot b \in S\)
--- Wikipedia
--- https://youtu.be/Nrp_LZ-XGsY?t=1041
Monoid Fold
aka reduce
see semigroup› fold, binary exponentiation
#stub
Free Monoid
--- https://en.wikipedia.org/wiki/Free_monoid
--- https://ncatlab.org/nlab/show/free+monoid
see free ‹semigroup, free ‹monad
notation \(S^*\)
definition the free monoid on a set is its smallest super‹set that forms a monoid under list › concatenation
definition \(S^* = S^+ \cup \{\varepsilon\}\), see free ‹semigroup
note \(\{\varepsilon\}^+ = \{\varepsilon\}\) and therefore it is not always the case that \(S^* = S^+ \sqcup \{\varepsilon\}\), see set› disjoint union --- https://cs.stackexchange.com/questions/35600/kleene-star-and-kleene-plus
equiv * operator in regular expressions
properties
the free ‹monoid operator has idempotence
Monoid Homomorphism
--- https://en.wikipedia.org/wiki/Monoid#Monoid_homomorphisms
see homo‹morphism
definition a monoid homomorphism from a monoid \(M\) to a monoid \(N\) is a function \(f : M \to N\) such that \(f\ e_M = e_N \land \forall a, b \in M.\ f\ (a \cdot_M b) = f\ a \cdot_N f\ b\)