Locally Finitely Poly-Presentable Categories

Paul Taylor

1990

Abstract

1 Gabriel-Ulmer-Diers duality

1.1 Finite presentability

Definition 1.1 A category I (or, according to context, a diagram d : I → X or its colimit) is filtered if every finite^{1} diagram e : F → I already has a cocone in I. By convention, I and J are small filtered categories, F is a finite category, G is a small groupoid and K and L are any small categories.

Definition 1.2 An object X ∈ X is finitely presentable if the functor

Hom_{X}(X, −) : X → Set

preserves small filtered colimits.

Lemma 1.3 Hom_{X} (X, −) : X → Set preserves the colimit of the filtered diagram d : I → X (say with colimiting cocone ψ_{I} : d(I) → Y) iff

(i) every map h : X → Y factors as h = f ; ψ_{I} for some I and f : X → d(I), and

(ii) if f ; ψ_{I} = g ; ψ_{J} : X → Y then f ; d(u) = g ; d(v) for some u : I → K and v : J → K in I. Proof The two parts respectively express surjectivity and injectivity of the mediator

colim^{↑} Hom(X, d(I))  \overline{}Hom(X, Y)

[figure: post(ψ_{I})]

Hom(X, d(I))

The first is clear. For the second, recall that a colimit in Set is constructed as a quotient of a disjoint union by the equivalence relation generated by (i.e. the transitive closure of) the reflexive symmetric relation

f ∼ g ⟺^{def} ∃u : I → K, v : J → K.f ; d(u) = g ; d(v)

1There is a good reason for splitting hairs like this: the results of this and the next section hold with “finite”

replaced throughout by “of cardinality less than α” for any regular cardinal α, and in section 3.1 we shall make use of this meta-theorem.

However in the case of a filtered diagram I, it is easy to show by completing diamonds^{2} that this relation is already transitive. □

Definition 1.4 A category X is algebroidal if

(i) it is locally small,

(ii) it has small filtered colimits,

(iii) the full subcategory of finitely presentable objects is essentially small, and

(iv) every object can be expressed as a small filtered colimit of finitely presentables.

Lemma 1.5 Condition (iv) is equivalent to

(iv′) for each X ∈ X the comma category X_{fp} ↓ X is filtered, and the obvious cocone with vertex X over the diagram X_{fp} ↓ X → X is colimiting.

From (i) and (iii), X_{fp} ↓ X is essentially small. Proof Let d : I → X_{fp} ⊂ X be a small filtered diagram of finitely presentables with colimiting cocone ϕ : d → X.

• For each I ∈ I, ϕ_{I} : d(I) → X is an object of X_{fp} ↓ X. Since ϕ is a cocone, arrows of the diagram are morphisms of this category. Hence there is a functor ϕ_{(−)} : I → (X_{fp} ↓ X) such that the cocone ϕ factors through the cocone (X_{fp} ↓ X) → X. I claim that this is final [Mac Lane, 1971, section IX.3].

• Let (X′ → X) ∈ (X_{fp} ↓ X). Then since X′ is finitely presentable and d is a filtered diagram with colimit X, this factors through some X′ → d(I′) → X by Lemma 1.1.3(i). Given X′ → X′′ → d(I′′) → X, we use part (ii) to obtain a cospan I′ → I ← I′′ making the pentagon commute. More generally, given a finite diagram e : F → X_{fp} ↓ X, for each vertex or arrow of F we may choose an object or cospan of I, giving a finite diagram in I, which has a cocone, which is also a cocone over F. Hence X_{fp} ↓ X is filtered, and also any cocone over I extends uniquely to one over X_{fp} ↓ X, so these diagrams have the same colimit. □

The Ind construction “freely adjoins small filtered colimits” to an essentially small category, and is described in detail in, for instance, [Johnstone 1983] pages 225–232. We shall just quote the result in a convenient form.

Proposition 1.6 Let 𝕏 be a small category and write Ind(𝕏) for the category whose objects are small filtered diagrams d : I → 𝕏 and whose hom-sets are

Hom_{Ind(𝕏)}(d, e) ≡ lim_{I∈I} colim_{J∈J} Hom_{𝕏}(e(J), d(I))

Then Ind(𝕏) is algebroidal and the inclusion of singleton diagrams 𝕏 → Ind(𝕏) has the following pseudo-universal property: let F : 𝕏 → Y be a functor into a category with small filtered colimits; then there is a unique (up to unique natural isomorphism) continuous functor F̄ : Ind(𝕏) → Y extending F. □

Proposition 1.7 If X is algebroidal then X ≃ Ind(𝕏) where 𝕏 ≡ X_{fp}.

2We use only that I is “ω-pre-filtered”, so the argument for part (ii) is valid for a discrete diagram, i.e. a coproduct. However in this case condition (i) is unlikely to hold.

Proof We show that X ↦ (X_{fp} ↓ X) is an equivalence; we already know by Lemma 1.1.5 that it’s essentially surjective. But

Hom _{X} (colim^{↑}(X_{fp} ↓ X), colim^{↑}(X_{fp} ↓ Y))
≅ lim_{X_{fp}↓X} Hom_{X}(X′, colim^{↑}(X_{fp} ↓ Y))  definition of colim
≅ lim_{X_{fp}↓X} colim_{X_{fp}↓Y} Hom_{X}(X′, Y′)  X′ finitely presentable

□

Lemma 1.8 If ℂ is essentially small and filtered then Ind(ℂ) has a terminal object. Proof Putting e = id_{ℂ} in the construction of Ind(ℂ), with d arbitrary, it follows easily from filteredness of J ≡ ℂ that the colimit is a singleton for all I, and so there is a unique map d → e.

□

1.2 Adjoint Functor Theorem

Definition 1.9 A category X is locally finitely polypresentable or LFPP if it is algebroidal and it has small wide pullbacks.

Lemma 1.10 A category is LFPP iff it has small filtered colimits, every slice is LFP and there is an essentially small class of finitely presentable objects. □

Let S : X → Y be a functor and w : Y → SX in Y. Recall that the category of factorisations has objects the ⟨X′, w′, f′⟩ with X′ ∈ X, w′ : Y → SX′ and f′ : X′ → X with w = w′ ; Sf′ and morphisms ⟨X′, w′, f′⟩ → ⟨X′′, w′, f′′⟩ the h : X′ → X′′ such that w′ ; Sh = w′′ and h; f′′ = f′.

Lemma 1.11 Let X be an algebroidal and Y a locally small category, and let S : X → Y be a functor which preserves small wide pullbacks and small filtered colimits, and let w : Y → SX in Y with Y ∈ Y_{fp}. Then the full subcategory of the category of factorisations consisting of those ⟨X′, w′, f′⟩ with X′ ∈ X_{fp} is cofinal and essentially small. Proof Since X and Y are locally small and X_{fp} has (essentially) only a set of objects, so does this category of finitely presentable factorisations, and moreover it is also locally small. Fo cofiniality, by Lemma 1.1.5 and preservation of filtered colimits, the cocone S(X_{fp} ↓ X′) → SX′ is colimiting. But Y is finitely presentable, so w′ : Y → SX′ factors through some w′′ : Y → SX′′ and h : X′′ → X′ with X′′ ∈ X_{fp}. □

Proposition 1.12 Let X be LFPP and Y a locally small category. Then any functor S : X → Y which preserves small wide pullbacks and small filtered colimits is stable in the sense of [T89]. Proof Given w : Y → SX, for each y : Y′ → Y with Y′ ∈ Y_{fp}, consider the category C of factorisations of Y′ → Y → SX.

• C has a terminal object and (essentially) only a set of finitely presentable objects, and so we may form their wide pullback in X. By cofinality, this wide pullback is the limit of the whole of C, i.e. its initial object.

• The initial factorisation (X′, u′, f′) is functorial in (y : Y′ → Y) ∈ Y_{fp} ↓ Y, so there is a mediator u : Y = colim^{↑} Y′ → colim^{↑} SX′ = SX_{0} with f : X_{0} → X, where X_{0} = colim^{↑} X′. Any other such factorisation gives rise to a cocone over the diagram defining X_{0} (by initiality of u′ : Y′ → SX′), and hence to a mediator from X_{0}, so u is a candidate. □

