nLab
cocompleteness of varieties of algebras

Idea

The purpose of this summary is to show that the category $⟨\Omega ,E⟩-\mathrm{Alg}$ (a variety of algebras) is cocomplete, using the general adjoint functor theorem. For a different proof in the context of Lawvere theories, see here.

Notation

Let us first fix some notation and recall the required facts on varieties of algebras. We assume the foundations of Categories Work (ZFC plus one fixed universe). Let $\Omega$ be a small signature consisting only of function symbols (this set is assumed to be equipped with an arity function $\Omega \to \mathbb{N}$), let $\Lambda$ be the set of $\Omega$-terms (also called derived operators), and let $E\subset {\Lambda }^2$ be a set of identities.

Recall that a $⟨\Omega ,E⟩$-algebra is just an $\Omega$-structure (that is, a pair $⟨S,A⟩$ where $S$ is a set and $A$ is a function $A:\Omega \to {\bigcup }_n{S}^{S^n}$ which assigns to each operator $\omega$ of arity $n$ a function ${\omega }_A:S^n\to S$) that is a model for $\mu =\lambda$ for any possible interpretation of the variables, for all $⟨\mu ,\lambda ⟩\in E$.

A morphism $f:⟨S,A⟩\to ⟨S\prime ,A\prime ⟩$ is a function $f:S\to S\prime$ that satisfies $f\circ {\omega }_A={\omega }_{A\prime }\circ f^n$ for all $n$ and all $\omega \in \Omega$ of arity $n$. The category $⟨\Omega ,E⟩-\mathrm{Alg}$ consists of all small $⟨\Omega ,E⟩$-algebras with the above morphisms as arrows.

There is an obvious forgetful functor $G:⟨\Omega ,E⟩-\mathrm{Alg}\to \mathrm{Set}$, and it can be verified directly that this functor creates small limits (in fact, this functor is monadic and hence creates all limits). Consequently $⟨\Omega ,E⟩-\mathrm{Alg}$ is small complete.

Cocompleteness of $⟨\Omega ,E⟩-\mathrm{Alg}$

Before proving cocompleteness, some preparations are required. Let us write $C:=⟨\Omega ,E⟩-\mathrm{Alg}$ for short. Let $J$ be a small category. To prove cocompleteness, we will use the general adjoint functor theorem to construct a left adjoint for the diagonal functor $\Delta :C\to C^J$.
Since $C$ is locally small and small-complete and $\Delta$ is continuous (as any diagonal functor), all that is required is a solution set for each $F\in obj(C^J)$.

Recall that given a functor $T:C\to X$ and an object $c$ of $C$, an arrow $f:x\to Tc$ of $X$ is said to span $c$ when, for all monic $i:c\prime \to c$, if $f$ factors through $Ti:Tc\prime \to Tc$, then $i$ is an isomorphism.

In our current context, we will replace ”monic” in the above definition by a stricter notion: the underlying function in $\mathrm{Set}$ is injective.

Lemma

(CWM, p. 127). In a category $C$, suppose that every set of subobjects of an object $c\in C$ has a pullback. Then if $T:C\to X$ preserves all these pullbacks, every arrow $h:x\to \mathrm{Tc}$ factors as $\mathrm{Tg}\circ f$ for some arrow $f:x\to \mathrm{Tc}\prime$ which spans $c\prime$ and some $g:c\prime \to c$.

It can be verified that this lemma still holds (in our context) if, in the definition of subobject and spanning arrow, ”monic” is replaced by ”the underlying function is injective.”

Lemma

If a cone $\tau :F\stackrel{\cdot }{\to }\Delta ⟨S,A⟩$ spans $⟨S,A⟩$, then $⟨S,A⟩$ is generated by ${\bigcup }_j{\tau }_j(F_j)$.

Proof

Let $⟨S\prime ,A\prime ⟩$ be the subalgebra of $⟨S,A⟩$ generated by ${\bigcup }_j{\tau }_j(F_j)$, and let $i:⟨S\prime ,A\prime ⟩\to ⟨S,A⟩$ be the inclusion. Then we have the cone $\tilde{\tau }:F\to \Delta ⟨S\prime ,A\prime ⟩$ obtained by restricting the codomains of the ${\tau }_j$, and $\tau$ splits as $\Delta (i)\circ \tau \prime$. So $i$ is an isomorphism, and therefore must be the identity.

We can now finally prove

Proposition

$⟨\Omega ,E⟩-\mathrm{Alg}$ is small cocomplete.

Proof

Let us fix some $F\in C^J$. Define

$$𝒮:=\{⟨S,A⟩\in obj(C)\mid \exists \tau :F\stackrel{\cdot }{\to }\Delta ⟨S,A⟩(\tau \text{spans}⟨S,A⟩)\}.$$\mathcal{S}:= \{\langle S,A\rangle\in \operatorname{obj}(C)|\exists \tau\colon F\stackrel{\cdot}{\to}\Delta\langle S,A\rangle(\tau \text{ spans }\langle S,A\rangle)\}.

