Theory and Applications of Categories, Vol. 9, No. 6, 2001, pp. 106–120.

CATEGORICAL DOMAIN THEORY: SCOTT TOPOLOGY, POWERCATEGORIES, COHERENT CATEGORIES

PANAGIS KARAZERIS

ABSTRACT. In the present article we continue recent work in the direction of domain theory were certain (accessible) categories are used as generalized domains. We discuss the possibility of using certain presheaf toposes as generalizations of the Scott topology at this level. We show that the toposes associated with Scott complete categories are injective with respect to dense inclusions of toposes. We propose analogues of the upper and lower powerdomain in terms of the Scott topology at the level of categories. We show that the class of finitely accessible categories is closed under this generalized upper powerdomain construction (the respective result about the lower powerdomain construction is essentially known). We also treat the notion of “coherent domain” by introducing two possible notions of coherence for a finitely accessible category (qua generalized domain). The one of them imitates the stability of the compact saturated sets under intersection and the other one imitates the so-called “2/3 SFP” property. We show that the two notions are equivalent. This amounts to characterizing the small categories whose free cocompletion under finite colimits has finite limits.

Introduction

The use of categories as domains for denotational semantics has had a long history by now. The reader may consult [2], [16] for some recent developments, and references to the subject. While most of the notions entering the theory of domains have direct category theoretic generalizations (directed suprema to filtered colimits, ideal completions to inductive completions, algebraic domains to finitely accessible categories [3], etc.), one of the central tools of domain theory, the Scott topology, has not been examined, at least explicitly, towards such a generalization. Nevertheless, the idea of representing the Scott topology by a suitably chosen topos is implicitly present in at least the two interrelated articles [9], [10].

In this work we take as starting point the ideas and results in those two articles and try to check the success of this metaphor with respect to some constructions and results of domain theory, where the Scott topology plays a major role. We discuss the possibility of using certain presheaf toposes as generalizations of the Scott topology at this level and examine whether certain features of the Scott topology are maintained. In particular, in what concerns injectivity, we prove that the toposes associated with Scott complete categories are injective with respect to dense inclusions of toposes. Then we focus on

Research carried out at the National Technical University of Athens. The author gratefully acknowledges support from a postdoctoral research grant of the Greek Scholarships Foundation (IKY)

Received by the editors 2000 December 20 and, in revised form, 2001 December 17. Published on 2001 December 20 in the volume of articles from CT2000. 2000 Mathematics Subject Classification: 18C35, 18B25, 03G30, 18A35. Key words and phrases: accessible category, Scott complete category, classifying topos, powerdomain

coherent domain, perfect topos, free cocompletion.

\begin{matrix}c \\ ◯ \end{matrix} Panagis Karazeris, 2001. Permission to copy for private use granted.

two goals: To describe the categorical analogues of powerdomains in terms of the Scott topology and, in view of its importance for various duality results in domain theory, to introduce a notion of “coherent domain” at the level of categories. In the first direction we show that the class of finitely accessible categories and of continuous categories with a small dense subcategory, respectively, are closed under the proposed generalized upper powerdomain construction (the respective results about the lower powerdomain construction are essentially known). In the second direction we introduce two possible notions of coherence for a finitely accessible category (qua generalized domain), one imitating the stability of the compact saturated sets under intersection and one imitating the so-called “2/3 SFP” property. We show that the two notions are equivalent, in essence giving a characterization of the perfect presheaf toposes, in the sense of [4]. This also amounts to characterizing the small categories whose free cocompletion under finite colimits has finite limits.

I wish to thank Professor J. Adámek for his comments on a very early version of this work and Dr. A. Tongas for his valuable assistance with TeX.

1. Scott toposes and injectivity

When we attempt to find a topos that imitates the behaviour of the Scott topology for domains we have three things in mind: First, we want a topos whose category of points is the category we start with (and view as a generalized domain). Secondly, we want to talk about a topos that, at least in the case of “good” categories, is injective in the category of toposes. Finally, in the case that K = L = Idl(P) is an algebraic poset and σL is the Scott topology on it, then we would like the topos in question to be equivalent to sh(L, σL).

On the other hand, given an algebraic poset D, the equivalence σD ≅ ⨆↑ (D, 2) ≅ 2^{D_{f}}, i.e the fact that upper segments determined by finite elements form a basis for the topology, suggests that we should be looking for a presheaf topos to play the role of the Scott topology. So for the needs of the present work we confine ourselves to this case. Specifically, given a finitely accessible category K, we let the “Scott topos” associated with K be the presheaf topos σK = Set^{K_{f}}, where K_{f} is the full subcategory of finitely presentable objects of K. This is a topos whose category of points is K. In the case K is locally finitely presentable, so that K_{f} has finite colimits, it is a topos that is injective (with respect to all inclusions) ([9], Prop. 1.2). In the case where K is a generalized Scott domain, it is injective with respect to dense inclusions (see below).

Also, in the case where K = L is an algebraic poset, so that ℂ = P is just a partially ordered set, we have that Set^{P^{op}} ≅ sh(L, σL), as desired ([9], Lemma 1.1). When we look at continuous categories with a small dense subcategory (in connection to the generalized powerdomain constructions), we regard as the appropriate version of the “Scott topos” the topos associated with such a category in [10]. These toposes are canonically constructed out of such continuous categories K, they arise as retractions of presheaf toposes, and then have the category K we started with as their categories of points.