Question 1.13 Is there a counterexample without preservation of filtered colimits?

Corollary 1.14 X has polycolimits of all small diagrams. Proof Let d : K → X be a diagram, which we consider as an object of the functor category X^{K}. By the Proposition, the diagonal functor X → X^{K}, which clearly preserves small wide pullbacks and small filtered colimits, is stable. The polycolimit candidates for the diagram are exactly the candidates of this stable functor at the object d. □

Exercise 1.15 Every polycolimit candidate for a finite diagram of finitely presentables is finitely presentable (but there may be infinitely many candidates). □

Proposition 1.16 The groupoid of polycolimit candidates has the following pseudo-universal property:

G × K \overline{π_{2}} K

⇐^{ϕ}

[figure: G; π_{1}; g; X; d]

Given another functor x : U → X and a natural transformation ψ : d ∘ π_{2} → x ∘ π_{1}, there is a functor f : U → G and a natural transformation χ : g ∘ f → x such that ψ = ϕ ∘ (f × K) ; χ ∘ π_{1} and these are unique up to unique isomorphism. □

Lemma 1.17 With this notation, if C : X → Y has a right adjoint then ⟨C ∘g, Cϕ⟩ is the groupoid of polycolimit candidates of C ∘ d. □

Definition 1.18 A plex category is a small category with polylimits of finite diagrams, i.e. its opposite has polycolimits.

Proposition 1.1.7 now becomes:

Proposition 1.19 Every LFPP category X is of the form Ind(𝕏) for some plex category 𝕏. □

Exercise 1.20 Show that the product of a set of LFPP categories is LFPP and that the projections are stable. What are the finitely presentable objects of an infinite product? What are the candidates for stability of the terminal projection X → 1 and the diagonal Δ : X → X × X? □

Lemma 1.21 Pullback against any map f : X → Y in an LFPP category X, as a functor f^{∗} : X ↓ Y → X ↓ X, preserves filtered colimits. Proof Let d : I → X ↓ Y be a filtered diagram with colimit y : Y′ → Y. Write x : X′ → X for the colimit of f^{∗}d : I → X ↓ X: we have to show that this is the pullback of y, and we may test this for maps from a finitely presentable object Z. So given u : Z → X and v : Z → Y′ with u ; f = v ; y, the latter factors through some d(I) → Y′. But f^{∗}d(I) → X is the pullback of d(I) → Y′ → Y, so there is a mediator Z → f^{∗}d(I) → X′. Conversely, any mediator Z → X′ factors through some f^{∗}d(I) by finite presentability, and using Lemma 1.1.3(ii) we can show that Z → X′ is unique.

Lemma 1.22 Let X be a category with filtered colimits. Suppose there is a stable functor S : X → Y to LFPP category which is full and faithful on slices and is such that for every Y ∈ Y_{fp}, the groupoid of candidates Y → SX is small. The X is LFPP. Proof Using the trace factorisation it suffices to prove the result for continuous functors with left adjoint (for which it is well known) and isotomies. Then X /X ≃ Y/SX is LFP; also, S preserves finite presentability but by hypothesis there is only (essentially) a set of objects X with Y ≅ SX for each finitely presentable Y. □

1.3 Characterisation of LFPP categories

We are going to investigate limits of various kinds in categories of the form Ind(𝕏) where 𝕏 is a plex category. The immediate task is to prove the converse of Proposition 1.2.7, but the following slightly complicated but nevertheless quite elementary result is also applicable to binary products and equalisers.

Remark 1.23 Recall that we can construct the polycolimit of a diagram d : K → X, where X ≃ Ind(𝕏), in the following three cases:

(a) X is LFPP (by Corollary 1.2.4), or

(b) K is filtered (by Definition 1.1.4(ii)), or

(c) 𝕏 is plex, K is finite and the image of d̂ lies in X_{fp} (by Exercise 1.2.5 and Definition 1.2.6). □

Lemma 1.24 Let K, L and X be categories. Then the following are equivalent:

(α) Let ê: L → X be a diagram and C be its category of cones. Then every diagram d : K → C has a colimit, computed on vertices.

(β) Let d̂: K → X be a diagram and suppose that it has a polycolimit, where G is the groupoid

of candidates. Then every functor e : L → G is (isomorphic to a) constant. Proof

[α ⇒ β] A functor e : L → G assigns to each L ∈ L a (polycolimit candidate) cocone over d̂, say with covertex ê(L). This consists of maps d̂(K) → ê(L) commuting with d(k) for k : K → K′ in K. But varying l : L → L′, they also commute with e(l) since this is a morphism of cocones. Hence we have cones under ê with vertex d̂(K), and in fact a diagram d : K → C. By hypothesis (α), this diagram has a colimit C; this object is simultaneously the vertex of a cone under ê and the covertex of a cocone over d̂. However each e(L) is a polycolimiting cocone over d̂, and so has a mediator ê(L) → C, which is the inverse of the map illustrated above. The cone now consists of isomorphisms, so any parallel pair of maps in the diagram ê must be equal. In other words, e : L → G is essentially constant.

[figure: ê(L); e(l); ê(L′); C; d̂(K); d(k); d̂(K′); e(L); e(l); e(L′); c(L); .; .; .; .; .; .; .; .; .; .; .; .; c(l); c(L′); d̂(K); d(k); d̂(K′)]

[β ⇒ α] The converse argument is similar, except that the cocones e(L) are no longer polycolimiting. However by assumption, a polycolimit candidate c(L) does exist — and hence a functor c : L → G. But by hypothesis (β), this is essentially constant, i.e. we may choose c(L) = C and c(l) = id_{C} for some fixed object C ∈ X. Then C is the vertex of a cone over the diagram d̂: L → X, i.e. an object of C, which is the covertex of a cocone under e : K → C. Moreover by candidacy it is the colimit in C. □

Lemma 1.25 Let ê: L → X be a small diagram in an algebroidal category, and C be its category of cones. Then filtered colimits of cones are computed in terms of their vertices, a cone is finitely presentable iff its vertex is, and C is algebroidal. Proof

• Let d : I → C be a filtered diagram of cones, so condition 1.3.1(b) holds. Condition 1.3.2(β) also holds because any filtered diagram in a groupoid is essentially constant. The result then follows from 1.3.2(α).

• Let ϕ : Y → d be a cone with Y ∈ X_{fp} and f : Y → X where X is the colimit of a filtered diagram in C. Then by the previous part we have f : Y → X′ → X where X′ is the vertex of a cone which is a term in the diagram. This is a map between cones (by a similar argument using Lemma 1.1.3) and so ϕ is finitely presentable in C.

• Every object of C can be expressed as a filtered colimit of cones with finitely presentable vertices. Hence C is algebroidal and a cone is finitely presentable if and only if its vertex is. □

Proposition 1.26 Let 𝕏 be a plex category and put X = Ind(𝕏). Then X is LFPP. Proof It only remains to show that the diagram ê : L → X, where L has a terminal vertex 1, has a limit. Let C be its category of cones, which is algebroidal by Lemma 1.3.3, so C ≃ Ind(ℂ). To show that C has a terminal object (which is the required limit), we only have to show (by Lemma 1.1.8) that C has colimits of finite diagrams 𝔡 : K → C of finitely presentables. Condition 1.3.1(c) guarantees that Lemma 1.3.2 is applicable, and condition (β) holds since any wide pullback diagram in a groupoid is essentially constant. □

We have now shown the “object” part of Diers’ generalisation of Gabriel-Ulmer duality (with the slight additional generalisation from “multi” to “poly”). Diers did not, however, generalise the functors or consider the natural transformations in the way we consider appropriate, so we shall do this in the next section.

To conclude this section, here are two more applications of Lemma 1.3.2. Condition (α) for all small K says that the category of cones for a diagram of type L is cocomplete and so has a terminal object, which is the limit. If L is the two-object discrete category then this is the binary product, and L = (• ⇉ •) gives the equaliser.

Proposition 1.27 An LFPP category has equalisers iff polycolimit candidates have no nontrivial automorphisms; such a category we call locally finitely multi-presentable. Proof In condition (β), an automorphism group is trivial iff any parallel pair of arrows are equal. □

Exercise 1.28 A category with binary pullbacks and either

