Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

April 3, 2017

Gluing Together Finite Shapes with Kelly

Posted by Emily Riehl

Guest post by David Jaz Myers

The Kan Extension Seminar continues with Kelly’s Structures defined by limits in the enriched context, I, or as I like to call it, Presenting categories whose objects are glued together out of finite shapes. This paper hit the presses in 1982 and represented both a condensation and generalization of the theory of locally finitely presentable categories. Kelly achieved both the condensing and the generalizing through his use of weighted (or, as he calls them, indexed) limits and colimits. The resulting theory is slick and highly categorical, but very dense. So, in this post, we’re going to button down a bit and skim over a few details so that we can focus on the story and the powerful results which sustain it, rather than the technicalities. I will label the propositions by where they appear in Kelly’s paper, so that you can find the technicalities if you would like.

At first, it will seem like this post is a radical departure from the previous seminar posts. But as we go on, we’ll see that gluing together finite shapes has a lot to do with the categorical approach to algebra that Evangelia wrote about in the post that kicked off our seminar.

Before I start, I’d like to thank Emily, Alexander, and Brendan for organizing this lovely seminar and inviting me to participate. I’d also like to thank my fellow students for their insight and conversation.

Throughout this paper, Kelly works in the enriched context. Where normally we like to think of there being a set of arrows between any two objects of a category, Kelly wants us to think of there being an object of arrows. This object of arrows can live in any suitably nice category, which here will mean a symmetric monoidal closed and cocomplete (and later, locally finitely presentable) category. We call this category our base category, and denote it by the letter 𝒱\mathcal{V}.

For the rest of this blog post, we will work from the 𝒱\mathcal{V}-point of view. When I say “category”, I will mean 𝒱\mathcal{V}-category, and same for “functor” and “natural transformation”. For the most part, this will work smoothly. But the crucial notion of being “filtered”, which we will come to later, is only defined over the category of sets. I’ll try and be explicit about this when it comes up. For a brief intro to the 𝒱\mathcal{V}-point of view, see the previous blog post which introduces enrichment and its limits.

Understanding Objects by Looking at Figures in Them

When we work with a mathematical structure XX, we often like to do so in terms of its elements. In our base category, it suffices to look at the points of XX, the maps 1X1 \to X. But, in more general categories 𝒞\mathcal{C}, we may need to consider figures SXS \to X of a more general shape.

Remark For the rest of this post, I will use the term “figure in XX” to mean a morphism SXS \to X in a category, and “shape” to mean the domain of a figure. By an “incidence relation” between shapes, I just mean morphisms between them. A somewhat more common name for “shape” would be “test space”, but I find the word “shape” to be more cozy.

Yoneda’s lemma tells us that we lose no information if we use figures of an arbitrary shape.

Lemma (Yoneda’s Lemma) In any category, morphisms XYX \to Y naturally correspond to functions which take figures in XX to figures of the same shape in YY which respect the incidence relations between the shapes.

However, it will often be the case that general shapes are just too complicated to work with. After all, we are trying to study an object in a category; a general morphism into it can be no less complicated. Even worse, there are often so many general shapes that they cannot be collected into a set (if we are working in a large category). It would be very nice to have a small subcategory 𝒢𝒞\mathcal{G} \hookrightarrow \mathcal{C} of “tractable shapes” that we could restrict our attention to. “Tractable” is not a technical term, but more of a suggestive name like “nice”.