Although presheaf toposes are not necessarily injective in the category of Grothendieck toposes, we can maintain some of the relative injectivity properties known for the Scott topology on continuous posets. For example it is well known that Scott domains with their Scott topology are exactly the injectives, with respect to dense inclusions, in the category of T_{0} spaces (see [7] for some more general discussion of these phenomena). We show here that the “Scott topos” associated to a Scott complete category, in the sense of [2], is injective with respect to dense inclusions of toposes. Recall that a Scott complete category is a finitely accessible category with an initial object, in which every diagram that has a cocone has a colimit (so that in particular it has copowers). In [2] Scott complete categories were characterized as categories of models for certain kinds of sketches, equivalently, for certain kinds of first-order (actually, coherent) theories.

More precisely a Scott complete category is the category of models of what we call a “Scott theory”, for brevity. These are theories in a multi-sorted language, whose axioms are of the following form:

(i) For formulae ϕ and ψ which are finite conjunctions of atomic ones, sentences of the

kind

(∀x_{i} : s_{i})[ϕ(x_{1}, …, x_{n}) → (∃y_{j} : t_{j})ψ(x_{1}, …, x_{n}, y_{1}, …, y_{m})],  (∗)

provided

ψ(x_{1}, …, x_{n}, y_{1}, …, y_{m}) ∧ ψ(x_{1}, …, x_{n}, y′_{1}, …, y′_{m}) → (y_{1} = y′_{1} ∧ … ∧ y_{m} = y′_{m})

is also provable in the theory (a theory given by axioms of this form is called a lim-theory).

(ii) For a specified collection of sorts S and s ∈ S, sentences

(∀x : s)[x = x → ⊥]  (∗∗)

The classifying topos of such a theory is simply the category of functors on the finitely presented models of the Scott theory: The classifying topos is a sheaf subtopos of the presheaf topos that classifies the lim-theory part. The topology inducing the sheaf subtopos is given by the requirement that the empty cover covers the objects realizing the specified sorts. An application of the comparison lemma [4] tells us that the classifying topos is eventually the one that is obtained by removing the objects covered by the empty cover from the category of finitely presented models for the lim-theory part of the Scott theory. See also [5] for details.

1.1. Definition. An inclusion of toposes i: E [figure]F is called dense if the following equivalent conditions are satisfied:

(i) i^{∗} reflects the initial object

(ii) i_{∗} preserves the initial object

(iii) The topology j, inducing the inclusion, has j(0) = 0.

1.2. Proposition. Toposes classifying Scott theories are injective with respect to dense inclusions between Grothendieck toposes.

Proof. Let i: E [figure]F be a dense inclusion between Grothendieck toposes and f: E

[figure]B[𝕋] be any geometric morphism to the classifying topos of a Scott theory. We adapt to our case the argument given in [9] for the injectivity of algebraic toposes with respect to all inclusions. So we will show that the functor

(− ∘ i): T op(F, B[𝕋]) [figure] T op(E, B[𝕋])

has a right adjoint, such that the counit of the adjunction is a natural isomorphism.

Under the universal property of the classifying topos, the above functor is transported to the functor ”take the inverse image of”

i^{∗}: Mod_{F}(𝕋) [figure] Mod_{E}(𝕋)

A right adjoint with the required property would be given by taking the image under i_{∗} of a model provided that the direct image functor preserved models. But this is indeed the case, because all we need for the preservation of models of a Scott theory is the preservation of finite limits as well as of the initial object. In particular, the validity of sentences like (∗∗), above, is preserved, so that if ∥ x = x ∥_{F}≤∥ ⊥ ∥_{F} holds in F then

i_{∗}(∥ x = x ∥_{F}) ≤ i_{∗}(∥ ⊥ ∥_{F}) =∥ ⊥ ∥_{E} .

The equivalent conditions in the definition of a dense inclusion exactly secure the preservation of the initial object.

2. Powerdomain constructions at the level of categories

The upper (Smyth) powerdomain of a domain D is usually described as the set of compact saturated subsets of D in the Scott topology σD on D, ordered by reverse inclusion. By the Hofmann - Mislove theorem this set is isomorphic to the set of Scott open filters (i.e filters inaccessible by directed joins) on the frame σD, ordered by inclusion. The latter set can, in turn, be identified with the set of maps that preserve directed joins and finite meets (=preframe maps) from the frame σD to the algebra of truth values Ω.

Here we attempt to generalize the construction of the upper powerdomain at the level of finitely accessible categories. For that we use as a guide the description of the upper powerdomain of a domain as the set of preframe maps from the frame of Scott opens on the domain to the algebra of truth values. Proceeding in formal analogy, we generalize this construction at the level of categories defining the upper powercategory of a finitely accessible category as the category of Set-valued functors that preserve finite limits and filtered colimits from the “Scott topos” corresponding to the finitely accessible category.

Similarly we define the lower powercategory of a finitely accessible category as the category of all small colimit preserving functors from the “Scott topos” corresponding to the finitely accessible category to the category of sets.

2.1. Definition. Let K = Flat(K_{f}^{op}) be a finitely accessible category. The upper powercategory of K is the category of functors that preserve finite limits and filtered colimits from the topos σK = Set^{K_{f}} to the category Set:

P_{U}(K) = LexCont(Set^{K_{f}} , Set)

2.2. Definition. Let K = Flat(K_{f}^{op}) be a finitely accessible category. The lower powercategory of K is the category of functors that preserve all small colimits from σK = Set^{K_{f}} to the category Set:

P_{L}(K) = Colim(Set^{K_{f}} , Set)