(a) binary products, or

(b) coequalisers, or

(c) ω^{op}-limits and equalisers of pairs of isomorphisms

has all equalisers, and indeed limits of all finite connected diagrams. □

Proposition 1.29 An LFPP category has binary products iff it is “boundedly (co)complete,” i.e. any small diagram which has a cocone has a colimit. A countably-based poset satisfying this condition is called a Scott domain. Proof Condition (β) says that any diagram has at most one polycolimit candidate, whilst the preceding exercise shows that these have no nontrivial automorphisms. Alternatively, allow the vertices of L to have automorphisms but make the diagram send these to the identity. □

Exercise 1.30 Characterise those diagram types for which limits exist in (a) all LFPP categories,

(b) all LFPP categories with equalisers and (c) all LFPP categories with binary products. □ There is one further connection between polycolimits (not related to limits):

Exercise 1.31 Let I and J be polyinitial candidates. Then there is a bijection between (isomorphism calsses of) polycoproduct candidates I + J and (iso)morphisms I → J. □

1.4 Duality

In [T89] it was shown that any stable functor S : X → Y factorises uniquely (up to unique natural isomorphism) as S = F H where H (preserves filtered colimits and) has a left adjoint C and F is an isotomy. The intermediate object, T, is called the trace, and ⟨C, F ⟩ : T → X × Y creates finite presentability and filtered colimits, so restricts to 𝕋 → 𝕏 × 𝕐.

Lemma 1.32 F : T → Y is an isotomy iff its restriction to 𝕋 → 𝕐 is an op-isotomy. Proof For T ∈ T_{fp}, T ↓ T ≃ Ind(T ↓ 𝕋)^{op} and Y ↓ F T ≃ Ind(F T ↓ 𝕐)^{op} by Lemma 1.3.3 with L a singleton. Then in the square

[figure: (T ↓ 𝕋)^{op}; (F T ↓ 𝕐)^{op}; T ↓ T; ∩; Y ↓ F T; ∩]

the top is an equivalence iff the bottom is. □

Lemma 1.33 C : 𝕋 → 𝕏 preserves finite polylimits. Proof Immediate from Lemma 1.2.5 and 7. □

We call C a plex functor.

Lemma 1.34 Let C : 𝕋 → 𝕏 be a plex functor. Then its continuous extension to T → X has a continuous right adjoint. Proof For X ∈ X, let U : X_{fp}↓X → 𝕏 be the forgetful functor and consider the comma category C ↓ U, whose objects are of the form (T′, CT′ → X′ → X) with T′ ∈ 𝕋 and X′ ∈ 𝕏.

• I claim his category is filtered. Since X_{fp}↓X is, given any finite diagram F → C↓U → X_{fp}↓X we can find a bound X′. Let CT′_{F} → X′′ be the polycolimit candidate below X′; then since C preserves polycolimits, there is a unique polycolimit candidate T′_{F} → T′ with this image.

• Let HX be the colimit of the diagram C ↓ U → T . To prove adjointness we need only test maps T → HX with T finitely presentable.

T′_{1}  CT′_{1}  \overline{}X′_{1}
[figure]
[figure: T; T′; HX; CT; CT′; X′; X]
[figure]
T′_{2}  CT′_{2}  \overline{}X′_{2}

Any map T → HX factors through some T′ with (T′, CT′ → X′ → X) ∈ C ↓ U, so we obtain CT → CT′ → X′ → X by composition. Given two such, by filteredness of C ↓ U we can choose onother making both diagrams commute, so the map CT → X is wll-defined. Conversely, this determines T → HX becuase CT is finitely presentable so for some X′ we have (T, T → X′ → X) ∈ C ↓ U.

• If X is given by a filtered colimit, the diagram C ↓ U is the filtered union of the diagrams of the constituents, whence H is continuous. □

The trace factorisation now becomes [state it in more detail, including natural and cartesian transformations]:

Proposition 1.35 Stable functors S : Ind(𝕏) → Ind(𝕐) are characterised by plex spans: a functor C : 𝕋 → 𝕏 which preserves finite polylimits and an op-isotomy F : 𝕋 → 𝕐. □

Diers did in fact prove the substance of the trace factorisation, but he did not consider modifying the 2-cells. For domain-theoretic reasons we choose to consider cartesian transformation, and these also have a very simple description in terms of traces.

Definition 1.36 A plex comparison is a plex functor which is also an op-isotomy; a rigid comparison is an isotomy with a continuous right adjoint.

In loc. cit. it was shown that there is a bijection between cartesian transformations and rigid comparisons. This completes the proof of our version of Gabriel-Ulmer-Diers duality:

Theorem 1.37 The 2-category of LFPP categories, stable functors and cartesian transformations is 2-equivalent to the 2-category of plex categories, plex spans and plex comparisons. □

1.5 Implications between polycolimits

Exercises 1.38 Show that

(a) in each component of X there is exactly one polyinitial candidate (up to isomorphism);

(b) if polycoproduct candidates exist for all pairs of objects of X then it is connected (or empty), so there is at most one polyinitial object (up to isomorphism). □

Lemma 1.39 Let I and J be polyinitial candidates. Then there is a bijection between (isomorphism classes of) polycoproduct candidates I + J and isomorphisms I ≅ J. Proof Applying the polyinitiality property of I to the diagram I → I + J ← J we obtain a unique map e : I → J making the triangle commute, and this must be invertible. Conversely, if e : I ≅ J then there is a cocone I →^{e} J ←^{id} J and so a corresponding polycoproduct candidate. It is easy to check these processes are mutually inverse. □

To summarise, the following equivalences and implications hold:

terminal all limits all colimits [figure]

1 ∧ 4  7=nonempty
[figure]
1  4

products non-empty limits bounded colimits

[figure]
[figure: connected=9; 6; 3]

equalisers multicolimits

[figure]
[figure: 8; 2; 5]

where:

1 coproducts nonempty
2 coproducts discrete
3 coproducts unique
4 coequalisers nonempty
5 coequalisers discrete
6 coequalisers unique
7 initial nonempty
8 initial discrete
9 initial unique

These phrases are of course gross abuses of language: they are abbreviations for saying that the appropriate groupoid of polycolimit candidates is respectively non-empty, discrete or has at most one component. We shall now show that there are no further implications.

\begin{matrix}[figure: •  •; •] & [figure: •; •  •; •  •; •] & [figure: •  •; •  •; •] & [figure: •  •; •; •; •] \\ (a) & (b) & (c) & (d) \end{matrix}

Example 1.40 [2–9 ⇏ ⇏ 1] A qualitative domain, such as the three-point domain (fig. a). □

Example 1.41 [1,3,5–9 ⇏ ⇏ 2] The category of fields and normal algebraic extensions over ℚ. Proof A normal algebraic extension of ℚ is determined by the set of irreducible polynomials with integer coefficients for which its elements are roots. Hence there is a unique amalgamation of any set of such fields, given by the union of the sets of polynomials. However if there are polynomials in common, their roots may be permuted, so the amalgamation has automorphisms over the components. There are no nontrivial bounded parallel pairs, and ℚ is initial. □

Example 1.42 [1,2,5–9 ⇏ ⇏ 3] The free category on fig. (b) for which the object at the bottom is initial (but that at the top is not terminal). □

Example 1.43 [2,4–9 ⇏ ⇏ 3] An L-domain, such as the five-point one (fig. c). □

Example 1.44 [1–3,5–9 ⇏ ⇏ 4] A quantitative domain [T89], such as the category QD(2, 1) of actions of the group of order 2 which have trivial point-stabilisers. □

Example 1.45 [1–3,6–9 ⇏ ⇏ 5] The category of models of the theory with three sorts, X, Y and Z, four unary functions f, g : Y ⇉ X, e : Z → Y and m : Z → Z with equations e; f = e; g, e = m; e and m^{2} = id, and the axioms

∀y ∈ Y.f(y) = g(y)  ⇒ ∃z ∈ Z.e(z) = y
∀z_{1}, z_{2}, z_{3} ∈ Z.e(z_{1}) = e(z_{2}) = e(z_{3}) ⇒ z_{1} = z_{2} ∨ z_{2} = z_{3} ∨ z_{3} = z_{1}
∀z ∈ Z.m(z) = z  ⇒ ⊥

