Monoid Action

definition example theorem

An action of a Monoid $(M,e,\star )$ on a set $S$ (an $M$-set) is a function $\circlearrowleft :M\times S\to S$ such that for all $m,n\in M$, $s\in S$:

$$e\circlearrowleft s=s,m\circlearrowleft (n\circlearrowleft s)=(m\star n)\circlearrowleft s.$$

(This is a left action; a right action satisfies $m\circlearrowleft (n\circlearrowleft s)=(n\star m)\circlearrowleft s$.) Category Theory for Scientists’ reading: “a common way to interpret phenomena we see around us is to say that agents are acting on objects” — the monoid records what the agent can do and how sequences of actions compose, the set records the states of the object. Categorically, an action is a Functor $\mathcal{M}\to \mathbf{Set}$ from the monoid viewed as a one-object category: the one object goes to $S$, each $m$ to the function $m\circlearrowleft -:S\to S$ (by Currying), and the two laws are preservation of identity and composition.

Sources: CTfS §3.1.2 (Definition 3.1.2.1, Remark 3.1.2.2, Examples 3.1.2.3, 3.1.2.9, Application 3.1.2.6, Remark 3.1.2.7, Exercises 3.1.2.4–3.1.2.5), §3.1.3 (action tables), §3.1.4.11 (restriction of scalars, Proposition 3.1.4.12, Examples 3.1.4.13–3.1.4.14, Exercise 3.1.4.15), §3.2 (group actions), §4.2.1.1, Example 3.5.3.3, Application 4.3.1.2; DaoFP §15.3 ($M$-sets and the Writer Monad); Kittenlab Lecture 5.

Examples

• The clock (CTfS Example 3.1.2.3): $(\mathbb{N},0,+)$ acts on $\{0,\dots ,11\}$ by $n\circlearrowleft s=(n+s)\mathrm{mod}12$ — $4\circlearrowleft 2=6$, $8\circlearrowleft 9=5$; $(\mathbb{R},0,+)$ acts on the continuous clock face $[0,12)$ (“the monoid of time acting on the clock”), which is a Coequalizer of $x\mapsto x$ and $x\mapsto x+12$ on $\mathbb{R}$ (CTfS Exercise 3.1.2.4).
• Video games (CTfS Exercise 3.1.2.5): the free monoid $\mathrm{List}(B)$ on the buttons of a controller acts on the states of a simple game; a button that never changes the state does nothing, and a state that no sequence of buttons changes is a game over screen. Games whose response depends on timing, not just on the sequence of presses, are not such actions.
• Newton’s method (CTfS Application 3.1.2.6): $x_{n+1}=x_n-f(x_n)/f^{\prime }(x_n)$ is an action of $\mathbb{N}$ (one generator) on $\mathbb{R}$; adding “perturb left/right” generators to escape critical points and oscillation gives a bigger, less deterministic monoid. Publishing which monoid was used is part of reproducibility: “by using the language of monoid actions, we can align our data model with our unspoken assumptions”.
• Finite state machines: an action of a free monoid $\mathrm{List}(\Sigma )$ on a finite set — the slogan of Finite State Machine.
• A monoid acts on itself by multiplication; CTfS’s multiplication table of $(\mathbb{N},1,\ast )$ has a column per generator (“applying column 2 and then column 2 returns the same as applying column 4”).
• Symmetry: a Group Action is an action in which every agent’s move can be undone — rotations of the earth, permutations, symmetries of a crystal.
• Vector spaces: the multiplicative monoid of scalars acts on the vectors.

Action tables and ologs

If $M$ is generated by $g_1,\dots ,g_m$, an action on a finite set is recorded by an action table with one row per state and one column per generator (CTfS §3.1.3); the table for all of $M$ is obtained by composing columns. In database terms this is an instance on the one-object schema whose arrows are the generators (C-Set, CTfS Example 3.5.3.3), and as an Olog it has a single box: “a character position when moved up results in a character position”, with facts such as $[\text{up},\text{down}]=[]$ and $[\text{up},\text{right}]=[\text{right},\text{up}]$ (CTfS Example 3.1.2.9). If every column is a permutation of the rows, the action factors through a group (CTfS Exercise 3.5.3.5).