Such a subcategory would induce a functor 𝒞(𝒢,):𝒞𝒱 𝒢 op\mathcal{C}(\mathcal{G}, -) : \mathcal{C} \to \mathcal{V}^{\mathcal{G}^{\text{op}}} sending an object of 𝒞\mathcal{C} to its functor of “figures with tractable shape”. If we can glue together the objects of 𝒞\mathcal{C} (that is, if 𝒞\mathcal{C} is cocomplete), then this functor will have a left adjoint given by taking the weighted colimit of the inclusion 𝒢𝒞\mathcal{G} \hookrightarrow \mathcal{C}. We can think of this left adjoint as gluing together a bunch of tractable shapes into an object of 𝒞\mathcal{C}. Let’s look at a few examples of this kind of arrangement.

  • As I mentioned above, it suffices to work with points (that is, figures 1X1 \to X of shape 11) when we are in the base category. This should mean that if we take our category of “tractable shapes” to be just the subcategory containing the monoidal unit 11, we will recover all of our base category. And indeed, 𝒱(1,):𝒱𝒱 1 op\mathcal{V}(1, -) : \mathcal{V} \to \mathcal{V}^{1^{\text{op}}} is an isomorphism of categories! Its inverse sends an object W:1 op𝒱W : 1^{\text{op}} \to \mathcal{V} of points to the copower W1W \cdot 1, the WW-indexed sum of points.
  • Let’s work over sets, and consider the category of graphs 𝒞\mathcal{C} (to be specific, by “graph” I mean a symmetric relation). It no longer suffices to just look at points *X\ast \to X (figures in XX whose shape is a single point *\ast), since there can be many graphs with the same set of points. Nor can we just look at figures whose shape is a single edge **\ast - \ast, since many graphs have the same set of edges. But if we keep in mind the incidence relations between these two shapes, which is just that the point *\ast lies in the edge **\ast - \ast in two ways, then we can recover the whole of our graph XX. We let 𝒢={*(**)}\mathcal{G} = \{\ast \rightrightarrows (\ast - \ast) \} be our subcategory of tractable shapes, and we find that 𝒞(𝒢,);𝒞𝒱 𝒢 op\mathcal{C}(\mathcal{G}, -) ; \mathcal{C} \to \mathcal{V}^{\mathcal{G}^{\text{op}}} is fully faithful. Its adjoint is the functor which glues a bunch of edges onto a bunch of points, and that it is fully faithful means that any morphism of graphs is determined by its actions on the points and edges.
  • Now let’s look at an example where our object XX is seriously intractable. Working over sets again, let 𝒞\mathcal{C} be the category of topological spaces. As above, a topological space XX is not determined by its points. We can try to get a grip on XX by modeling it with triangles. Higher dimensional triangles are called simplices, and they are particularly nice spaces, so we can take our tractable objects 𝒢\mathcal{G} to be the subcategory of simplices and their incidence relations. Then the 𝒞(𝒢,):𝒞𝒱 𝒢 op\mathcal{C}(\mathcal{G}, -) : \mathcal{C} \to \mathcal{V}^{\mathcal{G}^{\text{op}}} sends a topological space to its singular simplicial set, and its left adjoint gives the geometric realization of an abstract simplicial set. In this case, 𝒞(𝒢,)\mathcal{C}(\mathcal{G}, -) is only faithful; there are spaces (like Cantor’s space) which aren’t well studied by looking at triangles in them.

For this program of looking at “tractable shapes” to work out, we will need the objects of 𝒞\mathcal{C} to be suitably determined by the figures of tractable shape inside them. We will take “suitably determined” to mean that we can test if a morphism is an isomorphism by checking if it induces a bijection on figures of tractable shape.

Definition Let 𝒞\mathcal{C} be cocomplete and let 𝒢𝒞\mathcal{G} \hookrightarrow \mathcal{C} be a subcategory. We say that 𝒢\mathcal{G} is a strong generator of 𝒞\mathcal{C} if 𝒞(𝒢,)\mathcal{C}(\mathcal{G}, -) is conservative (that is, if it reflects isomorphisms).

So, we are looking for a strong generator 𝒢\mathcal{G} consisting of “tractable” objects of 𝒞\mathcal{C}. But what does “tractable” mean?

Let’s consider an algebraic example, say, the category 𝒞=Grp\mathcal{C} = \text{Grp} of groups (as a set-category). We often study algebras by looking at the equations that elements in them satisfy. For example, a group is abelian if ab=baab = ba for every two elements aa and bb in it. These finite sets of relations between elements can be seen as figures in the group; the shape of these figures is a finitely presented group, generated by the elements and quotiented by the relations in question. For example, the commuting pairs in a group are precisely the figures (homomorphisms) of shape (with domain) a,bab=ba\langle a, b \mid ab = ba \rangle.

In this algebraic setting, it seems reasonable to take “tractable” to mean finitely presentable. By finitely presentable, I mean admitting a finite presentation in terms of generators and relations in the usual sense. Here is a categorical way to describe a presentation in terms of generators and relations: we have a set of generators and a set of relations together with two homomorphisms from the free algebra on the relations to the free algebra on the generators taking a relation to the left and right hand sides of the equality that represents it. Then, to be presented by such a presentation means to be a coequalizer of those two arrows. For example, the group a,bab=ba\langle a, b \mid ab = ba\rangle above is given by the coequalizer of ca,b\langle c \rangle \rightrightarrows \langle a , b \rangle where the left arrow sends cc to abab and the right sends cc to baba.

