nLab
transfinite construction of free algebras

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):

• the free monad generated by an endofunctor
• the free monad generated by a pointed endofunctor
• the free monoid generated by an object of a monoidal category
• the orthogonal factorization system generated by a set of morphisms
• the reflectiveness of a small-orthogonality class?
• the reflectiveness of enriched presheaves preserving certain limits
• the cocompleteness of the category of algebras for a monad
• the existence of left adjoints to functors between categories of algebras for monads
• the existence of colimits for diagrams of monads
• the existence of colimits in categories of monoids
• the algebraic small object argument
• the existence of W-types and inductive types in categories
• the existence of higher inductive types in categories

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)$ and $(E\prime ,M\prime )$, and assumptions such as ”$T$ preserves the $E$-tightness of $(M\prime ,K)$-cones”) becomes unnecessary in this case, which also includes many if not most of the important examples.

Basic concepts

Let $𝒜$ be a locally presentable category. All endofunctors of $𝒜$ 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:𝒜\to 𝒜$ is called pointed if it is equipped with a natural transformation $\sigma :{\mathrm{Id}}_{𝒜}\to S$. It is called well-pointed if $S\sigma =\sigma S$ (as natural transformations $S\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 $H$ is an endofunctor, then an $H$-algebra is an object $A$ together with a map $HA\to A$. If $(S,\sigma )$ is a pointed endofunctor, then an $S$-algebra is an object $A$ with a map $a:SA\to A$ such that $a{\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,\sigma )$ is well-pointed, then an object $A$ admits at most one $S$-algebra structure. This happens exactly when ${\sigma }_A$ is an isomorphism, in which case its inverse is that unique algebra structure.

Thus, when $S$ is well-pointed, the category of $S$-algebras is a full subcategory of $𝒜$. Well-pointed endofunctors are important, so we mention a few other ways to obtain them.

Lemma

If $(S,\sigma )$ is a well-pointed endofunctor and $S\to T$ is a natural transformation whose components are epimorphisms, then $T$ is also well-pointed.

Lemma

Suppose $(S_i,{\sigma }_i)$ is a family of (accessible) well-pointed endofunctors and let $\sigma :\mathrm{Id}\to S$ be the wide pushout of all the points ${\sigma }_i:\mathrm{Id}\to S_i$. Then $(S,\sigma )$ is (accessible and) well-pointed, and $S\mathrm{Alg}={\bigcap }_i(S_i\mathrm{Alg})$.

Lemma

Let $F:𝒜\rightleftarrows ℬ:G$ be an adjunction and $(S\prime ,\sigma \prime )$ an (accessible) well-pointed endofunctor on $ℬ$. Let $(S,\sigma )$ be the pushout

$$\begin{array}{ccc}FG& \stackrel{F\sigma \prime G}{\to }& FS\prime G\\ \downarrow & & \downarrow \\ \mathrm{Id}& \stackrel{\sigma }{\to }& S.\end{array}$$\array{ F G & \xrightarrow{F \sigma' G} & F S' G \\ \downarrow && \downarrow \\ Id & \xrightarrow{\sigma} & S. }

Then $(S,\sigma )$ is (accessible and) well-pointed, and $A\in 𝒜$ is an $S$-algebra exactly when $GA$ is an $S\prime$-algebra.

Free algebras for well-pointed endofunctors

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

Theorem

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

Proof

Given $A\in 𝒜$, define inductively the following transfinite sequence in $𝒜$:

$$A\to SA\to S^{2}A\to S^{3}A\to \cdots$$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 $S$ is $\kappa$-accessible, then $S$ will preserve the relevant colimit, and hence we have an induced action $S(S^{\alpha }A)\to S^{\alpha }A$. It is easy to check that this makes $S^{\alpha }A$ into a reflection of $A$ into $S\mathrm{Alg}$.

Some important constructions are directly examples of this theorem.

Example

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

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,\tau )$ be a general (accessible) pointed endofunctor, not necessarily well-pointed. Let $T/𝒜$ denote the comma category, whose objects are triples $(A,B,a)$ where $a:TA\to B$. Then $T/𝒜$ is again locally presentable.

If $\alpha :T\prime \to T$ is a natural transformation, we have an adjunction ${\alpha }_{!}:T\prime /𝒜\rightleftarrows T/𝒜:{\alpha }^{*}$ in which ${\alpha }^{*}$ sends $(A,B,a)$ to $(A,B,a\circ {\alpha }_A)$ and ${\alpha }_{!}$ is defined by a pushout.

Note that if $\alpha$ is $\tau :\mathrm{Id}\to T$, then ${\tau }^{*}(A,B,a)$ is the composite $A\stackrel{{\tau }_A}{\to }TA\stackrel{a}{\to }B$ in ${𝒜}^2=\mathrm{Id}/𝒜$.

Lemma

The category $T\mathrm{Alg}$ of $T$-algebras is a reflective full subcategory of $T/𝒜$.

Proof

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

Theorem

The category $T\mathrm{Alg}$ is monadic over $𝒜$, and cocomplete. In particular, the algebraically-free monad on $T$ exists and is accessible.

Proof

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

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

$$\begin{array}{ccccccccc}& & 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 \end{array}$$\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_{\beta }\to X_{\beta +1}$ is equal to $x_{\beta }\circ {\tau }_{X_{\beta }}$.

We begin with $X_0=A$, $X_1=B$, and $x_0=a$. Given $X_{\beta }$ and $X_{\beta +1}$, we define $x_{\beta +1}:T{X}_{\beta +1}\to X_{\beta +2}$ to be the coequalizer of the two composites

$$T{X}_{\beta }\underset{T\tau }{\overset{\tau T}{\rightrightarrows }}{T}^2{X}_{\beta }\stackrel{T{x}_{\beta }}{\to }T{X}_{\beta +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_{\alpha }:T{X}_{\alpha }\to X_{\alpha +1}$ be the coequalizer of the two maps

$$\begin{array}{ccc}& & {colim}_{\beta <\alpha }{X}_{\beta +1}=X_{\alpha }\\ & \nearrow & & {\searrow }^{\tau }\\ {colim}_{\beta <\alpha }T{X}_{\beta }& & \to & & T{X}_{\alpha }.\end{array}$$\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 $H$ is the same as an algebra for the pointed endofunctor $T≔\mathrm{Id}+H$. Thus, Theorem 2 can be applied to unpointed endofunctors as well.

In this case, the transfinite sequence for the free $H$-algebra on $A\in 𝒜$ is much simpler: we have $X_0=A$ and $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 $T$ be a monad on $𝒜$, and let $T\mathrm{Alg}$ denote the category of $T$-algebras qua monad.

Theorem

The category $T\mathrm{Alg}$ is a reflective subcategory of $T/𝒜$.

Proof

For $(A,B,a)\in T/𝒜$, consider the pushout

$$\begin{array}{ccc}{T}^{2}A& \stackrel{\mu }{\to }& TA\\ {}^{Ta}\downarrow & & \downarrow \\ TB& \stackrel{c}{\to }& D\end{array}$$\array{ T^2 A & \xrightarrow{\mu} & T A \\ ^{T a}\downarrow && \downarrow\\ T B & \xrightarrow{c} & D }

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

Corollary

$T\mathrm{Alg}$ is locally presentable. Moreover, any functor $T\mathrm{Alg}\to T\prime \mathrm{Alg}$ induced by a monad morphism $T\prime \to T$ has a left adjoint.

Proof

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

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:K\to \mathrm{Monad}(𝒜)$ be a diagram in the category of monads on $𝒜$, and define a $V$-algebra to be an object $A$ together with $V_k$-algebra structures which commute with the images of morphisms in $K$.

Definition

An algebraic colimit of $V$ is a monad $P$ whose usual Eilenberg-Moore category $P\mathrm{Alg}$ is equivalent, over $𝒜$, to the category of $V$-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 $K$ has an initial object; otherwise, give it a new initial object $0$ and define $V_0=\mathrm{Id}$. Let $T$ be the (pointwise) colimit of $V$ in the category of endofunctors of $𝒜$, with coprojections $r_k:V_k\to T$. Our assumption on $K$ gives $T$ a unique point $\mathrm{Id}\to V_0\to T$ such that each $r_k$ is a map of pointed endofunctors. Moreover, a $T$-algebra (qua pointed endofunctor) is an object $A$ together with compatible pointed-endofunctor-algebra structures for each $V_k$. This clearly includes the $V$-algebras, as defined above, as a full subcategory.

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

$$\begin{array}{ccc}& & V_{k}A\\ & {}^{{\mu }_k}\nearrow & & {\searrow }^{V_k{\tau }_k}\\ V_k^{2}A& & \stackrel{\mathrm{id}}{\to }& & V_k^{2}A& \stackrel{V_k(a{r}_k)}{\to }& V_{k}B& \stackrel{r_k}{\to }TB.\end{array}$$\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)$, defining an endofunctor of $T/𝒜$. Then $L$ is accessible, and an $L$-algebra is precisely a $V$-algebra.

Moreover, $L$ admits an epimorphic transformation from the well-pointed endofunctor $S$ defined as in Theorem 2 whose algebras are the $T$-algebras (qua pointed endofunctor). Thus, by Lemma 2, $L$ 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.