If a forgetful functor between varieties preserves coproducts, does it have a right adjoint?

Question

Suppose that $C,D$ are two varieties (equational classes) and that $U:C\rightarrow D$ is the forgetful functor. Is it true that if this functor preserves coproducts and initial objects then it has a right adjoint?

I remember someone once told me this fact but I do not remember whom it was to ask for details. I just remember that I have been told that it follows from Freyd's criterion and some properties of varieties, but whenever I look at Freyd's criterion, it only talks about the existence of left adjoints and not right adjoints. Maybe this is easy, but I did not study the subject properly but need to use this result but I want to make sure it is true and understand some of its backgrounds.

I would appreciate any clarification/reference where I can find proof for this fact.

Answer 1

Yes, this is true. I claim first that if the forgetful functor $U:C\to D$ preserves coproducts, then it preserves coequalizers. Let $f,g:X\to Y$ be $C$-morphisms, let $\sim_C$ be the $C$-congruence relation they generate on $Y$ and let $\sim_D$ be the $D$-congruence relation they generate on $Y$. To show $U$ preserves coequalizers, we must show $\sim_C$ and $\sim_D$ are the same.

Let us denote the free $C$-algebra on $n$ generators $t_0,\dots,t_{n-1}$ by $F_n$. Note that $\sim_C$ is just the equivalence relation generated by saying that for any $\alpha(t_0,\dots,t_n)\in F_{n+1}$, any $x\in X$, and any $y_1,\dots,y_n\in Y$, $\alpha(f(x),y_1,\dots,y_n)$ is equivalent to $\alpha(g(x),y_1,\dots,y_n)$. So, it suffices to show that $\alpha(f(x),y_1,\dots,y_n)\sim_D \alpha(g(x),y_1,\dots,y_n)$ in this situation.

Let $i:F_{n+1}\to Y$ be the $C$-morphism sending the generators to $f(x),y_1,\dots,y_n$ and $j:F_{n+1}\to Y$ be the $C$-morphism sending the generators to $g(x),y_1,\dots,y_n$; it suffices to show that $hi=hj$ for any $D$-morphism $h:Y\to Z$ that coequalizes $f$ and $g$. Note that $F_{n+1}$ is a coproduct in $C$ of $n+1$ copies of $F_1$, and hence also in $D$ since $U$ preserves coproducts. So to show that $hi=hj$, it suffices to show their compositions with each coproduct inclusion $F_1\to F_{n+1}$ are the same. This is trivial for all the inclusions except the first one. For the first coproduct inclusion, the two maps we are comparing are just $hfk$ and $hgk$, where $k:F_1\to X$ is the $C$-morphism that sends the generator to $x$. These are equal since $h$ coequalizes $f$ and $g$.

Thus $U$ preserves coequalizers, and hence preserves all colimits. To show $U$ has a right adjoint, we now just have to verify the solution set condition of the general adjoint functor theorem (you mention being familiar with this theorem giving the existence of left adjoints, but you can get a criterion for the existence of right adjoints by just dualizing). Concretely, in this case, that just means we need the following: given a $D$-algebra $X$, there exists a cardinal $\kappa$ such that if $Y$ is any $C$-algebra and $f:Y\to X$ is a $D$-morphism, there is a $C$-algebra $Z$ of cardinality at most $\kappa$, a $C$-morphism $g:Y\to Z$, and a $D$-morphism $h:Z\to X$ such that $hg=f$. (Or more briefly, every $D$-morphism from a $C$-algebra to $X$ can be factored through a $C$-algebra of bounded cardinality.)

To prove this, suppose $Y$ is a $C$-algebra and $f:Y\to X$ is a $D$-morphism. Let $S$ be the set of $D$-morphisms $F_1\to X$. Then $f$ induces a function $\varphi:Y\to S$ as follows: given an element $y\in Y$, we get an associated $D$-morphism $F_1\to Y$ which we can then compose with $f$ to get an element of $S$.

Now consider the following diagram in $C$. The objects are $Y$, and a copy of $F_1$ for each element of $S$ that is in the image of $\varphi$. For each $y\in Y$, we have a morphism in the diagram from the copy of $F_1$ corresponding to $\varphi(y)$ to $Y$ which sends the generator to $y$. Let $g:Y\to Z$ be the colimit of this diagram in $C$ (which is also the colimit in $D$ since $U$ preserves colimits). That is, $g$ is the universal morphism that coequalizes the inclusions from $F_1$ of all pairs of elements $y,y'\in Y$ such that $\varphi(y)=\varphi(y')$. By definition of $\varphi$, $f$ coequalizes all such pairs of inclusions, so $f$ factors through $g$ (via a $D$-morphism $h:Z\to X$). On the other hand, note that $|Z|\leq |S|$, since pairs of elements of $Y$ that map to the same element of $S$ under $\varphi$ become equal in $Z$. Thus, taking $\kappa=|S|$, we have the desired factorization of $f$.