When K is just a continuous category with a small dense subcategory, by the upper and lower powercategory respectively we mean the categories defined as above with the appropriate Scott topos substituted for the full presheaf category. The Scott topos now is a retraction in the category of Grothendieck toposes (as in [10], Prop. 3.3) of the presheaf category.

Here we intend to show that the 2-category of finitely accessible categories (and continuous functors and all natural transformations) is closed under the upper and lower powercategory construction. Our task is considerably easier in the studying the lower powercategory, as it amounts to adapting to this context ideas relating to the lower bagtopos, something that has attracted much more attention in the literature so far ([11], [17], [6]).

When it comes to the upper powercategory, we want to show that when K is a finitely accessible category then so is P_{U}(K). We base our proof on the following more general

2.3. Proposition. Let E be a locally finitely presentable category and F be any Grothendieck topos. Then the category LexCont(E, F) of functors preserving finite limits and filtered colimits from E to F is equivalent to the category Flat_{F}(E_{f}) of flat functors to F on the full subcategory of E consisting of its finitely presentable objects.

Proof. Recall the well known equivalence between the categories Cont(E, F) of Scott continuous functors from E to F, on the one hand and F^{E_{f}}, on the other hand. We show that this equivalence restricts to one between their respective full subcategories LexCont(E, F) and Flat_{F}(E_{f}). The equivalence takes a functor E [figure] F to its restriction along the inclusion E_{f} [figure] E, in the one direction and a functor E_{f} [figure] F to its left Kan extension along the aforementioned inclusion in the other direction.

First, notice that when F: E_{f} [figure]F is flat then its left Kan extension along i: E_{f} [figure] E is left exact (so that Flat_{F}(E_{f}) is contained as a full subcategory in LexCont(E, F)), by some general properties of left Kan extensions of functors into a Grothendieck topos. This is a result that may be possible to trace in [4], but nevertheless see [12] for a discussion of the generality in which it holds.

In the opposite direction suppose that F: E [figure]F is left exact. We show that its restriction F ∘ i: E_{f} [figure] F is flat. We use the fundamental equivalence between flat and left filtering functors stated in [13],VII. 9.1. A functor H: E_{f} [figure] F is left filtering if it satisfies the following:

(i) The family of all maps H(C) [figure] 1, for all C ∈ E_{f}, is epimorphic

(ii) For any two objects C, D ∈ E_{f}, the family of maps H(B) [figure] H(C) × H(D), where B runs over all the cones C [figure] B [figure] D, is epimorphic.

(iii) For any pair of parallel arrows, u, v: C [figure]D in E_{f}, the family of induced maps H(B) [figure]Eq(H(u), H(v)) to the equalizer of H(u), H(v), where B runs over all

the cones B  [figure] C  [figure] D, is epimorphic.

Let us verify the third clause in the definition of a filtering functor, the others following similarly. So consider a pair of arrows Eq((F ∘ i)u, (F ∘ i)v) [figure]X in F, such that whenever they are restricted along any (F ∘ i)B [figure] Eq((F ∘ i)u, (F ∘ i)v), where B is a cone for u, v: C [figure] D, they become equal. Since F is left exact, Eq((F ∘ i)u, (F ∘ i)v) ≅ F (Eq(iu, iv)). Write E = Eq(iu, iv) as a filtered colimit of finitely presentable objects, Eq(iu, iv) ≅ colim_{E_{f} /E}iB. Since F is continuous F (Eq(iu, iv)) ≅ colim_{E_{f} /E}(F ∘ i)B. This way we have that two elements of

hom(Eq((F ∘ i)u, (F ∘ i)v), X) ≅ hom(colim_{E_{f} /E}(F ∘ i)B, X)
≅ lim_{E_{f} /E} hom((F ∘ i)B, X)

become equal whenever they are projected to the coordinates of the latter inverse limit. Thus they are already equal.

2.4. Corollary. a. The upper powercategory of a finitely accessible category is a finitely accessible category.

b. The upper powercategory of a continuous category with a small dense subcategory is continuous (with a small dense subcategory).

Proof. The proof of the first claim is immediate. For the second, recall from [10], Corollary 2.17, that a category L is as in the statement if and only if it is a retract by continuous functors of one of the form Flatℂ. By Prop. 3.3 of loc. cit., the “Scott topos” associated to the continuous category is a retract, in the category of Grothendieck toposes, of Set^{ℂ^{op}}. Postcomposition with the inverse images of the retraction renders P_{U}L a retract by continuous functors of LexCont(Set^{ℂ^{op}}, Set), hence a continuous category with small dense subcategory.

Remark. Beyond the formal analogy, there is a stronger reason suggesting that our definition of the upper powercategory is in the right direction: Our construction is in accordance with the “bagdomain” view of powerdomains, initiated in [17] and developed in [11]. According to this approach the elements of the powerdomain should be indexed families of elements of the domain we start with, rather than just sets of such elements. This way of looking at things forces us to abandon the idea of a powerdomain as an ordered set, and adopt instead a view of powerdomains as categories, even when we start with a classical domain.

In order to examine closer the connection of our approach with the “bagdomain” ideas [11], let K = Flatℂ be a finitely accessible category. Johnstone’s suggestion is that the category of points of the upper “bagtopos” of the “Scott topos” Set^{ℂ^{op}} should be the indcompletion of the category F am_{f}(ℂ)^{op}. In other words, it should be the ind-completion of the dual of the category obtained by freely adjoining finite coproducts to ℂ. Our P_{U}(K) = Flat([Set^{ℂ^{op}}]_{f}) is the ind-completion of the dual of the free cocompletion of ℂ under finite colimits.

