How can you actually do universal algebra with monads?

706 Views Asked by At

Instead of digging deep into "classical" universal algebra, it seems more interesting or fruitful to look at universal algebra categorically. This should be doable with monads, since every category of universal algebras is isomorphic to the category of $T$-algebras, where $T$ is the composition of the corresponding free and forgetful functor.

The question is: How can this practically be done? How can I categorically define things like quotients, the subalgebra of a $T$-algebra generated by a something, or what it means for a morphism to preserve subalgebras?

Is there at least a known class of monads for which these things work (considerably larger than the class of universal algebra-monads on $\mathsf{Set}$ of course)? Are there any texts that deal with this?

2

There are 2 best solutions below

0
On BEST ANSWER

Let $\mathcal{A}$ be a category of algebras over a monad over a regular (Barr-exact) category $\mathcal{X}$ in which regular epis split. Then $\mathcal{A}$ is also regular (Barr-Exact). In particular, assuming the axiom of choice, $\mathcal{A}$ is Barr-exact, if $\mathcal{X} = \mathsf{Set}$.

A morphism is a regular epi, if it is the coequalizer of a pair of morphisms.

A category is regular, if it has finite limits, coequalizers of kernel pairs (that is: pullbacks of morphisms along themselves) and where regular epis are stable under pullback.

Barr-exactness is a bit stronger the "being regular". I am going to explain that latter.

Anyway: For starters, here are some useful ideas:

Free objects

Well, they obviously exist since our monad (like every monad) arises from an adjunction between $\mathcal{X}$ and $\mathcal{A}$.

Subobjects

Let $A \in \mathcal{A}$ be an object and consider the slice category $\mathcal{A}/A$. Observe, that it has a full subcategory $\operatorname{Sub} A$, where the objects are all the monos $m : M \to A$ in $\mathcal{A}$. These monos are the subobjects of $A$. Observe, that $\operatorname{Sub} A$ is in fact a preorder. (Usually one goes one step further and identifies isomorphic objects in this category and calls the isomorphism classes "subobjects". I don't see any good reason to do that though).

Since $\mathcal{A}$ has finite limits we can form intersections of subobjects (products in $\operatorname{Sub} A$) as pullbacks in $\mathcal{A}$. Specifically, monos are stable under pullback and composition and furthermore the diagonal of the pullback square (which is a mono as I just explained) can be verified to be product of the two given subojects in $\operatorname{Sub} A$. This can probably be generalized to intersections of families via "wide pullbacks" a.k.a fiber products.

The problem of taking unions of subobjects (coproducts in $\operatorname{Sub} A$) is not dual to the problem of taking intersections, because dualizing would change "subobject" to "quotient" (i.e. epi in the coslice category). So (totally expected!) taking unions is more complicated. The notion of a "subobject generated by a subset" is mentoined here. I suppose this yields a way of constructing unions in some cases at least.

Fortunately, there is also a more "categorical" and general result: In a category with (finite) coproducts and strong-epi-mono-factorizations, the union of a (finite) family of subobjects always exists. Since $\mathcal{A}$ has regular-epi-mono-factorizations (because $\mathcal{A}$ is a regular category) only (finite) coproduct are needed for unions. Though, I think this puts some strong assumptions on $\mathcal{X}$.

While we are on the topic of factorizations: strong-epi-mono-factorizations are essentially unique (in a suitable sense). If a morphism $f$ factors as $m\circ e$ with a strong epi $e$ and a mono $m$, then $m$ is called the image of $f$. Equivalently: the image $\operatorname{im} f$ of a morphism $f$ is the smallest subobject of $f$'s codomain, through which $f$ factors. With chosen factorizations we get a functor (actually a monotone map):

$$\exists_f : \operatorname{Sub} A \to \operatorname{Sub} B, (m : M \to A) \mapsto \operatorname{im}(f\circ m)$$

for every morphism $f : A\to B$. Actually we get also a functor $f^* : \operatorname{Sub} B \to \operatorname{Sub} A$ by pulling subobjects back along $f$. This is precisely the categorical version of preimages. Finally, one can show that $\exists_f$ is left-adjoint to $f^*$ for all $f$ which also tells us, that $\exists_f$ preserves unions and $f^*$ preserves intersections.

Congruences and quotients

A relation on an object $A$ is a pair of jointly monic morphisms into $A$ or equivalently (by the universal property of products) a mono into $A^2$. Special relations are called congruences (or internal equivalence relations). These are really the congruence relations known from universal algebra. One takes the quotient by a congruence $(r_1,r_2 : R \to A)$ on $A$ by taking the coequalizer of $r_1,r_2$.

Also, the kernel relation of a morphism $f : A\to B$ given by $a \sim b \Leftrightarrow f(a) = f(b)$ is really just the kernel pair of $f$ (pullback of $f$ along itself) and can be easily verified to be a congruence on $A$. In fact: $\mathcal{A}$ is Barr-exact means, that $\mathcal{A}$ is regular and every congruence is a kernel pair.

We immediately get the "homomorphism theorem", it is just the universal property of a coequalizer. Well, almost. The universal morphism making a certain diagram commute is actually mono as we know from universal algebras, because $\mathcal{A}$ is regular.


These are just some ideas. Further and more detailed information can be found here:

  • "Handbook of categorical algebra" Volumes 1 and 2 by Francis Borceux
  • "Algebraic Theories" by Adamek, Rosicky and Vitale.

and for example:

  • Mal'cev, Protomodular, Homological and Semi-Abelian Categories

if one is interested in more specific kinds of algebraic varieties, including groups or rings (which do not form Abelian categories!).

2
On

The paper Recognisable Languages over Monads by Mikołaj Bojańczyk, contains some definitions that may suit your needs. Quotations from this paper:

A monad over a category is defined to be a functor $T$ from the category to itself, and for every object $X$ in the category, two morphisms $\eta_X :X \to TX$ and $\mu_X :TTX \to TX$, which are called the unit and multiplication operations. The monad must satisfy the axioms (...)

An Eilenberg-Moore algebra in a monad $T$, or simply $T$-algebra, is a pair $\mathbf{A}$ consisting of a universe $A$, which is an object in the category underlining the monad, together with a multiplication morphism $\text{mul}_\mathbf{A} :TA \to A$, such that $\text{mul}_\mathbf{A} \circ \eta_A$ is the identity, and which is associative in the sense that the following diagram commutes: $$ \newcommand{\ra}[1]{\kern-1.5ex\xrightarrow{\ \ #1\ \ }\phantom{}\kern-1.5ex} \newcommand{\ras}[1]{\kern-1.5ex\xrightarrow{\ \ \smash{#1}\ \ }\phantom{}\kern-1.5ex} \newcommand{\da}[1]{\bigg\downarrow\raise.5ex\rlap{\scriptstyle#1}} \newcommand{\dal}[1]{\raise.5ex\llap{\scriptstyle#1}\bigg\downarrow} \begin{array}{c} TTA & \ra{\mu_A} & TA \\ \dal{T\text{mul}_\mathbf{A}} & & \da{\text{mul}_\mathbf{A}} \\ TA & \ras{\text{mul}_\mathbf{A}} & A \\ \end{array} $$