(Incidentally, there really is something nontrivial going on in verifying the solution set condition here--if you drop the assumption that $U$ preserves coproducts, then it may not satisfy the solution set condition! For instance, the forgetful functor from groups to sets does not, since there exist simple groups of arbitrarily large cardinality and nonconstant maps out of them cannot factor through any smaller group. Here's the step of the argument that would break down in that case: in order to factor $f$ through $g$, you need to know that $g$ is a colimit not just in $C$ but also in $D$, so you need to know that $U$ preserves colimits.)

---

Let me close with an explicit construction of the right adjoint, starting with an illustrative example. Let $C$ be the variety of sets with a unary operation and let $D$ be the variety of sets. Then the right adjoint $G:D\to C$ sends a set $X$ to the set $X^\mathbb{N}$ of sequences of elements of $X$, with unary operation given by the left shift operator (sending a sequence $(x_0,x_1,x_2,\dots)$ to $(x_1,x_2,x_3,\dots)$). (To relate this to the construction above, note that $X^\mathbb{N}$ is just the set of $D$-morphisms from the free $C$-algebra on one generator (i.e., $\mathbb{N}$) to $X$. Indeed, with some work you can extract this description of the right adjoint from the proof of the general adjoint functor theorem using the solution set given above.)

Why is this right adjoint to the forgetful functor? Well, suppose $Y$ is a set with unary operation $s$ and $f:Y\to X$ is a function. Then $f$ induces a map $g:Y\to X^{\mathbb{N}}$ sending each $y\in Y$ to the sequence $(f(y),f(s(y)),f(s^2(y)),\dots)$, and $g(s(y))$ is just the left-shift of $g(y)$. Conversely, any $C$-morphism $g:Y\to X^{\mathbb{N}}$ must have this form for a unique function $f$: if we define $f(y)$ to be the first term of the sequence $g(y)$, then the second term must be $f(s(y))$, the third term must be $f(s^2(y))$, and so on, because $g(s(y))$ is the left-shift of $g(y)$.

More generally, the right adjoint $G:D\to C$ can always be constructed explicitly by defining $G(X)$ as the set $S$ of $D$-morphisms $F_1\to X$ equipped with a $C$-algebra structure defined as follows. An $n$-ary operation of $C$ can be thought of as a $C$-morphism $F_1\to F_n$. Given $n$ elements of $S$, we get $n$ morphisms $F_1\to X$, which give a morphism $F_n\to X$ (since $F_n$ is a coproduct of $F_1$s in $D$, not just in $C$). We can then compose this with our morphism $F_1\to F_n$ to get a morphism $F_1\to X$, i.e. another element of $S$. Then, given a $D$-morphism $Y\to X$ where $Y$ is a $C$-algebra, the function $\varphi:Y\to S$ described in the proof above is exactly the adjoint $C$-morphism.

Answer 2

Let me give a more conceptual proof using Lawvere theories.

Let $\mathcal{C}$ be a category of algebras of a variety. Suppose the language only has operations of arity $< \kappa$, where $\kappa$ is an infinite regular cardinal. Let $\mathcal{C}_\mathrm{F}$ be full subcategory of $\mathcal{C}$ spanned by the free algebras generated by each cardinal $< \kappa$. There is a fully faithful functor $\mathcal{C} \to [\mathcal{C}_\mathrm{F}^\textrm{op}, \textbf{Set}]$ defined by $X \mapsto \mathcal{C}(-, X)$. It is clear that $\mathcal{C}_\mathrm{F}$ has coproducts of families of $< \kappa$ objects and that this functor $\mathcal{C} \to [\mathcal{C}_\mathrm{F}^\textrm{op}, \textbf{Set}]$ has image contained in the full subcategory of functors $\mathcal{C}_\mathrm{F}^\textrm{op} \to \textbf{Set}$ that send coproducts of families of $< \kappa$ objects in $\mathcal{C}_\mathrm{F}$ to products in $\textbf{Set}$. The fundamental theorem regarding Lawvere theories is that this is precisely the essential image of $\mathcal{C} \to [\mathcal{C}_\mathrm{F}^\textrm{op}, \textbf{Set}]$.

Let $\mathcal{D}$ is a category of algebras of a variety. Suppose there is a forgetful functor $U : \mathcal{C} \to \mathcal{D}$ that preserves coproducts. (More precisely: suppose the language of $\mathcal{D}$ is a reduct of the language of $\mathcal{C}$ and that the forgetful functor $\mathcal{C} \to \mathcal{D}$ preserves coproducts.) This restricts to a functor $U : \mathcal{C}_\mathrm{F} \to \mathcal{D}$. Thus, for any object $Z$ in $\mathcal{D}$, we obtain a functor $\mathcal{D} (U -, Z) : \mathcal{C}_\mathrm{F}^\textrm{op} \to \textbf{Set}$ that sends coproducts of families of $< \kappa$ objects in $\mathcal{C}_\mathrm{F}$ to products in $\textbf{Set}$. By the fundamental theorem, this is representable by some object $G Z$ in $\mathcal{C}$, i.e. $\mathcal{C} (X, G Z) \cong \mathcal{D} (U X, Z)$ naturally in $X$, for $X$ in $\mathcal{C}_\mathrm{F}$. This defines a functor $G : \mathcal{D} \to \mathcal{C}$. Since $U$ preserves coproducts, the earlier isomorphism $\mathcal{C} (X, G Z) \cong \mathcal{D} (U X, Z)$ extends to all free algebras $X$. We don't yet know that $U$ preserves coequalisers in general, but it is straightforward to check that $U$ preserves the special reflexive coequalisers of the kind appearing in the precise monadicity theorem, and this is enough to extend the isomorphism $\mathcal{C} (X, G Z) \cong \mathcal{D} (U X, Z)$ to all algebras $X$. Thus $G : \mathcal{D} \to \mathcal{C}$ is a right adjoint of $U : \mathcal{C} \to \mathcal{D}$, and therefore $U : \mathcal{C} \to \mathcal{D}$ indeed preserves coequalisers.

---

Let me also give a proof dealing with coequalisers first and then constructing the right adjoint by abstract nonsense.

It is well known that the category of algebras of a variety is exact in the sense of Barr, i.e. every morphism factors as a regular epimorphism followed by a monomorphism, pullbacks preserve regular epimorphisms, and every congruence is a kernel pair. Moreover, the forgetful functor to the category of sets respects these properties. Thus, any forgetful functor between categories of algebras also respects these properties.

There are basically two ways to construct coequalisers in the category of algebras of a variety, corresponding to the two ways of constructing the smallest congruence extending a binary relation on an algebra. The first way is impredicative: the collection of all congruence relations extending a given binary relation is a set and is closed under arbitrary intersections, so there is indeed a smallest one. The second way is iterative: first, make the binary relation reflective and symmetric; next, if $a \sim b$ and $b \sim c$ then add in $a \sim c$ too; then close it under the algebraic operations; repeat these steps until the construction stabilises. If the language only has operations of arity $< \kappa$ and $\kappa$ is an infinite regular cardinal then the construction will stabilise after at most $\kappa$ steps.

Now back to category theory. Both constructions of the smallest congruence extending a binary relation can be translated into categorical language. For the purposes of this question, it is the iterative construction that we should think about. I claim:

Proposition. Let $\mathcal{C}$ be a category with finite limits, finite coproducts, $\kappa$-filtered colimits, exact in the sense of Barr, with $\kappa$-filtered colimits preserving finite limits. Then $\mathcal{C}$ also has coequalisers. Moreover, if $\mathcal{D}$ is a category of the same kind and $U : \mathcal{C} \to \mathcal{D}$ is a functor that preserves finite limits, finite coproducts, $\kappa$-filtered colimits, and regular epimorphisms, then $U : \mathcal{C} \to \mathcal{D}$ also preserves coequalisers.

Proof. The hypotheses are precisely what we need to translate the iterative construction of the smallest congruence extending a binary relation. Given a parallel pair of morphisms $X \rightrightarrows Y$ in $\mathcal{C}$, take the image of the induced morphism $X \to Y \times Y$: this defines a binary relation on $Y$, so we may form the smallest congruence $R \rightrightarrows Y$ extending it. Every congruence is a kernel pair, so $R \rightrightarrows Y$ has a coequaliser. It is straightforward to verify that the coequaliser of $R \rightrightarrows Y$ is the coequaliser of $X \rightrightarrows Y$. All of the structures used in this construction are preserved by $U : \mathcal{C} \to \mathcal{D}$, so we may conclude that coequalisers are also preserved.　■

Corollary. If a forgetful functor between categories of algebras preserves coproducts and $\kappa$-filtered colimits for some infinite regular cardinal $\kappa$, then it also preserves coequalisers.

Next, regarding the existence of adjoints: if there is an infinite regular cardinal $\kappa$ such that all the operations in the language have arity $< \kappa$, then the category of algebras is a locally $\kappa$-presentable category. It is known that any colimit-preserving functor between locally $\kappa$-presentable categories has a right adjoint. Thus, in this situation, preserving coproducts is enough to imply the existence of a right adjoint.