In particular, the above arguments show that the upper powercategory of the one point domain is calculated as follows:

P_{U}({∗}) = LexCont(Set, Set)
≅ Lex(Set_{f}, Set)
≅ Lex((BAlg)_{f}^{op}, Set)
≅ BAlg,

agreeing with the intuitions presented in loc.cit.

The lower powercategory construction: We show that the 2-category finitely accessible categories is closed under the lower powercategory construction.

2.5. Proposition. The lower powercategory P_{L}(K) of a finitely accessible category K is equivalent to Set^{K_{f}^{op}}

Proof. The fundamental result about free cocompletions, exposed as Corollary 1.3 in [15] gives the equivalence claimed above

2.6. Corollary. a. The lower powercategory of a finitely accessible category is an accessible category.

b. The lower powercategory of a continuous category with a small dense subcategory is continuous (with a small dense subcategory).

Proof. The first is obvious, the second follows as in Corollary 2.4.

3. Generalizing the notion of a coherent domain

One of the fundamental uses of the Scott topology in domain theory is in the study of the so called coherent domains. A coherent domain is one with the property that the ≪ relation on the frame of opens for the Scott topology on the domain is closed under intersection. The role of coherence in domain theory is fundamental, both in the study of exponentiability of domains as well as in the dual description of domains either in terms of “information systems” à la Scott or in “logical form’ à la Abramsky.

In analogy with the preordered case we state the relevant property in terms of the closure of the full subcategory of finitely presentable objects of a “Scott topos” E under finite limits. This is equivalent to saying that the full subcategory E_{coh} of E, consisting of the coherent objects, is closed under all finite colimits. In turn this is equivalent to the condition E_{f} = E_{coh} (cf. [4], Exposé VI, as well as the appendix of [14]). Such toposes are called “perfect” in [4] and include all the coherent toposes satisfying the noetherian condition on their lattices of subobjects, notably the simplicial topos, and, among others the Zariski and the etale topos over a scheme. (Notice that when E = Set^{K_{f}} is a perfect topos then the equivalence between functors from E_{f} to Set and continuous functors from E to Set takes left exact functors to left exact ones. So LexCont(E, Set) is equivalent to the category Lex(E_{f}, Set), which is a typical locally finitely presentable category.) One of the most pleasant features of coherent domains that lies in the heart of the duality theory, is that coherence can be described elementarily, in terms of the order of the domain. In particular a domain is coherent if and only if it satisfies the so-called 2/3-SFP property. Recall that a (classical) domain satisfies the 2/3-SFP property if, given any finite set S of finite elements of it, there is another finite set M of finite elements such that:

• the elements of M are upper bounds for S, and

• every other upper bound for S is greater or equal than some element of M.

3.1. Definition. A finitely accessible category K is coherent if the topos Set^{K_{f}} is perfect, that is, it is coherent and the equivalent conditions in the previous paragraph are satisfied.

3.2. Definition. A finitely accessible category K has the “2/3-SFP” property if for every finite (including empty) diagram K: I [figure] K_{f} in K_{f} there is a finite subcategory D of K_{f} such that

• the objects of the subcategory are cocones for the diagram and the arrows of the subcategory are morphisms of cocones. By the latter we mean that, for any two cocones λ: K ⇒ D and μ: K ⇒ D′, any i ∈ I and d: D [figure]D′ in D, we have μ_{i} = d ∘ λ_{i}.

• any other cocone for the diagram factors through one of the cocones in the finite subcategory and

• given any two such factorizations through x_{j}: D_{j}  [figure] F and x_{k}: D_{k}  [figure] F there is

a zig-zag

\xymatrix{ & D_{2} \ar@{.>}[ddr]_{α_{1}} &  & D_{2n} \ar@{.>}[ddl]^{α_{n}} \\ D_{j} = D_{1} \ar@{.>}[ur]^{ρ_{j,2}} \ar[drr]|{x_{j}} &  & D_{3} ... D_{2n−1} \ar@{.>}[ul]_{ρ_{2,3}} \ar@{.>}[ur]^{ρ_{2n−1,2n}} &  & D_{2n+1} = D_{k} \ar@{.>}[ul]_{ρ_{2n,k}} \ar[dll]|{x_{k}} \\  &  & F}

in the full subcategory, having vertices ρ_{l,l+1}and arrows α_{l}: D_{2l} [figure]F from the even-numbered vertices of the zig-zag to F, such that x_{j} = α_{1} ∘ ρ_{j,2}, α_{1} ∘ ρ_{3,2} = α_{2} ∘ ρ_{3,4}, …, α_{n} ∘ ρ_{2n,k} = x_{k}

Then we have the following:

3.3. Theorem. A finitely accessible category K is coherent if and only if it has the “2/3-SFP” property.

Proof. Suppose that K is coherent and consider a finite diagram C: I [figure] K_{f} of finitely presentable objects. There is an induced finite diagram in Set^{K_{f}}. Consider its limit lim_{I} hom(C_{i}, −). The assumption tells us that it is a finitely presentable object. It is, thus, a finite colimit of representables:

e: lim_{I} hom(C_{i}, −) ≅ colim_{J} hom(D_{j}, −): p

