Monoid

This is still a work in progress. It may be changed in the future.

A monoid is an elementary structure consisting of:

• a set S with equality ≈,
• a binary operation m : S × S → S, where
• m(x(m(y,z)) ≈ m(m(x,y),z) for all x, y, z : S, and
• an element i : S such that m(i,x) ≈ m(x,i) ≈ x for all x : S.

i is known as the identity. The third rule states that m is associative.

Monoids are ubiquitous throughout mathematics and play a foundational role in understanding formal grammars.

Introduction

Monoids are one of several ways to glue together multiple objects. The ingredients of a monoid give:

• a collection of things that can be glued and a rule for determining when things are equivalent,
• an operation that glues two things together to make a third thing,
• a rule that gluing a tree of things is equivalent to gluing a sequence of things, and
• no thing, a thing which disappears when glued to any other thing.

As an important example, consider a set of letters L drawn from an alphabet. The set of strings L* is a monoid. Its ingredients are:

• L* with the standard equality on strings,
• m(x,y) = x ++ y,
• string concatenation is associative; (x ++ y) ++ z = x ++ (y ++ z) = x ++ y ++ z, and
• i = "", the empty string.

We say that L* is the free monoid on L. Free monoids are an example of syntactic monoids; the easiest way to work with a syntactic monoid is to think of its elements as strings of text.

Not all monoids are syntactic. For example, the natural numbers form a monoid under addition with 0 as the identity element. Because the natural numbers are semantic objects, this is an example of a semantic monoid. Manipulating a semantic monoid requires using the tools of the semantic domain, rather than text-processing tools. More formally, let:

• N be the natural numbers with the standard (primitive-recursive) equality,
• m(x,y) = x + y,
• (x + y) + z = x++ (y + z) = x + y + z, and
• i = 0.

Free monoids

Main article: wikipedia:free monoid

In mathematics, a "free" mathematical structure is one in which two elements of the structure are known to be different except in cases where they can be proven equal using the rules of that type of structure. For example, a free monoid is a monoid for which, given two elements defined in terms of elements taken from a set of "generators" and the m operation, the results will always be different unless they can be proven equal using the monoid rules, e.g. a free monoid on generators {1, 2} would contain i, 1, 2, m(1, 2), m(1, m(2, 2)), etc. as distinct elements, but m(1, m(2, 2)) would be the same element as m(m(1, 2), 2) because m is associative.

For any set A, it can be used as a set of generators of a free monoid in order to produce a monoid A*, which turns out to just be the set of ordered lists of elements of A. The binary operation is list concatenation (which is associative); the identity element is the empty list.

Since the ordered lists of a set are also a set, there is a forgetful right-adjoint functor from monoids to sets. The monad generated by the composition of adjoint functors is called the list monad and is studied as a model of non-determinism.

Rank

...

Simple translations

Main article: simple translation

...

Concatenative languages

Main article: concatenative language

...

Word problems

...

Beyond sets

For languages which do not have set-valued semantics, the existence of semantic free monoids is connected to the existence of a natural numbers object (NNO) which can index ordered lists:

Proposition (Johnstone, 1977). A topos has an NNO if and only if its category of internal monoids has a free left-adjoint functor.

For example, consider a type theory with a hierarchy of universes. The types of such theories might not be sets. Nonetheless, they often have a type of natural numbers which facilitates the construction of free monoids.