Interestingly, there is an abstract categorical definition of finite presentability which doesn’t mention generators or relations at all!

Theorem In a category of algebras 𝒞\mathcal{C} (say, models of a Lawvere theory), an algebra AA is finitely presentable if and only if the hom functor 𝒞(A,)\mathcal{C}(A, -) commutes with filtered colimits.

Finite Shapes and Gluing Them Together

Given the above abstract definition of finite presentability, we will take “tractable” to mean “finitely presentable” in the abstract categorical sense. Let’s explain precisely what this is now.

Definition A set-category 𝒟\mathcal{D} is filtered if every functor 𝒥𝒟\mathcal{J} \to \mathcal{D} with 𝒥\mathcal{J} finite has a cocone.

The colimit of a diagram 𝒟𝒞\mathcal{D} \to \mathcal{C} is filtered if 𝒟\mathcal{D} is.

A functor 𝒞\mathcal{C} \to \mathcal{B} is finitary if it commutes with filtered colimits.

An object GG in 𝒞\mathcal{C} is finitely presentable (or f.p.) if 𝒞(G,):𝒞𝒱\mathcal{C}(G, -) : \mathcal{C} \to \mathcal{V} is finitary. We denote by 𝒞 f\mathcal{C}_f the (full) category of f.p. objects in 𝒞\mathcal{C}.

Finitely presentable objects are “morally finite”, relative to whatever category they are in. A good grounding example occurs in the truth value enriched setting.

Theorem Let Ω\Omega be the order of open sets in a topological space XX, considered as a category over the truth values. If KXK \subseteq X is a subset, then the functor UKUU \mapsto K \subseteq U is finitary if and only if KK is compact.

Proof Commuting with filtered colimits means K iU ii(KU i) K \subseteq \bigcup_i U_i \iff \exists i (K \subseteq U_i) for each filtered family of open sets (U i) i(U_i)_i. We can complete any open cover to a filtered cover by throwing in finite unions of opens in the cover; if the functor is finitary, then one such finite union contains KK, so KK is compact.

If KK is compact, any open cover (including one that is filtered) contains a finite subcover; since the cover is filtered, there is open set in it containing the finite cover, which shows that the functor is finitary.

It’s reasonable to think of compact sets as “topologically finite”. Representing a finitary functor makes an object “finite” in the category in question. For example, a finitely presentable set is finite.

Claim A finitely presentable set is finite.

Proof If XX is finitely presentable, then Set(X,)\text{Set}(X,-) commutes with filtered colimits. Every set is the filtered colimit of its finite subsets, so in particular Set(X,X)colimSet(X,n)\text{Set}(X,X) \cong \text{colim}\text{Set}(X, n). But then the identity of XX factors through one of its finite subsets, so XX is finite.

It would be good to show further that every finite set is finitely presentable. We can do even better by showing that gluing together finitely many finite shapes gives us a finite shape. But first, we should make sure we know what “finitely many” means in the enriched context.

Definition A weight W:𝒟𝒱W : \mathcal{D} \to \mathcal{V} is finite when

  • 𝒟\mathcal{D} has finitely many objects (up to isomorphism),
  • 𝒟(i,j)\mathcal{D}(i, j) is f.p. for all ii and jj in 𝒟\mathcal{D}, and
  • W iW_i is f.p. for all ii in 𝒟\mathcal{D}.

Finite (co)limits are those whose weights are finite.

Lemma (4.41) For 𝒞\mathcal{C} cocomplete, 𝒞 f\mathcal{C}_f is closed under finite colimits.

Corollary A set is finite if and only if it is finitely presentable.

Proof We saw that finitely presentable sets are finite, so it remains to show that finite sets are finitely presentable. But a finite set is a finite coproduct of the set 11, and 11 is finitely presentable because Set(1,X)X\text{Set}(1, X) \cong X commutes with filtered colimits.

Now that we have a good formal definition of “tractable”, we can define those categories whose objects are suitably determined by the tractable figures within them.

Definition A category 𝒞\mathcal{C} is locally finitely presentable (l.f.p.) when

  • it is cocomplete, and
  • there is a small subcategory 𝒢𝒞\mathcal{G} \hookrightarrow \mathcal{C} so that the induced 𝒞(𝒢,)\mathcal{C}(\mathcal{G}, -) is finitary and conservative.

