nLab
cocompleteness of varieties of algebras

Contents

Idea

The purpose of this summary is to show that the category Ω,EAlg\langle \Omega,E\rangle-\mathbf{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Λ 2E\subset \Lambda^2 be a set of identities.

Recall that a Ω,E\langle\Omega,E\rangle-algebra is just an Ω\Omega-structure (that is, a pair S,A\langle S,A\rangle where SS is a set and AA is a function A:Ω nS S nA\colon \Omega\to\bigcup_n S^{S^n} which assigns to each operator ω\omega of arity nn a function ω A:S nS\omega_A\colon S^n\to S) that is a model for μ=λ\mu=\lambda for any possible interpretation of the variables, for all μ,λE\langle\mu,\lambda \rangle\in E.

A morphism f:S,AS,Af\colon\langle S,A\rangle\to \langle S',A'\rangle is a function f:SSf:S\to S' that satisfies fω A=ω Af nf\circ \omega_A = \omega_{A'}\circ f^n for all nn and all ωΩ\omega\in \Omega of arity nn. The category Ω,EAlg\langle \Omega,E\rangle-\mathbf{Alg} consists of all small Ω,E\langle\Omega,E\rangle-algebras with the above morphisms as arrows.

There is an obvious forgetful functor G:Ω,EAlgSetG:\langle\Omega,E\rangle-\mathbf{Alg}\to \mathbf{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 Ω,EAlg\langle \Omega,E\rangle-\mathbf{Alg} is small complete.

Cocompleteness of Ω,EAlg\langle\Omega,E\rangle-\mathbf{Alg}

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

Recall that given a functor T:CXT\colon C\to X and an object cc of CC, an arrow f:xTcf\colon x\to T c of XX is said to span cc when, for all monic i:cci\colon c'\to c, if ff factors through Ti:TcTcT i\colon T c'\to T c, then ii is an isomorphism.

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

Lemma

(CWM, p. 127). In a category CC, suppose that every set of subobjects of an object cCc\in C has a pullback. Then if T:CXT\colon C\to X preserves all these pullbacks, every arrow h:xTch\colon x\to Tc factors as TgfTg\circ f for some arrow f:xTcf\colon x\to Tc' which spans cc' and some g:ccg\colon c'\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 τ:FΔS,A\tau\colon F\stackrel{\cdot}{\to}\Delta\langle S,A\rangle spans S,A\langle S,A\rangle, then S,A\langle S,A\rangle is generated by jτ j(F j)\bigcup_j\tau_j(F_j).

Proof

Let S,A\langle S',A'\rangle be the subalgebra of S,A\langle S,A\rangle generated by jτ j(F j)\bigcup_j\tau_j(F_j), and let i:S,AS,Ai:\langle S',A'\rangle\to\langle S,A\rangle be the inclusion. Then we have the cone τ˜:FΔS,A\tilde{\tau}\colon F\to\Delta\langle S',A'\rangle obtained by restricting the codomains of the τ j\tau_j, and τ\tau splits as Δ(i)τ\Delta(i)\circ\tau'. So ii is an isomorphism, and therefore must be the identity.

We can now finally prove

Proposition

Ω,EAlg\langle\Omega,E\rangle-\mathbf{Alg} is small cocomplete.

Proof

Let us fix some FC JF\in C^J. Define

𝒮:={S,Aobj(C)τ:FΔS,A(τ 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𝒮\langle S, A\rangle\in \mathcal{S}, then by Lemma 2, SX S,τΩXΩ|S|\leq|\mathbb{N}\cup X_{S,\tau}\cup \Omega|\leq |\mathbb{N}\cup X\cup \Omega|, where
X S,τ:= jτ j(F j)X_{S,\tau}:=\bigcup_j\tau_j(F_j) for some τ:FΔS,A\tau:F\stackrel{\cdot}{\to}\Delta\langle S,A\rangle that spans S,A\langle S,A\rangle, and X:= jF jX:=\bigsqcup_j F_j. Since JJ is small and each F jF_j is small, so is XX (in detail, XX may be written as Im(j{j}×F j)\cup\operatorname{Im}(j\mapsto\{j\}\times F_j), and the image of a function from a UU-small set into the universe UU is UU-small). Now, as XX and Ω\Omega are small, so is XΩ\mathbb{N}\cup X\cup \Omega, and therefore we see that the underlying sets of all members of 𝒮\mathcal{S} have cardinal numbers smaller than that of some fixed small set XX'.

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

Now define

:={τarr(C J)dom(τ)=F and S,A𝒮(cod(τ)=Δ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 τ:FΔS,A\tau\colon F\stackrel{\cdot}{\to}\Delta\langle S,A\rangle for some S,A𝒮\langle S,A\rangle\in\mathcal{S}'). To see that \mathcal{F} is small, note that each τ\tau\in\mathcal{F} is in particular a function obj(J) jJ,S,A𝒮hom(F j,S,A)\operatorname{obj}(J)\to\bigcup_{j\in J,\langle S,A\rangle\in\mathcal{S}'}\operatorname{hom}(F_j,\langle S,A\rangle), and the set of all such functions is small (as any set of functions between two small sets).

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

Cocompleteness of algebras of monads over SetSet

First, the category of algebras of a monad TT on SetSet 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 Set TSet^T has coproducts.

Proof

Let U:Alg TSetU: Alg_T \to Set be the underlying functor, with left adjoint FF. Given a family of TT-algebras {A i}\{A_i\}, there are canonical coequalizers

FUFUA iFUεA iεFUA iFUA iA iF 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( iUA i)F(\sum_i U A_i) is the coproduct iFUA i\sum_i F U A_i in the category of algebras, i.e., since coproducts of free algebras exist, the coproduct of the A iA_i is constructed as a coequalizer of the pair

( iεFUA i, iFUεA i): iFUFUA i iFUA 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 ii each of the parallel pairs.

Over a cocomplete cartesian closed category

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

U:X TXU: 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 TX^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:ABf, g: A \stackrel{\to}{\to} B, there is a reflexive parallel pair

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

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

See also cocompleteness of categories of algebras.

Revised on January 5, 2011 13:50:03 by Todd Trimble (69.118.58.208)