so that Z is exactly twice the equaliser of f and g. Proof Coproducts are obviously constructed componentwise, and it is an exercise to show that the same is true of wide pullbacks and filtered colimits. The representable objects X̂ = (1, 0, 0), Ŷ = (2, 1, 0) and Ẑ = (1, 1, 2) form a polycoequaliser diagram with automorphism group of order 2. One should also show that any parallel pair has at most one polycoequaliser candidate. □

Example 1.46 [1–3,5,7–9 ⇏ ⇏ 6] The category of actions of the group 2^{4} whose point stabilisers have order 1, 2 or 8. [Hint: consider an equivalence relation with four classes on the regular action; there are several two-element quotients.] □

Example 1.47 [2–5,7–9 ⇏ ⇏ 6] The category in fig. (d) where any two parallel composites of two or more maps are equal. □

Example 1.48 [1–6,8,9 ⇏ ⇏ 7] The empty category. □

Example 1.49 [1,2,5,6,7,9 ⇏ ⇏ 8] Any group. □

Example 1.50 [2–8 ⇏ ⇏ 9] The two-element discrete set. □

2 Limits and Exponentials

2.1 Inserters and Equifiers

Limits in 2-categories raise substantially more complex than in 1-categories. The most obvious kind of limit replaces equality with isomorphism — this is called a pseudolimit — but an obvious generalisation of this is to drop the requirement that the 2-cells be invertible; such limits are alled lax or oplax depending on orientation. The notion of equaliser then bifurcates into two primitives: inserters and equifiers.

Definition 2.1 Let S, T : X ⇉ Y be two [stable] functors. Their inserter is the universal [stable] functor U : U → X with a [cartesian] natural transformation ϕ : SU → T U.

Lemma 2.2 CAT, the (super-large) 2-category of categories, functors and natural transformations, has inserters. In the above notation, the objects are of the form ⟨X, y : SX → T X⟩ with X ∈ X and y in Y. The morphisms are those x : X′ → X such that y′ ; T x = Sx; y. □

Lemma 2.3 Let S, T : X ⇉ Y be two stable functors. Let U be the category with objects ⟨X, y⟩ and morphisms x as above, except that the square

[figure: X′; SX′; y′; T X′; X; x; SX; Sx; y; T X; T x]

must be cartesian. Then the forgetful functor U → X is stable and the inserted natural transformation is cartesian. Proof It is easy to see that the forgetful functor which extracts X creates wide pullbacks and filtered colimits and that the inserted natural transformation obtained by extracting y is cartesian. In fact the functor is also full and faithful on slices, but it remains to prove that it is stable.

Suppose we are given x_{0} : X_{0} → X in X and (X, y : SX → T X) ∈ U. First let v_{0} : SX_{0} → T X′_{0} be a candidate for T and x′_{0} : X′_{0} → X such that Sx_{0} ; y = v_{0} ; T x′_{0}. Second define Y_{0} by pullback. Third, factor Y_{0} → SX through a candidate u_{0} : Y_{0} → SX_{1} with x′′_{0} : X′′_{0} → X. Finally, let X_{1} be the coproduct of X_{1}, X′_{0} and X′′_{0} below X.

[figure: X; X_{ω}; ⋮; X_{2}; q_{1}; r_{1}; X′_{1}  X′′_{1}; X_{1}; p_{2}; q_{0}; r_{0}; X′_{0}; p′_{1}; X′′_{0}; p′′_{2}; X_{0}; p_{0}; SX; y; T X; SX_{ω} ≅ SX′′_{ω} ≅ Y_{ω}; Sx_{ω}; T X′_{ω}; T x_{ω}; ⋮  ⋮; SX_{2}; SX′′_{1}; Y_{1}; u_{1}; T X′_{1}; T p′_{1}; v_{1}; Sp_{1}; SX_{1}; ⟨Sx_{1}, v_{1}⟩; SX′′_{0}; Sr_{0}; Y_{0}; u_{0}; T X′_{0}; T p′_{0}; v_{0}; Sp_{0}; SX_{0}; ⟨Sx_{0}, v_{0}⟩]

This gives another problem of the same kind, but this time we have an additional condition and X_{2} is the pushout below X. Iterating, we obtain a fixed point, since S, T and pullback against y are continuous. It is an exercise to show that this is a candidate. □

Exercise 2.4 The natural (not cartesian) equifier is also stable. [Hint: use the same construction, omitting Y_{i}.] □

The mediator is stable by 1.2.3 since preserves wide pullbacks and filtered colimits.

However the slices are LFP categories and so ... U is LFPP. Size? Have to show that the groupoid of polycolimit candidates is essentially small (dont know how to do this for cartesain inserter).

Proposition 2.5 LFPP, the 2-category of LFPP categories, stable functors and cartesian transformations, has equifiers. Definition 2.6 Given two stable functors S, T : X ⇉ Y and two [cartesian] transformations ϕ, ψ : S ⇉ T, the equifier is the universal U → X making them equal. Lemma 2.7 LFPP has equifiers. Proof Plainly this is the full subcategory on which they are equal. However this subcategory is also isotomic, because since ϕ and ψ are cartesian, if they agree at X then they agree at X′ where x : X′ → X. □ Lemma 2.8 non-cartesian equifiers: inclusion creates wide pullbacks and filtered colimits.

2.2 Lax and pseudo limits

Express lax and pseudo limits in terms of products, inserters and equifiers. Recall that products and equalisers suffice to construct limits. Thus for a diagram e : L → X, we form

∏_{L∈obL} d(L) [figure: ⟨π_{doml} ; d(l)⟩; ⟨π_{codl}⟩] ∏_{l∈morL} d(codl)

and then the equaliser of this pair is the required limit.

Definition A pseudo-functor d : L → LFPP consists of

• for each vertex L, there is an LFPP category d(L);

• for each arrow l : L′ → L, there is a stable functor d(l) : d(L′) → d(L);

• for each vertex L, there is a natural isomorphism α_{L} : d(id_{L}) ≅ d(L);

• for each composable pair L′′ →^{l′} L′ →^{l} L, there is an isomorphism γ_{l,l′} : d(l ∘ l′) ≅ d(l) ∘ d(l′); such that

• for each arrow l : L′ → L, [unit law];

• for each composable triple, [associative law]. The last two conditions will not concern us, for the same reason that functoriality of a diagram is not relevant to defining and constructing its limit (as Lambek and Scott point out, we construct limits of graphs, not categories.) Definition 2.9 A [cartesian] lax cone ϵ : X → d consists of

• for each vertex L, a stable functor ϵ_{L} : X → d(L);

• for each arrow l : L′ → L, a [cartesian] transformation ϵ_{l} : ϵ′_{L} ; d(l) → ϵ_{L}; such that

• for each vertex L, ϵ_{id_{L}} = ϵ_{L} ; α_{L}’;

• for each composable pair L′′ →^{l′} L′ →^{l} L, (γ_{l′,l} ∘ ϵ_{L′′}) ; (d(l) ∘ ϵ_{l′}) ; ϵ_{l} = ϵ_{l∘l′}.

A strict morphism of lax cones F : (X , ϵ) → (Y, δ) is a functor F : X → Y such that ϵ = δ_{F}.

Oplax and pseudo cones are defined similarly, with the natural transformations reversed or invertible. The lax, oplax and pseudo limits are the terminal objects in the respective categories of cones and strict morphisms; the mediating functor is therefore unique and the triangles of functors commute exactly, not up to isomorphism.

[figure: precones; ∏_{L∈obL} d(L); ⟨d(l) ∘ π_{doml}⟩; ⟨π_{codl}⟩; ∏_{l∈morL} d(codl)]

[figure: laxcones; precones; ⟨⟨d(id_{L}) ∘ ϵ_{L}⟩, ⟨d(l ∘ l′) ∘ ϵ_{L′′}⟩⟩; ⟨⟨ϵ_{id_{L}}⟩, ⟨ϵ_{l∘l′}⟩⟩ ⇓  ⇓ ⟨⟨α_{L} ∘ ϵ_{L}⟩, ⟨(γ_{l,l′} ∘ ϵ_{L′′}) ; (d(l) ∘ ϵ_{l′}) ; ϵ_{l}⟩⟩; ⟨⟨ϵ_{L}⟩, ⟨ϵ_{L}⟩⟩; ∏_{L′′→^{l′}L′→^{l}L} d(L)]