We note that if $⟨S,A⟩\in 𝒮$, then by Lemma 2, $\mid S\mid \le \mid \mathbb{N}\cup X_{S,\tau }\cup \Omega \mid \le \mid \mathbb{N}\cup X\cup \Omega \mid$, where
$X_{S,\tau }:={\bigcup }_j{\tau }_j(F_j)$ for some $\tau :F\stackrel{\cdot }{\to }\Delta ⟨S,A⟩$ that spans $⟨S,A⟩$, and $X:={⨆}_j{F}_j$. Since $J$ is small and each $F_j$ is small, so is $X$ (in detail, $X$ may be written as $\cup Im(j\mapsto \{j\}\times F_j)$, and the image of a function from a $U$-small set into the universe $U$ is $U$-small). Now, as $X$ and $\Omega$ are small, so is $\mathbb{N}\cup X\cup \Omega$, and therefore we see that the underlying sets of all members of $𝒮$ have cardinal numbers smaller than that of some fixed small set $X\prime$.

It follows that there exists a small set $𝒮\prime \subseteq 𝒮$ including one element from each isomorphism class of $𝒮$ (for example, since $𝒮$ is closed under isomorphisms, each isomorphism class includes an algebra whose underlying set is a subset of $X\prime$).

Now define

$$ℱ:=\{\tau \in arr(C^J)\mid dom(\tau )=F\text{and}\exists ⟨S,A⟩\in 𝒮\prime (cod(\tau )=\Delta ⟨S,A⟩)\}$$\mathcal{F}:=\left\{\tau\in\operatorname{arr}(C^J)|\operatorname{dom}(\tau)=F\text{ and }\exists\langle S,A\rangle\in \mathcal{S}'(\operatorname{cod}(\tau)=\Delta\langle S,A\rangle)\right\}

(the set of all arrows $\tau :F\stackrel{\cdot }{\to }\Delta ⟨S,A⟩$ for some $⟨S,A⟩\in 𝒮\prime$). To see that $ℱ$ is small, note that each $\tau \in ℱ$ is in particular a function $obj(J)\to {\bigcup }_{j\in J,⟨S,A⟩\in 𝒮\prime }hom(F_j,⟨S,A⟩)$, and the set of all such functions is small (as any set of functions between two small sets).

Clearly, if for all $⟨S,A⟩\in C$ the set of subobjects is small-indexed, then it follows from Lemma 1 that $ℱ$ is the required solution set (since $C$ is small complete and $\Delta$ is continuous), and we are done . But two injections $f,g$ with codomain $⟨S,A⟩$ are equivalent iff they have the same image in $S$, and hence there is a bijection between the subobjects of $⟨S,A⟩$ and the subalgebras of $⟨S,A⟩$, as required (recall that we replaced ”monic” by ”injective as a function” in the definition of subobject).

Cocompleteness of algebras of monads over $\mathrm{Set}$

First, the category of algebras of a monad $T$ on $\mathrm{Set}$ has coequalizers; see the proof of proposition 3.4 (page 278 of 303) of Toposes, Triples, and Theories by Barr and Wells. So we have only to prove the following.

Proposition

The algebra category ${\mathrm{Set}}^T$ has coproducts.

Proof

Let $U:{\mathrm{Alg}}_T\to \mathrm{Set}$ be the underlying functor, with left adjoint $F$. Given a family of $T$-algebras $\{A_i\}$, there are canonical coequalizers

$$FUFU{A}_i\stackrel{\stackrel{\epsilon FU{A}_i}{\to }}{\underset{FU\epsilon A_i}{\to }}FU{A}_i\to A_i$$F U F U A_i \stackrel{\overset{\varepsilon F U A_i}{\to}}{\underset{F U \varepsilon A_i}{\to}} F U A_i \to A_i

and since $F({\sum }_{i}U{A}_i)$ is the coproduct ${\sum }_{i}FU{A}_i$ in the category of algebras, i.e., since coproducts of free algebras exist, the coproduct of the $A_i$ is constructed as a coequalizer of the pair

$$(\sum _i\epsilon FU{A}_i,\sum _{i}FU\epsilon A_i):\sum _{i}FUFU{A}_i\overrightarrow{\to }\sum _{i}FU{A}_i$$(\sum_i \varepsilon F U A_i, \sum_i F U \varepsilon A_i): \sum_i F U F U A_i \stackrel{\to}{\to} \sum_i F U A_i

obtained by summing over $i$ each of the parallel pairs.

Over a cocomplete cartesian closed category

If $T$ is a finitary monad defined on a cocomplete cartesian closed category $X$, then $T$ preserves reflexive coequalizers (see the argument here), and therefore the underlying functor

$$U:X^T\to X$$U: X^T \to X

reflects reflexive coequalizers (since the underlying functor reflects classes of colimits preserved by the monad). Since the parallel pairs in the proof of the preceding proposition are reflexive, we see by adapting that proof that $X^T$ has coproducts. It remains only to prove the following.

Lemma

If a category has finite coproducts and reflexive coequalizers, then it has general coequalizers.

Proof

Given a parallel pair $f,g:A\overrightarrow{\to }B$, there is a reflexive parallel pair

$$(f,1_B),(g,1_B):A+B\overrightarrow{\to }B$$(f, 1_B), (g, 1_B): A + B \stackrel{\to}{\to} B

whose coequalizer is the coequalizer of the pair $f,g$.

See also cocompleteness of categories of algebras.