The construction of limits in Set gives, for all objects F ∈ K_{f}, a bijection between elements of lim_{I} hom(C_{i}, F) and cocones of the diagram C: I [figure] K_{f} . Then the image, under the bijection, of id_{D_{j}} renders each (D_{j}, λ_{j}: C [figure] D_{j}) a cocone for the diagram. Furthermore, if we start with a cocone (F, ξ: C [figure]F) then the image, under the bijection, of the element that it determines in lim_{I} hom(C_{i}, F) is an element o colim_{J} hom(D_{j}, F). It is thus represented by some arrow x: D_{j} [figure]F. Then (F, x ∘ λ_{j}) is still a cocone for the diagram. By naturality we have a commutative square

\xymatrix{colim_{J} hom(D_{j}, D_{j}) \ar[d]_{\overline{x∘−}} \ar[r]^{p_{j}} & lim_{I} hom(C_{i}, D_{j}) \ar[d]^{x∘−} \\ colim_{J} hom(D_{j}, F) \ar[r]^{p_{F}} & lim_{I} hom(C_{i}, F)}

We have that p ∘ e = id, so

(ξ_{i})_{i=1}^{n} = p_{F} e_{F} (ξ_{i})_{i=1}^{n}
= p_{F} (x̄)
= p_{F} (\overline{x ∘ id_{j}})

= x ∘ p_{j}(id_{j})
= (x ∘ λ_{j,i})_{i=1}^{n},

thus having the desired factorization. The above naturality square manifests also the fact that the vertices of the diagram D: J [figure]K_{f} are morphisms of cocones (this is a diagram taking values inside Set^{K_{f}} but it factors through K_{f}). In particular, consider any d: D_{j} [figure]D_{j′} in the image of D and let λ: C ⇒ D_{j} be a cocone corresponding to some element inside colim_{J} hom(D_{j}, D_{k}) represented by id: D_{j} [figure] D_{j}. Let also μ: C ⇒ D_{j′} be the cocone corresponding to the element of colim_{J} hom(D_{j′}, D_{j′}) represented by id: D_{j′} [figure]D_{j′}. The latter is also represented by the element d: D_{j} [figure]D_{j′} inside colim_{J} hom(D_{j}, D_{j′}) since there is an obvious zig-zag connecting the two elements of colim_{J} hom(D_{j}, −) that are defined at stage D_{j′}. The naturality square then gives us

μ = p_{j′}(\overline{d}) = d ∘ p_{j}(\overline{id_{j}}) = d ∘ λ.

Finally, consider any two factorizations of (F, ξ: C [figure]F) through some (D_{j}, λ_{j}: C [figure]D_{j}), (D_{k}, λ_{k}: C [figure]D_{k}). By naturality we have e_{F} (x_{j} ∘ λ_{j}) = \overline{x_{j} ∘ e_{j}(λ_{j})} and

e_{F} (x_{k} ∘ λ_{k}) = \overline{x_{k} ∘ e_{k}(λ_{k})} . So x_{j} ∘ e_{j}(λ_{j}) and x_{k} ∘ e_{j}(λ_{k}) represent the same element inside the colimit. By the construction of colimits in the category of sets we get that, if the arrows y_{j}: D_{n} [figure] D_{j} and y_{k}: D_{m} [figure] D_{k} represent e_{j}(λ_{j}) and e_{k}(λ_{k}), respectively, then there is a zig-zag

\xymatrix{ & D_{2} &  &  &  & D_{2ν} \\ D_{n} = D_{1} \ar@{.>}[ur]^{ρ_{n,2}} &  & D_{3} \ar@{.>}[ul]_{ρ_{2,3}} & ... & D_{2ν−1} \ar@{.>}[ur]^{ρ_{2ν−1,2ν}} &  & D_{2ν+1} = D_{m} \ar@{.>}[ul]_{ρ_{2ν,m}}}

connecting D_{n} and D_{m}, with the relevant identities holding, the x_{j} ∘y_{j} and x_{k} ∘y_{k} entering the leftmost and rightmost equation. Then the augmented zig-zag

\xymatrix{ & D_{j} &  &  &  & D_{k} \\ D_{j} = D_{−1} \ar@{.>}[ur]^{id_{j}} &  & D_{n} = D_{1} \ar@{.>}[ul]_{y_{j}} & ... & D_{2ν+1} = D_{m} \ar@{.>}[ur]^{y_{k}} &  & D_{2ν+3} = D_{k} \ar@{.>}[ul]_{id_{k}}}

gives the desired conditions.

Conversely let us assume that K satisfies the 2/3-SFP property. Notice that the definition of the 2/3-SFP property includes the conditions that are necessary and sufficient for a presheaf topos to be coherent ([4], Exposé VI, Exercise 2.17 c)), so that we only have to verify that the finitely presentable objects are closed under finite limits. We first show that the finitely presentable objects of Set^{K_{f}} are closed under products. Since retractions are preserved by products and, due to the cartesian closedness of the topos, the product of two colimits of representables is a colimit of products of representables, it suffices to show that the product of two representable functors is a finitely presentable object. So consider a product hom(C, −) × hom(D, −). For the discrete diagram {C, D}, there is a finite set {B_{i}} of cocones, with the property that any other cocone for this diagram factors through them. This means that there is a map e: hom(C, −) × hom(D, −) [figure] colim_{I} hom(B_{i}, −) sending a pair of arrows out of C, D to their factorization through a B_{i}. In the opposite direction there is a map p: colim_{I} hom(B_{i}, −) [figure]hom(C, −) × hom(D, −) sending an element of colim_{I} hom(B_{i}, −) defined at stage F and represented by an x: B_{i} [figure]F to the cocone produced by composition with the cocone λ_{i}: {C, D} ⇒ B_{i}. This establishes an obvious isomorphism between the two, provided the map p were well defined. This is indeed the case: Let \overline{x} = \overline{y} as elements of colim_{I} hom(B_{i}, F), where y: B_{j} [figure] F. Then there is a zig-zag with vertices B_{i} = B_{1}, ..., B_{2n+1} = B_{j}, edges ρ_{l,l+1}, l = 1, ..., 2n + 1 and arrows z_{l}: B_{2l} [figure] F, l = 1, ..., n satisfying

