Sep 28, 2026
Monoids show up everywhere once you are aware of them. 1 They can be used to reduce large amounts of data to a small amount of data that can be used to make decisions. It is no surprise they show up in statistics and pivot tables.
A monoid is a set M with an associative binary operation m that has an identity element e. The binary operation is a function m\colon M\times M\to M satisfying the associative law m(m(a,b),c) = m(a, m(b, c)).
If we write ab for the monoid product m(a,b) then the associative law is (ab)c = a(bc). This allows us to write abc unambiguously.
The identity element e satisfies ea = a = ae for all a\in M.
Exercise. Show the identity element is unique.
Hint: If e'a = a = ae' for all a\in M show e = e'.
A semigroup has an associative binary operation but not necessarily an identity element. If s\colon S\time S\to S is the semigroup binary operation we can define M = S\cup\{e\} where e\not\in S and m\colon M\times M\to M by m(e,e) = e, m(e, s) = s = m(s, e) for s\in S, and m(a,b) = s(a,b) for a,b\in S.
Exercise. Show this is a monoid.
It is easy to fix up a semigroup into a monoid.
A group is a monoid where every element has an inverse. Let g\colon G\times G\to G be the binary operation. Every a\in G has an inverse a^{-1}\in G with g(a,a^{-1}) = e.
Exercise. Show g(a^{-1},a) = e for all $aG.
Note that it is not neccesary to assume G is abelian, ab = ba for a,b\in G.
Not only abc is unambiguous, so is any product a_1\cdots a_n.
Define m^n\colon M^n\to M for n\ge0 by m^0(()) = e and {m^{n+1}((a_0,\ldots, a_n)) = m(a_0, m^n((a_1,\ldots,a_n))}.
Exercise. Show m^1((a)) = a and m^2((a,b)) = m(a,b).
Define the Kleene star M^* = \cup_{n\ge0} M^n and m^*\colon M^*\to M by m^*(a_1, \dots, a_n) = m^n((a_1,\ldots,a_n)).
Addition and multiplication of numbers are the most well known examples of monoids with respective identities 0 and 1.
They are also monoids, but not groups, when restricted to non-negative numbers. They are semigroups when restricted to positive numbers.
The maximum and minimum of numbers are also a monoid with respective identities -\infty and +\infty.
Exercise. Show \max\{x,-\infty\} = x and \min\{x,+\infty\} = x.
String concatenation is another example of a monoid where the empty string is the identity element.
(Dean and Ghemawat 2004) made a breakthrough in distributed computing using monoids. Calculating a monoid product a_1\cdots a_n sequentially takes order O(n) time. Breaking it into k pieces of size n/k allows the computation to be mapped over k computers that can run simultaneously in time O(n/k). The results can then be reduced in O(k) time.
The total time is O(n/k) + O(k) and we can can use a back-of-the-envelope calculation to find the optimal number of pieces by pretending we can take a derivative with respect to k. If {0 = (d/dk)(O(n/k) + O(k)) = O(-n/k^2) + O(1)} then {k = \sqrt{n}} is optimal.
We can also break the computation into k_1 pieces and each n/k_1 computation into k_2 pieces.
Exercise. (Due to Bill Goff) What are the optimal values of k_1 and k_2?
Hint: $O(n/k_1 k_2) + O(n/k_1) + O(k_1) = ? $
A statistic is a function from a lot of numbers to one number. The (sample) mean of {x_1,\ldots,x_n} is {\mu = \mu(x_1,\ldots,x_n) = (x_1 + \cdots + x_n)/n = \sum_{i=1}^n x_i/n. It is a number giving an indication of location. If all x_i are equal to x then the mean is x.
The mean is not a monoid but \boldsymbol{R}\times\boldsymbol{N} is with the binary operation m((x,i),(y,j)} = (ix + jy, i+j) with identity (0,0).
Exercise. Prove this.
The (sample) variance is {\sigma^2 = \sigma^2(x_1,\ldots,x_n) = \sum_{i=1}^n (x_i - \mu)^2/n}. It is a number indicating the spread of how far samples are from the average. If all x_i are equal to x then the variance is 0.
This can be repeated to come up with a measure of how good the variance statistic is.
Categories with a single object form a monoid. A (small) category is a partial monoid with left and right identities. A category \mathbf{C} has a partial binary operation \circ\colon\mathbf{C}\times\mathbf{C}\rightharpoonup\mathbf{C} and for every f\in\mathbf{C} there exist right and left identities {}_f e\in\mathbf{C} with f\circ {}_f e = f and e_f\in\mathbf{C} with e_f\circ f = f. Using the usual category theory notation f\colon A\to B where A and B are objects with arrow f we can identify {_f}e with A = \operatorname{dom}f and e_f with B = \operatorname{cod}f. Objects are determined by arrows in category theory.
If M is a commutative monoid let M^+ be the collection of all finite subsets of M. Define a function m^+\colon M^+\to M by m^+(\{m_1,\ldots,m_n\}) = m_1 \cdots m_n when m_j are distinct and m^+(\emptyset) = e, the monoid identity.
Exercise. Show this is well-defined.
Hint: This requires M to be commutative.
We can define a binary operation on disjoint finite subsets of M to M by {m^+(A,B) = m^+(A\cup B)}.
Exercise. If A,B\subseteq M are finite disjoint subsets show {m^+(A,B) = m^+(A)m^+(B)}.
Exercise. If A,B,C\subseteq M are finite pairwise-disjoint subsets show m^+(m^+(A, B), C) = m^+(A, m^+(B,C)).
Since m^+(\emptyset, A) = A = m^+(A, \emptyset) this shows finite disjoint subsets of a monoid form a monoid with identity \emptyset.
The Kleene star of M is the union of all finite sequences of elements of M, M^* = \cup_{n\ge0} M^n where M^n = \{(m_1,\dots,m_n)\mid m_j\in M\}. Define m^*\colon M^*\to M by m^*((m_1,\ldots,m_n)) = m_1 \cdots m_n and m^*(()) = e, the monoid identity.
Exercise. Show M^* is a monoid under m^* with identity (()).
Equivalence relations are a generalization of equality. Equality satisfied a = a, if a = b then b = a and if a = b and b = c then a = c.
An equivalence relation on a set S is a subset R\subseteq S\times S with (s,s)\in R, (s,t)\in R implies (t,s)\in R, and if (s,t)\in R and (t,u)\in R then (s,u)\in R. We write sRt for (s,t)\in R.
Exercise. Show aRa, aRb implies bRa, and if aRb and bRc then aRc if R is an equivalence relation.
Exercise. Show I = \{(s,s)\mid s\in S\} is an equivalence relation.
The equivalence class of s\in S is \overline{s} = \{s'\in S\mid sRs'\}.
Exercise. Show \overline{S} = \{\overline{s}\mid s\in S\} is a a partition of S.
Hint: A partition of S is a collection of pairwise disjoint sets whose union is S.
Exercise. If \overline{S} = \{S_i\}_{i\in I} is a partition of S show sRs' if and only if s,s'\in S_i for some i\in I is an equivalence relation.
This shows equivalence relations on S are in 1-1 correspondence with partitions of S.
Pivot tables use monoids to aggregate data. Suppose we have tick data for stock prices (t_j, s_j). We can partition the trading times \{t_j\} by years, months, days, etc. The high and low price apply max and min to all stock prices falling in a given partition. The open and close price apply min and max to the times in a given partition and return the corresponding stock price.
The first step in creating a pivot table is to specify a function. For the example above define S\colon T\to \boldsymbol{R} by S(t_j) = s_j. If \overline{T} is a partition of T and \mu is a commutative binary opreration on \boldsymbol{R} define \overline{S}\colon \overline{T}\to\boldsymbol{R} by \overline{S}(\overline{t}) = \mu^+(S(\overline{t})). This is how high and low are defined using max and min on \boldsymbol{R} respectively. We can also define \underline{S}\colon \overline{T}\to\boldsymbol{R} by \underline{S}(\overline{t}) = S(\mu^+(\overline{t})). This is how open and close are defined using min and max on T respectively.