Monoids, groups & actions
Binary operations and the invertibility axis; why processing is a monoid not a group; presentations and the word problem; group actions and symmetry.
A signal-processing pipeline is a sequence of stages you apply in order: gain, then saturate, then quantize, then downsample. You can always glue two pipelines end to end, the empty pipeline does nothing, and — crucially — you usually cannot run the pipeline backwards (the quantizer alone has thrown away the low bits). That last clause is the whole story of this module. The algebra of “compose, but don’t assume you can undo” is a monoid, and the single most important claim of the entire reference is that processing is a monoid, not a group.
Here path-dependence and irreversibility acquire exact algebraic addresses: order-sensitivity is non-commutativity, the inability to undo is the failure of cancellation, and both appear the moment you refuse to assume inverses.
One operation: from binary op to monoid
Strip everything down to a single set \(S\) of “states” and one rule for combining two things into a third of the same kind. Formally a binary operation is a function \(\mu\colon S\times S\to S\), written \(\mu(a,b)=ab\); the codomain being \(S\) again is the closure axiom — a step followed by a step is still a step.
Two axioms turn this into the object we want.
- Associativity: \((ab)c=a(bc)\). This is about bracketing, not reordering. It is exactly what lets us write a recipe as an unambiguous word \(a_1a_2\cdots a_n\) with no parentheses. It is the shadow of function composition, where \((h\circ g)\circ f=h\circ(g\circ f)\) always holds.
- Identity: an element \(e\) with \(ea=ae=a\) — the do-nothing step, the empty recipe. It is unique if it exists.
A set with just an associative operation is a semigroup (the minimum needed to speak of sequences). Add a two-sided identity and you have a monoid \((M,\mu,e)\); the category of monoids is \(\mathsf{Mon}\). A monoid need not have inverses, and that omission is deliberate, not a defect.
Intuition. A monoid is the algebra of composable, order-sensitive, possibly-irreversible actions. The prototype to keep in mind: all functions \(X\to X\) under composition. Monoids are nothing but abstract collections of self-maps — and self-maps generally lose information.
Three canonical examples recur throughout: \((\mathbb{N},+,0)\); the endomorphisms \(X\to X\) under \(\circ\); and strings under concatenation (the free monoid, below). Operations on material states are the second kind — endomorphisms of a state space, composed in sequence.
The invertibility axis: monoid vs group
Now ask the one structural question that organizes this whole subject: does every element have an inverse?
An element \(a\) is invertible if some \(a^{-1}\) satisfies \(aa^{-1}=a^{-1}a=e\) (unique when it exists). In any monoid the invertible elements form a group, the group of units. A group is a monoid in which every element is invertible; its category is \(\mathsf{Grp}\).
As the figure shows, two independent axes generate a 2×2 of structures. Horizontally: drop the inverse requirement and you step from group to monoid. Vertically (anticipating categories): allow more than one object and a monoid becomes a category, a group becomes a groupoid. Processing lives in the left column — non-invertible — and as soon as there are several distinct material types it lives in the bottom-left cell, a genuine category.
There is even a canonical way to force inverses: every monoid \(M\) has a universal group completion \(K(M)\) with a map \(M\to K(M)\) — for \((\mathbb{N},+)\) it produces \((\mathbb{Z},+)\). But this map generally loses information: distinct processes collapse to one element once you pretend everything is reversible. (It is a free construction, an adjoint to forgetting, in the sense of free objects.)
In the synthesis. This axis is P2 (composition + irreversibility). Modeling processing as a group silently discards the very irreversibility you are trying to capture. Groups are the wrong model for recipes but the right model for symmetry of configurations — reversible relabelings — which is why they return later for counting microstructures (P4/P13). Keep the two uses separate: a group for symmetry, a monoid for process.
Cancellation, order, and the signatures of irreversibility
The abstract definitions above acquire physical meaning through two failure modes.
Cancellation. A monoid is left-cancellative if \(ab=ac\Rightarrow b=c\) — intuitively, “\(a\) destroyed no information, so we can read \(b\) and \(c\) off the results.” Invertible elements are always cancellable, but in a general monoid the converse fails.
A hard reset. Take the monoid of self-maps of a two-state set \(\{s_0,s_1\}\) and let \(a\) be the constant map sending everything to \(s_0\) — a register clear, a clamp-to-zero, a ReLU saturated into its dead zone. Then \(a b = a c\) for distinct maps \(b\ne c\): whatever distinction \(b\) and \(c\) produced, \(a\) erased it. A step that drives every input to the same fixed value — a hard reset — is exactly such a non-cancellative element. This is precisely why \(M\to K(M)\) must collapse things: a group is cancellative, so it cannot host a lossy step.
So failure of cancellation = information loss = irreversibility (P2), made algebraic.
Commutativity. A monoid is commutative (abelian) if \(ab=ba\) for all \(a,b\) — rare in processing. It is non-commutative when some \(a,b\) have \(ab\ne ba\): for a robot, rotate then translate \(\ne\) translate then rotate, and two rotations in \(\mathrm{SO}(3)\) generally fail to commute (the gimbal). Function composition — and matrix multiplication, \(AB\ne BA\) — is the canonical non-commutative operation.
In the synthesis. Non-commutativity is P1 (path-dependence): order is a primary feature of recipes, not noise. Cancellation-failure is P2. The two are independent knobs, and the commutator and abelianization below will quantify the first.
Pitfall. Associativity is not commutativity. Associativity (\(abc\) is unambiguous) holds for processing; commutativity (order doesn’t matter) generally does not. Conflating them is the single most common error here.
Bridge. The phenomenology this formalizes — thermal history, shear history, the fact that the same ingredients in a different order give a different coating — is the subject of the materials chapter on processing. Here we name the structure; there you see it on the bench.
Maps, kernels, and the canonical factorization
To compare two process algebras, or to model one inside another, we need structure-preserving maps. A homomorphism \(\varphi\colon M\to N\) satisfies \(\varphi(ab)=\varphi(a)\varphi(b)\) and \(\varphi(e_M)=e_N\); it is fully determined by its values on generators.
Every homomorphism comes with two invariants:
- the image \(\operatorname{im}\varphi=\{\varphi(a)\}\), a sub-object of \(N\) — the honestly reachable algebra inside the target;
- the kernel, which measures what is identified. For groups this is \(\ker\varphi=\{a:\varphi(a)=e\}\), a normal subgroup. For monoids one element is not enough — you must track the whole kernel congruence \(a\sim b\iff\varphi(a)=\varphi(b)\).
A congruence is an equivalence relation compatible with the operation (\(a\sim a'\), \(b\sim b'\Rightarrow ab\sim a'b'\)), and it is exactly what you need to form a quotient. For groups, congruences correspond bijectively to normal subgroups \(N\trianglelefteq G\) (those with \(gNg^{-1}=N\) for all \(g\)), and the quotient is \(G/N\) with \((aN)(bN)=(ab)N\); the projection \(q\colon G\to G/N\) has \(\ker q=N\). Cosets \(gH\) partition \(G\) into equal blocks, giving Lagrange’s count \(|G|=|H|\,[G:H]\).
This machinery assembles into one theorem that we have already met for sets and functions and will meet again for modules: the first isomorphism theorem.
Theorem (First isomorphism / canonical decomposition). Any homomorphism factors as \[\varphi\colon\; G \;\twoheadrightarrow\; G/\ker\varphi \;\xrightarrow{\ \cong\ }\; \operatorname{im}\varphi \;\hookrightarrow\; H,\qquad\text{so}\qquad G/\ker\varphi\;\cong\;\operatorname{im}\varphi.\] Read left to right: collapse what cannot be distinguished, faithfully rename what remains, then embed into the target.
The same three-step shape is clearest as a commuting diagram:
\[\begin{CD} G @>{\varphi}>> H \\ @V{q}VV @AA{\iota}A \\ G/\ker\varphi @>>{\cong}> \operatorname{im}\varphi \end{CD}\]
In the synthesis. This is P3 (mediation through a hidden intermediate). Any model or translation \(\varphi\) of a process algebra automatically factors through a canonical quotient — a forced intermediate representation determined by what the map identifies. The kernel quantifies the information the model discards (the engine of degeneracy classes, P4), and recognizing the middle object is how you find the “real” reduced description hiding inside a messy mapping.
Recipes as words: free monoids, presentations, the word problem
Where do process algebras come from? From a menu of unit operations. A subset \(X\) generates \(M\) when every element is a finite product of elements of \(X\); the unit operations are the generators of the whole process monoid — a finite menu describing an unbounded space of recipes (RD2).
The most generic monoid on an alphabet \(\Sigma\) is the free monoid \(\Sigma^{*}\): all finite words, operation = concatenation, identity = the empty word \(\varepsilon\). It is the maximally non-commutative monoid on \(\Sigma\), and it has a defining universal property:
Definition (Free monoid). For any monoid \(N\) and any function \(f\colon\Sigma\to N\), there is a unique homomorphism \(\bar f\colon\Sigma^{*}\to N\) extending \(f\). (Adding formal inverses with only \(aa^{-1}=a^{-1}a=\varepsilon\) gives the free group \(F(\Sigma)\).)
This property is the rigorous version of “define your operations, get all recipes for free.” Interpreting a recipe is a homomorphism \(\Sigma^{*}\to\operatorname{End}(\text{states})\): assign each letter an action on the state space, and the universal property hands you the action of every word automatically — exactly the recipe-algebra pattern of RD2.
Real recipes have rules, though: some steps commute, some are idempotent, some pairs undo. We impose them as relations. A presentation \(\langle\Sigma\mid R\rangle=\Sigma^{*}/\!\sim_R\) is the free monoid quotiented by the smallest congruence containing the relation pairs \(R\) — “building blocks plus rules of the game.” Two words are equal precisely when one can be rewritten into the other by finitely many applications of the relations.
Pitfall (the word problem). Deciding whether two words denote the same element — the word problem — is undecidable in general (Novikov–Boone, for groups and likewise monoids). You cannot assume a generic algorithm exists. The good news is a signpost: restricting the kind of relations buys back computability. Trace monoids — where you set only selected commutators to the identity — are a decidable fragment handled by confluent terminating rewriting, treated in computation & locality.
Actions, symmetry, and decomposition into atoms
A monoid earns its keep by acting. An action of \(M\) on a set \(X\) is a map \(M\times X\to X\) with \(e\cdot x=x\) and \(a\cdot(b\cdot x)=(ab)\cdot x\) — equivalently a homomorphism \(M\to\operatorname{End}(X)\). Through the lens that a monoid is a one-object category \(\mathsf{B}M\) (its single object’s self-arrows are the elements of \(M\)), an action is exactly a functor \(\mathsf{B}M\to\mathsf{Set}\); if \(M\) is a group, \(\mathsf{B}M\) is a one-object groupoid and the functor lands in bijections \(\operatorname{Sym}(X)\). A monoid action need not — and that is the natural model when steps are lossy.
In the synthesis. This is the central dynamical model: operations act on material states by (generally non-invertible) endomorphisms, and a recipe’s effect is the composite endomorphism. The orbit \(O(x)\) — states reachable from \(x\) — partitions \(X\) for a group but is only a one-directional preorder for a monoid, which is precisely irreversibility (P2) showing up in the reachability geometry. The stabilizer \(\operatorname{Stab}(x)\) collects operations fixing \(x\).
For genuine symmetries (a group action), orbit counting is sharp: orbit–stabilizer gives \(|O(x)|=[G:\operatorname{Stab}(x)]\), and Burnside’s lemma \[|X/G|=\frac{1}{|G|}\sum_{g\in G}\bigl|\operatorname{Fix}(g)\bigr|\] counts configurations modulo symmetry — distinct microstructures up to relabeling (P4/P13). Note this is a group technique: symmetry is reversible, complementing the monoid model of processing.
Two further constructions quantify and decompose.
Commutator and abelianization. The commutator \([a,b]=aba^{-1}b^{-1}\) measures the gap between do \(a\) then \(b\) and do \(b\) then \(a\): it is the identity iff they commute. The commutator subgroup \([G,G]\) is normal, and the abelianization \(G^{\mathrm{ab}}=G/[G,G]\) is the largest abelian quotient — the canonical “forget the order” projection (for monoids, \(\Sigma^{*}\twoheadrightarrow\mathbb{N}^{\Sigma}\), “count each operation, discard order”). This is the quantitative face of P1: comparing a process algebra to its abelianization tells you exactly how much order matters — what is lost if you wrongly treat a recipe as an unordered bag of steps. (Trace monoids again sit in between, killing some commutators and keeping others.)
Atoms and gluing. A simple object has no nontrivial proper quotient — an algebraic atom. A composition series \(\{e\}=G_0\trianglelefteq\cdots\trianglelefteq G_n=G\) has simple factors \(G_{i+1}/G_i\), and the Jordan–Hölder theorem says any two such series have the same factors up to order and isomorphism: the decomposition into atoms is a canonical multiset invariant.
In the synthesis. This is P11 (canonical decomposition into irreducible atoms) — but with a sharp caveat. The factors do not determine \(G\): \(\mathbb{Z}/4\) and the Klein four-group share the same factors yet differ. You also need the gluing data, packaged as an extension \(1\to N\to G\to Q\to 1\). The reconstruction spectrum runs direct product (no interaction) \(\subset\) semidirect product \(N\rtimes_\theta Q\) (one-sided coupling via \(\theta\colon Q\to\operatorname{Aut}(N)\)) \(\subset\) general non-split extension (inseparable entanglement) — also the coupling hierarchy of P8. The slogan: atoms plus gluing, never atoms alone.
Finally, the group axioms (multiplication, unit, inverse) can be written purely as commuting diagrams in any category with finite products, giving a group object: read the template in \(\mathsf{Set}\) for ordinary groups, in \(\mathsf{Top}\) for topological groups, in smooth manifolds for Lie groups. Dropping only the inverse arrow yields a monoid object. One template, many domains — P7 in its purest form, the archetype behind “transfer = functoriality.”
Recap
- Processing is a monoid, not a group. Steps compose and associate (a recipe is a well-defined word), there is a do-nothing identity, but inverses are not assumed — and that single omission is the home of irreversibility (P2).
- Two failure modes carry the meaning. Non-commutativity (\(ab\ne ba\)) is path-dependence (P1); failure of cancellation (\(ab=ac\) with \(b\ne c\)) is information loss / irreversibility (P2). They are independent.
- The invertibility axis organizes everything: drop inverses (group→monoid), add objects (→category/groupoid). Group completion \(M\to K(M)\) exists but discards exactly the irreversibility you care about.
- Every map factors canonically as collapse–rename–embed (\(G/\ker\varphi\cong\operatorname{im}\varphi\)): the forced hidden intermediate of P3, with the kernel measuring discarded information.
- Recipes are words modulo relations. \(\Sigma^{*}\) is the raw recipe algebra (RD2); presentations \(\langle\Sigma\mid R\rangle\) add process identities; the word problem is undecidable in general, with trace monoids a decidable fragment.
- Actions, symmetry, atoms. Operations act as endomorphisms (monoid action, irreversible); symmetry is counted by Burnside (group action, reversible); Jordan–Hölder gives canonical atoms (P11) but reconstruction also needs the extension/gluing data (P8).
Part of a four-document set: the ARiSE draft (problem + AI solution), this modular Mathematics reference, the companion materials reference, and the synthesis. Generated from modular Markdown with a custom static-site builder.
Mathematics is typeset with MathJax (loaded once from a CDN with Subresource Integrity; needs network on first view). Diagrams are inline SVG and follow the light/dark theme. Keyboard: / search · [ ] prev/next · t theme.