x = z_{1} ∘ ρ_{1,2},  z_{1} ∘ ρ_{2,3} = z_{2} ∘ ρ_{3,4},
... ,  z_{n} ∘ ρ_{2n,2n+1} = y

The fact that the edges are morphisms of cocones gives

x ∘ λ_{i} = z_{1} ∘ ρ_{1,2} ∘ λ_{i}
= z_{1} ∘ λ_{2}
= z_{1} ∘ ρ_{2,3} ∘ λ_{3}
= z_{2} ∘ ρ_{3,4} ∘ λ_{3}
= ...
= y ∘ λ_{j}

proving the good definition of the map p.

Next, we show the closure of the finitely presentable objects under equalizers. We can reduce the proof to showing that the equalizer of a pair of arrows

f, g: hom(C, −) [figure] colim_{J} hom(D_{j}, −)

is finitely presentable. The two arrows correspond, via Yoneda, to a pair of elements f̌, ǧ ∈ colim_{J} hom(D_{j}, C). An arrow x: C [figure] F belongs to the equalizer of f, g at stage F if the composites x∘f̌, x∘ǧ represent equal elements in colim_{J} hom(D_{j}, F). Thus when D_{j}, D_{k} are not part of the same connected component of the diagram D: J [figure] K_{f}^{op}, the equalizer of f, g is the initial presheaf, which is finitely presentable. So we assume that f̌, ǧ are connected by a zig-zag:

\xymatrix{ & D_{2} \ar[dddr]^{α_{1}} &  & D_{2n} \ar[dddl]_{α_{n}} \\ D_{j} = D_{1} \ar@{.>}[ur]^{ρ_{j,2}} \ar[drr]_{f̌} &  & D_{3} ... D_{2n−1} \ar@{.>}[ul]_{ρ_{2,3}} \ar@{.>}[ur]^{ρ_{2n−1,2n}} &  & D_{2n+1} = D_{k} \ar@{.>}[ul]_{ρ_{2n,k}} \ar[dll]^{ǧ} \\  &  & C \ar[d]^{x} \\  &  & F}

For every finite diagram \overline{D_{z}} consisting of some zig-zag connecting D_{j} and D_{k}, as well as f̌ and ǧ, let C_{z,n} be the set of cocones for it, as provided by the first clause of the “2/3-SFP” property.

We will exhibit a pair of natural maps

Eq(f, g) [figure: e; p] colim_{z}colim_{n} hom(C_{z,n}, −)

where the first colimit on the right hand side is taken over all possible zig-zags connecting D_{j} and D_{k}. As morphisms between zig-zags in the indexing category for that colimit are taken morphisms between their respective vertices in the image of J satisfying the obvious commutativities. Notice that there are finitely many such zig-zags and that any two of them can be taken of equal length by possibly adding identities. Also notice that every morphisms (z) ⇝ (z′) induces morphisms of cocones C_{z,n} [figure] C_{z′,n′} for any of the cocones of the diagrams \overline{D_{z}} and \overline{D_{z′}}, respectively, that are prescribed by the “2/3-SFP” property.

The action of e is as follows: As explained above an element of the equalizer at level F determines an element in colim_{J} hom(D_{j}, F), represented by both x ∘ f̌, x ∘ ǧ. The fact that the two arrows represent the same element in the colimit means, by the construction of the colimits in the category of sets, that they are edges of a cocone for one of the above diagrams \overline{D_{z}} . Hence there is a factorization C_{z,n} [figure]F through one of the C_{z,n}’s, by the second clause of the “2/3-SFP” property. Thus we obtain the image e_{F} (x) in colim_{z}colim_{n} hom(C_{z,n}, F). Whenever we have another zig-zag manifesting the equality of x ∘ f̌, x ∘ ǧ as elements of colim_{J} hom(D_{j}, C) and a factorization of x through a different cocone C_{z′,n′}, for the respective diagram, then we can concatenate the two zig-zag’s into a larger diagram. A cocone C_{z′′,n′′} for this larger diagram remains a cocone for each one of the two smaller subdiagrams and so does F, so we have factorizations C_{z_{1},n_{1}} [figure] C_{z′′,n′′}, regarding the first subdiagram,C_{z′_{1},n′_{1}} [figure] C_{z′′,n′′}, regarding the second and C_{z′′,n′′} [figure] F, regarding the larger subdiagram. Now, using the third clause in the definition of the “2/3-SFP” property, there are zig-zag’s from C_{z,n} to C_{z_{1},n_{1}} and an edge from C_{z_{1},n_{1}} to C_{z′′,n′′}, as well as from C_{z′,n′} to C_{z′_{1},n′_{1}} and an edge from C_{z′_{1},n′_{1}} to C_{z′′,n′′}, and respective arrows from their vertices to F, satisfying the equations of the definition. Pasting the two zig-zag’s together, we find a zig-zag from C_{z,n} to C_{z′,n′} and edges to F, satisfying the relevant identities, showing that the image of x under e_{F} is well defined.

