Computing colimits in a Lawvere theory

Question

Let Prod(C, D) be the set of finite-product preserving functors from C to D. Is it true that for any Lawvere theory L, Prod(L, Set) has small colimits? This seems to be the case, as it is invoked here:

http://ncatlab.org/nlab/show/database+of+categories

Where do this colimits come from? In the case of sifted colimits, pointwise calculation works, as sifted colimits commute with finite products in Set. However, it doesn't seem at all obvious that an arbitrary colimit of product-preserving functors would also be product-preserving.

Does anyone know of a reference or proof that such colimits exist, or even better, how to go about computing them?

Answer 1

Let $T$ be a Lawvere theory. Then view the category of $T$-algebras, as Professor Blass wrote, as a class of universal algebras for a signature that corresponds to $T$ and is equationally definable, i.e. a variety. Then do what one does with these kinds of algebras:

To get coequalizers use quotients of algebras by what are called congruences (at least, that is what they are called in Universal Algebra). A congruence is an equivalence relation on the set that corresponds under your functor $A$ to the object 1 in $T$ (that is, the underlying set) that is preserved under all operations of the theory (arrows in $T$).

To get coproducts construct the left adjoint by defining the free $T$-algebra on some set $S$ to be the obvious structure on the set of all formal expressions $f(s_1,...,s_n)$ with $f$ an arrow of $T$ and $s_1,...,s_n\in S$. It is then clear what the coproduct of a set of free $T$-algebras is, and you can use congruences to get the coproduct on an arbitrary set of $T$-algebras.

Answer 2

The OP is right that a colimit of product-preserving functors need not be product-preserving. Consider, for example, the Lawvere theory whose models (i.e., product-preserving functors to Set) are the groups. The coproduct of two groups is their free product, whose underlying set is certainly not the disjoint union (i.e., the coproduct in Set) of the underlying sets of the two groups.

In general, the colimits in a category Prod(L,Set) can be obtained by the adjoint functor theorem or by explicit algebraic constructions (appropriate quotients of appropriate free algebras) in Prod(L,Set) viewed as a variety of algebras.

Answer 3

Prod(L, Set) is equivalent to the category of algebras for a finitary monad on Set and so is complete and cocomplete by e.g. Borceux Vol. 2 prop. 4.3.6.

Answer 4

Just saw this question and thought I would mention the ``explicit construction". You seem to be happy with reflexive coequalisers, as they are sifted colimits can just be computed pointwise in Prod(L,Set). From coproducts and reflexive coequalisers in a category one can get arbitrary coequalisers: To give coequalisers in a category A is to give a left adjoint to $\Delta:A \to Graph(A)$, to give reflexive coequalisers is to give a left adjoint to $\Delta:A \to RGraph(A)$. But if you have coproducts then then the forgetful functor $RGraph(A) \to Graph(A)$ has a left adjoint, where you freely add identities to a graph $d,c:A \to B$ (two arrows meant), giving a new graph $d_{1},c_{1}:A+B \to B$ with the evident description. Therefore composing this left adjoint $Graph(A) \to RGraph(A)$ by the reflexive coequaliser functor $RGraph(A) \to A$ gives arbitrary coequalisers. Therefore reflexive coequalisers and coproducts gives coequalisers and coproducts and thus all colimits. The problem then is to understand coproducts. This is probably most easily seen on the monads side which again you seem happy with. Any algebra for a monad is a coequaliser of frees, via its canonical presentation: $(T^{2}A,\mu_{TA}) \to (TA,\mu_{A}) \to (A,a)$ (two arrows meant from $(T^{2}A,\mu_{A})$ to $(TA,\mu_{A})$ . This explicit presentation of an algebra contains all we need to construct an explicit presentation for coproducts. Well we must have that to give $(A,a)+(B,b) \to (C,c)$ is to give a pair $(A,a) \to (C,c)$ and $(B,b) \to (C,c)$ which, by the above presentation is to give maps $(TA,\\mu_{A}) \to (C,c)$ and $(TB,\\mu_{B}) \to (C,c)$ each coequalising those morphisms of the respective presentation. But to give $(TA,\\mu_{A}) \to (C,c)$ and $(TB,\\mu_{B}) \to (C,c)$ is to give an arrow from their sum, $(T(A+B),\mu_{A+B}) \to (C,c)$, the free algebra functor preserving coproducts. Now those maps of the respective presentations induce a pair $(T^{2}(A+B),\mu_{T(A+B)}) \to (T(A+B),\mu_{A+B})$ and to say that the maps $(A,a) \to (C,c)$ and $(B,b) \to (C,c)$ coequalise the previous pairs amounts to saying that the induced map $(T(A+B),\mu_{A+B}) \to (C,c)$ coequalises this pair; thus the coproduct of $(A,a)$ and $(B,b)$ must be the coequaliser of the maps $(T^{2}(A+B),\mu_{T(A+B)}) \to (T(A+B),\mu_{A+B})$ constructed (good exercise to work this out). This explains why the coproduct of a pair of groups and so on is a quotient of the free group on the disjoint union of the underlying sets. This construction may be interpreting just the same in the Lawvere theory setting.

Answer 5

Claim: A functor $F \in Set^L$ is an $L$-algebra if and only if it's a sifted colimit of (co)representables.

One direction is easy: representables are algebras, and sifted colimits of algebras are algebras since sifted colimits commute with finite products in $Set$.

The other direction: If $A:L \to Set$ is an algebra, one can show its category of elements is sifted. One way to deduce this is simply to show that it has binary coproducts. It's more convenient to look at the opposite category, which has objects $\left(l,\alpha\right)$ with $l \in L$ and $\alpha \in A\left(l\right).$ The arrows $$\left(t,\alpha\right) \to \left(t',\alpha'\right)$$ are morphisms $$g:t' \to t$$ such that $A\left(g\right)\left(\alpha'\right)=\alpha.$

It follows that $$\left(l,\alpha\right) \times \left(l',\alpha'\right)=\left(l \times l',\left(\alpha,\alpha'\right)\in A\left(l\right) \times A\left(l'\right)=A \left(l \times l'\right)\right).$$

This establishing the claim.

This implies that $Alg\left(L\right)$ has sifted colimits. It suffices to prove that it has binary coproducts (this implies cocompleteness, since sifted colimits give you reflexive coequalizers). Notice that free algebras $Alg\left(L\right)$ have binary coproducts (these are the representables). By the claim, it follows that $Alg\left(L\right)$ has binary coproducts. Hence we are done.