Presentation of a Monoid

definition example theorem

A presentation of a Monoid consists of a set $G$ of generators and a set of relations $\{(m_i,m_i^{\prime })\}$, pairs of words $m_i,m_i^{\prime }\in \mathrm{List}(G)$. The presented monoid is

$$M:=\mathrm{List}(G)/\sim ,$$

the Free Monoid modulo the Equivalence Relation generated by $x{m}_{i}y\sim x{m}_i^{\prime }y$ for all words $x,y$ (relations may be applied inside longer words); the unit is the empty word and multiplication is concatenation of representatives. “Lists of generators provide all the possible ways to write elements of $M$; the relations allow two such ways to denote the same element.” A free monoid is the presented monoid with no relations; a monoid with a finite presentation is finitely presented. Presentations are to monoids what presentations are to categories: a finite description of a possibly infinite structure.

Sources: CTfS §3.1.1.9 (Definitions 3.1.1.10–3.1.1.14, Remark 3.1.1.15, Example 3.1.1.16, Application 3.1.1.17, Exercises 3.1.1.18–3.1.1.19), §3.1.1.20 (Definition 3.1.1.21, Example 3.1.1.22, Exercise 3.1.1.23), Example 3.1.2.9, Exercise 3.2.1.8, Slogan 4.2.2.1; 7 Sketches Examples 3.13, 3.18, Exercise 3.19 (the same idea for one-object categories); Presentation of a Prop for the monoidal version.

Buttons (CTfS Example 3.1.1.16)

Think of $G=\{a,b,c,d\}$ as buttons; $\mathrm{List}(G)$ is the set of all ways of pressing them. Suppose you notice that pressing $[a,a,c]$ always has the same effect as $[d,d]$, and that $[a,c,a,c]$ does nothing. With relations $[a,a,c]=[d,d]$ and $[a,c,a,c]=[]$:

$$[b,c,b,d,d,a,c,a,a,c,d]=[b,c,b,a,a,c,a,c,a,a,c,d]=[b,c,b,a,a,a,c,d]=[b,c,b,a,d,d,d].$$

Everyday presented monoids

• A buffer (CTfS Application 3.1.1.17): strings of at most 32 characters, where typing beyond 32 either overwrites the last character, $[a_1,\dots ,a_{32},b]{\sim }_1[a_1,\dots ,a_{31},b]$, or is discarded, $[a_1,\dots ,a_{32},b]{\sim }_2[a_1,\dots ,a_{32}]$ — both finitely presented ($26^{33}$ relations for 26 letters). With a buffer of size 3, $[a,b,c,d,e,f]=[a,b,f]$ under ${\sim }_1$ and $=[a,b,c]$ under ${\sim }_2$ (CTfS Exercise 3.1.1.18).
• A keyboard with backspace (CTfS Exercise 3.1.1.19): generators $\{\mathrm{BS},a,\dots ,z\}$ with relations $[x,\mathrm{BS}]=[]$ for every letter $x$, so $[a,b,d,\mathrm{BS}]=[a,b]$. Note that $[\mathrm{BS}]\ne []$ in this monoid — a backspace at the start of the text is remembered and will delete the next character typed before it. To make backspace on an empty line do nothing one needs a Monoid Action on texts rather than a monoid of keystrokes.
• A character in a video game (CTfS Example 3.1.2.9): generators up, down, right with $[u,d]=[d,u]=[]$, $[u,r]=[r,u]$, $[d,r]=[r,d]$ — the monoid $\mathbb{Z}\times \mathbb{N}$ of moves.
• Groups: the symmetries of a square are presented by $\rho ,\phi$ with ${\rho }^4={\phi }^2=\mathrm{id}$ and ${\rho }^3\phi =\phi \rho$ (CTfS Example 3.2.1.4, Group).

Cyclic monoids (CTfS §3.1.1.20)

A monoid is cyclic if it has a presentation with a single generator $Q$. Examples: no relations gives $(\mathbb{N},0,+)$ (CTfS Example 3.1.1.22); $Q=[]$ gives the trivial monoid; $Q^{12}=[]$ gives the clock $\mathbb{Z}/12$.