Comma categories and trace.

2.3 Slices of function spaces

Express slices of funnction spaces in tersm of pseudo limits. Do it for dependent product.

Write (X → Y) and [X → Y] for the continuous and stable function spaces. For S_{0} ∈ (X → Y), the slice (X → Y)/S_{0} has objects the natural transformations ϕ : S → S_{0} and as morphisms the commutative triangles of natural transformations. Similarly for S_{0} ∈ [X → Y] the objects are cartesian transformations, but it is not necessary to state cartesianness of the morphisms because it is automatic. Moreover, in both cases we only need define S on X_{fp}.

We shall no re-interpret these as lax and pseudo limits over the diagram L = 𝕏 = X_{fp}^{op}. Put d(X) = Y/S_{0}X and d(x) = (S_{0}x)^{∗}, i.e. pullback along S_{0}x. Note that in both the continuous and stable cases we have LF(P)P categories, stable functors and (cartesian) isomorphisms. In fact the pullback functor has a left adjoint in the 2-category LFPP.

Now we have a lax cone given by ϵ = ev:

• for X ∈ X, ϵ_{X} : ϕ ↦ ϕX;

• for x : X′ → X, ϵ_{x} is the mediator from SX′ to the pullback; this is a natural transformation in the continuous case, an isomorphism in the stable case;

• the coherences say that S is functorial and ϕ is natural (do it).

SX′

[figure: Sx; ϵ_{x}; ϕX]

(S_{0}x)^{∗}(SX) \overline{}S_{0}X′

[figure: SX; ϕX; S_{0}X; S_{0}x]

Plainly this is lax or pseudo limiting. Also slices of dependent sums.

3 Cartesian Closure

3.1 Filtered colimits of stable functors

We write [X → Y] for the category of stable functors from X to Y and cartesian transformations between them. We still have a lot of work to do to show that it is LFPP! Let S_{−} : I → [X → Y] be a filtered diagram of stable functors and S : X → Y its pointwise colimit; we aim to show that this is the colimit in [X → Y].

Exercise 3.1 S is continuous. □

Lemma 3.2 The natural transformations S_{i} → S in the colimiting cocone are cartesian. Proof Since Y is LFPP, in order to show that the square is a pullback it suffices to test it with maps from a finitely presentable object Y.

Y  \overline{}S_{j}X′

[figure]

S_{i}X′  \overline{}SX′

S_{j}X

[figure]

[figure: S_{i}X; SX]

Using finite presentability, Y → SX′ factors through some S_{j}X′, where without loss of generality i → j in I. But the left-hand parallelogram is a pullback and so there is a unique mediator Y → S_{i}X′. If we have two mediators for the pullback, they give different maps Y ⇉ S_{j}X′ which are identified in the colimit SX′, but Y is finitely presentable and the diagram is filtered, so they must already be identified at a later j′; choosing this instead of j, we find the mediators are equal. □

Lemma 3.3 S is stable. Proof Given Y → SX with Y finitely presentable, it factors through some Y → S_{i}X → SX. Now S_{i} is stable, so the first part factors through a candidate u_{i} : Y → S_{i}X′. By the previous lemma S_{i} → S is cartesian and so by [T88] the composite Y → S_{i}X′ → SX′ is a candidate. Hence the given map factors as u; Sf as required. □

Lemma 3.4 Let ϕ : S_{−} → T be a cocone of cartesian transformations. Then the natural mediator S → T is cartesian. Proof Again given Y → T X′ and Y → SX with Y finitely presentable we have a factorisation Y → S_{i}X → SX for some i. But S_{i} → T is cartesian and so there is a unique mediator Y → S_{i}X′. By filteredness this is unique Y → SX′. □

Proposition 3.5 [X → Y] has filtered colimits, computed pointwise, and ev : [X → Y] × X → Y preserves them. Proof Only the last part remains, but joint continunity is equivalent to separate continuity. □

We can use the duality together with this result to prove the limit-colimit coincidence. For simplicity we shall do this just for strict diagrams and (co)cones (in which triangles of functors commute exactly rather than up to coherent isomorphism); the interested reader will be able to make the appropriate (but very messy) generalisation. The commonest case, ω-sequences, are without loss of generality strict.

Lemma 3.6 The colimit of a strict filtered diagram of plex comparisons is computed as the filtered union on objects and hom-sets. Proof Plex comparisons, being restrictions of rigid comparisons, are faithful, so in computing the colimit of the categories and functors no identification of morphisms takes place. Let 𝕏 = colim 𝕏_{i} be such a colimit, where 𝕏_{i} is a plex category and the arrows Φ_{u} : 𝕏_{i} → 𝕏_{j} are plex comparisons. We have to show that 𝕏 is a plex category and that the inclusion functors Φ_{i} : 𝕏_{i} → 𝕏 are plex comparisons. For the latter, given a finite diagram d : F → 𝕏_{i}, any cone ψ : X → Φ_{i}d in 𝕏 is already of the form Φ_{j}(ψ′ : X′ → Φ_{u}d) for some u : i → j and X′ ∈ 𝕏_{j}, and so factors through a unique candidate in 𝕏_{j}. But Φ_{u} is a plex functor and so this candidate is already in 𝕏_{i}. Hence Φ_{i} is a plex functor and we can argue similarly that it is an op-isotomy. Finally, any finite diagram in 𝕏 is the image of a diagram in some 𝕏_{i}, which has a polylimit which is preserved by Φ_{i}. □

Lemma 3.7 Let 𝕏 = colim 𝕏_{i} be a filtered colimit of plex categories and plex comparisons (as in the previous lemma) and Φ_{i} : Ind𝕏_{i} → Ind𝕏 be the induced rigid comparison, with Φ_{i} ⊣ Θ_{i}. Then there is a filtered diagram of stable functors and cartesian transformations. Φ_{i}Θ_{i} : Ind𝕏 → Ind𝕏 whose colimit is the identity. Proof The arrows in the diagram are given by counits of Φ_{u} ⊣ Θ_{u}. We onle have to check that the pointwise colimit is the identity on finitely presentable objects of Ind𝕏, but these are objects of 𝕏 and hence of some 𝕏_{i}, where the functor is the inclusion. □

Lemma 3.8 With the same notation, Ind𝕏 is the colimit of the Ind𝕏_{i} with respect to (a) continuous functors, (b) comparisons, (c) isotomies, (d) stable functors, and (e) rigid comparisons F_{i} : Ind𝕏_{i} → Y. Proof

[fa] Ind and colim^{↑} are pseudo-left adjoints and so commute.

[fb] Each F_{i} preserves finite presentability and finite polycolimits, so restricts to a plex functor 𝕏_{i} → 𝕐 ≡ Y_{fp}^{op}. By a similar argument to the construction of the colimit, the mediator is plex and so extends to a comparison.

[fc] Similarly with op-isotomies to 𝕐.

[fd] The mediator is the pointwise colimit of F_{i}Θ_{i} : Ind𝕏 → Y, which is a filtered diagram of stable functors and cartesian transformations.

[fe] Immediate from (b) and (c). □

Lemma 3.9 Θ_{i} : Ind𝕏 → Ind𝕏_{i} is a limiting cone with respect to (a) functors, (b) continuous functors, (c) stable functors and (d) homomorphisms (continuous functors with left adjoint). Proof

[fa] Given F_{i} : Y → Ind𝕏_{i}, let F = colim^{↑} Φ_{i}F_{i}; we have to show Θ_{i}F ≅ F_{i}. First note that

Θ_{i}Φ_{j} = colim^{↑} Θ_{u}Φ_{v}  over  [figure: i; u; k; v; j]

Then Θ_{i}F = colim Θ_{u}Φ_{v}F_{k} (irrespectively of continuity of F_{k}). However we may simplify the diagram by taking v = id (because this is a final sub-diagram), and then the terms are all isomorphic to F_{i}.

[fb] If each F − I is continuous then so is colim^{↑} Φ_{i}F_{i}.

