nLab
transfinite construction of free algebras

Transfinite constructions of free algebras, etc.

Idea

In category theory, there is a common problem of the construction of free objects in “algebraic” categories. The idea is that one has to start from some “generators” and repeatedly throw in the results of applying “operations”, subject to some “relations”, over and over again until the result “converges”. In general, this convergence will require a transfinite iteration, and the fact that it converges at all requires some smallness/accessibility hypotheses.

If this construction is performed in sufficient generality, then it includes a large number of important special cases, such as the following (not mutually exclusive):

In 1980, Max Kelly (Kelly) wrote a very long paper detailing very precise and general conditions under which such constructions can be performed, and showing how they can all be reduced to the case of free algebras for well-pointed endofunctors.

In what follows we will summarize Kelly’s constructions, restricted to the special case of accessible functors on locally presentable categories. Much of the technical apparatus of Kelly’s paper (including, among other things, two different ambient orthogonal factorization systems (E,M)(E,M) and (E,M)(E',M'), and assumptions such as “TT preserves the EE-tightness of (M,K)(M',K)-cones”) becomes unnecessary in this case, which also includes many if not most of the important examples.

Basic concepts

Let 𝒜\mathcal{A} be a locally presentable category. All endofunctors of 𝒜\mathcal{A} which we consider will be accessible, that is, they preserve κ\kappa-filtered colimits for some sufficiently large cardinal number κ\kappa. In fact, we will only need to know that they preserve sufficiently long transfinite compositions.

Definition

An endofunctor S:𝒜𝒜S:\mathcal{A}\to \mathcal{A} is called pointed if it is equipped with a natural transformation σ:Id 𝒜S\sigma:Id_\mathcal{A} \to S. It is called well-pointed if Sσ=σSS\sigma = \sigma S (as natural transformations SS 2S\to S^2).

Of course, a monad can be regarded as a pointed endofunctor where σ\sigma is its unit. Such an endofunctor is well-pointed precisely when the monad is idempotent.

Definition

If HH is an endofunctor, then an HH-algebra is an object AA together with a map HAAH A\to A. If (S,σ)(S,\sigma) is a pointed endofunctor, then an SS-algebra is an object AA with a map a:SAAa:S A \to A such that aσ A=1 Aa \sigma_A = 1_A.

We have obvious categories of algebras of both sorts. Of course, any algebra for a monad is also an algebra for that monad qua pointed endofunctor. The converse holds in the well-pointed/idempotent case. In fact, we have:

Lemma

If (S,σ)(S,\sigma) is well-pointed, then an object AA admits at most one SS-algebra structure. This happens exactly when σ A\sigma_A is an isomorphism, in which case its inverse is that unique algebra structure.

Proof

Commutativity of the diagram

SSA Sa SA σ SA=Sσ A σ A SA a A \begin{array}{ccc} S S A & \overset{S a}\to & S A \\ \mathllap{\scriptsize{\sigma_{S A}=S\sigma_A}}\uparrow && \;\;\;\;\uparrow\mathrlap{\scriptsize{\sigma_A}} \\ S A & \underset{a}\to & A \end{array}

gives that σ Aa=1 SA\sigma_A\circ a= 1_{S A}, which together with aσ A=1 Aa\sigma_A= 1_A gives the invertibility of a:SAAa\colon S A\to A and the uniqueness of the algebra structure.

Thus, when SS is well-pointed, the category of SS-algebras is a full subcategory of 𝒜\mathcal{A}. Well-pointed endofunctors are important, so we mention a few other ways to obtain them.

Lemma

If (S,σ)(S,\sigma) is a well-pointed endofunctor and α:ST\alpha\colon S\to T is a natural transformation whose components are epimorphisms, then TT is also well-pointed.

Proof

The putative transformation η:1T\eta\colon 1\to T is the composition ασ\alpha\circ \sigma. First of all notice that σTα=Sη\sigma T\circ \alpha = S\eta, since

Sη A =Sα ASσ A =Sα Aσ SA =σ TAα A\begin{array}{cc} S\eta_A &= S \alpha_A \circ S\sigma_A \\ &= S\alpha_A \circ \sigma_{S A}\\ &= \sigma_{T A}\circ \alpha_A \end{array}

by naturality of the transformations involved. Now, it suffices to show that ηTα=Tηα\eta T \circ \alpha = T\eta \circ \alpha: this follows, again, from

(ηTα) A = α TAσ TAα A = α TASη A = Tη Aα A = (Tηα) A\begin{array}{ccc} (\eta T \circ \alpha)_A &=& \alpha_{T A}\circ \sigma_{T A}\circ \alpha_A \\ &=& \alpha_{T A} \circ S \eta_A\\ &=& T \eta_A \circ \alpha_A \\ &=& (T\eta \circ\alpha)_A\end{array}

Now since α\alpha is an epimorphism, we can conclude.

Lemma

Suppose (S i,σ i)(S_i,\sigma_i) is a family of (accessible) well-pointed endofunctors and let σ:IdS\sigma:Id \to S be the wide pushout of all the points σ i:IdS i\sigma_i:Id \to S_i. Then (S,σ)(S,\sigma) is (accessible and) well-pointed, and SAlg= i(S iAlg)S Alg = \bigcap_i (S_i Alg).

Proof

The last statement is almost obvious using Lemma 1 above. Well-pointedness for SS follows adapting Lemma 2 to the case of a jointly epimorphic family of arrows {S iS}\{S_i\to S\}, like the colimiting cocone for SS.

Lemma

Let F:𝒜:GF:\mathcal{A} \rightleftarrows \mathcal{B} :G be an adjunction and (S,σ)(S',\sigma') an (accessible) well-pointed endofunctor on \mathcal{B}. Let (S,σ)(S,\sigma) be the pushout

FG FσG FSG Id σ S. \array{ F G & \xrightarrow{F \sigma' G} & F S' G \\ \downarrow && \downarrow \\ Id & \xrightarrow{\sigma} & S. }

Then (S,σ)(S,\sigma) is (accessible and) well-pointed, and A𝒜A\in\mathcal{A} is an SS-algebra exactly when GAG A is an SS'-algebra.

Proof

Free algebras for well-pointed endofunctors

The basic theorem to which all others can be reduced is the following.

Theorem

If 𝒜\mathcal{A} is locally presentable and SS is an accessible well-pointed endofunctor, then SAlgS Alg is reflective in 𝒜\mathcal{A}. Therefore, the algebraically-free monad on SS exists (and is accessible).

Proof

Given A𝒜A\in\mathcal{A}, define inductively the following transfinite sequence in 𝒜\mathcal{A}:

ASAS 2AS 3A A \to S A \to S^2 A \to S^3 A \to \cdots

in which each transition map is a component of σ\sigma, and we take colimits at limit stages. If we continue this out to some κ\kappa-filtered ordinal α\alpha, where SS is κ\kappa-accessible, then SS will preserve the relevant colimit, and hence we have an induced action S(S αA)S αAS(S^\alpha A) \to S^\alpha A. It is easy to check that this makes S αAS^\alpha A into a reflection of AA into SAlgS Alg.

Some important constructions are directly examples of this theorem.

Example

Let KK be a set of morphisms in 𝒜\mathcal{A}; recall that an object A𝒜A\in\mathcal{A} is said to be orthogonal to KK if 𝒜(k,A)\mathcal{A}(k,A) is a bijection for all kKk\in K, which is to say that each functor 𝒜(k,):𝒜Set 2\mathcal{A}(k,-):\mathcal{A}\to Set^{\mathbf{2}} takes AA to an isomorphism, where Set 2Set^{\mathbf{2}} is the arrow category of Set. Now the subcategory of isomorphisms is reflective in Set 2Set^{\mathbf{2}}, hence is the algebras for a well-pointed endofunctor R kR_k. By Lemma 4, there is a well-pointed endofunctor S kS_k on 𝒜\mathcal{A} whose algebras are the objects orthogonal to kk. And by Lemma 3, there is a well-pointed endofunctor SS whose algebras are those objects orthogonal to all kKk\in K. Thus, by Theorem 1, the category of objects orthogonal to KK is reflective in 𝒜\mathcal{A}.

Example

Applying the previous example on slice categories, we can construct orthogonal factorization systems.

The rest of the constructions proceed by building, out of other data, a well-pointed endofunctor, and applying Theorem 1.

Free algebras for pointed endofunctors

Now let (T,τ)(T,\tau) be a general (accessible) pointed endofunctor, not necessarily well-pointed. Let T/𝒜T/\mathcal{A} denote the comma category, whose objects are triples (A,B,a)(A,B,a) where a:TABa:T A \to B. Then T/𝒜T/\mathcal{A} is again locally presentable.

If α:TT\alpha:T'\to T is a natural transformation, we have an adjunction α !:T/𝒜T/𝒜:α *\alpha_! : T'/\mathcal{A} \rightleftarrows T/\mathcal{A}: \alpha^* in which α *\alpha^* sends (A,B,a)(A,B,a) to (A,B,aα A)(A,B,a\circ \alpha_A) and α !\alpha_! is defined by a pushout.

Note that if α\alpha is τ:IdT\tau:Id \to T, then τ *(A,B,a)\tau^*(A,B,a) is the composite Aτ ATAaBA \xrightarrow{\tau_A} T A \xrightarrow{a} B in 𝒜 2=Id/𝒜\mathcal{A}^{\mathbf{2}} = Id/\mathcal{A}.

Lemma

The category TAlgT Alg of TT-algebras is a reflective full subcategory of T/𝒜T/\mathcal{A}.

Proof

It is easy to show that it is a full subcategory. Moreover, (A,B,a)(A,B,a) lies in TAlgT Alg just when τ *(A,B,a)\tau^*(A,B,a) is an isomorphism. The isomorphisms are a reflective subcategory of 𝒜 2\mathcal{A}^{\mathbf{2}}, hence the algebras for a well-pointed endofunctor RR. Now by Lemma 4, there is a well-pointed endofunctor SS of T/𝒜T/\mathcal{A} whose algebras are precisely the TT-algebras. Now apply Theorem 1.

Theorem

The category TAlgT Alg is monadic over 𝒜\mathcal{A}, and cocomplete. In particular, the algebraically-free monad on TT exists and is accessible.

Proof

A left adjoint to the forgetful functor TAlg𝒜T Alg \to \mathcal{A} is supplied by reflecting the object (A,TA,τ A)(A,T A,\tau_A) of T/𝒜T/\mathcal{A} into TAlgT Alg. The monadicity theorem then applies. Colimits can be constructed in T/𝒜T/\mathcal{A} and then reflected into TAlgT Alg.

It is possible to β-reduce this proof and describe the resulting transfinite construction more explicitly. Given (A,B,a)(A,B,a), we define inductively a transfinite sequence

TX 0 TX 1 TX 2 x 0 x 1 x 2 X 0 X 1 X 2 X 3 \array{ && T X_0 & \to & T X_1 & \to & T X_2 & \to & \dots \\ && \downarrow^{x_0} && \downarrow^{x_1} && \downarrow^{x_2} \\ X_0 & \to & X_1 & \to & X_2 & \to & X_3 & \to & \dots }

such that X βX β+1X_\beta \to X_{\beta+1} is equal to x βτ X βx_\beta \circ \tau_{X_\beta}.

We begin with X 0=AX_0=A, X 1=BX_1=B, and x 0=ax_0 = a. Given X βX_\beta and X β+1X_{\beta+1}, we define x β+1:TX β+1X β+2x_{\beta+1}:T X_{\beta+1}\to X_{\beta+2} to be the coequalizer of the two composites

TX βTττTT 2X βTx βTX β+1. T X_\beta \;\underoverset{T \tau}{\tau T}{\rightrightarrows}\; T^2 X_\beta \xrightarrow{T x_\beta} T X_{\beta+1}.

At limit ordinals α\alpha we take colimits, and at successors of limit ordinals we let x α:TX αX α+1x_\alpha : T X_\alpha \to X_{\alpha+1} be the coequalizer of the two maps

colim β<αX β+1=X α τ colim β<αTX β TX α. \array{ && \colim_{\beta\lt\alpha} X_{\beta+1} = X_\alpha \\ & \nearrow && \searrow^{\tau} \\ \colim_{\beta\lt\alpha} T X_\beta && \to && T X_\alpha.}
Example

The algebraic small object argument consists of building the free monad on a pointed endofunctor.

Free algebras for unpointed endofunctors

An algebra for an unpointed endofunctor HH is the same as an algebra for the pointed endofunctor TId+HT \coloneqq Id + H. Thus, Theorem 2 can be applied to unpointed endofunctors as well.

In this case, the transfinite sequence for the free HH-algebra on A𝒜A\in\mathcal{A} is much simpler: we have X 0=AX_0 = A and X β+1=A+HX βX_{\beta+1} = A + H X_\beta.

Example

A W-type in a category is an initial algebra for a polynomial functor. Equivalently, it is the free algebra on the initial object for that functor. Thus, we obtain the existence of W-types, and likewise of more general inductive types.

Colimits of algebras for a monad

Let TT be a monad on 𝒜\mathcal{A}, and let TAlgT Alg denote the category of TT-algebras qua monad.

Theorem

The category TAlgT Alg is a reflective subcategory of T/𝒜T/\mathcal{A}.

Proof

For (A,B,a)T/𝒜(A,B,a)\in T/\mathcal{A}, consider the pushout

T 2A μ TA Ta TB c D \array{ T^2 A & \xrightarrow{\mu} & T A \\ ^{T a}\downarrow && \downarrow\\ T B & \xrightarrow{c} & D }

Define L:T/𝒜T/𝒜L:T/\mathcal{A}\to T/\mathcal{A} to take (A,B,a)(A,B,a) to (B,D,c)(B,D,c) in this pushout. Then LL-algebras (qua pointed endofunctor) are precisely TT-algebras (qua monad), and we have a pointwise epimorphism SLS\to L, where SS is the well-pointed endofunctor from the proof of Theorem 2 whose algebras are the TT-algebras (qua pointed endofunctor). Thus, by Lemma 2, LL is well-pointed; now apply Theorem 1.

Corollary

TAlgT Alg is locally presentable. Moreover, any functor TAlgTAlgT Alg \to T' Alg induced by a monad morphism TTT'\to T has a left adjoint.

Proof

Since TAlgT Alg is reflective in the cocomplete T/𝒜T/\mathcal{A}, it is cocomplete. Since it is accessible by the limit theorem, it is locally presentable. For the second statement, the functor T/𝒜T/𝒜T/\mathcal{A} \to T'/\mathcal{A} has an easily defined left adjoint; now compose it with the reflection into T/𝒜T/\mathcal{A}.

Colimits of monads

When speaking of colimits of monads, we are not interested merely in colimits in the category of monads, but algebraic colimits in the following sense. Let V:KMonad(𝒜)V:K\to Monad (\mathcal{A}) be a diagram in the category of monads on 𝒜\mathcal{A}, and define a VV-algebra to be an object AA together with V kV_k-algebra structures which commute with the images of morphisms in KK.

Definition

An algebraic colimit of VV is a monad PP whose usual Eilenberg-Moore category PAlgP Alg is equivalent, over 𝒜\mathcal{A}, to the category of VV-algebras.

It follows, by arguments similar to those for algebraically-free monads, that an algebraic colimit is also a colimit in the category of monads.

Theorem

Algebraic colimits of (accessible) monads exist (and are accessible).

Proof

WLOG we may assume KK has an initial object; otherwise, give it a new initial object 00 and define V 0=IdV_0 = Id. Let TT be the (pointwise) colimit of VV in the category of endofunctors of 𝒜\mathcal{A}, with coprojections r k:V kTr_k:V_k \to T. Our assumption on KK gives TT a unique point IdV 0TId \to V_0 \to T such that each r kr_k is a map of pointed endofunctors. Moreover, a TT-algebra (qua pointed endofunctor) is an object AA together with compatible pointed-endofunctor-algebra structures for each V kV_k. This clearly includes the VV-algebras, as defined above, as a full subcategory.

We will show the category of VV-algebras to be reflective in T/𝒜T/\mathcal{A}. Given (A,B,a)(A,B,a), let c:TBDc:T B \to D be the joint coequalizer of all the parallel pairs

V kA μ k V kτ k V k 2A id V k 2A V k(ar k) V kB r kTB. \array{ && V_k A \\ & ^{\mu_k}\nearrow && \searrow^{V_k \tau_k}\\ V_k^2 A && \xrightarrow{id} && V_k^2 A & \xrightarrow{V_k (a r_k)} & V_k B & \xrightarrow{r_k } T B. }

Let L(A,B,a)(B,D,c)L(A,B,a) \coloneqq (B,D,c), defining an endofunctor of T/𝒜T/\mathcal{A}. Then LL is accessible, and an LL-algebra is precisely a VV-algebra.

Moreover, LL admits an epimorphic transformation from the well-pointed endofunctor SS defined as in Theorem 2 whose algebras are the TT-algebras (qua pointed endofunctor). Thus, by Lemma 2, LL is well-pointed; now apply Theorem 1.

Example

The categorical semantics of higher inductive types can be described using certain “presentations” of monads. (More to come…)

References

  • Max Kelly, “A unified treatment of transfinite constructions for free algebras, free monoids, colimits, associated sheaves, and so on.” Bull. Austral. Math. Soc. 22 (1980), 1–83.
Revised on June 14, 2014 00:30:20 by Fosco Loregian (95.233.61.184)