Monoids are the formal concept of "and then." You've got some set of things \(S\), and you can put two of them together to get another thing in \(S\). If \(S\) is actions, then doing one "and then" the other is a new action, so it's also in \(S\). Monoids also have something in \(S\) for "doing nothing," so if you "do nothing and then" something, you only did one thing, and if you do something "and then do nothing," you only did one thing. If we call our "and then" operator \(\otimes\), and our "do nothing" element \(e\), then we write the monoid \((S,\otimes,e)\).
To properly capture the idea of "and then," we need to say that \(\otimes\) is associative, and that \(e\) is an identity for \(\otimes\). That just means three equations need to be true: \(a\otimes(b\otimes c)=(a\otimes b)\otimes c\), \(e\otimes a=a\), and \(a\otimes e=a\).
The most common example of a monoid is the set of natural numbers with addition, \((\mathbb{N},+,0)\). We can also use multiplication, \((\mathbb{N},\times,1)\). For addition, the idea is that \(2+3\) is \(2\) "and then" \(3\), which, by choosing \(+\), we've defined to mean \(5\). When we choose multiplication instead, \(2\) "and then" \(3\) means \(6\) instead. And notice how the "do nothing" element changed as well.
The "do nothing" element is formally called the "identity" element or "neutral" element. The "and then" thing is formally called the "operator" or "product." The set of things is formally called the "underlying set" or "carrier set."
Notice that not all monoids are commutative; that is, \(a\otimes b\) doesn't always equal \(b\otimes a\). In general, \(a\) "and then" \(b\) is not the same as \(b\) "and then" \(a\). An example follows.
The most representative monoid for a set \(S\) is the set of lists of elements of \(S\). This is formally called the "free monoid" for \(S\), since we can generated a monoid "for free" from the elements of \(S\) using lists. If \(S\) is \(\mathbb{N}\), then some example elements in the carrier set of the free monoid are \([1,1,7]\) and \([9,3]\). Putting them together gives \([1,1,7,9,3]\), this is formally called "concatenation." The identity element is the empty list, \([]\). Writing \(\oplus\) for concatenation, the free monoid is \(([S],\oplus,[])\). Notice that this monoid operator is not commutative, since \([1,1,7]\oplus[9,3]\) is not the same as \([9,3]\oplus[1,1,7]\).
Why are lists the most representative monoid for a set? Any monoid whose carrier set is \(S\) can be seen as an equivalence class of the free monoid. For example, \((\mathbb{N},+,0)\) can be seen as (\([\mathbb{N}],\oplus,[]\)), except that we consider two lists equivalent when their sums are equal. So \([1,1,7]\equiv[9]\equiv[5,0,4,0,0]\), etc. When we add these equivalences, concatenation behaves just like addition, and the empty list behaves just like zero. As another example, you can hopefully see how seeing lists as equivalent when their products are equal then gives the multiplication monoid \((\mathbb{N},\times,1)\).
A generalization of monoids is a "category," which perhaps encodes the idea of "and then" even better than monoids do. In a category, it's like the things are jigsaw-puzzle pieces, and the "and then" operation (called "composition," written \(a\circ b\)) is gluing them together. It's a generalization of monoids because pieces can only be put together when their edges match up: \(a\) might have an \(x\) edge on the left and a \(y\) edge on the right, so \(a\circ b\) is only possible if \(b\) has a \(y\) edge on the left. For categories we write things like \(a:x\to y\) to talk about the left and right edges of \(a\). The identity element has matching edges on both sides, but now there's an identity element for every kind of edge. A category becomes a monoid when all the edges on all the pieces are the same, so there's only one kind of edge and any two objects can be put together in either order to make a third object.
© 2024 Ryan Brewer.