[fc] Likewise stable, since the arrows in the diagram are essentially counits of Φ_{u} ⊣ Θ_{u}.

[fd] Immediate from (b) of the previous lemma. □

Theorem 3.10 For a filtered diagram of LFPP categories and rigid comparisons, the colimit of the comparisons quâ functors, the limit of their right adjoints quâ functors and the colimit of the comparisons quâ rigid comparisons are equivalent. □

3.2 Wide pullbacks of stable functors

Lemma 3.11 Let S : X → Y be a (continuous) stable functor, F : X → Y and functor and ϕ : F → S a cartesian transformation. Then F is stable. Proof Let w : Y → F X and let w ; ϕ_{X} = u; Sf be the factorisation (via X_{0}) using stability of S. Then by cartesianness there is a pullback mediator u′ : Y → F X_{0}, and this is a candidate by [T88]. Hence w has the required factorisation. Continuity of F follows from the fact that pullback functors are continuous. □

Proposition 3.12 [X → Y] has wide pullbacks, computed pointwise, and ev : [X → Y] × X → Y preserves them. Proof Let S_{−} : K → [X → Y] be a wide pullback diagram of stable functors and S their pointwise limit. We shall show that S is stable and is the limit in [X → Y]. Proof First, it is easy to show that S → S_{i} is cartesian. Then by the lemma S is stable. This gives a cone in [X → Y]. Let T → S_{i} be another cone and T → S the natural mediator; this is cartesian by a well-known property of pullbacks: if a rectangle and the right square are pullbacks, so is the left. Joint preservation of cofiltered limits, like filtered colimits, is equivalent to separate preservation, but for joint preservation of pullbacks it is also necessary (and sufficient) that the arguments be orthogonal; but this is exactly cartesianness. □

Limit-colimit coincidence.

3.3 Stability of evaluation

We have shown that [X → Y] has filtered colimits and wide pullbacks and that ev : [X → Y]×X → Y preserves them. However we are still a long way from showing that [X → Y] is LFPP or that ev is stable!

First it is convenient to make a comparison (literally) with the category of continuous functors and natural transformations between X and Y, which we call

(X → Y)

This is in fact also an LFPP category, and we shall show that the slices of [X → Y] are reflective subcategories of its slices, so our result would follow. However it is even more difficult to identify the finitely presentable objects of (X → Y) than to find those of [X → Y]! In any case we’re not really interested in continuous functors, so we aim to find [X → Y]_{fp} directly.

Exercise 3.13 The forgetful functor [X → Y] → (X → Y) creates filtered colimits and wide pullbacks, and is full and faithful on slices. [Hint: fullness follows from the well-known rectangle property of pullbacks.] □

Proposition 3.14 [X → Y] → (X → Y) is stable. Proof We are given S : X → Y stable, F : X → Y continuous and σ : F → S natural. We must find the initial object of the category with objects (T, τ, ϕ) where ϕ : T → S is cartesian (whence T : X → Y is automatically stable) and τ : F → T is natural with σ = τ ; ϕ. Of course the morphisms are (necessarily cartesian) transformations T → T′ making the two triangles commute. Write C for this category; it is convenient to consider also the larger category D where we drop the assumption of cartesianness but still take T to be continuous. We say that an object of D is pre-initial for C if it has a unique map to each object of C: clearly (F, id, σ) is pre-initial, but what we require is a pre-initial object which is actually in C. Observe that C ⊂ D is full, and it suffices to define T on X_{fp}.

The construction is in three stages.

Stage 1. For any X ∈ X, it is easy to define a stable functor T_{X}^{0} : X ↓X → Y with τ_{X}^{0} : F → T_{X}^{0} natural, ϕ_{X}^{0} : T_{X}^{0} → S cartesian and τ_{X}^{0} ; ϕ_{X}^{0} = σ:

\overline{σX′}

[figure: F X′; τ_{X}^{0}x; T_{X}^{0}x; ϕ_{X}^{0}x; SX′]

[figure: F x]

[figure: T_{X}^{0}id_{X} = F X; σX; SX; Sx]

Moreover given any object (T, τ, ϕ) of C (so ϕ is cartesian) there is a unique cartesian transformation T_{X}^{0} → T making the triangles commute. So if X has a terminal object the problem is solved.

Stage 2. More generally, we may form T_{X}^{0} for each object X ∈ X_{fp}, and we have seen that the required functor is “bigger than” all of them, so we take the colimit. More precisely, for each X′ → X in X_{fp}, we have ϕ_{X}^{0}x : T_{X}^{0}x → SX′ and hence a diagram X′ ↓ X_{fp} → Y ↓ SX′, of which we may take the colimit. Call this ϕ^{1}X′ : T^{1}X′ → SX′, where we also have σ^{1}X′ : F X′ → T^{1}X′ with σ^{1} ; ϕ^{1} = τ. This extends uniquely (up to isomorphism, of course) to a continuous functor T^{1} : X → Y. Now any object of C gives a cocone at each X′ ∈ X_{fp} over this diagram, which has a unique mediator T^{1}X′ → T X′. This extends uniquely to all objects of X, so T^{1} is a pre-initial object.

Unless pullbacks preserve colimits, T^{1} is not stable, and so we have another problem of the same kind. We form T_{X}^{1} for each X ∈ X_{fp} and hence T^{2}, and so on. This gives a diagram of type ω in D, and we can form T^{ω}. We can carry on from here throughout the ordinals, but in fact we can show that T^{ω} is already the solution.

Stage 3. We just have to show that ϕ^{ω} : T^{ω} → S is cartesian, which it suffices to test for x : X′ → X in X_{fp}.

[figure: F^{n}X′; F_{X}^{n}x; F^{n+1}X′; F^{ω}X′; ϕX′; SX′]

[figure: F^{n}x]

[figure: F^{n}X; F^{n+1}X; F^{n+1}x; F^{ω}X; F^{ω}x; ϕX; SX; Sx]

The rectangle from F_{X}^{n}x to SX is by construction a pullback, and since it is “sandwiched” (cofinal) between F^{n}X′ and F^{n+1}X′ it is the typical term in a filtered diagram with colimit F^{ω}X′. But pullbacks preserve filtered colimits, and so the right-hand square is a pullback as required. □

That proof was a lot of work, but we shall make use of both the result and the method of proof several times. Let us return to stability of (pointwise) evaluation, and consider the special case of factorising id : A → ev_{A}(id) for some fixed object A ∈ X.

Exercise 3.15 The category of factorisations of this has objects (M, α, κ), where M : X → X is stable, κ : M → id cartesian and α : A → MA is a coalgebra for (M, κ), i.e. α; κA = id, and morphisms (M, α, κ) → (M′, α′, κ′) the (necessarily cartesian) transformations ϕ : M → M′ with α; ϕA = α′ and ϕ; κ′ = κ. Hence it is required to find the initial object of this category. □

Exercise 3.16 If X has binary products, (−×A, Δ, π_{0}) is the initial factorisation, where Δ : A → A × A is the diagonal and π_{0} : X × A → X the left projection. □

Lemma 3.17 There is a pre-initial factorisation (in the larger category in which we do not require M to be stable or κ cartesian). Proof We exploit the previous exercise by looking for the best we have by way of a binary product. For X ∈ X, consider the category X_{fp} ↓(X, A) whose objects are (X′, f, g) with X′ ∈ X_{fp}, f : X′ → X and g : X′ → A. The forgetful functor X_{fp} ↓ (A, X) → X ↓ X is a small diagram, so we may take its colimit, which we call κ^{0}X : M^{0}X → X

A  M^{0}X \overline{κ^{0}X} X

[figure: g]

[figure: X′; f; ⋯; X′′]

It is an exercise to show that M^{0} is a continuous functor and κ^{0} is natural, but there need not be a “right projection” M^{0}X → A. However, putting X = A and f = g : X′ → X in X_{fp} ↓ X, we obtain a mediator α^{0} : M^{0}X → X with α^{0} ; κ^{0}X = id.

\overline{id}

[figure: A; α; MA; κA; A]

[figure: X′; g; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; MX′; Mg; κX′; X′; g]

[figure: M^{0}X; .; .; .; .; .; .; .; .; .; .; .; .; .; MX; Mf; κX; X; f]

\overline{κ^{0}X}