Note that 𝒞(𝒢,)\mathcal{C}(\mathcal{G}, -) being finitary implies that 𝒢𝒞 f\mathcal{G} \hookrightarrow \mathcal{C}_f, since we can calculate colimits in 𝒱 𝒢 op\mathcal{V}^{\mathcal{G}^{\text{op}}} pointwise.

Since being finitary relies on a definition over the category of sets, there can be subtle differences between the objects which are finitely presented over sets versus objects that are finitely presented over the base 𝒱\mathcal{V}. For example, the monoidal unit 11 is always finitely presentable over 𝒱\mathcal{V}, since 𝒱(1,X)X\mathcal{V}(1, X) \cong X. But over sets, it might not be, since the set of points of an object in 𝒱\mathcal{V} might be ill-behaved. Kelly gives a good example of this: in the category of actions of a group GG, the monoidal unit GG is always finitely presentable over the actions, but it is only finitely presentable over sets if GG is finite.

For more on these subtleties, see section 5 of the paper; from now on, we will assume that our base 𝒱\mathcal{V} is l.f.p. over sets and that moreover the f.p. objects in 𝒱\mathcal{V} are the same whether taken over 𝒱\mathcal{V} or over sets. This occurs if and only if the monoidal unit of 𝒱\mathcal{V} is f.p. over sets and the tensor product of two f.p.-over-sets objects is f.p. over sets (see 5.5 in the paper). Kelly calls this situation being “l.f.p. as a monoidal closed category”, and so we will as well.

Now, Kelly proves some serious theorems about l.f.p. categories.

Theorem (7.2) Let 𝒞\mathcal{C} be l.f.p. with strong generator 𝒢𝒞 f\mathcal{G} \hookrightarrow \mathcal{C}_f. Then

  • 𝒞 f\mathcal{C}_f is the closure of 𝒢\mathcal{G} under finite colimits,
  • 𝒞 f\mathcal{C}_f is dense in 𝒞\mathcal{C}, meaning that 𝒞(𝒞 f,)\mathcal{C}(\mathcal{C}_f,-) is fully faithful.
  • 𝒞(𝒞 f,)\mathcal{C}(\mathcal{C}_f, -) is also finitary.
  • 𝒞\mathcal{C} is complete.

This theorem shows that the finite shapes in a category whose objects are determined by some particular subcategory 𝒢\mathcal{G} of finite “tractable” shapes are precisely those shapes which can be glued together out of finitely many “tractable” shapes from 𝒢\mathcal{G}. For example, working over sets, we see that the finitely presentable graphs are precisely the finite colimits of the point and the edge, that is, precisely the finite graphs. We can also deduce that the finitely presentable simplicial sets are those which have a finite number of simplices.

Rather surprisingly, we also find that 𝒞\mathcal{C} is complete. Perhaps this is not so surprising though; if we know how to glue our objects together out of finite shapes, then we can form families of objects by forming families of these shapes. So, l.f.p. categories are very nice categories indeed. As a corollary of this theorem, Kelly gives a few more characterizations of l.f.p. categories that show that the choice of generators 𝒢\mathcal{G} is not essential.

Corollary (7.3) The following are equivalent for a cocomplete category 𝒞\mathcal{C}:

  • 𝒞\mathcal{C} is locally finitely presentable,
  • 𝒞 f\mathcal{C}_f is small and strongly generating,
  • 𝒞 f\mathcal{C}_f is small and dense,
  • 𝒞\mathcal{C} is a reflective subcategory of 𝒱 𝒢 op\mathcal{V}^{\mathcal{G}^{\text{op}}} with finitary inclusion, for some 𝒢\mathcal{G}.

Here we see that the l.f.p. categories are reflective subcategories of presheaf categories. Since presheaf categories are always fantastically nice (inheriting, as they do, most of the nice structure of the base), l.f.p. categories are fantastically nice as well. For example, in the category of sets, finite limits commute with filtered colimits. In a l.f.p. category over an l.f.p. base, we can deduce the same.

Lemma (4.9) Let 𝒞\mathcal{C} be a l.f.p. category over an l.f.p. (as a monoidal closed category) base. Then finite limits commute with filtered colimits in 𝒞\mathcal{C}.

Furthermore, l.f.p. categories satisfy two really nice adjoint functor theorems. Before we can express them, we need to mention that the above discussion of filtered colimits and f.p. objects can be repeated with “finite” (that is, “less than 0\aleph_0”) being replaced by “less than κ\kappa” for any regular cardinal κ\kappa.