Remark (CTfS 3.1.2.7). In a monoid action every action is available in every state. “In reality it is often the case that contexts can change and different actions are available at different times; the commands of one application have no meaning in another.” Allowing several objects — several kinds of state — turns the monoid into a Category and the action into a functor to $\mathbf{Set}$: that is where CTfS’s Chapter 4 begins.

Restriction of scalars

A monoid homomorphism $f:M\to M^{\prime }$ turns any $M^{\prime }$-action $\alpha$ into an $M$-action ${\Delta }_f(\alpha )(m,s):=\alpha (f(m),s)$ (CTfS Proposition 3.1.4.12): “take an element of $M$, send it over to $M^{\prime }$, and act”. Restricting the $\mathbb{Z}$-action on $\mathbb{R}$ by translation to $\mathbb{N}\subseteq \mathbb{Z}$; restricting complex scalars to real ones turns a complex vector space into a real one — hence the name. Along $\mathbb{N}\to \mathrm{List}(\{a,b\})$, $1\mapsto [a,b,b]$, a state machine becomes a single “macro” button (CTfS Exercise 3.1.4.15). In functor language restriction of scalars is precomposition ${\Delta }_f=-\circ f$, the simplest Data Migration Functor, and it has adjoints ${\Sigma }_f⊣{\Delta }_f⊣{\Pi }_f$ (induction and coinduction of representations).

Morphisms of actions

An equivariant map $h:S\to S^{\prime }$ between $M$-sets satisfies $h(m\circlearrowleft s)=m\circlearrowleft h(s)$ — a Natural Transformation between the functors $\mathcal{M}\to \mathbf{Set}$. For state machines this is “a refinement of one model by another” (CTfS Application 4.3.1.2, worked out in Natural Transformation). $M$-sets and equivariant maps form the Topos ${\mathbf{Set}}^{\mathcal{M}}$; its free objects $S\times M$ give the Writer Monad.

JuliaLeanHaskell

Docs: ACSets API · Theories & presentations — Kittenlab Lecture 5

using Catlab
# A monoid action is an instance on a one-object schema (CTfS Example 3.5.3.3):
# the clock, an action of (ℕ, 0, +) generated by "advance one hour".
@present SchClock(FreeSchema) begin
  Hour::Ob
  tick::Hom(Hour, Hour)
end
@acset_type Clock(SchClock)
C = @acset Clock begin Hour = 12; tick = [2:12; 1] end   # row h+1 is the hour h ∈ {0,…,11}
act(n, h) = foldl((i, _) -> C[i, :tick], 1:n; init = h + 1) - 1   # n ⋅ h = tickⁿ(h)
act(4, 2), act(8, 9), act(12, 5)                                  # (6, 5, 5)
# restriction of scalars along the homomorphism ℕ → ℕ, n ↦ 3n: "advance three hours at a time"
act3(n, h) = act(3n, h)
act3(1, 11)                                                       # 2

import Mathlib
#check @MulAction                 -- class: one_smul, mul_smul (a left action)
#check @MulAction.compHom         -- restriction of scalars along a monoid hom
#check @MulActionHom              -- equivariant maps  X →[M] Y
-- every monoid acts on itself; the clock face ZMod 12 acting on itself by addition
example : AddAction (ZMod 12) (ZMod 12) := inferInstance
#check @CategoryTheory.SingleObj  -- a monoid as a one-object category; actions ↔ functors to Type

{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances #-}
-- a left action of a monoid m on a set s
class Monoid m => Action m s where
  act :: m -> s -> s          -- laws: act mempty = id,  act (m <> n) = act m . act n
 
newtype Hours = Hours Int deriving Show
instance Semigroup Hours where Hours a <> Hours b = Hours (a + b)
instance Monoid Hours where mempty = Hours 0
 
newtype Clock = Clock Int deriving Show
instance Action Hours Clock where
  act (Hours n) (Clock s) = Clock ((n + s) `mod` 12)
 
-- restriction of scalars along a monoid homomorphism f
restrict :: (Action m' s) => (m -> m') -> m -> s -> s
restrict f m = act (f m)