Now if (M, α, κ) is any (stable) factorisation, we can form the above diagram for any (X′, f, g) ∈ X_{fp} ↓ (X, A), where the middle composite is id_{X′}, and hence construct the unique mediator M^{0} → M. □

Putting these two results together and using the trace factorisation, we have

Proposition 3.18 Evaluation is stable.

Proof We have constructed the factorisation of id : A → ev_{A}(id), and so ev_{A} is stable below the identity. But by the trace factorisation, [X → Y]/S ≃ [T → T ]/id, where T is the trace of SA : X → Y, and evaluation factors through this in the obvious way, so pointwise evaluation below any stable functor is stable. Clearly ev(S, A) is stable in A for fixed stable S, and the arguments are orthogonal by definition of cartesianness, so ev is (jointly) stable. □

3.4 Cartesian closure

We still have some, but not much, more work to do to construct finitely presentable stable functors. Recall that [X → Y]/S ≃ [T → T ]/id, so we restrict attention to the identity. Write cat for the 1-category of categories and functors (no tranformations!).

Consider U : [X → X]/id → cat/𝕏 by

(M →^{κ} id) ↦ (Coalg(M, κ)_{fp}^{op} → 𝕏)

The forgetful functor from a category of finitary coalgebras is a comparison, so preserves finite presentability. Hence this is well-defined and I claim it extends to a (strict) functor which is full, faithful and continuous; later we shall show that it has a left adjoint.

For ϕ : (M′, κ′) → (M, κ) in [X → X]/id, we have a forgetful functor Coalg(M′, κ′)_{fp}^{op} → Coalg(M, κ)_{fp}^{op}, given simply by (X, ξ′) ↦ (X, ξ′;ϕ). Clear this commutes exactly with the forgetful functor to 𝕏, and so the functor U is well-defined.

To show that U is full and faithful, let

F : Coalg(M′, κ′)_{fp}^{op} → Coalg(M, κ)_{fp}^{op}

be any functor which commutes with the forgetful functors. Consider the cofree algebra (M′X, ν′X); its image under F must be of the form (M′X, ψX) where ξX;κM′X = id. Put ϕX = ψX;Mκ′X; this determines ψX as the mediator to the pullback expressing cartesianness of κ against κ′ or vice versa, and ψ = ν′ ; ϕ. Then ϕ; κ = κ′, so ϕ : (M′, κ′) → (M, κ) in [X → X]/id.

Now let (X, ξ′) ∈ Coalg(M′, κ′)_{fp} be an arbitrary coalgebra; then ξ′ : (X, ξ′) → (M′X, ν′X) is a coalgebra homomorphism, as is its image F ξ′ : F (X, ξ′) = (X, ξ) → (M′X, ψ′X). But the square expressing any coalgebra homomorphism is cartesian, so ξ′ is the pullback of ν′X and ξ = ξ′; ϕX is the pullback of ψX = ν′X ; ϕM′X. Hence F is indeed given by postcomposition with ϕ.

For continuity, if (X, ξ) is a finitely presentable coalgebra for colim^{↑}(M_{i}, κ_{i}) then it is already a coalgebra for some (M_{i}, κ_{i}).

Now I claim U has a left adjoint, so let ℂ → 𝕋 be any functor. We have already constructed this left adjoint in the case where ℂ is a singleton A: this was stability of evaluation below the identity. The extension of the argument to any small diagram is obvious.

Hence [X → X]/id is a reflective subcategory of an LFP category, where the image is continuous, so is LFP.

It remains to count [X → Y]_{fp}. Show first that if two functors S_{1}, S_{2} : X → Y are obtained from the same 𝕏 ← ℂ → 𝕐 then they are isomorphi (?). Also every finitely presentable stable functor is obtained from some such diagram where ℂ is a finitely presentable stable category.

Theorem 3.19 The 2-category of LFPP categories, stable functors and cartesian transformations is cartesian closed. □

4 Extensions

4.1 Locally Presentable Categories

Some authors, Diers for instance, do not discuss finitely presentable objects, etc., but instead always generalise to α-presentability. There are several important cases of ℵ_{1}-presentability, notably metric spaces and indeed anything concerning the real numbers, but personally I feel that presenting the arguments with α everywhere obscure rather than enlighten. Also, whilst locally α-(poly)presentable categories arise naturally, α-continuous functors are of no particular interest. Indeed, in this section we aim to generalise the categories whilst retaining continuous functors, so we have more work to do after applying the obvious meta-theorem.

However having completed our account of locally finitely poly-presentable categories, let us observe that whereever the word “finite” occurs in the foregoing definitions and theorems, it may be replaced by “of cardinality less than α” for any regular cardinal α. Beware that this also applies to the definition of filteredness: a diagram or category is α-filtered if every sub-diagram of size less than α already has a cone within the diagram.

There are several contravariances here (for β < α):

• cardinality < β implies < α,

• α-filtered implies β-filtered,

• β-presentable implies α-presentable,

• β-algebroidal or locally β-(poly-)presentable implies α-algebroidal, etc.,

• β-continuous implies α-continuous, and

• α-plex implies β-plex.

Immediately from this translation we have the generalisation of Theorem 1.4.6:

Proposition 4.1 There is a duality between

• locally α-poly-presentable categories, α-continuous stable functors and cartesian transformations, and

• α-plex categories, α-plex spans and α-plex comparisons.

Moreover, this 2-category is cartesian closed. □

However, as we have said, this is not the result which interests us: we want to keep ω-continuous stable functors.

Let X and Y be α-poly-presentable categories and β < α. Suppose that they have small β-filtered colimits, and that pullbacks in Y preserve these. Write [X →^{α} Y] for the category of α-continuous stable functors and cartesian transformations, and similarly [X →^{β} Y].

Lemma 4.2 The (full) inclusion [X →^{β} Y] ⊂ [X →^{α} Y] is an isotomy and creates β-filtered colimits. It preserves but may not reflect polycolimit candidates. Proof The first part is the same as lemma 3.2.1. Any pointwise colimit of β-continuous functors is β-continuous, so since β-filtered colimits are constructed pointwise (because pullbacks preserve them), the inclusion creates β-filtered colimits. Preservation of polycolimit candidates follows from isotomy, but it is possible for a non-β-continuous functor to be a polycolimit of β-continuous ones. □

Definition 4.3 A stable category is one which is locally α-poly-presentable for some α and has ω-filtered colimits which are preserve by pullbacks.

Theorem 4.4 The 2-category of stable categories, (ω-continuous) stable functors and cartesian transformations is cartesian closed. Proof Specialising the lemma to β = ω and taking α to be the larger rank, the function-space is stable. Since ω-filtered colimits are computed pointwise, evaluation is continuous. □

Conjecture 4.5 Let X be a category with small wide pullbacks and small filtered colimits which are preserved by pullbacks, and suppose that for every obejct X ∈ X, id_{X} : X → ev_{X}(id_{X}) factors through a candidate for ev_{X}. Then X is α-poly-presentable for some α. In other words, the 2-category described above is the largest which is cartesian closed (and for which the morphisms are the stable functors).

2-limits of α-presentable categories?

4.2 Products and equalisers

In this section we aim to throw more light on the notion of polycolimit by demonstrating the various (accidental) implications which hold between them.

Lemma 4.6 Let X be a category with (binary) pullbacks and f, g : X ⇉ Y be a pair of arrows in X. Suppose either (a) the product Y × Y exists or (b) there is an arrow q : Y → Q with f ; q = g ; q. Then the equaliser exists. □ Proof Construct the diagrams

[figure: E; e; X; Y; ⟨id, id⟩; Y × Y; ⟨f, g⟩; X  Y; e; ⟨f, g⟩; q; E  Z  Q; ⟨id, id⟩; q; Y  Y]

□

Exercises 4.7 Let X be a category with binary pullbacks. Show that

(a) X has finite wide pullbacks [Hint: adapt [Mac Lane] with pullbacks for products and Lemma 1.1(b) for equalisers.]

(b) If X has a terminal object then it has all finite limits.

(c) If X has binary products then it has finite non-empty limits.

(d) If X has equalisers then it has finite connected limits.

(e) If additionally X has countable or small cofiltered limits then in each of (a–d) we may replace finite by countable or small. □

