Archive for February, 2016

ELI5: monoids

Monday, February 29th, 2016

(Resulting from my claim that “a child of 8 can understand monoids…”)

Wikipedia says: “In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single associative binary operation and an identity element.”

Wolfram says: A monoid is a set that is closed under an associative binary operation and has an identity element I ∈ S such that for all a ∈ S, Ia = aI = a.

Mathematics has to be precise, which is why it uses jargon. But what do these concise definitions mean in everyday language? Consider adding up numbers.

  • The set is the whole numbers (and we need zero). 0, 1, 2, 3 etc.
  • The associative binary operation is addition.
    • “binary” just means it’s a thing you do to two numbers.
    • “associative” means it doesn’t matter what order you group things in. 1 + 2 + 3 gives the same answer whether you add 1 and 2 first and then add 3, or add 2 and 3 first and then add the answer to 1.
  • The set being “closed” under addition means that when you add two numbers you get another number – you don’t get some other kind of thing. (You might think this is obvious, but in maths it has to be stated.)
  • The identity element is 0 – the thing that doesn’t make any difference when you add it. Anything plus zero is itself.

So adding whole numbers is a monoid. A mathematician would say that the non-negative integers form a monoid under addition. The important thing is that the numbers aren’t a monoid on their own; it’s the combination of the set (0, 1, 2, 3…) and the operation (+) that makes the monoid. If we chose another operation, we could get another monoid. Think about multiplication, for instance.

It turns out that lots of things behave the same way as addition on numbers, which is why the notion of a monoid is very useful to mathematicians and computer scientists.