This also shows the naturality of e: If γ: F [figure] G is a transition arrow then the square

\xymatrix{Eq(f, g)(F) \ar[d]_{γ∘−} \ar[r]^{e_{F}} & colim_{z}colim_{n} hom(C_{z,n}, F) \ar[d]^{\overline{γ∘−}} \\ Eq(f, g)(G) \ar[r]^{e_{G}} & colim_{z}colim_{n} hom(C_{z,n}, G)}

is commutative. Because, if { \atop e_{F} (x)} represents e_{F} (x) in colim_{z}colim_{n} hom(C_{z,n}, F) then

\overline{γ ∘ { \atop e_{F} (x)}} and e_{G}(γ ∘ x) represent two factorizations of the element γ ∘ x of the equalizer, defined at level G, through different cocones among the prescribed ones. Thus, as elements of the colimit at level G, they are equal.

In the opposite direction p sends an element x: C_{z,n} [figure] F to the element x ∘ λ_{C}: C [figure]C_{z,n} [figure]F, where λ_{C} is the C− edge of the cocone λ for the diagram \overline{D_{z}}. This

can readily seen to be an element of the equalizer of f, g. The necessary commutativities manifesting the equality of x ∘ λ_{C} ∘ f̌ with x ∘ λ_{C} ∘ ǧ inside colim_{J} hom(D_{j}, F) follow from the fact that C_{z,n} is a cocone for \overline{D_{z}}. The fact that the definition of p does not depend on the choice of the representative x (thus the naturality of p, as well) is as follows: Let x_{1}: C_{z_{1},n_{1}} [figure]F represent the same element of colim_{z}colim_{n} hom(C_{z,n}, F) as x_{k}: C_{z_{k},n_{k}}

[figure]F, where μ: \overline{D_{z_{k}}} ⇒ C_{_{k},n_{k}} is a cocone for another diagram \overline{D_{z_{k}}}. Then there are cocones C_{z_{i},n_{i}} for diagrams \overline{D_{z_{i}}} and a zig-zag connecting them as in the diagram

[figure: C; λ_{c}; μ_{c}; (λ_{2})_{c}; (λ_{3})_{c}; (λ_{k−2})_{c}; (λ_{k−1})_{c}; C_{z_{2},n_{2}}; x_{2}; C_{z_{k−1},n_{k−1}}; x_{k−1}; …; C_{z_{1},n_{1}}; x_{1}; α_{1,2}; C_{z_{3},n_{3}}; α_{2,3}; α_{3,4}; x_{2}∘α_{2,3}=x_{3}∘α_{3,4}; C_{z_{k−2},n_{k−2}}; C_{z_{k},n_{k}}; α_{k−1,k}; x_{k}; F]

The edges α_{i,i+1} are morphisms induced by morphisms of zig-zags, thus they are morphisms of cocones for the diagrams \overline{D_{z_{i}}}. Thus we have

x_{1} ∘ λ_{C} = x_{2} ∘ α_{1,2} ∘ λ_{C}
(compatibility for the zig-zag) = x_{2} ∘ (λ_{2})_{C}
(the α’s are morphisms of cocones) = x_{2} ∘ α_{2,3} ∘ (λ_{3})_{C}
(compatibility for the zig-zag) = x_{3} ∘ α_{3,4} ∘ (λ_{3})_{C}
= ...
= y ∘ μ_{C}

Also from the construction follows that p ∘ e = id, having thus presented the equalizer in question as a retract of a finite colimit of representables. In a locally finitely presentable category the retracts of finite colimits of objects in a set of regular generators are exactly the finitely presentable objects ([8], Satz 7.6, in a presheaf category however these happen to be just the finite colimits of representables).

The general case now follows, because the equalizer of two arrows out of a finite colimit of representables is a retract of the colimit of the equalizers of the arrows produced after composing with the inclusion of each representable into the colimit.

Remark. It is obvious that when K_{f} is a Plotkin category, in the sense of [16], then it has the “2/3-SFP” property, something that ought to hold, as the former notion is meant as a categorical version of the “SFP” property.

3.4. Corollary. The upper powercategory of a coherent category is a locally finitely presentable one

Proof. If K is coherent then the finitely presentable objects of Set^{K_{f}} are closed under finite limits and we have P_{U}(K) = Lex((Set^{K_{f}})_{f}).

Finally, observe that the “2/3-SFP” property is involves only the small category of finitely presentable objects of a finitely accessible category. So it can be stated for any small category ℂ. On the other hand the full subcategory of finitely presentable objects of Set^{ℂ^{op}} is just the free cocompletion of ℂ under finite colimits. Thus a restatement of the above theorem is

3.5. Corollary. The free cocompletion of a small category ℂ under finite colimits has finite limits if and only if the dual of ℂ satisfies the conditions in the definition of the “2/3-SFP” property.

References

[1] S. Abramsky, A. Jung, Domain Theory, in Handbook of Logic in Computer Science, S. Abramsky, D. Gabbay, T. S.E Maibaum eds., Vol. 3 Oxford University Press (1995)

[2] J. Adámek, A categorical generalization of Scott domains, Mathematical Structures in Computer Science, 7 (1997), 419 - 443 Theory and Applications of Categories, Vol. 9, No. 6 120

[3] J. Adámek, J. Rosický, Locally Presentable and Accessible Categories, Cambridge University Press, (1994)

[4] M. Artin, A. Grothendieck, J.l. Verdier, Theorie de Topos et Cohomologie Etale des Schemas, Lecture Notes in Mathematics, Vol. 269, 270, Springer (1971)

