3.6. Actions of monoids and categories

Actions of monoids

Since monoids lost their role as sets of transformations, such a role can be given back to them as follows.
An action (or left action) of a monoid (M,e, •) on a set X, is an operation ⋅ : M×XX such that ∈ Mor{e,•}(M, XX) : Examples:

Acts as algebraic structures

For any sets M, X with M-algebra structures • : M×MM and ⋅ : M×XX (seeing M as a set of function symbols), ∀xX,

x(e) = xex = x
x ∈ MorM(M,X) ⇔ ∀a,bM, (ab)⋅x = a⋅(bx)
e = IdM ⇔ (∀aM, ae = a) ⇒ ∀g∈ MorM(M,X), ⋅g(e) = g

where the last ⇒ comes by ∀aM, ag(e) = g(ae) = g(a). So in the following equivalence

xX, ∀gXM, g = ⋅x ⇔ (g ∈ MorM(M,X) ∧ g(e) = x)

⇒ expresses the axioms of action of M on X ; an M-algebra X satisfying these is called an M-set.
⇐ is implied by the last monoid axiom (•e = IdM); conversely, the variant of ⇐ replacing (X, ⋅) by (M, •) implies this axiom :

(IdM ∈ MorM(M,M) ∧ IdM(e) = e) ∴ •e = IdM

Effectiveness and free elements

An action of M on X is said effective if ⋅ : MXX :

a,bM, (∀xX, a·x = b·x) ⇒ a = b

An effective action is a way of seeing a monoid as a transformation monoid (Im ⋅ ∈ Sub{Id,⚬}XX), by using this action in guise of function evaluator. Indeed, the effectiveness condition is similar to the axiom (=Fnc), making unique the function with given domain E fitting any definition of the form (∀xE, f(x) =...)
This way, the axioms of action amount to defining e and • as playing with this action, the same roles as those of Id and ⚬ with the function evaluator.

An element xX of an M-set (X, ·), is free if ⋅x : MX. The existence of a free element implies the effectiveness of the action :

(∃xX, ∀abM, a·xb·x) ⇒ (∀abM, ∃xX, a·xb·x)
Inj(πx ⚬ ⋅ ) ⇒ Inj ⋅

For the natural action of a monoid on itself, the identity element is free. Thus, this action is effective.

Trajectories

The trajectory of an element xE by a monoid M acting on E, can be defined in 2 equivalent ways:

〈{x}〉M = {ax | aM} = Im ⋅xE

Indeed, 〈{x}〉M ⊂ Im ⋅x because x = ⋅x(e) ∈ Im ⋅x ∈ SubM E.
The converse is obvious.

Right actions

A right action, also called co-action, of a monoid M on a set X, is like an action with sides switched: it is an operation ⋅ : X × MX such that
It amounts to an action of the opposite monoid, and defines an anti-morphism from M to XX.

The commutation of 2 submonoids of XX looks like an associativity formula when written as acting by opposite sides on X: aM acting on X commutes with bN co-acting on X when

xX, (ax)⋅b = a⋅(xb)

Actions of categories

Generalizing from the above case of monoids, an action α of a category C gives for each object X of C a set Xα, and for each morphism f ∈ Mor(X,Y) a function fα : XαYα, preserving identities and compositions:

CX, (1X)α = IdXα
CX,Y,Z, ∀f∈ Mor(X,Y), ∀g∈ Mor(Y,Z), (gf)α = gαfα

The category C with the action α will be called an acting category and denoted Cα.
An acting category Cα is effective if ∀CX,Y, Inj(Mor(X,Y)∋ ffα).
An effective acting category is synonymous with a concrete category. Even if not effective, an acting category Cα defines a concrete category |Cα| with objects the sets Xα, and with sets of morphisms

Mor(Xα, Yα) = {fα | f∈Mor(X,Y)}

Dually, a co-action β of a category C (forming a co-acting category Cβ) gives for each object X of C a set Xβ, and for each morphism f ∈ Mor(X,Y) a function fβ : YβXβ, preserving identities, and anti-preserving compositions:

CX, (1X)β = IdXβ
CX,Y,Z, ∀f∈ Mor(X,Y), ∀g∈ Mor(Y,Z), (gf)β = fβgβ

In the literature, co-actions of categories are called presheafs.
Actions and co-actions of a category may be seen as typed meta-algebras with types given by its objects, and function symbols given by its morphisms.

Some constructions of actions

Given an action α of C, a sub-action of α is an action β of C defined by restriction of α to a preserved unary predicate:

CX, XβXα
CX,Y, ∀f∈ Mor(X,Y), fα[Xβ] ⊂ Yβfβ = fα|Xβ.

Generalizing the natural actions of monoids on themselves, every choice of an object M defines an action C(M) of C called action from M, where

CX, X(M) = Mor(M,X)
f∈Mor(X,Y), f(M) = Hom(M, f) = ∘(f)|Mor(M,X) : X(M)Y(M)

and a co-acting category C(M) of co-action to M where

CX, X(M) = Mor(X,M)
f∈Mor(X,Y), f(M) = Hom(f,M) = ∘(f)|Mor(Y,M) : Y(M)X(M)

If C is a concrete category then C(M) is a sub-action of CM (which to each X gives XM), and C(M) is a sub-co-action of CM (which to each X gives MX).

The axioms for monoids M and M-sets X can be read as contained in the axioms of categories. Namely, pick an object K of a category C, and let M = End(K). Then any object E defines an M-set X = K(E) = E(K). As actions by composition on opposite sides commute by associativity, morphisms in the co-acting category C(K) preserve this M-structure :

f ∈Mor(E,F), f(K) ∈ MorM(F(K), E(K))
xX=Mor(E,K), x(K) = ⋅x ∈ MorM(K(K), E(K)).

Trajectories of tuples in concrete categories

For any concrete category C and any number n∈ℕ, trajectories of the action Cn of C are preserved relations : for any fixed n-tuple t of elements of an object K, the trajectory s of t by C, interpreted as CE, sE = {ft | f ∈ Mor(K,E)}, is preserved.

Proof : ∀g∈Mor(E,F), ∀xsE, ∃f∈Mor(K,E), (x = ftgf ∈ Mor(K,F)) ∴ gx = gftsF.∎

With an inclusion between objects EF, the so defined sE may differ from the restriction of sF to E, but we shall usually not face this kind of issue.
Set theory and foundations of mathematics
1. First foundations of mathematics
2. Set theory
3. Algebra 1
4. Arithmetic and first-order foundations
5. Second-order foundations
6. Foundations of Geometry

Other languages:
FR : Actions de monoides et de catégories