transfinite construction of free algebras

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

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.

An endofunctor $S:\mathcal{A}\to \mathcal{A}$ is called **pointed** if it is equipped with a natural transformation $\sigma:Id_\mathcal{A} \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.

If $H$ is an endofunctor, then an $H$-algebra is an object $A$ together with a map $H A\to A$. If $(S,\sigma)$ is a pointed endofunctor, then an $S$-algebra is an object $A$ with a map $a:S A \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:

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 $\mathcal{A}$. Well-pointed endofunctors are important, so we mention a few other ways to obtain them.

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.

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

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

$\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\mathcal{A}$ is an $S$-algebra exactly when $G A$ is an $S'$-algebra.

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

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

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

$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 Alg$.

Some important constructions are directly examples of this theorem.

Let $K$ be a set of morphisms in $\mathcal{A}$; recall that an object $A\in\mathcal{A}$ is said to be *orthogonal* to $K$ if $\mathcal{A}(k,A)$ is a bijection for all $k\in K$, which is to say that each functor $\mathcal{A}(k,-):\mathcal{A}\to Set^{\mathbf{2}}$ takes $A$ to an isomorphism, where $Set^{\mathbf{2}}$ is the arrow category of Set. Now the subcategory of isomorphisms is reflective in $Set^{\mathbf{2}}$, hence is the algebras for a well-pointed endofunctor $R_k$. By Lemma 4, there is a well-pointed endofunctor $S_k$ on $\mathcal{A}$ 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 $\mathcal{A}$.

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.

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

If $\alpha:T'\to T$ is a natural transformation, we have an adjunction $\alpha_! : T'/\mathcal{A} \rightleftarrows T/\mathcal{A}: \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:Id \to T$, then $\tau^*(A,B,a)$ is the composite $A \xrightarrow{\tau_A} T A \xrightarrow{a} B$ in $\mathcal{A}^{\mathbf{2}} = Id/\mathcal{A}$.

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

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

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

A left adjoint to the forgetful functor $T Alg \to \mathcal{A}$ is supplied by reflecting the object $(A,T A,\tau_A)$ of $T/\mathcal{A}$ into $T Alg$. The monadicity theorem then applies. Colimits can be constructed in $T/\mathcal{A}$ and then reflected into $T 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

$\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 \;\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

$\array{ && \colim_{\beta\lt\alpha} X_{\beta+1} = X_\alpha \\
& \nearrow && \searrow^{\tau} \\
\colim_{\beta\lt\alpha} T X_\beta && \to && T X_\alpha.}$

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

An algebra for an unpointed endofunctor $H$ is the same as an algebra for the pointed endofunctor $T \coloneqq 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\mathcal{A}$ is much simpler: we have $X_0 = A$ and $X_{\beta+1} = A + H X_\beta$.

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.

Let $T$ be a monad on $\mathcal{A}$, and let $T Alg$ denote the category of $T$-algebras *qua* monad.

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

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

$\array{ T^2 A & \xrightarrow{\mu} & T A \\
^{T a}\downarrow && \downarrow\\
T B & \xrightarrow{c} & D }$

Define $L:T/\mathcal{A}\to T/\mathcal{A}$ 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.

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

Since $T Alg$ is reflective in the cocomplete $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/\mathcal{A} \to T'/\mathcal{A}$ has an easily defined left adjoint; now compose it with the reflection into $T/\mathcal{A}$.

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 Monad (\mathcal{A})$ be a diagram in the category of monads on $\mathcal{A}$, 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$.

An **algebraic colimit** of $V$ is a monad $P$ whose usual Eilenberg-Moore category $P Alg$ is equivalent, over $\mathcal{A}$, 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.

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

WLOG we may assume $K$ has an initial object; otherwise, give it a new initial object $0$ and define $V_0 = Id$. Let $T$ be the (pointwise) colimit of $V$ in the category of endofunctors of $\mathcal{A}$, with coprojections $r_k:V_k \to T$. Our assumption on $K$ gives $T$ a unique point $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/\mathcal{A}$. Given $(A,B,a)$, let $c:T B \to D$ be the joint coequalizer of all the parallel pairs

$\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) \coloneqq (B,D,c)$, defining an endofunctor of $T/\mathcal{A}$. 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.

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

- 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 January 4, 2013 22:54:45
by Mike Shulman
(108.225.239.218)