[5] A. Blass, A. Scedrov, Classifying topoi and finite forcing, Journal of Pure and Applied Algebra 28 (1983) 111-140

[6] M. Bunge, J. Funk, Spreads and the symmetric topos, Journal of Pure and Applied Algebra, 113 (1996), 1-38

[7] M. H. Escardó, Properly injective spaces and function spaces, Topology and its Applications, 89 (1998) 75-120

[8] P. Gabriel, F. Ulmer, Lokal Præsentierbare Kategorien, Lecture Notes in Mathematics, vol. 221, Springer (1971).

[9] P. T. Johnstone, Injective toposes, in Lecture Notes in Mathematics 871, Springer (1979)

[10] P. T. Johnstone, A. Joyal, Continuous categories and exponentiable toposes, Journal of Pure and Applied Algebra 25 (1982), 255-296

[11] P. T. Johnstone, Partial products, bagdomains and hyperlocal toposes, Proceedings of the LMS Symposium on Applications of Categories in Computer Science, Cambridge University Press (1991)

[12] A. Kock, Postulated colimits and left exactness of Kan extensions, Matematisk Institut, Aarhus Universitet, Preprint Series, 9 (1989)

[13] S. Mac Lane, I. Moerdijk, Sheaves in Geometry and Logic, Springer, (1992)

[14] M. Makkai, G. Reyes, First order categorical logic, in Lecture Notes in Mathematics 611, Springer (1977)

[15] A. Pitts, On product and change of base for some toposes, Cahiers de Topologie et Geometrie Differentiele Categoriques, Vol. XXVI(1), (1985), 43-61

[16] V. Trnkova, J. Velebil, On categories generalizing universal domains, Mathematical Structures in Computer Science, 9 (1999), 159-175

[17] S. Vickers, Geometric theories as databases, Proceedings of the LMS Symposium on Applications of Categories in Computer Science, Cambridge University Press (1991)

Department of Mathematics, University of Patras, 26500 Patras, Greece

Email: pkarazer@math.upatras.gr

This article may be accessed via WWW at http://www.tac.mta.ca/tac/ or by anony-

mous ftp at ftp://ftp.tac.mta.ca/pub/tac/html/volumes/9/n6/n6.{dvi,ps}

THEORY AND APPLICATIONS OF CATEGORIES (ISSN 1201-561X) will disseminate articles that significantly advance the study of categorical algebra or methods, or that make significant new contributions to mathematical science using categorical methods. The scope of the journal includes: all areas of pure category theory, including higher dimensional categories; applications of category theory to algebra, geometry and topology and other areas of mathematics; applications of category theory to computer science, physics and other mathematical sciences; contributions to scientific knowledge that make use of categorical methods.

Articles appearing in the journal have been carefully and critically refereed under the responsibility of members of the Editorial Board. Only papers judged to be both significant and excellent are accepted for publication.

The method of distribution of the journal is via the Internet tools WWW/ftp. The journal is archived electronically and in printed paper format.

Subscription information. Individual subscribers receive (by e-mail) abstracts of articles as they are published. Full text of published articles is available in .dvi, Postscript and PDF. Details will be e-mailed to new subscribers. To subscribe, send e-mail to tac@mta.ca including a full name and postal address. For institutional subscription, send enquiries to the Managing Editor, Robert Rosebrugh,

rrosebrugh@mta.ca.

Information for authors. The typesetting language of the journal is TEX, and L^{A}TEX is the preferred flavour. TEX source of articles for publication should be submitted by e-mail directly to an appropriate Editor. They are listed below. Please obtain detailed information on submission format and style files from the journal’s WWW server at http://www.tac.mta.ca/tac/. You may also write to tac@mta.ca to receive details by e-mail.

Editorial board.

John Baez, University of California, Riverside: baez@math.ucr.edu Michael Barr, McGill University: barr@barrs.org, Associate Managing Editor Lawrence Breen, Université Paris 13: breen@math.univ-paris13.fr Ronald Brown, University of North Wales: r.brown@bangor.ac.uk Jean-Luc Brylinski, Pennsylvania State University: jlb@math.psu.edu Aurelio Carboni, Università dell Insubria: aurelio.carboni@uninsubria.it P. T. Johnstone, University of Cambridge: ptj@dpmms.cam.ac.uk G. Max Kelly, University of Sydney: maxk@maths.usyd.edu.au Anders Kock, University of Aarhus: kock@imf.au.dk F. William Lawvere, State University of New York at Buffalo: wlawvere@acsu.buffalo.edu Jean-Louis Loday, Université de Strasbourg: loday@math.u-strasbg.fr Ieke Moerdijk, University of Utrecht: moerdijk@math.uu.nl Susan Niefield, Union College: niefiels@union.edu Robert Paré, Dalhousie University: pare@mathstat.dal.ca Andrew Pitts, University of Cambridge: Andrew.Pitts@cl.cam.ac.uk Robert Rosebrugh, Mount Allison University: rrosebrugh@mta.ca, Managing Editor Jiri Rosicky, Masaryk University: rosicky@math.muni.cz James Stasheff, University of North Carolina: jds@math.unc.edu Ross Street, Macquarie University: street@math.mq.edu.au Walter Tholen, York University: tholen@mathstat.yorku.ca Myles Tierney, Rutgers University: tierney@math.rutgers.edu Robert F. C. Walters, University of Insubria: walters@fis.unico.it R. J. Wood, Dalhousie University: rjwood@mathstat.dal.ca