Theorem (7.8, 7.9) Let 𝒞\mathcal{C} and \mathcal{B} be l.f.p. and let F:𝒞F : \mathcal{C} \to \mathcal{B} be a functor. Then

  • FF is a left adjoint if and only if it commutes with colimits, and
  • FF is a right adjoint if and only if it and commutes with limits and κ\kappa-filtered colimits for some regular cardinal κ\kappa.

As an example, let 𝒞\mathcal{C} be the category of graphs over sets, and let F=𝒞(*,)F = \mathcal{C}(\ast, -) be the functor of points. As a covariant representable, FF commutes with limits, and since colimits of graphs are constructed pointwise, it also commutes with colimits. Therefore, FF has both a left and a right adjoint, given by forming the discrete graph with no edges and the complete graph with all possible edges.

An Aside: Essentially Algebraic Theories

As an aside, let’s discuss the notion of an essentially algebraic theory. A theory is algebraic when it involves equations between functions of finitely many variables, and therefore may be interpreted in any category with finite products. A theory is essentially algebraic when it involves equations between partial functions of finitely many variables (whose domains are carved out by equations). Therefore, an essentially algebraic theory may be interpreted in any category with finite limits. The theory of categories is an example of an essentially algebraic theory which is not algebraic; composition is only defined for some pairs of morphisms.

Definition An essentially algebraic theory 𝒯\mathcal{T} is a small finitely complete category.

A model of an essentially algebraic theory 𝒯\mathcal{T} is a left exact functor M:𝒯𝒞M : \mathcal{T} \to \mathcal{C}. Being left exact (or, shortly, lex) means commuting with finite limits.

A moral of this story is that a lot of what works for Lawvere theories over sets works for enriched essentially algebraic theories. In particular, we can take the free finite completion 𝒞\mathcal{L}_{\mathcal{C}} of a category 𝒞\mathcal{C}, which by definition satisfies the following universal property: Lex( 𝒞,)𝒱-Cat(𝒞,)\text{Lex}(\mathcal{L}_{\mathcal{C}}, \mathcal{B}) \simeq \mathcal{V}\text{-Cat}(\mathcal{C}, \mathcal{B}) for f.c. \mathcal{B}. In particular, 1𝒱 f op\mathcal{L}_1 \cong \mathcal{V}_f^{\text{op}}, so we see that Lex(𝒱 f op,𝒱)𝒱-Cat(1,).\text{Lex}(\mathcal{V}_f^{\text{op}}, \mathcal{V}) \simeq \mathcal{V}\text{-Cat}(1, \mathcal{B}) \cong \mathcal{B}. Therefore, we can see 𝒱 f op\mathcal{V}_f^{\text{op}} as the “theory of an object”; its models are just objects.

An algebra of an essentially algebraic theory is a model in the base category. Kelly gives the following characterization of algebras of theories.

Corollary (6.11) Let M:𝒯𝒱M : \mathcal{T} \to \mathcal{V} be a functor from an essentially algebraic theory 𝒯\mathcal{T}. Then the following are equivalent:

  • MM is left exact, and hence an algebra.
  • MM is a filtered colimit in 𝒱-Cat(𝒯,𝒱)\mathcal{V}\text{-Cat}(\mathcal{T}, \mathcal{V}) of representables.
  • MM is an element of the filtered-colimit completion of 𝒯 op\mathcal{T}^{\text{op}} (as the completion of 𝒯 op𝒱-Cat(𝒯,𝒱)\mathcal{T}^{\text{op}} \hookrightarrow \mathcal{V}\text{-Cat}(\mathcal{T}, \mathcal{V}) under filtered colimits).

The appearance of filtered colimits in this theorem suggests that our brief aside into essentially algebraic theories is anything but an aside.

That Wasn’t an Aside!

In this section, we will see that locally finitely presentable categories and essentially algebraic theories are closely intertwined. In fact, we will show that essentially algebraic theories present l.f.p. categories, and that this gives rise to a duality between a doctrine of theories and a doctrine of l.f.p. categories. I’m using the word “doctrine” here to mean just a “theory of theories”. Thus, categories whose objects are glued together out of finite shapes are precisely the categories of algebras for essentially algebraic theories.

We begin with the following theorem.

