Monoids for Free! (and other ways to earn a living)

I've been thinking recently about the free monoid, in particular about why it is what it is. Before you run off in fear of the terminology, read on. The rest of this post is in English, a rare thing for discussions of fundamentals of mathematics. It's that rareness which led me to muse on what all that abstract nonsense actually means.

For those who don't know what a monoid is, it's a triple <S, ⋅, ε> where S is a set, ⋅ is a binary operation over that set which is associative (i.e. (x ⋅ y) ⋅ z == x ⋅ (y ⋅ z)), and ε is the left and right identity of ⋅ (i.e. x ⋅ ε == x == ε ⋅ x). These kinds of functions are incredibly common. Semirings, which are also incredibly common, each have two. For example: addition with 0 and multiplication with 1 over the natural numbers; disjunction with False and conjunction with True over the booleans; union with the empty set and intersection with the universal set over the subsets of some universal set. Given how common they are, sometimes we'd like to construct an arbitrary one for as cheaply as possible, for free.

( Read more... )