Proposition 4.8 Suppose X has equalisers of pairs of isomorphisms and countable wide pullbacks. Then it has all equalisers. Proof Given f_{0}, g_{0} : X_{1} ⇉ X_{0}, form the following pullbacks, starting from the right:

[figure: ⋯; X_{3}; f_{3}; f_{2}; X_{4}  X_{2}; g_{3}; g_{2}; X_{3}; X_{2}; f_{2}; f_{1}; X_{3}  X_{1}; g_{2}; g_{1}; X_{2}; X_{1}; f_{1}; f_{0}; X_{2}  X_{0}; g_{1}; g_{0}; X_{1}]

Then form the limits of the odd and even terms in the sequence, remembering that f_{n+1} ; f_{n} = g_{n+1} ; g_{n}:

E

[figure]

[figure: ⋯; X_{3}; f_{2}; g_{2}; X_{2}; f_{1}; g_{1}; X_{1}; f_{0}; g_{0}; X_{0}]

[figure]

[figure: O]

There are two ways of extending one limiting cone to a cone over the other diagram and hence two isomorphisms E ≅ O. It is easy to show that any map equalising the given pair extends to a cone over the whole diagram and hence to a map equalising these isomorphisms, and vice versa. Hence the equaliser of the automorphisms is also the equaliser of the given pair. □

Now let X be an LFPP category

Proposition 4.9 X has equalisers iff all polycolimit candidates have trivial automorphisms. Proof

[⇒] Let d : K → X be a diagram and ϕ : d → X a polycolimit candidate with automorphism x : X ≅ X. Let e : E ↪ X be its equaliser with the identity; then because x commutes with ϕ, the latter factors though e. Let ψ : d → Y be the candidate through which this factors; then Y → E → X is invertible and so is e itself. Hence x = id.

[⇐] We are given a diagram d : K → X where K = (• ⇉ •). Then in Remark 1.3.1 the diagram c is a parallel pair of isomorphisms of candidates, but by hypothesis these must be equal, so we have a constant diagram. □

This is Diers’ original version; in this case we speak of multicolimits instead of polycolimits.

Proposition 4.10 X has binary products iff every small diagram in X which has a cocone has a colimit. Proof

[⇒] Let d : K → X be a diagram; since it has a cocone it has at least one polycolimit candidate, and since X has equalisers this has trivial automorphism group. We must show that any two polycolimit candidates are isomorphic. Let ϕ : d → X and ψ : d → Y be polycolimit candidates; then there is a cocone ⟨ϕ, ψ⟩ : d → X ×Y, which factors through some candidate χ : d → Z. But then Z → X × Y → X is invertible, so X ≅ Z ≅ Y.

[⇐] We apply Remark 1.3.1 for the last time, with a discrete diagram type K = (• •). The diagram of candidates is constant because by hypothesis there is only one candidate up to isomorphism. □

A (countably based) poset satisfying these conditions, i.e. algebraic and having joins of bounded sets, is often called a Scott domain.

4.3 Biased product

Now we shall look more closely at (the first attempt at) the biased product functor P : X ×X → X together with its projection

(\begin{matrix}P (A, Y) \\ Y & \begin{aligned}κ_{A}X \\ & \end{aligned} \end{matrix}) ≡ \begin{matrix}colim \\ ( & \begin{aligned}A & & & & Y \\ & [figure: f] & & [figure: g] \\ & & X \end{aligned} & ) \end{matrix} (\begin{matrix}Y \\ X & \begin{aligned}g \\ & \end{aligned} \end{matrix})

and the diagonal αX : X → P (X, X).

Exercise 4.11 Show that P is a continuous functor and κ and α are natural, but α is not necessarily cartesian [Hint: take X = Set.]. □

Remark 4.12 P need not be stable in its first argument.

Proof Let X be the poset with fifteen points

A_{N}, Y_{N}, U_{N}, V_{N}, A_{W} , Y_{W} , U_{W} , V_{W} , A_{E}, Y_{E}, U_{E}, V_{E}, A_{S}, Y_{S}, ⊥ = U_{S}, V_{S}

where

[figure: Γ_{N}; Γ_{W}  Γ_{E}; Γ_{S}; A_{Δ}  Y_{Δ}; U_{Δ}; V_{Δ}]

for Γ = A, Y, U, V and Δ = N, W, E, S. Then

P (A_{Δ}, Y_{N}) ≡ A_{Δ} ∨_{Y_{N}} B_{Δ} = \{ \begin{matrix}Y_{Δ} & for Δ = N, W, E \\ ⊥ & for Δ = S \end{matrix}

whereas the left-hand diamond above is a pullback for each Γ. □

Lemma 4.13 Suppose that X is LFPP and also locally cartesian closed (LCCC), i.e. pullback functors have right adjoints and so preserve colimits. Then P : X × X → X is stable in its second argument, κ_{A} : P (A, −) → id is cartesian and the arguments of P are orthogonal. Proof At first sight it is obvious that the result follows immediately from preservation of colimits, but we have to be careful because the diagram types are different. Fix A and let f : Y′ → Y then

f^{∗}(P (A, Y) → Y ) ≡ f^{∗} ( colim_{A←X→Y} (X → Y))
≅ colim_{A←X→Y} (f^{∗}X → Y′)  f^{∗} preserves colimits
≅ colim_{A←X′→Y′}(X′ → Y′)  cofinality

To be more precise, there is an obvious forgetful functor from the primed diagram to the unprimed one, and any cocone over the primed one extends uniquely.

This shows that κ_{A} is cartesian; then by lemma ?, P (A, −) is stable, and by the well-known property of pullback rectangles, P (a, −) : P (A′, −) → P (A, −) is cartesian for a : A′ → A. □

Unfortunately, we are only able to show that P defines a stable functor of two variables in the poset case.

Lemma 4.14 If X is a distributive algebraic L-domain, i.e. a poset which is LFPP and LCCC, then P is stable in its first argument. Proof The candidate of P (−, X) below A is P (X, A) (sic). □

[object of ΠX.X → X → X].

4.4 Notes

Suppose X ∈ X is not presentable, i.e. Hom(X, −) does not preserve κ-filtered colimits for any κ. Counterexample to adjoint functor theorem without preservation of filtered colimits?

Proposition 4.15 Let X and Y be stable categories and S ; X → Y a stable functor. Then the comma category Y ↓ S is stable. Proof The forgetful functor Y ↓ S → X × Y is faithful and creates wide pullbacks and filtered colimits. If G, H generate X and Y respectively, I claim H↓SG generates Y ↓S. Given w : Y → SX in Y ↓ S, the G → X be a typical approximant of X by G in X. Form the pullback

[figure: H; Y_{G}; Y; SG; SX]

and let H → Y_{G} be a typical approximant of Y_{G} by H in Y. Now both S and pullback against Y → SX preserve filtered colimits, so the Y_{G} approximate Y, and then the H approximate Y too, and the H → SG approximate Y → SX. □

Lemma 4.16 Let X _{⊂} E ; ⊥ ; ◁ _{P} Y be an adjunction, where Y is a stable category and P also preserves

filetred colimits. Then X is stable. Proof E is faithful and creates filtered colimits. Let D → X be a wide pullback diagram in X and Y be its limit in Y; I claim that P Y is the limit in X. For let X → D be a cone, so EX → ED is also a cone and factors EX → Y → ED, so X → D factors as X ≅ P EX → P Y → P ED ≅ D. Now let X_{i} → X be a typical map in a colimiting cocone over a filtered diagram in X and X′ → X; form the pullback

[figure: Y_{i}; EX′; EX_{i}; EX; P Y_{i}; X′; X_{i}; X]

in Y and X. Then Y_{i} → EX′ is colimiting in Y and its image P Y_{i} → X′ is in X. Finally let H generate Y and put G = P H ⊂ X. Then H↓EX is filtered with colimit EX, so G↓X ≅ P (H↓EX) is filtered with colimit X. □

Coalg : Copt(X) → cat/𝕏 by (κ : M → id) ↦ {(X ∈ X_{fp}, α : X → MX)} (ϕ : M′ → M) ↦ ((X, α′) ↦ (X, α′ ; ϕ)) functorial on the nose!