Lemma (7.2) Let 𝒞\mathcal{C} be l.f.p.. Then 𝒞Lex(𝒞 f op,𝒱)\mathcal{C} \simeq \text{Lex}(\mathcal{C}_f^{\text{op}}, \mathcal{V}).

Proof By 6.116.11, this is equivalent to 𝒞\mathcal{C} being the filtered-colimit completion of 𝒞 f op\mathcal{C}_f^{\text{op}}, which holds by (the rest of) 7.27.2.

Since this says that 𝒞\mathcal{C} is the category of algebras of 𝒞 f op\mathcal{C}_f^{\text{op}}, we can see 𝒞 f op\mathcal{C}_f^{\text{op}} as “the theory of an object of 𝒞\mathcal{C}”. As an example, this shows that the essentially algebraic theory of groups is equivalent to the opposite of the category of finitely presentable groups. Since a finitely presentable group is a coequalizer of finitely generated free groups, left exact functors out of this category are determined by their actions on the finitely generated free groups. We ran into the fact that the opposite of the category of finitely generated free groups determines the Lawvere theory of groups before; we are seeing this fact again, but in some more generality.

Now, let’s turn out attention to the restriction and extension of scalars between theories. Let F:𝒯𝒯F : \mathcal{T} \to \mathcal{T}' be a lex functor between theories. Since composites of lex functors are lex, we get a functor F *:Lex(𝒯,𝒱)Lex(𝒯,𝒱)F^\ast : \text{Lex}(\mathcal{T}', \mathcal{V}) \to \text{Lex}(\mathcal{T}, \mathcal{V}) by precomposition. This is the restriction of scalars functor; between theories of modules of rings it would be just that. We call functors F *:Alg 𝒯Alg 𝒯F^{\ast} : \text{Alg}_{\mathcal{T}'} \to \text{Alg}_{\mathcal{T}} induced in this way algebraic functors.

Corollary (9.5, 6.12) F *F^\ast is finitary, and therefore colim F:𝒱-Cat(𝒯,𝒱)𝒱-Cat(𝒯,𝒱)\text{colim}_F : \mathcal{V}\text{-Cat}(\mathcal{T}, \mathcal{V}) \to \mathcal{V}\text{-Cat}(\mathcal{T}', \mathcal{V}) (by which I mean left Kan extension along FF) descends to F *:Lex(𝒯,𝒱)Lex(𝒯,𝒱)F_{\ast} : \text{Lex}(\mathcal{T}, \mathcal{V}) \to \text{Lex}(\mathcal{T}', \mathcal{V}) which is left adjoint to F *F^\ast.

Adjoint to the restriction of scalars, we get our usual extension of scalars functor. As a corollary, we get the following nice result.

Corollary The category of algebras of a theory 𝒯\mathcal{T} is a reflective subcategory of the category 𝒱 𝒯\mathcal{V}^{\mathcal{T}} of copresheaves on it.

Proof Alg 𝒯𝒱-Cat(𝒯,𝒱)Lex( 𝒯,𝒱)\text{Alg}_{\mathcal{T}} \hookrightarrow \mathcal{V}\text{-Cat}(\mathcal{T}, \mathcal{V}) \cong \text{Lex}(\mathcal{L}_{\mathcal{T}}, \mathcal{V}) is algebraic, given by the reflection 𝒯𝒯\mathcal{L}_{\mathcal{T}} \to \mathcal{T} of 𝒯 𝒯\mathcal{T} \hookrightarrow \mathcal{L}_{\mathcal{T}} sending formal limits to the actual limits in 𝒯\mathcal{T}.

Now, a few sections ago we proved that reflective subcategories of presheaves were locally finitely presentable. Therefore, we can turn the previous corollary into the following theorem.

Theorem (9.8) For a finitary theory 𝒯\mathcal{T},

  • the category Alg 𝒯\text{Alg}_{\mathcal{T}} of 𝒯\mathcal{T}-algebras is l.f.p.,
  • Alg 𝒯f\text{Alg}_{\mathcal{T} f} is the essential image of 𝒯 opAlg 𝒯\mathcal{T}^{\text{op}} \hookrightarrow \text{Alg}_{\mathcal{T}}, and
  • Alg 𝒯f𝒯 op\text{Alg}_{\mathcal{T} f} \simeq \mathcal{T}^{\text{op}}.

This theorem intertwines l.f.p. categories and essentially algebraic theories in the following precise way.

Corollary A category 𝒞\mathcal{C} is l.f.p. precisely when it is the category of algebras for a finitary theory (which is then equivalent to 𝒞 f op\mathcal{C}_f^{\text{op}}.)

In fact, we can say something more. Since categories of algebras are l.f.p., a functor F *:Alg 𝒯Alg 𝒯F^{\ast} : \text{Alg}_{\mathcal{T}'} \to \text{Alg}_{\mathcal{T}} has a left adjoint if it is finitary and continuous. If this occurs, then its adjoint F *F_{\ast} preserves f.p. objects by the following calculation. Alg 𝒯(F *X,colim) Alg 𝒯(X,F *colim) by adjointness, Alg 𝒯(X,colimF *) by finitariness, colimAlg 𝒯(X,F *) by f.p. colimAlg 𝒯(F *X,) by adjointness. \begin{aligned} \text{Alg}_{\mathcal{T}'}(F_{\ast}X, \colim -) &\cong \text{Alg}_{\mathcal{T}}(X, F^{\ast}\colim -) &\qquad\text{by adjointness,}\\ &\cong \text{Alg}_{\mathcal{T}}(X, \colim F^{\ast} -) &\qquad\text{by finitariness,}\\ &\cong \colim \text{Alg}_{\mathcal{T}}(X, F^{\ast}-) &\qquad\text{by f.p.}\\ &\cong \colim \text{Alg}_{\mathcal{T}'}(F_{\ast}X, -) &\qquad\text{by adjointness.} \end{aligned}

Therefore, F *F_{\ast} restricts to a functor 𝒯 op𝒯 op\mathcal{T}^{\text{op}} \to \mathcal{T}'^{\text{op}}, and as a left adjoint it is cocontinuous. Therefore, F *:𝒯𝒯F_{\ast} : \mathcal{T} \to \mathcal{T}' commutes with limits. We have shown that F *F^{\ast} is algebraic precisely when it is finitary and continuous, and we can bundle all of this up into the following general theorem.

Theorem (9.14) Let

  • 𝒱-Th\mathcal{V}\text{-Th} be the 𝒱-Cat\mathcal{V}\text{-Cat} enriched category of theories and lex functors, and
  • 𝒱-lfp\mathcal{V}\text{-lfp} be the 𝒱-Cat\mathcal{V}\text{-Cat} enriched category of l.f.p. 𝒱\mathcal{V}-categories and finitary right adjoint functors.

Then

Gabriel-Ulmer Duality

is a bi-equivalence.

Over sets, this bi-equivalence is called the Gabriel-Ulmer duality. Following Lawvere, we could call this contravariant bi-equivalence the “structure-semantics duality”. The structure map is the one which extracts the finite objects from an l.f.p. category, and the semantics map takes a theory to its category of algebras. In the language of this post, this bi-equivalence shows that categories whose objects can be glued together out of finite shapes and the suitably finite functors between them are presented by essentially algebraic theories. On this blog, David Corfield has discussed other variants of this sort of duality.

Concluding Thoughts

We’ve covered a lot of ground in this blog post, and we’ve still managed to skip out on big sections of Kelly’s paper. In particular, we missed section 5 relating finite presentability over a general base to finite presentability over sets, section 6 studying flatness of functors, section 8 concerning local finite presentability over sets in more detail, and section 10 which concerns sketches. Here are some of the things we did get to see.

  • Weighted (co)limits as the enriched version of (co)limits.
  • Objects being glued together out of figures of “tractable shape”.
  • A definition of “finite” in the general categorical context.
  • A characterization of the categories whose objects are glued together out of finite shapes.
  • A general notion of “algebraic theory”, general enough to include the dual of the finite shapes.
  • That the models of this theory (dual to the finite shapes) are precisely the objects of the category.
Posted at April 3, 2017 1:52 AM UTC

TrackBack URL for this Entry:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2955

3 Comments & 0 Trackbacks

Re: Gluing Together Finite Shapes with Kelly

Great post!

I really like your series of motivating examples, building up from points to edges to simplices. In your example of topological spaces, could we restrict to some special subcategory 𝒞𝒞\mathcal{C}' \subset \mathcal{C} of topological spaces under which 𝒞(𝒢,)\mathcal{C}'(\mathcal{G}, -) is conservative? Would such a 𝒞\mathcal{C}' be something like topological manifolds?

(I was initially confused by the notation 𝒞(𝒢,)\mathcal{C}(\mathcal{G}, -), because the Yoneda embedding c𝒞(,c)c \mapsto \mathcal{C}(-,c) would then be written 𝒞(𝒞,)\mathcal{C}(\mathcal{C},-) (with 𝒞\mathcal{C} on the ‘other side’ of cc). But once I got used to it, it actually works very nicely with the rest of your post.)

The characterization of l.f.p. categories in (7.2) reminds me of Hilbert spaces: every Hilbert space HH has a maximal orthonormal subset BB such that Span(B)\text{Span}(B) (finite linear combinations) is dense in HH. I think of 𝒢\mathcal{G} as BB and its closure under finite colimits 𝒞 f\mathcal{C}_f as Span(B)\text{Span}(B). Daniel, Alexander and you had some reasons for and against this analogy; maybe you guys could raise them here.

In David Corfield’s post that you linked, he mentions this short paper by Brian Day. The upshot is that

Lex 𝒰(𝒞 op,𝒰)C-Comod \text{Lex}_{\mathcal{U}}(\mathcal{C}^{op}, \mathcal{U}) \cong C\text{-Comod}

where CC is a coendomorphism coalgebra given by the coend of a ‘fiber functor’ 𝒞𝒰 f\mathcal{C} \to \mathcal{U}_f. We have Gabriel-Ulmer on the left, and Tannaka on the right. What’s nice about the Tannaka point of view is that structures on 𝒞\mathcal{C} (e.g. monoidal, rigid) can be transferred to structures on CC (bialgebra, antipode resp.), and vice versa. The paper doesn’t seem to use much more than the stuff in your post (all the stuff leading up to Gabriel-Ulmer duality) and Simon’s (Day convolution), but following the details is proving to be a bit harder than I had anticipated.

(Does anyone know where the names ‘end’ and ‘coend’ come from? Are they somehow motivated by ‘endomorphism algebra’ and ‘coendomorphism coalgebra’?)

Posted by: Ze on April 5, 2017 7:28 PM | Permalink | Reply to this

Re: Gluing Together Finite Shapes with Kelly

Thanks Ze!

Topoligical spaces are not l.f.p, and indeed they are not presentable for any cardinal. This MathOverflow post lists a citation; basically, there are spaces like the Sierpinski space (which classifies open sets) that are not presentable.

I’m used to thinking about the objects of an equipment (say, the equipment of enriched cats, functors, and bimodules) as \emph{bases} of vector spaces, with bimodules/proarrows being \emph{matrices} expressed in this bases. This is because if we consider the equipment of finite sets and spans, then we can move between this and “finite dimensional N\N-modules with a basis” quite nicely; given a span m:MI×Jm : M \to I \times J, we think of m 1(i,j)m^{-1}(i, j) as M ijM_{ij}, and composition of spans (pullback) gives matrix multiplication. But you are saying that we should think of these objects 𝒞\mathcal{C} as the spaces themselves, arrows 𝒥𝒞\mathcal{J} \to \mathcal{C} as “lists of vectors”, with the dense ones (such as 𝒞 f𝒞\mathcal{C}_f \hookrightarrow \mathcal{C} for l.f.p. Ca\Ca) being the bases.

So if we think of the categorification of sum in a vector space as being a general colimit, then I would think of a small dense subcategory as a basis for a large category. But if we were to categorify sums to be the filtered colimits, then our hilbert spaces would be l.f.p. categories which are generated by a finitary dense subcategory. Or if we used sifted colimits, then we would get categories presented by algebraic theories as our “hilbert spaces”. So I think it really depends on the doctrine.

I do wonder about categorifying concepts from spectral analysis in this setting.

That paper was very interesting! I think I need to learn more about the motivating example (recovering coalgebras from their f.d. comodules) before really getting what was going on. I’m looking forward to it.

Posted by: David Jaz Myers on April 5, 2017 8:51 PM | Permalink | Reply to this

Re: Gluing Together Finite Shapes with Kelly

“End” is a Germanic word for where or when something stops, which is sort-of what the more-Latiny “finish” is about (also recalled in “define”: drawing the borders around an idea; and things are reasonably finite when you can finish listing them) and which is poetically evoked as a threshold or, in Latin, limina (think of sub-liminal, “under the threshold”); which is where we put (or find) limits.

Posted by: Jesse C. McKeown on April 7, 2017 3:16 AM | Permalink | Reply to this

Post a New Comment