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. For example, "man", "bear", and "pig" are all elements of L* over the English alphabet, so we can concatenate them and produce another element of L*:

("man" ++ "bear") ++ "pig" = "man" ++ ("bear" ++ "pig") = "manbearpig"

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.

Commutative monoids

A monoid is commutative when m(x, y) ≈ m(y, x). Commutative monoids tend to be simpler than monoids, and sometimes the idea that a monoid is not commutative is important for refuting a claim. N is commutative.

Free monoids

Main article: wikipedia:free monoid

In mathematics, the elements of a free mathematical structure are distinct by default and only equal 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. For example, 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)) ≈ m(m(1, 2), 2) because one of the monoid laws is that m is associative.

Any set A can be used as a set of generators of a free monoid, which we will always denote A*. One way to think of A* is as 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.

From here, we will adopt some standard notation and definitions. An element of A* is called a word. The length of a word w is notated as |w|. A root of w is another word z such that w ≈ z × k for some natural number k, usually with non-zero k; in other words, w is equivalent to k concatenated copies of z.

Definition. A word is primitive if it is the empty word or has no roots.

Intuitively, there is one primitive word per generator as well as one for the empty word. We will make this more detailed later.

The number of generators is important. A free monoid with one generator is commutative, and the converse is true too.

Lemma. A free monoid is commutative if and only if it has at most one generator.

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.

Presentations

Main article: wikipedia:presentation of a monoid

We can declare that two words are equivalent. For example, consider N where 0 ≈ 3. Then the elements of the monoid are 0, 1, 2, 3 ≈ 0, 4 ≈ 1, 5 ≈ 2, 6 ≈ 0, etc. By adding this additional equivalence, the structure of the monoid is limited to something smaller than it originally was. In our example, N has infinitely many elements, but N where 0 ≈ 3 has only three elements.

A presentation of a monoid is a monoid and some equivalences. We will notate presentations as <M|R> where R is an equivalence relation and M is a monoid. Our example monoid could be notated as <N|0 ≈ 3>. When a monoid is equivalent to some presentation, it is called presentable or a quotient.

Rank

Often we are interested in a monoid subset: not all of the words, but only words which fit some rule. In particular, when studying a free monoid or presentation, we only care about words which fit some grammar.

If we can construct some word w from a monoid subset X then we say that X factorizes w. Note carefully what this means; X does not contain w, but the free monoid X* does. A monoid subset is simplifiable if there is another subset which factorizes all of its words.

Perhaps we don't care exactly what the subset is, but we want to only know its cardinality. After all, as computer scientists, we aren't scared of reassigning syntax. So, we can define the rank of a monoid subset as the smallest free monoid simplifying it, regardless of exactly what's in that subset.

Definition (factorization). X factorizes w if and only if w is a word of X*.

Definition (simplification). Y simplifies X if and only if X ⊆ Y* ⊆ A*.

Definition (rank). r(X, A*) = minimum{ |Y| : X ⊆ Y* ⊆ A* }.

Here are some facts about rank. Let Y=A; A* simplifies X, although it may not be the minimum. Also, X* simplifies X. So:

Theorem. r(X, A*) ≤ minimum{ |A|, |X| }.

Theorem (rank is increasing). If X and Y are monoid subsets of A* and X ⊆ Y then r(X, A*) ≤ r(Y, A*). (Neraud, 1992)

Theorem (rank of intersections). r(X & Y, A*) ≤ minimum{ r(X, A*), r(Y, A*) }. (Neraud, 1992)

Theorem (rank of unions). maximum{ r(X, A*), r(Y, A*) } ≤ r(X | Y, A*) ≤ r(X, A*) + r(Y, A*). (Neraud, 1992)

We can upgrade the commutative lemma from earlier. To understand the forward implication, note that regardless of which word w we choose in X, we can always use X* to describe the possible words built from copies of w.

Lemma. A free monoid X* is commutative if and only if r(X, A*) ≤ 1.

Concatenating a subset with itself repeatedly doesn't increase its rank. Indeed, we will generally take X to be as small as possible and not contain any factorizable words because of the following theorems.

Theorem (rank of X(k)). For any non-zero natural number k, Let X(k) be the monoid subset where each word is k concatenations of words in X. r(X(k), A*) = r(X, A*). (Neraud, 1992)

Theorem (rank of X*). r(X*, A*) = r(X, A*). (Neraud, 1992)

Rank interacts with presentations. Intuitively, adding more equivalences to a presentation cannot increase the overall number of words.

Theorem. For equivalence relations R and S on a monoid M with S ⊆ R and all monoid subsets X ⊆ M, r(<X|R>, M) ≤ r(<X|S>, M).

Corollary. For any equivalence relation R on a monoid M and all monoid subsets X ⊆ M, r(<X|R>, M) ≤ r(X, M).

NP-completeness

Simplification and rank are expensive to compute.

Theorem. It is NP-complete whether a monoid subset is simplifiable. (Neraud, 1990)

Theorem. It is NP-complete whether a monoid subset X of a monoid A* has r(X, A*) ≤ k < |A*| for natural k. (Neraud, 1990)

However, the rank of a monoid subset can be computed with a fairly cheap algorithm when all of its words have exactly two letters.

Theorem. Let X be a finite subset of a free monoid A* where every word has length 2. r(X, A*) is computable in quadratic time, O(|X|²). (Neraud, 1990)

Simple translations

Main article: simple translation

Let A and B be monoids. A simple translation is a pair of equivalence relations R and S such that <A|R> is isomorphic to <B|S>.

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.