Classification (CTfS Exercise 3.1.1.23). Every cyclic monoid is isomorphic to exactly one of

• $\mathbb{N}$ (infinite), or
• $C_{n,k}:=⟨Q\mid Q^{n+k}=Q^n⟩$ for some tail $n\ge 0$ and cycle length $k\ge 1$, with the $n+k$ elements $Q^0,\dots ,Q^{n+k-1}$ — “rho-shaped”: a tail of length $n$ running into a cycle of length $k$.

(CTfS’s hint — “classified by $\mathbb{N}\bigsqcup \{\infty \}$” — is on the right track but one number is not enough: the tail and the cycle can vary independently.) Proof sketch. If the powers $Q^i$ are all distinct the monoid is $\mathbb{N}$. Otherwise let $n$ be the least exponent such that $Q^n=Q^{n+k}$ for some $k\ge 1$, and $k$ the least such; then $Q^i=Q^j$ iff $i=j$ or $i,j\ge n$ and $i\equiv j(\mathrm{mod}k)$. $■$ The cyclic groups are those with $n=0$: $\mathbb{Z}/k$ (and $\mathbb{Z}$, which as a monoid needs two generators) (CTfS Exercise 3.2.1.8). The same monoids appear as the one-object schema $\mathrm{Loop}$ with the PED $f^{n+k}=f^n$ (a finite hierarchy with $n$ management levels is $C_{n,1}$), and 7 Sketches Exercise 3.19’s $s^4=s^2$ is $C_{2,2}$.

Universal property

Monoid homomorphisms out of $⟨G\mid R⟩$ into $M^{\prime }$ are the functions $G\to M^{\prime }$ that send both sides of each relation to equal elements — freeness plus “check the equations”. This is exactly how functors out of a presented category and prop functors out of a presented prop are defined, and it makes “a database schema is a category presentation” precise (CTfS Slogan 4.2.2.1).

JuliaLeanHaskell

Docs: ThCategory (GATlab) · Theories & presentations

using Catlab
# A presented monoid is a presented category with one object. CTfS Example 3.1.2.9:
# up, down, right with [u,d] = [d,u] = [], [u,r] = [r,u], [d,r] = [r,d]
@present Moves(FreeCategory) begin
  Pos::Ob
  (u, d, r)::Hom(Pos, Pos)
  u ⋅ d == id(Pos); d ⋅ u == id(Pos)
  u ⋅ r == r ⋅ u;   d ⋅ r == r ⋅ d
end
# cyclic monoids C_{n,k} = ⟨Q | Q^(n+k) = Q^n⟩ computed by brute force: the powers of Q
function cyclic(n, k)
  normal(i) = i < n ? i : n + mod(i - n, k)      # the normal form of Qⁱ
  sort(unique(normal.(0:(n + 3k))))
end
cyclic(0, 12)          # 0:11, the clock ℤ/12
cyclic(2, 2)           # [0, 1, 2, 3]: 7 Sketches' s⁴ = s²

import Mathlib
#check @PresentedMonoid          -- the monoid FreeMonoid α ⧸ (congruence generated by rels)
#check @PresentedMonoid.toMonoid -- universal property: a map respecting the relations
#check @PresentedGroup           -- the group version
#check @FreeMonoid.lift          -- the free case

-- the backspace monoid by normal forms: a word is (number of pending backspaces, text)
data Key = BS | Chr Char deriving (Eq, Show)
newtype Typed = Typed (Int, String) deriving (Eq, Show)   -- BS^k followed by letters
 
press :: Typed -> Key -> Typed
press (Typed (k, s)) BS | null s    = Typed (k + 1, s)      -- nothing to delete: remember it
                        | otherwise = Typed (k, init s)     -- [x, BS] = []
press (Typed (k, s)) (Chr c) = Typed (k, s ++ [c])
 
typeWord :: [Key] -> Typed
typeWord = foldl press (Typed (0, ""))
-- typeWord [Chr 'a', Chr 'b', Chr 'd', BS] == typeWord [Chr 'a', Chr 'b']
-- typeWord [BS] /= typeWord []