Survey

* Your assessment is very important for improving the workof artificial intelligence, which forms the content of this project

Survey

Document related concepts

Transcript

TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY Volume 299, Number 2, February 1987 SOME RESULTS ON LOCALLY FINITELY PRESENTABLE CATEGORIES M. MAKKAI AND A. M. PITTS ABSTRACT. We prove that any full subcategory of a locally finitely pre- sentable (l.f.p.) category having small limits and filtered colimits preserved by the inclusion functor is itself l.f.p. Here "full" may be weakened to "full with respect to isomorphisms." Further, we characterize those left exact functors T. C —» D between small categories with finite limits for which the functor /*: LEX(D,Set) —>LEX(C,Set) induced by composition is full and faithful. As an application, we prove a theorem on sheaf representations, a consequence of which is that, for any site C = (C, J) on a category C with finite limits, defined by a subcanonical Grothendieck topology J, the closure in LEX(C, Set) under small limits and filtered colimits of the models of C is the whole of LEX(C,Set). Introduction. In this paper, we make contributions to the logic of 'essentially algebraic' theories. Although the terminology will be categorical, the motivation is a model-theoretical one: our interest lies in arriving at results connecting the syntax and the semantics of that logic. The definition of 'essentially algebraic' theory can be given conveniently only in categorical terms. As is usually done, we identify such a theory with a small category having (all) finite limits. The 2-category of all such categories, with functors preserving finite limits as morphisms (1-cells), and all natural transformations as 2-cells, is denoted by Lex; LEX denotes the 2-category with the smallness restriction removed. Set, the category of (small) sets, is the 'standard' 'theory', an object of LEX. A 'model' of a theory C G Lex is a morphism C —>Set in LEX; LEX(C, Set) is the 'category of models of C Talking about relations of syntax and semantics amounts, roughly, to relating C and LEX(C,Set). Following [KR, we could call our subject the "doctrine of Cartesian logic". The doctrine of Cartesian logic corresponds to a logic with existential quantification restricted to cases when unique existence is assured. For a detailed account of this correspondence, cf. [C]. The main fact of the correspondence can be stated simply. Call a first-order theory T over a language L axiomatized by sentences of the form Vx(y?(x) —>3=1yi/>(x, y)) with <p and ii finite conjunctions of atomic formulas (3=1y means: "there is a unique y such that ...") a lim-theory. Then the categories of models of lim-theories, with ordinary homomorphisms as morphisms, are the same as the categories LEX(C, Set), -for C G Lex. The connection of the lim-theories themselves and objects of Lex is a bit less easy to state; it is done in [C]. Received by the editors May 8, 1984 and, in revised form, April 20, 1985. 1980 Mathematics Subject Classification (1985 Revision). Primary 03G30, 18B99; Secondary 03C20, 03C52. ©1987 American Mathematical Society 0002-9947/87 $1.00 + $.25 per page 473 License or copyright restrictions may apply to redistribution; see http://www.ams.org/journal-terms-of-use 474 M. MAKKAI AND A. M. PITTS The, by now, classic work [GU] gives, among others, an intrinsic characterization of categories which, up to equivalence, can be written as LEX(C,Set); such categories are called locally finitely presentable (l.f.p.). One would be tempted to call them simply algebraic categories since they seem to be comprehensive enough to include all categories of structures which are defined, in one sense or another, by 'unitary algebraic' conditions. One of the main points about l.f.p. categories is the following exactness property: LEX(C, Set) has all (small) limits and filtered colimits and they are preserved by the evaluation ('underlying-set') functors (-)oC: LEX(C, Set) —*Set (C G C). In fact, l.f.p. categories are cocomplete (have colimits) as well, although the colimits are not 'standard'; they are not preserved by the evaluation functors. The mentioned facts concerning limits and filtered colimits are a consequence of a basic fact concerning Set: in Set, finite limits commute with limits and filtered colimits. In §1, we give an essentially self-contained account of the 'duality' of small categories with finite limits and l.f.p. categories. This duality amounts to an equivalence of the 2-categories Lexop and LFP, the 2-category of l.f.p. categories, with morphisms the functors preserving limits and filtered colimits. This duality may be known to many people; most of it is already in [GU], and the remaining parts are more or less folklore. Some technical results used later are also put in §1. The main part of the paper, §§2 and 3, was greatly inspired by Hugo Volger's paper [V]. In a traditional model-theoretical language, Volger arrives, sometimes implicitly, at intriguing results concerning the Cartesian doctrine. One of his main results is a somewhat complicated, but very useful syntactical characterization of those theories whose class of models, considered as a full subcategory of the category of all structures of the underlying language, has limits preserved by the inclusion. One of the main results of the present paper is a purely categorical result, Proposition 2.6, which characterizes those morphisms F: C —>D in Lex that induce a full and faithful morphism F*: LEX(D, Set) -> LEX(C,Set) in LFP. Although the two results concern closely related situations, their statements or their proofs look pretty unrelated. Another result of [V] (Proposition 16) is the fact that any full subcategory of the category of all L-structures (with homomorphisms as morphisms) for which the inclusion creates limits and filtered colimits is an elementary class. Lemma 2.2 in the present paper is a more general form of this result. Using 2.2, and material from §1 we prove (Corollary 2.4) that any full subcategory of a l.f.p. category for which the inclusion creates limits and filtered colimits is again l.f.p.; and even the more general statement where the inclusion is required to be full only on isomorphisms (Proposition 2.3). Volger's remarks after his characterization theorem (Theorem 14) seem to amount to a proof of the weaker result, Corollary 2.4 (although the result as such is not stated). However, as far as we can see, the proof is incomplete (it does not seem to follow that the categories of models of T and T*, in Volger's remarks, are equivalent). We shall give some comments as to why 2.3 is of interest beyond its having 2.4 . as a consequence. Finally, a result that can be deduced from the work of Volger is the fact that whenever a structure is represented as the structure of global sections of a sheaf, License or copyright restrictions may apply to redistribution; see http://www.ams.org/journal-terms-of-use LOCALLY FINITELY PRESENTABLE CATEGORIES 475 then the structure can always be constructed by using (possibly repeatedly) limits and filtered colimits on the stalks of the sheaf. The precise, and more general, statement is Theorem 3.3. Our proof of it uses two of the above-mentioned results: 2.4 and 2.6. An interesting-looking corollary concerning subcanonical Grothendieck topologies ends the paper. 1. Gabriel-Ulmer duality. Let LEX be the 2-category of all categories having finite limits; LFC the 2-category of all categories having all (small) limits and filtered colimits. The morphisms (1-cells) of LEX are all functors between categories with finite limits preserving finite limits; the 2-cells are all natural transformations between such functors; similarly for LFC. We have forgetful functors (inclusions) (1) LEX -> CAT, (2) LFC -> CAT which are faithful and 2-full: full on 2-cells. Set, or S as we will sometimes abbreviate it in this section, the category of all small sets, is an object of both LEX and LFC. Moreover, each of the LEXoperations on S, i.e., the finite limits, commute with each of the LFC-operations, small limits and filtered colimits, on S as is well known (cf. [CWM]). We may say that Set is a symmetric (LEX, LFC)-bistructure. Now, Set as a symmetric (LEX, LFC)-bistructure gives rise, all by itself, to a pair of (2-)adjoint (2-)functors G,F, (3) LEXop ê LFC F presently described. We start with the adjunction CATop g CAT F0 Vo-IdcAT -> Go^o en: FoGo —>IdcAT°p (unit) (counit) given by Go = CAT(—, S), abbreviated as ( —,S), Fo = (-,S), (£o)c- C —>((C, S), S): evaluation, (Vo)a- A —>((A, S), S): evaluation. (The fact that this is an adjunction /-, means that the composites noGo f, j? /-, LrO —► CoroCro -co —» rocro^o Go£o r-, —► Crfj -► c are identities.) The 'symmetry property' of 5 implies that, for any C G LEX, LEX(C, S) G LFC; similarly, and symmetrically, LFC(>i, S) G LEX for A G LFC. Also, for License or copyright restrictions may apply to redistribution; see http://www.ams.org/journal-terms-of-use 476 M. MAKKAI AND A. M. PITTS any LEX-morphism C A C, the functor LEX(C, S) ^ LEX(C, S) defined by composition is an LFC-morphism; of course, a dual statement These facts give rise to the promised 2-functors G: LEXop ^ LFC, F:LFC^LEXop, can also be made. G(C) = LEX(C, S), F(A) = LFC(A, S). To define the counit and the unit of the desired adjunction e: FG —>Wlex°p i/:IdLFC°p —*GF we proceed as follows. The inclusion (1) gives rise to the 'restriction' functor, for each C G LEX: ((C,S),S)-(LEX(C,S),S). Pre-composing this with (eo)ci the resulting functor factors through the inclusion LFC(LEX(C,5), S) -» (LEX(C,S), S), resulting in the functor £C:C^LFC(LEX(C,S),S). This defines e; the description of n is symmetric. The fact that £ and r/ form an adjunction is a formal consequence of their definition together with the corresponding fact for £0 and rjoWe are going to take full sub-2-categories (full with respect to both 1-cells and 2-cells), Lex and LFP, of LEX and LFC, respectively, so that the corresponding restriction of the above adjunction is in fact an equivalence. Lex is the full sub2-category of LEX with objects the essentially small objects of LEX (i.e., those equivalent to a small category). The following definitions describe the smallness conditions determining LFP inside LFC. 1.1 Definitions. (i) A collection Q of objects (for A) if every object in A can (ii) An object A of a (locally if the functor A(A, —): A —>Set subcategory of A whose objects in a category A is called a collection of generators be expressed as a filtered colimit of objects in Q. small) category A is called finitely presentable (f.p.) preserves filtered colimits. Af.p. will denote the full are finitely presentable. (iii) A category A is called locally finitely presentable (l.f.p.), ii A G LFC, A is locally small and it has a small set of generators consisting of finitely presentable objects. LFP is the full sub-2-category of LFC with objects the l.f.p. categories. REMARKS. The use of the expression "collection of generators" in (i) is slightly nonstandard. The definition of "finitely presentable" is, of course, the usual definition; in [GU], one finds "rVpresentable" instead. As the reader may already see, and as will be pointed out in due course, the definition of "l.f.p." given here is equivalent to that of [GU]. 1.2 THEOREM (GABRIEL-ULMER DUALITY). The pair of adjoint functors (3) obtained from the symmetric (LEX, L,FC)-bistructure Set restricts Lexop~LFP. License or copyright restrictions may apply to redistribution; see http://www.ams.org/journal-terms-of-use to an equivalence LOCALLY FINITELY PRESENTABLE CATEGORIES 477 In other words, (i) if C G Lex, then G(C) G LFP and £c is an equivalence of categories; and (ii) if A G LFP, then F (A) G Lex, and 774 is an equivalence of categories. Before the proof of the theorem, we list some facts and lemmas. 1.3. FACTS. Let C G Lex. (i) The inclusion LEX(C, 5) <-»(C, S) creates limits and filtered colimits. (ii) The Yoneda embedding y: Cop —>(C, S) is full, faithful, and sends colimits in C to limits in (C, S). (iii) The Yoneda embedding y is dense, i.e., for any M G (C, S), the diagram DM- Cop I M -> (C, $): (G, -) -»■M i-> (G, -) has colimit M, with the canonical colimiting cone (G,-) —>M i-> (C, -) -> M. (iv) The diagram DM of (ii) is filtered if and only if M G LEX(C, S). (v) M G LEX(C, S) is f.p. if and only if M is representable, i.e., isomorphic to (C,-), for some G e C. These facts are, of course, well known. For completeness, we give a few words concerning their proofs. The fact that finite limits commute with limits and filtered colimits in Set implies that a limit or a filtered colimit in (C, S) oí functors preserving finite limits is again such a functor; this shows (i). For (iii), whose proof is a straightforward computation, see [SGA4, Exp. I, 3.4, p. 19], or [CWM, Corollary X.6.3, p. 243]. For (iv), see [SGA4,Exp. I, proof of 8.3.3 (i)=>(ii),p. 77]. Since for M G (C, S), and G € C, ((G, -), M) = M(C) (Yoneda), the fact that each representable functor in LEX(C, 5) is f.p. follows from (i) and the fact that (filtered) colimits in (G, S) are computed pointwise. Conversely, if A is an f.p. object of a category A, and A is the filtered colimit colim¿ A¿ of objects A¿, then one concludes (by considering the identity morphism A —>colim¿ Ai) that there is an index i such that A is a retract of A¿. Put A¿ = B. If we have p Ac^B, pi - ldA, i then Ids „ B =t B^ A ip is a coequalizer diagram. Thus, if A G A = LEX(C, 5), and we use the filtered colimit representation given by (iii) and (iv) via objects coming from C by y, using (i) and the fact that C has finite limits we obtain that A is isomorphic to a representable functor. This proves (v). D Note that facts 1.3(i), (iii), (iv) and (v) contain the first part of the statement of 1.2(i): G(C) = LEX(C, S) G LFP. The following lemma will have uses beyond Theorem 1.2. 1.4 LEMMA. Suppose that A is locally small and has limits and filtered colimits which are preserved by a functor G: A —>B into a locally finitely presentable category 8- If A has a generating set of objects, Q say, then G has a left adjoint F: B —>A. PROOF. We have to show that for every B G B, we have: (*)b there is an object FB and a 'universal arrow' r/ß'- B —*G(FB) 'from B to G', i.e., r?s such that for every arrow B -^ G A, thee is a unique /: FB —>A such that g — G(f)r¡B- If we have B = colim¿e/R¿, a filtered colimit representation, and (*)b, holds for all i, License or copyright restrictions may apply to redistribution; see http://www.ams.org/journal-terms-of-use 478 M. MAKKAI AND A. M. PITTS then (*)b holds as well. In fact, for each a: i —*j in Morph(7), let Fa be defined so that Bi -» G(FBl) _ G(FBj) rcP I I GFa B. commute; thus, the filtered colimit colim¿ FBi makes sense, and we can take FB to be it. Since G preserves filtered colimits, we have a canonical arrow B = colim B% —> colimG(FBl) = G (colim FBi); we take ps to be this arrow; it is easy to verify that it will have the required property. By the last remark, and since B is l.f.p., it suffices to show the statement (*)b for B f.p. in 3. Since A has limits and G preserves them, we can apply the Adjoint Functor Theorem "at B", i.e., we need only find a set of arrows {gl:B^G(Al)\iGl} with the property that any g: B —► G (A) factors as g:BhG(Al)GH)G(A) for some i G I and /: Ai —► A in A. But {B -» G(A) | A G 9} is such a set. For, given any A G A, we can express it as a filtered colimit of objects in g, say A = colim Ak, fcGK with colimiting cone (ik:Ak -> A | kGK). Since G preserves filtered colimits, we have G A = colimfc€K G(Ak) and (G(ik):G(Ak)^G(A)\kGK) is a colimiting cone. But now given any g: B —>G(A), since B is finitely presentable, g factors through one of the maps in this colimiting cone, i.e., g factors as g:B^G(Ak)G^k)G(A) for some k G K; and Ak G g as required. 1.5 COROLLARY. Let A G LFP. D 1.4 For A G At.p. clearly the representable functor A(A, —) G LFC(A, S). Hence we have a canonical functor hA:A°l^LFC(A,S) This functor (A^A(A,-)). is an equivalence of categories. PROOF. As a consequence of the Yoneda lemma, h¿¿s full and faithful. To show that h & is essentially surjective on objects, let X: A —►5 be a functor in LFC. natural By 1.4, X has a left adjoint Y. The adjunction Y H X specializes to the isomorphisms A(Y(1),A) = S(1,XA) = XA for any A G A. i.e. A(Y(1),-)~X. License or copyright restrictions may apply to redistribution; see http://www.ams.org/journal-terms-of-use LOCALLY FINITELY PRESENTABLE 479 CATEGORIES Since X preserves filtered colimits, Y(l), by definition, is f.p. D 1.5 Now, we can complete the proof of 1.2(i); the assertion to be proved is that £c is an equivalence of categories, for C G Lex. Let A = LEX(C, S). A is l.f.p. By 1.3(v), the Yoneda embedding Cop -» A factors through A{.p. ■—»¡ncl. A, and in fact, the resulting equivalence of categories. Moreover, the composite functor Cop —► Af.p. is an CoplZ AZ^LFC(A,S) hfi (with hA from 1.5) is isomorphic to £c- Therefore, by 1.5, £c is an equivalence as well. G 1.2(i) Turning to the proof of 1.2(h), we let A be an l.f.p. category, C = A¡p , B = LFC(A, S), i: A{.p.t-> A the inclusion, h: C —► B the functor of 1.5. By 1.5, h is an equivalence of categories. It is clear that LFC(A, S) has finite limits preserved by the inclusion LFC(A,S)->(A,S). It follows from h¿ being an equivalence that Ai.p. has finite colimits preserved by i. Since by the argument in the proof of l-3(v), A(.P. is in the closure under finite colimits of a small set contained in A(.p., A(.P. is essentially small. It follows that F (A) =B~Cg Lex, as required for the first part of 1.2(h). h induces the equivalence /i*:LEX(B, S) —>LEX(C,5). r\A.:A —>LEX(B, S) and h*, we obtain a functor Composing r\ — t:A^LEX(C,S) which, as inspection shows, is identical to A^A(i(-),A). Since h* is an equivalence, to show that r¡ is an equivalence, it suffices to show that t is one. The fact that the functor r is an equivalence, for any l.f.p. category A, with a suitable definition of "l.f.p.", is due to Gabriel and Ulmer, and is arguably the main result of [GU]. We are going, nevertheless, to outline the proof, especially since some ingredients of it will be useful for other purposes as well. First, we give a concept which will be important to us. The lemma that follows the definition is due to [GU]; the second part of it is relatively little known. 1.6 DEFINITION. A collection C of objects in a category A will be called conservative if, given /: A —*B in A such that for each G G C U:A(C,A)^A(C,B) is a bijection, then / is an isomorphism. Thus, assuming A to be locally small, C is conservative iff the restricted Yoneda functor, A —»Setc " (sending A i—>A(—, A)) reflects isomorphisms. 1.7 LEMMA. Let A be a locally small category with filtered colimits. (i) Any set of generators in A is a conservative set. License or copyright restrictions may apply to redistribution; see http://www.ams.org/journal-terms-of-use 480 M. MAKKAI AND A. M. PITTS (ii) // C is a conservative set of finitely presentable objects in A which when regarded as a full subcategory of A has finite colimits that are preserved by the inclusion i: C "—>A, then i is dense. PROOF, (i) This is an easy exercise in category theory. (ii) (Cf. 7.4 of [GU].) To say that i is dense is to say that, given an object A G A, the forgetful functor Ua'- C/A —>A from the category of objects of C over A has (f:UA(f)-+A\fGC/A) as a colimiting cone. Note that by assumption hence we can form colimc/A Ua in A. Let is:UA(f)^ be the colimiting on C, C/A is small and filtered; colimUA(h)\f G C/A hSC/A cone and let q: colim UA —>A C/A be the unique morphism making colimc/A Ua UA(f) commute for each / G C/A. We have to show that g is an isomorphism and since C is a conservative set of objects, it suffices to show that for each G G C g,: A (C, colimUA(f)) ~^A(C,A) V fec/A ) is a bijection. But G is finitely presentable; sition with the canonical bijection so it suffices to show that the compo- G: colim A(C,UA(f))=>A(C, colimUA U A(C,A) fec/A V C/A ) is a bijection. Now, this canonical bijection is that induced by the maps (if)*: A(C, Ua(})) —* A(C, colime/a Ua)- Recalling that we may form the colimit of a filtered diagram of sets as the quotient of the disjoint union of the sets by a suitable equivalence relation, we see that if [h] G colime/a A(C,Ua) denotes the equivalence class rep- resented by h: C —>UA(f), then G[h]= g*(if)*h = gifh = fh. But since [G -i UA(f)\ = [C ^ UA(fh)] in colimc/AA(C,UA), it follows that G is indeed a bijection with inverse the map sending k: C —► A to [idc: C —>UA(k)\. D 1.7 License or copyright restrictions may apply to redistribution; see http://www.ams.org/journal-terms-of-use LOCALLY FINITELY PRESENTABLE CATEGORIES IS 1 1.8 COROLLARY.If A is l.f.p., then the inclusion i:Ai.P. ^->A is dense. PROOF. By defintion of "l.f.p.", and 1.7(i), A{.p. is a conservative set in A. We said above that A{.p. has finite colimits preserved by i. Thus, the assertion follows from 1.7(H). D 1.8 We return to the proof of 1.2(ii), specifically of the fact that the functor r is an equivalence.By (the dual of) [CWM,X.6.2, p. 242] and 1.8, t is full and faithful (indeed, this fact is equivalent to the density of i). To show that r is essentially surjective, let M G LEX(^°P , S) be arbitrary; M can be represented (1.3(iii) and (iv)) as a filtered colimit M = colimk Aopp(Ak,-) = colimk A(i(-), Ak); but the last is isomorphic to A(i( —), colimk Ak), by the definition of At.p.- In other words, M = t(A) for A = colinifcAk, as was to be shown. D 1.2(h) The following characterization communication). appears in [Mu] (the referee's of l.f.p. categories 1.9 COROLLARY. The locally small category A is l.f.p. if and only if it satisfies the following conditions (i) A has filtered colimits. (ii) ^f.p. has finite colimits preserved by i: A{.p. '-» A. (iii) A has a small set of generators consisting of f.p. objects. PROOF. It is clear from the above that every l.f.p. category A satisfies condition (ii). Conversely, one sees that the conclusion of 1.8 remains true for A satisfying the three conditions, with the same proof. Thus, the final argument above establishes that the canonical functor r: A —► LEX(i?op , S) is an equivalence in this case; also, A°pp is essentially small. D 1.9 The official definition of "l.f.p." in [GU] is this: A is l.f.p. iff A is co-complete (has all small colimits), and it has a small conservative set contained in Af.p.. With out definition of "l.f.p.", this is a true statement: the 'if part is contained in 1.9 and 1.7(h); the 'only if' part follows by the fact that LEX.(A°P , 5) is a full and reflective subcategory of (Aopp, S) (a consequence of 1.4), which implies that LEX(A°P , S) is co-complete [CWM, Exercise V.5.3, p. 116]. Here is a new set of conditions ensuring that a category is l.f.p. 1.10 PROPOSITION. Suppose B is l.f.p., A has limits and filtered colimits, G: A —> B preserves them, and G is conservative (reflects isomorphisms). Suppose either that (i) A has a small set of generators or that (ii) G has a left adjoint and A{.p. has finite colimits preserved by the inclusion Ai.p. ^-> A. Then A is l.f.p. Moreover, Af.p. is equal to the finite colimit closure of {F(B): B G Bf.p.}, for F the left adjoint of G. For the proof, we need 1.11 LEMMA. Suppose A is locally small, has limits, and has a small set of generators. Then Af.p. has finite colimits, and the inclusion A{.p. <—► A preserves them. PROOF. We have to show that given a finite category J, every diagram D: J —► A whose vertices are finitely presentable has a colimit in A (since this colimit will automatically be finitely presentable). In other words, given such a diagram we License or copyright restrictions may apply to redistribution; see http://www.ams.org/journal-terms-of-use 482 M. MAKKAI AND A. M. PITTS have to find a cone (oj: D(j) —>A | j G J) under D which is initial amongst such cones; but since A has limits, it is sufficient to verify a "solution set" condition (cf. Theorem V.6.1 of [CWM]), i.e., find a set of cones under D so that an arbitrary cone under D factors through one of the cones in the set. We claim that if C is a set of generators for A, then the collection of cones under D with vertices in g forms such a solution set. (It is a set since J and g are small and A is locally small.) For suppose (üj: D(j) —>A \ j G J) is an arbitrary cone under D. Express A as a filtered colimit of objects in g, say A = colim G(k) with colimiting cone (ik:G(k)^A\kGK). Since each D(j) is finitely presentable, a3 factors through one of the ik: „A Since there are only finitely many objects j G J and K is filtered, we can take the same k for every j in the above; then since there are only finitely many arrows a-j ~* f m Ji by changing k if necessary we can also arrange (by using now the 'uniqueness condition' in the D(j)'s being finitely presented) that for each a D(j) °^ D(f) G(k) commutes. Thus (gjk: D(j) —»G(k) \ j G J) is a cone in the solution set through which the given cone factors (via ik). D 1.11 PROOF OF LIO. Assume the hypotheses of the proposition and condition (i), in particular. By 1.11, A{.p. has finite colimits preserved by the inclusion A{.p. <—> A. By 1.4, G has a left adjoint, say F. In other words, condition (ii) is satisfied too. Consider the objects of A of the form FB, for B G Sf.p.. Using the adjunction and the fact that G preserves filtered colimits, one immediately checks that FB G A(.p. when B G B{.p.. We claim that the set {FB: B G B(.P.} is conservative for A. In fact, with any f:A—>A' in A, and B G Sf.p., the map in Set (FB,A) — (FB,A') {FBjy is isomorphic to (B,GA) -» (B,GA') by the adjunction F H G. Therefore, if the former is a bijection, so is the latter. Since Sf.p. is conservative in S (1.7(i)), it follows that if the former maps are all injections, Gf is an isomorphism; hence, since G reflects isomorphisms, / is an isomorphism as well. This shows the claim. License or copyright restrictions may apply to redistribution; see http://www.ams.org/journal-terms-of-use LOCALLY FINITELY PRESENTABLE 483 CATEGORIES Take the closure of {FB:B G Sf.p.} under finite colimits; call this closure C. C is an essentially small full subcategory of At.p. having finite colimits preserved by the inclusion C '—yA. By 1.7(h), C is dense in A. It follows that A is l.f.p., and C = Ai.p. (the latter by the argument given for 1.3(v)). G 1.10 Finally, let us note a consequence of 1.4, and introduce a piece of notation. 1.12 COROLLARY/DEFINITION. Every morphism F:A^B adjoint. We write Ft for the essentially unique left adjoint of F. in LFP has a left D 1.12 Let us note that all results in this section remain valid, with essentially the same proofs, upon systematically replacing, in all definitions and assertions, the term "finite" by the term "of cardinality less than /c" for a fixed regular cardinal k. In fact, this is the context in which the results of [GU] are stated. 2. Reflective subcategories of l.f.p. categories. Throughout this section we will consider a fixed locally finitely presentable category S, a category A with limits and filtered colimits and a functor F: A —>S preserving these limits and colimits. By Theorem 1.2 we can take S to be LEX(C, Set) with C a small category with finite limits. Thus if L is the underlying graph of C, objects of S can be regarded as certain kinds of diagram of type L in Set, the category of all such diagrams being denoted Set . Now we can regard L as specifying a many-sorted language: the objects of L are the sorts and the arrows of L the (unary) function symbols. From this viewpoint, diagrams of type L in Set are just L-structures in the usual sense of model theory. In prticular the essential image of F, viz K = {B G B | B = F(A) some A G A}, is a class of L-structures and we can apply the terminology and methods of model theory to study it. We thus have the notion of an elementary embedding M —>N (a particular kind of morphism in Set ), the concept of two objects M, N G SetL being elementarily equivalent (denoted M = N), ultraproducts of objects of SetL, etc. We also need the following model-theoretic concepts: An ultralimit oí an L-structure M is a filtered colimit of the form colim/g<a Mß, where a is an ordinal, Mo = M and for each ß with ß + 1 < a, Mß —*Mß+1 is the diagonal embedding of Mß into an ultrapower of itself; moreover there is a "continuity" condition, namely that for each limit ordinal A < a, M\ = colim/a<A Mß. It is well-known that ultraproducts in SetL are combinations of products and filtered colimits; by their definition ultralimits are such combinations too. More precisely, if A is a (not necessarily full) subcategory of SetL, with the inclusion A *-> Set creating all limits and filtered colimits, and M G A, then all ultralimits of M are (up to isomorphism) in A as well. Now let k be an infinite cardinal and M an L-structure. Say that M is < ksaturated if for all sets I of cardinality < /c, for any /-indexed system (a¿ \i G I) of elements of M and for any set $(x) of formulae with single free variable x in the language L extended by adding the a¿ as constants, if every finite subset of <J>(z) is satisfiable in M, then so is $(x). M is called < K-homogeneous if for any sets /, J of cardinality < k, any map /: / —>J and any indexed systems (o¿ \ i G I), (bj | j G J) of elements of M, if (M, (a, | i G I)) = (M, (bm | i G I)) License or copyright restrictions may apply to redistribution; see http://www.ams.org/journal-terms-of-use 484 M. MAKKAI AND A. M. PITTS then there is an automorphism h oí M with h(af) = i>/(¿), all i G I. 2.1 LEMMA. For k and M as above, there is an ultralimit of M which is < nsaturated and < n-homogeneous. PROOF. The result follows from Theorems 6.1.8, 6.1.4 and 5.1.17 of [CK]. D 2.1 2.2 LEMMA. With F: A —>S, L and K as above, suppose that F is faithful and full on isomorphisms, i.e., if g:FA —>FA' is an isomorphism in B, then g — F(f) for some (isomorphism) /: A —>A' in A. Then (i) K is an elementary class ofL-structures, i.e., there is a first-order theory T in the language L with K = Mod(T) the class of models of T in Set. (ii) F is full for elementary embeddings, i.e., if g:FA —»FA' is an elementary embedding of L-structures, then g = F(f) for some f: A —>A' in A. PROOF, (i) By assumption on F its essential image K = {B \ B = FA some A G A} is closed under taking ultraproducts and ultralimits. However it is also closed under elementary equivalence. For suppose M = N with N G K. Taking k > card M (= ^{card M(c) \ c G L}), by Lemma 2.1 there is a < /c-saturated, < /«-homogeneous L-structure P which is an ultralimit of N and hence in AT. By saturation there is an elementary embedding e: M —>P (cf. 5.1.12 of [CK]). We will show that e is the joint equalizer of the automorphisms h of P with he = e: it then follows by assumption on F (in particular since F is full on isomorphisms) that M G K. So given a G P\im(e) we have to find an automorphism hoiP such that he — e but h(a) t^ a. By the homogeneity of P it suffices to find b G M with (P,a,(e(c)|ceM))EE(P,6,(e(c)|ceM)) and b ^ a. Such b satisfies the formulae in the set <3>(x)= {a / x} U {<p(x. e(c)) | c e M and P N ip(a, e(c))}. By saturation, we can find 6 provided each finite subset of $(x) is satisfied in P. But if a/jA is the conjunction t¡j(x,e(c)) of such a finite set which is not satisfied in P, then PI=Vx(^(x,e(c)) ->x = a). Now x = a shows that P\= 3xip(x,e(c)) and e is elementary: so there is en G M with Pr=V(e(co),e(c)). Hence a = e(cn), contradicting o ^ im(e). Thus /C is closed under ultraproducts and elementary is an elementary class (cf. [CK]). equivalence and hence it (ii) Given the elementary embedding g: FA -> FA' = N, find e: N -> P as in the proof of (i). Thus g and eg are the equalizers of collections License or copyright restrictions may apply to redistribution; see http://www.ams.org/journal-terms-of-use of automorphisms LOCALLY FINITELY PRESENTABLE of P and hence (changing P by an isomorphism CATEGORIES 485 if necessary) are in the image of F. But since FA A id | FA FA' | e % P is a pullback square, it follows that g is also in the image of F. D 2.2 REMARK. Lemma 2.2 for the case when F is full is due to Volger; cf. Proposition 16 in [V]. 2.3 PROPOSITION.Given a functor F: A -> S with B G LFP and such that A has and F preserves limits and filtered colimits, suppose that F is faithful and full on isomorphisms. Then A G LFP (and hence F is a morphism in LFP). PROOF. By the Löwenheim-Skolem theorem, every L-structure is the colimit of a directed diagram of L-structures of power at most card L + No and of elementary embeddings. Hence, by 2.2, A has an essentially small set of generators, consisting of those objects that are, as L-structures, of power at most cardL + Ho- Now, the result follows from 1.10. G 2.3 REMARKS. 1. The referee suggested that the above proof could be made more categorical by employing the methods and results of [AN1, AN2, and NS], or the equivalent versions given by [GL]. 2. To put ourselves in a familiar situation, let S the category of L-structures, for an arbitrary fixed language L. Let K be an arbitrary class of L-structures (objects in S). Then there is, up to equivalence, a smallest subcategory (not necessarily full) \K]S of S containing K such that the inclusion [K]s —>S is full on isomorphisms, creates limits and filtered colimits. [K]s is constructed by starting with objects in K and by successively throwing in the objects and morphisms of limiting and filtered colimiting cones based on diagrams already in, as well as all isos between objects already in [K]s. The structures in[K]s can be said to share the common algebraic properties of the ones in K, in a rather wide sense of 'algebraic', since algebraic properties should be preserved under the operations that are used to build [K]g from K. Eg., let L contain the single relation symbol C, and let K be the class of all partial orders 0(X) of open sets of any topological space X. Then the properties summarized in "M is a Heyting algebra" will all be shared by the structures M in [K]s. Note that the quoted properties are expressed in terms of C by first-order sentences of fairly high complexity; nevertheless, they are to be regarded as 'algebraic', in contrast to arbitrary first-order properties. Lemma 2.2 says that the class of objects in [K]3 is an elementary class; in other words that, conversely, any structure that shares all those first-order properties common to members of [K]s is, in fact, a member of [K}¿-. Although we have not found a neat syntactic description of the algebraic properties, in the wide sense, common to members of K, we have found a simple description of the class of all structures sharing these properties. We are encouraged to define the algebraic properties of K as the axioms true in [K] s. Proposition 2.3 reassures us that, at least abstractly, [K]s is an 'algebraic' category, i.e., it can be presented as LEX(C,Set) for some (although not very wellknown) C € Lex. In [MI], further observations will be made on C ~ ([K]s)° p ■ License or copyright restrictions may apply to redistribution; see http://www.ams.org/journal-terms-of-use 486 M. MAKKAI AND A. M. PITTS 2.4 COROLLARY. If A ^-> S is a full subcategory of a locally finitely presentable category and A is closed under limits and filtered colimits in B, then A is also locally finitely presentable and a reflective subcategory of B. D 2.4 If in 2.4, S = LEX(C,Set), then by Lemma 2.2(i), A = Mod(T) for T some first-order theory in the language L = graph of C. Volger has given a syntactic characterization of the kind of theories that arise in this way: cf. Theorem 14 of [V]. Volger's theorem says the following. Given any language L, and an elementary class A oí L-structures; then A, when considered a full subcategory of the category of L-structures, has limits and filtered colimits preserved by the inclusion if and only if A can be axiomatized by an L-theory T of the following kind: the axioms of T are all of the form Vx(ip(x) —>3yt/>(x, y)), where <p and tp are conjunctions of atomic formulas; moreover, for each such axiom—and, in fact, for each consequence of T of the given form—there exists a formula a(x, y) :=: 3zt(x, y, z) with r a conjunction of atomic formulas such that T h Vx(^(x) -> 3y^(x, y) A a(x, y)) and n-Vx3^V(x,y). A simple way for a theory T to satisfy Volger's condition is to be axiomatized by sentences of the form \rx(<p(x) —>3=1y?/>(x,y)). Volger gives an example of a theory satisfying his conditions which cannot be axiomatized in the simpler way. This complication is expressed, in the categorical context, by the following fact: it is possible that a morphsm /: C —►D in Lex has the property that 7*:LEX(D,Set) —»LEX(C,Set) is full and faithful, and yet, I is not a quotient morphism in the appropriate sense for the 2-category Lex. Let us say a few words about quotient morphisms in Lex. Intuitively, the morphism /: C —>D, as an interpretation of the 'theory' C in D, is a quotient if D is obtained by adding new axioms but no new primitives to C. Working with categories rather than syntax, the process of adding new axioms to C becomes that of inverting a collection S of (mono)morphisms in C in a way that is universal for Lex. The "category of fractions" construction Q:C —► C[S_1] (cf. [GZ]) gives an explicit way of doing this for suitable collections S. "Universal" here means that for any D G Lex Q*:Lex(C[E_1],D) -> Lex(C,D) is full and faithful and has essential image those functors inverting every morphism in S. Let us call a morphism Q in Lex which arises in this way a quotient morphism. Examining the construction of C[S_1] one can prove that Q: C —► D in Lex is a quotient iff it satisfies the condition: For every g: d —► Q(c) in D, there is /: c' —► c in C and an isomor- Qf phism d = Qc' in D so that g factors as g: d = Qc' —>Qc. The class of quotient morphisms in Lex is orthogonal to the class of conservative morphisms, i.e., those /: C —>D which reflect isomorphisms. These two classes form a factorization system on the 2-category Lex (cf. [FT I]); in particular I is an equivalence (or more precisely full, faithful, and essentially surjective) iff it is both conservative and a quotient. License or copyright restrictions may apply to redistribution; see http://www.ams.org/journal-terms-of-use LOCALLY FINITELY Returning to the situation PRESENTABLE of Corollary 487 CATEGORIES 2.4, by Theorem 1.5 up to equivalence the inclusion A '-* S in LFP is of the form A = LEX(D, Set) £ LEX(C, Set) = S for some I: C —► D in Lex; thus 7 has the property that I* is full and faithful. We can now translate the possible failure of T (the theory with Mod(T) ~ A) to be a finite limit theory quotient of C into the statement that I need not be a quotient morphism. (Of course if J is a quotient then I* is full and faithful.) Let us see an example of this. 2.5 EXAMPLE. Let To be the single-sorted theory of one constant Co and one binary relation a (written x a y and read "y immediately succeeds x" ) satisfying for each n = 1,2,3,... the axiom n (i) (coo-yio- ■•• ayn KcooZfO ■■■a zna z) -> f\ y¿ = z¿. í=i Let Ti be the extension of To by countably many constants Cf,C2, ■■■satisfying the additonal axiom (Ü) CnfJC„+1 for n = 0,1,2,.... Thus To and Tf are Horn theories and the faithful forgetful functor U: Mod(Ti) —►Mod(To) is in LFP. Now axiom (i) shows that in any To-model (X, a, xo) there is at most one way to choose a sequence of elements in X starting at Xo and satisfying axiom (ii); i.e., each To-model has at most one Ti-model structure. Moreover if (X, a, xo, Xf,...) is a Ti-model and /: (X,a, xo) —»(X',a', x0) is a T0homomorphism, then (X',0',x'0=fxo, fxf,...) is a Tf-model. It follows that the forgetful functor U is not only faithful but also full. We claim that the morphism in Lex corresponding to U is not a quotient; this morphism is Fop: Mod(T0)° p —► Mod(T!)op , where F: Mod(T0) -> Mod(T,) is left adjoint to U. We can describe F explicitly as follows. Given a To-model predecessors (X,a,xq), let P(X) = {x | 3x' xax'} in X. By axiom (i) any (finite or infinite) sequence be the subset of Xf, X2,... in P(X) satisfying Xo <TXf a X2 a ■■■ is uniquely determined. Call the longest such sequence the "spine" of X: its length may be finite (possibly zero) or countably infinite. In the latter case X is already a Tf-model and we can take F(X, a, Xo) to be (X, a, xo,xi,...) (and the unit of the adjunction at X to be the identity). If however this length is finite, so that the spine is (xi, X2, • • •, xn), we can form F(X) by adjoining countably many new elements to X, denoted xn.|_i, xn+2, • • -, and extend a by defining xn a xn+f a xn+2 o- (The unit of the adjunction {xn+i,Xn+2,... at X will be in this case the inclusion X —>X U ,}■) Now the free To-model on a set I is easily seen to be 1 +1 with a the empty relation. F thus sends this to N +1 with <r= {(n,n+l) I neN}. License or copyright restrictions may apply to redistribution; see http://www.ams.org/journal-terms-of-use 488 M. MAKKAI AND A. M. PITTS Let q: F(l + 1) —»F(l + 0) be the map N + 1 —>N which sends the unique element of 1 to 1 G N and sends each n 6 N to itself. It is not hard to see that a Tomodel is finitely presentable iff it is finite and that the only finite To-model X with F(X) = F(l) is 1 itself. Thus if Fop:Mod(T0)opp -» ModiTi)^ were a quotient morphism in Lex (recalling the characterization of such morphisms given above), there would have to be p: 1 +1 —>1 in Mod(To) and an automorphism F(l) = F(i) in Mod(Ti) so that q: F(l + 1) -> F (I) is F(l + 1) F^] F(1) = F(1). Of course there is just one To-homomorphism 1+ 1 —► 1, and the only automorphism of F"(l) is the identity: hence we would have q = F(p). But these two maps differ on the unique element of 1 <^-> TV+ 1 = F(l). □ 2.5 This situation should be contrasted with that for pretoposes (which are the proper categorical counterpart of theories in the intuitionistic logic of =, A, V and 3; cf. [MR] and [KR]). Specifically if 7:P —>Q is a morphism in the 2-category Pt of (essentially small) pretoposes, the hard part of the "conceptual theorem" of Reyes and the first author says that if completeness 7*:PT(Q,Set)^PT(P,Set) is full and faithful then I is a quotient morphism (in the sense appropriate to Pt); we refer the reader to Chapter 7 of [MR] for the details. Whilst 2.5 shows that the corresponding statement for Lex fails, one should note that nevertheless a very strong form of conceptual completeness holds for Lex by virtue of the Gabriel- Ulmer duality; viz for C, D e Lex, if LEX(C, Set) ~ LEX(D, Set) then C ~ D. The natural question which therefore arises is whether one can give a condition on 7: C —>D in Lex, weaker than that of being a quotient, which is necessary and sufficient for 7*:LEX(D,Set) -> LEX(C,Set) to be full and faithful. We devote the rest of this section to proving a positive answer to this question. the following proposition, which provides 2.6 PROPOSITION. For I: C —>D in Lex, the following are equivalent: (i) The geometric morphism i: Set —>Set induced by I (viz i* = left Kan extension along Iop and i* = precompositon with I°p) is an inclusion. (ii) 7*:LEX(D,Set) -> LEX(C,Set) is full and faithful. (hi) For each c G C, every object of the slice category E*/Ic is a retract object in the image of the functor llApply 7" Ie: C/c —>D/7c, i.e. given g:d —>Ic in D, there is f:c' —*c in C and maps i: d —>7c' and r: Ic' —>d in D such that r o i — id, g o r = If (and hence If Oi = g) License or copyright restrictions may apply to redistribution; see http://www.ams.org/journal-terms-of-use of an LOCALLY FINITELY PRESENTABLE 489 CATEGORIES PROOF, (i) => (ii). Recall (or cf. [TT]) that if TOP denotes the 2-category of Grothendieck toposes and geometric morphisms, there is an equivalence LEX(C, £) ~ TOP(<f, Setc°P) that is natural in C G Lex and £ G TOP. commutes LEX(D,Set) ~ i'l = LEX(C.Set) ~ up to isomorphism. In particular TOP(Set,SetD°P) I ¿o(-) TOP(Set,Setc°P) But if i is an inclusion, i o ( —) is full and faithful and hence so is 7*. (ii) => (iii). First note that if 7: C —>D is in Lex, so is 7c:C/c —>D/7c. Similarly, given S in LFP and B G S, the category B/B of objects in S under B is locally finitely presentable. (For the forgetful functor U: B/B —>S creates limits and filtered colimits, and reflects isomorphisms; it has a left adjoint U, given by coproduct with B; also, B/B has arbitrary small colimits. Thus, 1.10 (with condition (ii)) is applicable.) Moreover, given F: A -> S in LFP, we get B/F-.FB/A -> B/B in LFP by sending an object under F\B, F\B —►A, to its transpose B —> FA across the adjunction F\ H F, and similarly for morphisms. It follows that if F is full and faithful, so is B/F. Now there is an equivalence of categories LEX(C/c,Set) ~ Fc/LEX(C,Set) where Yc is the representable functor C(c, —). This is because A: C —>C/c (sending d to 7T2:c' X c —*c) is characterized in LEX as the result of freely adjoining a global element 1 —>c to c G C (i.e., in terms of theories, the result of expanding the language by a constant of type c without adding any new axioms). The equivalence is natural in C: thus given 7: C —>D LEX(D/7c,Set) ~ Y(7c)/LEX(D,Set) ~ 7!(Fc)/LEX(D,Set) (/«)• \ = / Yc/r LEX(C/c, Set) ~ Fc/LEX(C, Set) commutes up to isomorphism. (Here 7|:LEX(C, Set) —► LEX(D,Set) denotes the left adjoint of 7*, i.e., left Kan extension along 7.) Thus if 7* is full and faithful, so is Yc/I* and hence so is (7C)*, each c G C. So we will have (iii) if we can show: 7* full and faithful implies that every object of D is a retract of an object in the image of 7. By Theorem 1.2 this is equivalent to showing that if F: A —>S in LFP is full and faithful, then each A G A{.p. is a retract of some F\B with B G Sf.p.. But given such an F and A G A(.p., we can express FA as a filtered colimit of finitely presentable objects of S, say FA = colim Bk, fceK with Bk G Bf p all k G K. Then as F is full and faithful A = FFA = co\imFBk. fceK License or copyright restrictions may apply to redistribution; see http://www.ams.org/journal-terms-of-use M. MAKKAI AND A. M. PITTS 490 Since A is finitely presentable, the vertices of the colimit this composite A » ^> isomorphism factors through one of colim F\ Bk **. fceK Î for some fceK. Thus A is a retract of F\Bk with Bk G Sf.p., as required. Dop Setc°P is full and (iii) =>•(i). We have to show that ¿, = (7op)*:Set faithful. For this it is sufficient to take X = Setop in the following lemma. 2.7 LEMMA. 7/7:C —► D ¡n Lex satisfies (iii) of 2.6, then for any category X, I*: Xu —>Xe is full and faithful. PROOF. To show 7* is faithful, given ip, vj: F =t G in Xo suppose <p¡ = vb¡. Then for any d G D, taking c = 1 (the terminal object in G) in 2.6(iii), we can express d as a retract of an object in the image of 7: d \ 7c id Then >Gd F<T -*-G7c F7c<Plc=lt>Ic commutes and Gi is (split) mono: hence ¡pd = r¡>¿. To show that 7* is full, given F,G G XD suppose we have 9:FI —>GI in Xe. Then given d G D find c, i, and r as above and define f-U Gd ÎGr tpd = Gr o 0C o Ft -» F7c We will show simultaneously that <p<¿is independent G7c. of the choice of retract natural in d. Given g: df —► (¿2 in D and retracts \' 7cj id I 0 = 1,2), d1 applying 2.5(iii) to d —> /Ci X iC2 = i(Cf X C2), License or copyright restrictions may apply to redistribution; see http://www.ams.org/journal-terms-of-use and is LOCALLY FINITELY PRESENTABLE CATEGORIES 491 we can find (/i, /2): C3 —>Ci x c2 and maps ¿3: df —>7c3, r3: 7c3 —><7i such that r3 o ¿3 = id, ¿1 o r3 = 7/1 and i2g o r3 = 7/2 (and hence Iff oi3 — if and 7/2 o ¿3 = z2g) (7ci x 7c2; Thus Grf6CiFif = Grf9ClFIffFi3 = Gr1G7/1ÖC3Fi3 = GriGiiGr30c3Fi3 = Gr36C3Fi3. Hence Gg(Gr1eciFil) = Gg(Grz6C3Fi3) = Gr2GÍ2GgGr3ec;íFi3 = Gr2GIf26C2Fi3 = Gr2ec2FIf2Fi3 Thus Gg o y?dl = <pd2o Ff/, so that <p<iis natural = (Gr2ec2Fi2)Fg. in d; moreover, taking g = id we also get Gr20C2FÍ2 — Gri0ClFif, i.e., the definition of <p¿ is independent of which retract when d = Ic for some c 6 C, we can take the we choose. In particular, retract i = id = r and conclude that ip¡c = 9C. Thus 7* is indeed full. This completes the proof of 2.6. D 2.6 D 2.7 REMARK. The equivalence of conditions (i) and (ii) could be deduced from the "conceptual completeness result" for pretoposes, mentioned above. 3. Regaining the global sections of a sheaf from its stalks. Suppose that C is a small, finitely complete category and that £ is a Grothendieck topos. We can think of a functor F G LEX(C, £) as being a "sheaf of models of C over the generalized space £." From this viewpoint, the global sections of F, TF G LEX(C, Set), is the composition of F with T = £(1, -): £ —*Set. Similarly, given a point of £, i.e., a geometric morphism p G TOP(Set, £) = Pt(£), the stalk of F at p, Fp G LEX(C, Set), is the composition of F with the inverse image part of p, p*: £ —>Set. From the point of view of models of C in Set, F provides a sheaf representation of TF in terms of the stalk models Fp. Can one express this relationship solely in terms of the category of models in Set, LEX(C,Set)? One often thinks of a sheaf representation as a kind of generalized limit, and indeed for presheaf toposes limits do indeed provide the answer to the above question. 3.1 EXAMPLE. Suppose that £ = SetA°P with A a small category. Then V: t -> Set is just liniA°p, i.e., "take the limit over Aop." Now each object a G A provides a point pa of £ whose inverse image part is just evaluation at a: P*a(F) = F (a) (and similarly for morphisms transformation pa, —* pa. in £). Moreover such a: a —>a' in A gives a natural We thus get a diagram of type Aop in LEX(f,Set) whose limit is T: r= lim pi. oGAop License or copyright restrictions may apply to redistribution; see http://www.ams.org/journal-terms-of-use M. MAKKAI AND A. M. PITTS 492 In particular, for any F G LEX(C, £), the global sections of F is expressible as a limit (in LEX(C, Set)) of stalks of F. A particular case, proved by Ellerman [E], is when £ is sheaves on a partially ordered set P topologized by the order topology: for then £ ~ Set . G 3.1 For general Grothendieck toposes £, the operation of taking limits may not suffice to regain TF from {Fp | p G Pt(£)} in LEX(C, Set). Of course the latter collection of models might be rather small if £ has few points. (Recall that it is perfectly possible for £ to be nontrivial but have no points at all; cf. Chapter 7 of [TT].) So we will only consider toposes with enough points, i.e., such that if f:X —► Y in £ and p*(f) is a bijection for each p G Pt(£), then / is an isomorphism. Now, as well as taking limits, we emphasized in §1 that the other natural oper- ation in LEX(C, Set) is that of taking filtered colimits. 3.2 NOTATION. If K is a collection of objects in a locally finitely presentable category A, let [K\ ^-> A denote the least full subcategory of A containing K that is closed under taking limits and filtered colimits in A. (We will always assume that full subcategories are replete, i.e., if an object is isomorphic to something in the full subcategory, it too is in the subcategory.) Note that by Corollary 2.4, \K\ is also locally finitely presentable and \K\ •—»A is a morphism in LFP. 3.3 THEOREM. Suppose that C is a small category with finite limits, that £ is a Grothendieck topos with enough points and that F G LEX(C, £). Then for any LeLEX(<f,Set) L o F G [{Fp I p G Pt(<f)}] «->LEX(C, Set). In particular, taking L = Y we get that the global sections of F, as a model of C in Set, is in the closure of the stalks of F under limits and filtered colimits. PROOF. Let K = {Fp \ p G Pt(<?)}. Then as remarked above, by Corollary 2.4 [<} -+ LEX(C,Set) is in LFP, and hence by Theorem 1.2 there is 7: C -> D in Lex and an equivalence [K] — LEX(D,Set) making [K] - LEX(D,Set) \ = /r LEX(C,Set) commute up to isomorphism. (Thus D ~ [K]°p .) Hence a functor is in [K] just in case it is isomorphic to one in the image of 7*. Since £ has enough points, we can find a sufficient set of points, i.e., a set P of points such that the associated geometric morphism tt: Setp -> £ (whose inverse image part has component at p G P equal to (n*)p = p*) is a surjection. The existence of such a set P is really an application of the downward Löwenheim-Skolem theorem: cf. 7.16 and 7.17 of [TT]. Now if p G P, (ir*F)p = p*F = Fp G K Ç [K]: so by the remark above, there is Gp G LEX(D,Set) and an isomorphism I*(GP) ~ (7r*F)p. The functors Gp (p G P) fit together to give a finite-limit preserving functor License or copyright restrictions may apply to redistribution; see http://www.ams.org/journal-terms-of-use G: D —>Set , and by LOCALLY FINITELY PRESENTABLE 493 CATEGORIES construction D 5 Setp iÎ = W C £ £ commutes up to isomorphism in LEX. TOP commuting up to isomorphism: SetDop *1 Setc°P We therefore get a corresponding «L square in Setp — I *■ ¿ £ Here i is the geometric morphism induced by 7 (as in 2.6(i)), / corresponds to F under the equivalence LEX(C, £ ) ~ TOP(£\ Setc°P), and similarly for t; and G. Since 7* is full and faithful, by Proposition 2.6 i is an inclusion. struction n is a surjection; hence the square in TOP factors as Setc°" Correspondingly 4- we thus get a factorization But by con- -£ in LEX: Setp So for any L G LEX(¿\ Set), L o F = I*(LH), and so LF G [XT]as required. D 3.3 By geometric logic we mean the intuitionistic logic of =, A, V, 3 and infinitary disjunction \f (of formulae involving only finitely many free variables); cf. Chapter 2 of [MR]. Specifying a theory T in this logic amounts to giving a small site (C, J), i.e., a small category C G Lex equipped with a Grothendieck topology J. The category of models of T in Set, Mod(T), is then the full subcategory of LEX(C, Set) whose objects are the J-continuous functors; this category is equivalent to the category of points of the classifying topos of T, i.e., of the topos of sheaves on the site, Sh(C, J). See for example [MR] or Chapter 7 of [TT] for the details of this. From Theorem 3.3 we can obtain the following result about geometric theories. 3.4 COROLLARY. Suppose that T is a geometric theory which is specified by a small site (C, J), where C has finite limits and the Grothendieck License or copyright restrictions may apply to redistribution; see http://www.ams.org/journal-terms-of-use topology J is 494 M. MAKKAI AND A. M. PITTS subcanonical (i.e., representable presheaves are sheaves). in Set (i.e., Sh(C, J) has enough points), then [Mod(T)]=LEX(C,Set). PROOF. Since J is subcanonical If T has enough models ■ the Yoneda embeding 77: C <—> Setc factors through Sh(C, J) <->Setc°P and for any c G C C^—->■ Sh(C,J) vX Sh(C,J)/77c \, commutes up to isomorphism, ir Set where Yc is the representable functor C(c, —) and A is right adjoint to the forgetful functor E:Sh(C, J)/77c -> Sh(C, J). For rA77(-) = Sh(C,J)/77c(l,A77(-)) = Sh(C,J)(E(l),77(-)) = Sh(C, J)(Hc,H(-)) = C(c,-). Applying Theorem 3.3 with £ = Sh(C, J), F = 77 and L = T o A, we have Yc = VA o H G [Hp \ p GPt(£)}. But by definition of £, {77p| p G Pt(£)} = ob Mod(T). Thus Yc G [ModT]. Now any functor in LEX(C, Set) can be expressed (canonically) as a filtered colimit of such representable functors. Hence [ModT] is the whole of LEX(C, Set). D 3.4 3.5 REMARKS, (i) The proof of 3.4 gives no information about the number of times one has to alternate the operations of taking limits and filtered colimits to obtain a particular functor in LEX(C, Set). We do not know to what extent the maximum number of such alternations is an interesting measure of the complexity of T as a geometric extension of the finite limit theory C. (ii) Theorem 3.3 and Corollary 3.4 are best viewed in the context of a general "sheaf representation GIVEN problem" for geometric theories over finite limit theories, a finite limit theory, i.e., C G Lex; a geometric quotient viz: T of it, i.e., a Grothendieck topology J on C; and a model F G LEX(C, Set) of C in Set. FIND a Grothendieck topos £ and a sheaf M of T-models continuous functor in LEX(G, £)), whose global sections is F. over £ (i.e., a J- M. Coste [C] has shown that one can always find such a representation (£,M) for F provided J is subcanonical and generated by finite covering families (so that T is a coherent theory). Indeed in this case we can take (£,M) to be the spectrum of F, i.e., the value at F of the left adjoint to the functor (T-modelled toposes)op — LEX(C,Set) sending (f.MlHroAf. License or copyright restrictions may apply to redistribution; see http://www.ams.org/journal-terms-of-use LOCALLY FINITELY PRESENTABLE 495 CATEGORIES Returning to the general case, let us remark that recent (unpublished) work of A. Joyal shows that if a representation (£,M) exists for F, then we can always take £ to be localic over Set, i.e., a topos of sheaves on a complete Heyting algebra. For Joyal has shown that for any Grothendieck topos £ there exists a connected, locally connected geometric surjection q:Sh(A)-^£ with A a complete Heyting algebra (i.e., a locale). This means in particular that q* has a left adjoint q¡:Sh(A) —>£ satisfying q\(l) = 1. Hence £ £ r\ Sh(A) = /r Set commutes up to isomorphism since Tq*(-) = Sh(A)(l, </*(-)) SS£(q,(l), -) = T(-). Thus if (£,M) is a representation for F, so is (Sh(A), q*M). REFERENCES [B] J. Benabou, Introduction to bicategories, Lecture Notes in Math., Berlin and New York, 1967, pp. 1-77. [CK] C. C. Chang and H. J. Keisler, Model theory, North-Holland, [C] [E] vol. 47, Springer-Verlag, Amsterdam, 1973. M. Coste, Localisation dans les catégories de modeles, Thesis, Univ. Paris Nord, 1977. D. P. Ellerman, Sheaves of structures and generalized ultra products, Ann. Math. Logic 7 (1974), 163-195. [GU] P. Gabriel and F. Ulmer, Lokal präsentierbare Kategorien, Lecture Notes in Math., vol. 221, Springer-Verlag, Berlin and New York, 1971. [GZ] P. Gabriel and M. Zisman, Mathematik, Calculus of fractions and homology theory, Ergebnisse der Band 35, Springer-Verlag, Berlin and New York, 1967. [TT] P. T. Johnstone, Topos theory, Academic Press, London, 1977. [FT I] _, Factorization theorems for geometric morphisms. I, Cahiers Topologie et Géom. Différentielle 22 (1981), 3-17. [KR] A. Kock and G. E. Reyes, Doctrines (J. Barwise, ed.), North-Holland, [CWM] [M] S. Mac Lane, Categories in categorical Amsterdam, for logic, Handbook the working mathematician, vol. 5, Springer-Verlag, Berlin and New York, 1971. M. Makkai, on papers Remarks of Mathematical Logic 1977, pp. 283-313. by Y. Diers and II. Graduate Volger Texts on sheaf in Math., representation, Abstracts Amer. Math. Soc. 5 (1984), #84T-18-76. [MI] _, Ultraproducts and categorical logic, Methods in Categorical Logic (Ed., C. A. Di Prisco), Lecture Notes in Math., vol. 1130, Springer-Verlag, Berlin and New York, 1985, pp. 222-309. [MR] M. Makkai and G. E. Reyes, First order categorical logic, Lecture Notes in Math., vol. 611, Springer-Verlag, Berlin and New York, 1977. [V] H. Volger, Preservation theorems for limits of structures and global sections of sheaves of structures, Math. Z. 166 (1979), 27-53. [Mu] F. Mouen, Sur la caractérisation sémantique des catégories de structures, Diagrammes 2 (1984). [AN1] A. Andréka and I. Németi, A general axiomatizability theorem formulated in terms of cone-injective subcategories, Colloq. Math. Soc. J. Bolyai, Esztergom, 1977, pp. 17-35. [AN2] _, Injectivity in categories to represent all first order formulas. I, Demonstrate Math. 12 (1979), 717-732. License or copyright restrictions may apply to redistribution; see http://www.ams.org/journal-terms-of-use 496 [GL] M. MAKKAI AND A. M. PITTS R. Guitart and C. Lair, Calcul syntaxique des modèles et calcul des formules internes, Diagrammes 4 (1980), GL1-GL-106. [NS] I. Németi and I. Sain, Cone implicational subcategories and some Birkhoff type theorems, Colloq. Math. Soc. J. Bolyai, Esztergom, 1977. [SGA4] Théorie des topos et cohomologie étale des schémas, Eds., M. Artin, A. Grothendieck and J. L. Verdier, Lecture Notes in Math., vol. 269, Springer-Verlag, Berlin and New York, 1972. Department of Mathematics and Statistics, McGill University, Montreal, CANADA H3A 2K6 (Current address of M. Makkai) DEPARTMENT SION, University OF MATHEMATICAL of Sussex, United AND PHYSICAL Kingdon SCIENCES, MATHEMATICS DIVI- BNi 9QH (Current address of A. M. Pitts) License or copyright restrictions may apply to redistribution; see http://www.ams.org/journal-terms-of-use