Theory and Applications of Categories, Vol. 26, No. 21, 2012, pp. 538–553.

YONEDA REPRESENTATIONS OF FLAT FUNCTORS AND CLASSIFYING TOPOSES

OLIVIA CARAMELLO

Abstract. We obtain semantic characterizations, holding for any Grothendieck site (C, J), for the models of a theory classified by a topos of the form Sh(C, J) in terms of the models of a theory classified by a topos [C^{op}, Set]. These characterizations arise from an appropriate representation of flat functors into Grothendieck toposes based on an application of the Yoneda Lemma in conjunction with ideas from indexed category theory, and turn out to be relevant also in different contexts, in particular for addressing questions in classical Model Theory.

1. Introduction

In [2] a bijection is established between the subtoposes of the classifying topos of a geometric theory 𝕋 and the quotients of 𝕋 (i.e., geometric extensions of 𝕋 over its signature), considered up to the obvious notion of syntactic equivalence (i.e. the equivalence which identifies two quotients of 𝕋 precisely when they prove the same geometric sequents over the signature of 𝕋); the subtopos corresponding via this duality to a given quotient of 𝕋 can be identified with its classifying topos (cf. Theorem 3.6 [2]).

In light of the methodologies introduced in [3], the fact that the notion of subtopos is a topos-theoretic invariant admitting a ‘natural behaviour’ with respect to sites acquires fundamental importance for using the duality to investigate different aspects of quotients of geometric theories. Indeed, in most situations, a given representation for the classifying topos of some theory naturally gives rise to a related representation for the classifying topos of any quotient of the theory, and hence paves the way for effectively using the classifying topos of the quotient as a ‘bridge’ to relate the syntactic properties of the theory to properties of the alternative representations of its classifying topos. In fact, these techniques are extensively exploited in [2] to transfer results from elementary topos theory to geometric logic.

YONEDA REPRESENTATIONS OF FLAT FUNCTORS AND CLASSIFYING TOPOSES 539

Working in the same spirit, in this paper we exploit the natural behaviour of the notion of subtopos with respect to sites (recall that the subtoposes of a topos of the form Sh(C, J) are in natural bijection with the Grothendieck topologies J′ on C which contain J) to achieve an entirely semantic characterization of the models (in any Grothendieck topos) of a quotient 𝕋′ of a theory 𝕋 classified by a presheaf topos [C^{op}, Set] in terms of the models of 𝕋 and of the Grothendieck topology J on C defined by saying that the subtopos Sh(C, J) ↪ [C^{op}, Set] corresponds to 𝕋′ via the duality of Theorem 3.6 [2]. In fact, we introduce the notion of J-homogeneous 𝕋-model (in a given Grothendieck topos) and show that, up to equivalence, the models of 𝕋′ (in any Grothendieck topos) can be characterized among the models of 𝕋 as precisely the J-homogeneous ones. If C satisfies the right Ore condition and J is the atomic topology on it then the notion of J-homogeneous model specializes essentially to the notion of homogeneous model in Model Theory. In fact, this connection with classical Model Theory has already produced a number of useful insights; specifically, it has been exploited in [1] to derive a topostheoretic interpretation of Fraïssé’s construction leading to new results on homogeneous models and countably categorical theories.

Received by the editors 2012-03-18 and, in revised form, 2012-09-10.

Transmitted by Ieke Moerdijk. Published on 2012-10-11.

2010 Mathematics Subject Classification: 03G30, 18C10, 18B25.

Key words and phrases: Classifying topos, Yoneda lemma, flat functor, theory of presheaf type.

© Olivia Caramello, 2012. Permission to copy for private use granted.

Notation and terminology: The notation used in this paper is standard and borrowed from [5], if not otherwise specified.

2. Yoneda representations of flat functors

In this section, we introduce a technique, based on ideas from indexed category theory, for representing flat functors into arbitrary Grothendieck toposes; this technique will be applied in the following sections of the paper to obtain insights in the theory of classifying toposes.

2.1. Preliminary facts. We start by introducing the terminology and recalling the facts from the theory of indexed categories that will be useful for our analysis. We refer the reader to [5] (especially sections B1.2, B2.3 and B3.1) and to [8] for the background. As an introduction to Topos Theory, we recommend [7].

We will generally denote indexed categories by underlined letters, to distinguish them from their underlying categories which will be denoted by the corresponding simple letters; so for example the underlying category of an indexed category 𝔻 will be denoted by D. The indexed category corresponding to a cartesian category S will be denoted by \underline{𝕊}. Internal categories will be denoted by letters ℂ, 𝔻, etc., and the corresponding indexed categories will be denoted by \underline{ℂ}, \underline{𝔻}, etc.

By a topos (defined) over Set we mean an elementary topos E such that there exists a (necessarily unique up to isomorphism) geometric morphism γ_{E}: E → Set; we denote by γ_{E}^{∗} the inverse image functor and by Γ_{E} its right adjoint, that is the “global sections” functor. A topos is defined over Set if and only if it is locally small and has arbitrary set-indexed copowers of 1; in particular every locally small cocomplete topos (and hence every Grothendieck topos) is defined over Set.

Given a small category C and a topos E defined over Set, we can always internalize C into E by means of γ_{E}^{∗}; the resulting internal category in E will be denoted by ℂ.

Every topos E (over Set) gives rise to a E-indexed category \underline{𝔼} obtained by indexing E over itself; the inverse image functor γ_{E}^{∗} then induces an indexing of E over Set, which coincides with the canonical indexing of E provided that E is cocomplete and locally small.

For a topos E and an internal category ℂ in E, we have a E-indexed category \underline{[ℂ, E]}, whose underlying category is the category [ℂ, E] of diagrams of shape ℂ in 𝔼 and morphisms between them. [ℂ, E] is equivalent (naturally in E) to the category of E-indexed functors \underline{ℂ} → \underline{𝔼} and indexed natural transformations between them (by Lemma B2.3.13 [5]).

The E-indexed category \underline{[ℂ, E]} is locally small (by Lemma B2.3.15 [5]); from this it follows that there exists a E-indexed hom functor

HomE ; \underline{[ℂ,E]} : \underline{[ℂ, E]}^{op} × \underline{[ℂ, E]} → \underline{𝔼}

whose underlying functor

Hom_{[ℂ,E]}^{E}: [ℂ, E]^{op} × [ℂ, E] → E

assigns to a pair of diagrams F and G in [ℂ, E] an object Hom_{[ℂ,E]}^{E}(F, G) of E, which we call the object of morphisms from F to G in \underline{[ℂ, E]}; also, there is a Yoneda E-indexed functor 𝕐: \underline{ℂ} → \underline{[ℂ^{op}, E]}, which plays in this context the same role as that of a Yoneda functor in ordinary category theory (cf. [8]).

If C is a small category and ℂ is its internalization in a cocomplete and locally small topos E (by means of the functor γ_{E}^{∗}) then the category [ℂ, E] is equivalent to the category [C, E] (by Corollary B2.3.14 [5]). For this reason, we will restrict our attention to locally small cocomplete toposes; we will occasionally loosely refer to them simply as toposes. The equivalence between [ℂ, E] and [C, E] restricts to an equivalence between the full subcategories Tors(ℂ^{op}, E) of ℂ^{op}-torsors in E (as in section B3.2 of [5]) and Flat(C, E) of flat functors C → E (as in chapter VII of [7]). Given a functor F ∈ [C, E], the internal diagram that corresponds to it via the natural equivalence [C, E] ≃ [ℂ, E] will be called the internalization of F and denoted by F^{i}; of course, this is defined only up to isomorphism.

We denote by E^{∗}: E → E/E the pullback functor along the unique arrow E → 1, that is the (logical) inverse image functor of the local homeomorphism E/E → E. Then, since [C, E] ≃ [ℂ, E], we have a hom functor Hom_{[C,E]}^{E}: [C, E]^{op} × [C, E] → E, which assigns to each pair of functors F and G in [C, E] an object HomE ; \underline{[ℂ,E]}(F, G) of E such that for each E ∈ E the morphisms E → HomE ; \underline{[ℂ,E]}(F, G) in E are in natural bijection with the morphisms in [C, E/E] from E^{∗} ∘ F to E^{∗} ∘ G, that is with the natural transformations E^{∗} ∘ F ⇒E^{∗} ∘ G. We remark that, since Flat(C, E) is a full subcategory of [C, E], we may use the objects HomE ; \underline{[ℂ,E]}(F, G) for F, G ∈ Flat(C, E) as the objects of morphisms from F to G, so to obtain a locally small E-indexed category \underline{Flat(C, E)}.

Given an S-indexed category \underline{𝔻} and an object I ∈ S, we have an S/I-indexed category \underline{𝔻}/I (defined in the obvious way), which is called the localization of \underline{𝔻} at I. If \underline{𝔻} and \underline{𝔼} are two S-indexed categories, we denote by [\underline{𝔻}, \underline{𝔼}] the category of S-indexed functors from \underline{𝔻} to \underline{𝔼} and indexed natural transformations between them. The assignment I → [\underline{𝔻}/I, \underline{𝔼}/I] is pseudofunctorial in I ∈ S and makes [\underline{𝔻}, \underline{𝔼}] into an S-indexed category.

2.2. Yoneda representations. It is well known that, by Yoneda, for each F ∈ [C^{op}, Set] there is a natural isomorphism of functors

F ≅ Hom_{[C^{op},Set]}^{Set}(Y (−), F),

where Hom_{[C^{op},Set]}^{Set}(Y (−), F) is the functor given by the composite

\xymatrix{C^{op} \ar[r]^{Y^{op}×ΔF} & [C^{op}, Set]^{op} × [C^{op}, Set] \ar[r]^{^{HomSet ; [C^{op},Set]}} & Set .}

Thanks to the remarks in the last section we are able to generalize this result to the case of functors with values in an arbitrary topos. In fact, the following result holds.

2.3. Theorem. Let C be a small category and E be a locally small cocomplete topos. Then for every functor F: C^{op} → E, there is a natural isomorphism of functors

F ≅ Hom_{[C^{op},E]}^{E}(\overline{Y} (−), F),

where \overline{Y} : C → [C^{op}, E] is the functor given by the composite

\xymatrix{C \ar[r]^{Y} & [C^{op}, Set] \ar[r]^{γ_{E}^{∗}∘−} & [C^{op}, E]}

and Hom_{[C^{op},E]}^{E}(\overline{Y} (−), F) is the functor given by the composite

\xymatrix{C^{op} \ar[r]^{\overline{Y}^{op}×ΔF} & [C^{op}, E]^{op} × [C^{op}, E] \ar[r]^{^{Hom{E \atop [C^{op},E]}}} & E .}

Moreover, the isomorphism above is natural in F.

Proof. One can observe that the internal ℂ^{op}-diagram in 𝔼 given by the composite

\xymatrix{ℂ^{op} \ar[r]^{Y^{op}×ΔF^{i}} & [ℂ^{op}, E]^{op} × [ℂ^{op}, E] \ar[r]^{^{Hom{E \atop [ℂ^{op},E]}}} & E}

is on one hand equal to F^{i} (by an internal version of Yoneda Lemma) and on the other hand equal to the internalization of the functor

Hom_{[C^{op},E]}^{E}(\overline{Y} (−), F) .

The verifications are easy and left to the reader.

One may also proceed as follows. We want to prove that F (c) ≅ Hom_{[C^{op},E]}^{E}(\overline{Y} (c), F), naturally in c ∈ C (and in F). It suffices to observe that we have the following sequence of natural bijections:

E ⟶ Hom_{[C^{op},E]}^{E}(\overline{Y} (c), F)
E^{∗} ∘ \overline{Y} (c) ⟹ E^{∗} ∘ F
γ_{E/E}^{∗} ∘ Y (c) ⟹ E^{∗} ∘ F
Y (c) ⟹ Γ_{E/E} ∘ E^{∗} ∘ F
element of (Γ_{E/E} ∘ E^{∗} ∘ F)(c)
E ⟶ F (c) .

In the case of flat functors, the theorem specializes to the following result.

2.4. Corollary. Let C be a small category and E be a locally small cocomplete topos. Then for every flat functor F: C^{op} → E, there is a natural isomorphism of functors

F ≅ Hom_{Flat(C^{op},E)}^{E}(\overline{Y} (−), F),

where \overline{Y} : C → Flat(C^{op}, E) is the functor given by the composite

\xymatrix{C \ar[r]^{Y} & Flat(C^{op}, Set) \ar[r]^{γ_{E}^{∗}∘−} & Flat(C^{op}, E)}

and Hom_{Flat(C,E)}^{E}(\overline{Y} (−), F) is the functor given by the composite

\xymatrix{C^{op} \ar[r]^{\overline{Y}^{op}×ΔF} & Flat(C^{op}, E)^{op} × Flat(C^{op}, E) \ar[r]^{^{Hom{E \atop Flat(C^{op},E)}}} & E .}

Proof. This immediately follows from the theorem and the remarks in section 2.1.

From now on we will refer to this result as to the Yoneda representation of flat functors.

2.5. Representation problems. In this section we introduce the notion of representation problem in the general context of locally small indexed categories. This concept will lead to a universal characterization of the Yoneda embeddings, which will be employed in the next section to derive a criterion for a theory to be of presheaf type.

2.6. Definition. Let S be a cartesian category and \underline{𝔻} be a locally small S-indexed category. We say that a S-indexed functor F: \underline{𝔻}^{op} → \underline{𝕊} is S-representable if there exists an object A ∈ D such that F is isomorphic in [\underline{𝔻}^{op}, \underline{𝕊}] to the composite

\xymatrix{\underline{𝔻}^{op} \ar[r]^{1\underline{𝔻}×ΔA} & \underline{𝔻}^{op} × \underline{𝔻} \ar[r]^{^{Hom𝕊 ; \underline{𝔻}}} & \underline{𝕊}}

We denote this composite by Hom𝕊 ; \underline{𝔻}(−, A).

If D is the underlying category of a locally small S-indexed category \underline{𝔻} then we say that a functor F : D^{op} → S is S-representable if it is the underlying functor of an indexed functor of the form Hom𝕊 ; \underline{𝔻}(−, A).

2.7. Definition. Let S be a cartesian category, \underline{𝔻} a locally small S-indexed category and \underline{𝕂} a S-indexed full subcategory of \underline{[\underline{𝔻}^{op}, \underline{𝕊}]}. A locally small S-indexed category \underline{𝔽} together with S-indexed functors i: \underline{𝔻} → \underline{𝔽} and r: \underline{𝕂} → \underline{𝔽} is said to be a solution to the 1-representation problem for \underline{𝕂} if

Hom𝕊 ; \underline{𝔽}(−, r(F)) ∘ i^{op} ≅ F

canonically in F ∈ K:

\xymatrix{\underline{𝔻}^{op} \ar[d]_{i^{op}} \ar[r]^{F} & \underline{𝕊} \\ _{\underline{𝔽}_{op}} \ar@{-->}[ur]_{Hom𝕊 ; \underline{𝔽}(−,r(F))}}

The triple

(\underline{𝔽}, i: \underline{𝔻} → \underline{𝔽}, r: \underline{𝕂} → \underline{𝔽})

is said to be a solution to the representation problem for 𝕂 if for each I ∈ S the triple

(\underline{𝔽}/I, i/I: \underline{𝔻}/I → \underline{𝔽}/I, r/I: \underline{𝕂}/I → \underline{𝔽}/I)

is a solution to the 1-representation problem for the S/I-indexed category \underline{𝕂}/I.

A solution (\underline{𝔽}, i: \underline{𝔻} → \underline{𝔽}, r: \underline{𝕂} → \underline{𝔽}) to the representation problem for 𝕂 is said to be universal if for any other solution (\underline{𝔽′}, i′: \underline{𝔻} → \underline{𝔽′}, r′: \underline{𝕂} → \underline{𝔽′}) to the same problem there exists a unique (up to canonical isomorphism) S-indexed functor z: \underline{𝔽} → \underline{𝔽′} such that z ∘ r ≅ r′ and z ∘ i ≅ i′ canonically. Of course, if such a solution exists, it is unique up to canonical isomorphism by the universal property.

2.8. Proposition. Let S a cartesian category, \underline{𝔻} a locally small S-indexed category and \underline{𝕂} a S-indexed full subcategory of \underline{[\underline{𝔻}^{op}, \underline{𝕊}]}. If 𝕐: \underline{𝔻} → \underline{[\underline{𝔻}^{op}, \underline{𝕊}]} factors as 𝕐′: \underline{𝔻} → \underline{𝕂} through the full embedding \underline{𝕂} ↪ \underline{[\underline{𝔻}^{op}, \underline{𝕊}]}, then the triple

(\underline{𝕂}, 𝕐′: \underline{𝔻} → \underline{𝕂}, 1_{𝕂}: \underline{𝕂} → \underline{𝕂})

is the universal solution to the representation problem for the S-indexed category \underline{𝕂}.

Proof. This follows as an immediate consequence of the indexed version of the Yoneda lemma ([8], 1.5.1).

So, if ℂ is an internal category in S, the embedding 𝕐: ℂ → [ℂ^{op}, 𝕊] can be characterized not only, as it is well known, as the free S-cocompletion of ℂ, but also as the universal solution to the representation problem for the S-indexed category [ℂ^{op}, 𝕊].

2.9. Corollary. Let ℂ be an internal category in a topos E. Then the factorization 𝕐′: \underline{ℂ} → \underline{Tors(ℂ, E)} of the Yoneda indexed functor

𝕐: \underline{ℂ} → \underline{[ℂ^{op}, E]}

through the full embedding

\underline{Tors(ℂ, E)} ↪ [ℂ^{op}, E]

is the universal solution to the representation problem for the E-indexed category \underline{Tors(ℂ, E)}.

2.10. Theories of presheaf type.

2.11. Definition. A geometric theory 𝕋 is said to be of presheaf type if it is classified by a presheaf topos.

2.12. Remark. The class of theories of presheaf type contains all the cartesian, and in particular all the finitary algebraic, theories, and also many other interesting mathematical theories (for example, the theory of linear orders, cf. [7] and [6] and the geometric theory of finite sets, cf. [6]).

A theory 𝕋 is of presheaf type if and only if it is classified by the topos [C, Set], where C := f.p.𝕋-mod(Set) is the category of (representatives of isomorphism classes of) finitely presentable 𝕋-models in Set i.e. (a skeleton of) the full subcategory of 𝕋-mod(Set) on the finitely presentable objects (recall that an object c of a finitely accessible category C is said to be finitely presentable if the representable functor Hom_{C}(c, −) : C → Set preserves filtered colimits). To prove this recall that, by Diaconescu’s theorem, we have an equivalence of categories 𝕋-mod(Set) ≃ Flat(C^{op}, Set) = Ind-C. Hence the category 𝕋-mod(Set) is finitely accessible and the Cauchy completion Č of the category C is recoverable (up to equivalence) from Ind-C as the full subcategory Č ≃ f.p.𝕋-mod(Set) of finitely presentable objects (cf. Proposition C4.2.2 [6]); but [C, Set] and [Č, Set] are naturally equivalent (cf. Corollary A1.1.9 [5]), from which our claim follows.

Let us now proceed to give a semantic characterization of the (geometric) theories of presheaf type based on the ideas in the last section.

We observe that, if 𝕋 is a geometric theory, we can regard it informally as a category \underline{𝕋-mod} indexed by the (meta)category of Grothendieck toposes via the pseudofunctor 𝕋-mod (which assigns to every topos E the category of 𝕋-models in E); in particular, for each Grothendieck topos E, by ‘restricting’ this pseudofunctor to the slices of E, we obtain a E-indexed category \underline{𝕋-mod_{E}}, which is locally small as a E-indexed category. Indeed, it is well known that 𝕋 is Morita-equivalent (that is, has the same category of models - up to natural equivalence - into every Grothendieck topos E naturally in E, equivalently has the same classifying topos) to the theory of flat functors on a category C which are continuous with respect to a Grothendieck topology J on C, and the categories of such functors are all full subcategories of the corresponding categories of functors on C (cf. the remarks in section 2.1).

By Diaconescu’s theorem, any theory (of presheaf type) 𝕋 classified by a topos [Č, Set] comes equipped with a Morita-equivalence ξ^{E} : Flat(Č^{op}, E) → 𝕋-mod(E) to the theory of flat functors on the category Č^{op}. Via this equivalence, the Yoneda embedding \overline{Y} : Č → Flat(Č^{op}, E) corresponds to the embedding of f.p.𝕋-mod(Set) into 𝕋-mod(E) given by the inverse image functor γ_{E}^{∗}. Notice that the image in 𝕋-mod(E) of this embedding can be thought as the subcategory of ‘constant 𝕋-models which are finitely presentable in Set’.

As we have remarked, for each Grothendieck topos E \underline{𝕋-mod_{E}} is locally small, so it does make sense to ask if γ_{E}^{∗}(−): f.p.𝕋-mod(Set) → 𝕋-mod(E) (regarded here as a Eindexed functor to \underline{𝕋-mod_{E}}) is the universal solution to the representation problem for the E-indexed category

\underline{Flat(f.p.𝕋-mod(Set)^{op}, E)} .

If this holds for every E naturally in E then we may conclude by Corollary 2.9 that 𝕋 is of presheaf type. More concretely, we have the following criterion for a theory to be of presheaf type.

2.13. Theorem. Let 𝕋 a geometric theory. Then 𝕋 is of presheaf type if and only if for each Grothendieck topos E, every flat functor

F: f.p.𝕋-mod(Set)^{op} → E

can be extended to a E-representable along

γ_{E}^{∗}(−)^{op} : f.p.𝕋-mod(Set)^{op} → 𝕋-mod(E)^{op}

and conversely every E-representable 𝕋-mod(E)^{op} → E arises up to isomorphism in this way, naturally in F and E.

Proof. This is immediate from the discussion above.

2.14. Quotients of theories of presheaf type. Let us suppose we have a geometric theory 𝕋 classified by a presheaf topos [C^{op}, Set] and wish to understand what the quotient of 𝕋 classified by a subtopos Sh(C, J) of [C^{op}, Set] via the duality of Theorem 3.6 [2] looks like, in terms of 𝕋, and without any reference to flat functors. The technique of the Yoneda representation for flat functors provides us with a means for solving this problem. Specifically, we will succeed in describing in terms of the 𝕋-models and of the Grothendieck topology J the 𝕋′-models in any Grothendieck topos E.

We denote by Č the Cauchy completion of the category C. Recall that Č can alternatively be characterized as the full subcategory of Ind-C consisting of the finitely presentable objects and also as the closure of C under retracts in Ind-C.

Now, we have already observed that the toposes [C^{op}, Set] and [Č^{op}, Set] are naturally equivalent. It follows (from the theory of elementary toposes) that there exists a unique Grothendieck topology J̌ on Č such that subtopos

Sh(Č, J̌) ↪ [Č^{op}, Set]

corresponds to the subtopos

Sh(C, J) ↪ [C^{op}, Set]

under the equivalence

[Č^{op}, Set] ≃ [C^{op}, Set] .

We describe it explicitly in the theorem below.

Let us adopt the following conventions: if S is a sieve in C, we denote by \overline{S} the sieve in Č generated by the members of S; if R is a sieve in Č, we denote by R ∩ arr(C) the sieve in C formed by the elements of R which are arrows in C. Moreover, given an arrow g: d → c in C and sieves S and R on c respectively in C and Č, we denote by g_{C}^{∗}(S) and g∗ ; Č(R) the sieves obtained by pulling back S and R along g respectively in the categories C and Č.

2.15. Theorem. Let C be a category and Č its Cauchy completion. Given a Grothendieck topology J on C, there exists a unique Grothendieck topology J̌ on Č that induces J on C, which is defined by: for each sieve R on d ∈ Č, R ∈ J̌(d) if and only if there exists a retract d ↪^{i} a →^{r} d with a ∈ C and a sieve S ∈ J(a) such that R = i^{∗}(\overline{S}). Furthermore, if d ∈ C then R ∈ J̌(d) if and only if there exists a sieve S in C on d such that R = \overline{S}.

Proof. Since the full embedding C ↪ Č is (trivially) dense with respect to every Grothendieck topology on Č, it follows from the Comparison Lemma (Theorem C2.2.3 [6]) and the remarks above that there is at most one Grothendieck topology on Č that induces J on C. Therefore, it will be enough to prove that the coverage J̌ in the statement of the theorem is a Grothendieck topology that induces J on C. This, as well as the second part of the thesis, can be easily proved by using the following easy fact (whose proof is left to the reader): given an object c ∈ C, the assignments R → R ∩arr(C) and S → \overline{S} are inverse to each other and define a bijection between the set of sieves in C on c and the set of sieves in Č on c. Moreover, these bijections are natural with respect to the operations of pullback of sieves along an arrow in C.

By way of example, we provide the details of the proof that J̌ satisfies the ‘stability axiom’ for Grothendieck topologies. Given R ∈ J̌(d) and g: e → d in Č, we want to prove that g^{∗}(R) ∈ J̌(e). Since R ∈ J̌(d), there exists a retract d ↪^{i} a →^{r} d with a ∈ C and a sieve S ∈ J(a) such that R = i^{∗}(\overline{S}). There exists a retract e ↪^{j} b →^{z} e with b ∈ C. Now, g^{∗}(R) = g^{∗}(i^{∗}(T)) = (i ∘ g)^{∗}(T) = ((i ∘ g ∘ z) ∘ j)^{∗}(T) = j^{∗}((i ∘ g ∘ z)^{∗}(T)) = j^{∗}((i ∘ g ∘ z)∗ ; Č(\overline{S})) = j^{∗}(\overline{(i ∘ g ∘ z)_{C}^{∗}(S)}). Our thesis then follows at once from the stability axiom for J.

2.16. Theorem. Let C be a category and J a Grothendieck topology on C.

If J is the trivial topology then J̌ is the trivial topology.

If J is the dense (respectively, the atomic) topology on C, then J̌ is the dense (respectively, the atomic) topology on Č.

Proof. All can be easily proved by using the ‘retract technique’ employed in the proof of the previous theorem. We omit the details.

Coming back to our original problem, we have seen that it is natural to replace the topos Sh(C, J) with Sh(Č, J̌). The advantage for us of this replacement is that the category Č, being Cauchy complete, can be recovered from Flat(Č^{op}, Set) as the full subcategory of finitely presentable objects. Hence, if 𝕋 is a theory classified by [Č, Set] then the Morita-equivalence ξ^{Set} : Flat(Č^{op}, Set) ≃ 𝕋-mod(Set) restricts to a natural equivalence τ^{ξ} : Č ≃ f.p.𝕋-mod(Set), as in the following diagram:

\xymatrix{Č \ar[d]_{\overline{Y}} & f.p.𝕋-mod(Set) \ar[l]^{∼}_{τ^{ξ}} \ar[d]^{i} \\ Flat(Č^{op}, Set) \ar[r]_{∼} & 𝕋-mod(Set)}

Now we want to rewrite the Yoneda representation

F ≅ Hom_{[Č^{op},E]}^{E}(\overline{Y} (−), F),

of a flat functor F : Č → E (given by Corollary 2.4) in terms of 𝕋, regarded here as a E-indexed category. We recall that \underline{𝕋-mod_{E}} is locally small, with

Hom_{𝕋-mod(E)}^{E}(M, N)

object of morphisms in \underline{𝕋-mod_{E}} from M to N in 𝕋-mod(E). The naturality in E of the Morita-equivalence between 𝕋 and the theory of flat functors on Č^{op} implies the commutativity of the following diagram:

\xymatrix{Flat(Č^{op}, Set) \ar[r]^{∼} \ar[d]_{γ_{E}^{∗}∘−} & 𝕋-mod(Set) \ar[d]^{γ_{E}^{∗}(−)} \\ Flat(Č^{op}, E) \ar[r]_{∼} & 𝕋-mod(E)}

¿From the commutativity of the two diagrams above we deduce the following representation for F ∘ τ:

F ∘ τ^{ξ} ≅ Hom_{𝕋-mod(E)}^{E}(γ_{E}^{∗}(i(−)), M_{F}),

where M_{F} is the 𝕋-model in E corresponding to F ∈ Flat(Č^{op}, E) via the Moritaequivalence.

We note that, given a Morita-equivalence ξ for a theory of presheaf type 𝕋 classified by the topos [f.p.𝕋-mod(Set), Set] (as in 2.10 above), we can modify ξ so that τ^{ξ}(c) ≅ c naturally in c ∈ f.p.𝕋-mod(Set). Indeed, composing with (τ^{ξ})^{−1} gives rise to an equivalence

((−) ∘ (τ^{ξ})^{−1})^{E} : Flat(f.p.𝕋-mod(Set)^{op}, E) → Flat(f.p.𝕋-mod(Set)^{op}, E)

natural in E ∈ 𝔅𝔱𝔬𝔭, and it easily follows from the Yoneda representation and the Yoneda Lemma that the composite equivalence ξ′ := ξ ∘ ((−) ∘ (τ^{ξ})^{−1}) is such that τ^{ξ′} ≅ 1_{f.p.𝕋-mod(Set)}. In fact, given a theory of presheaf type 𝕋, we will assume below that 𝕋 comes equipped with an equivalence ξ satisfying the condition τ^{ξ′} ≅ 1_{f.p.𝕋-mod(Set)}; we will call such an equivalence canonical, and, accordingly, we will say that an equivalence

χ^{E} : 𝕋-mod(E) ≃ Geom(E, [f.p.𝕋-mod(Set), Set])

natural in E ∈ 𝔅𝔱𝔬𝔭 is canonical if it is induced by a canonical equivalence

ξ^{E} : Flat(f.p.𝕋-mod(Set)^{op}, E) → 𝕋-mod(E)

by composition with Diaconescu’s equivalence.

This motivates the following definition.

2.17. Definition. Let E be a locally small cocomplete topos, 𝕋 a theory of presheaf type and J a Grothendieck cotopology on C := f.p.𝕋-mod(Set). A model M ∈ 𝕋-mod(E) is said to be J-homogeneous if for each cosieve S ∈ J(c) the family of all the arrows

\xymatrix{Hom_{𝕋-mod(E)}^{E}(γ_{E}^{∗}(cod(f)), M) \ar[r]^{Hom_{𝕋-mod(E)}^{E}(γ_{E}^{∗}(f),M)} & Hom_{𝕋-mod(E)}^{E}(γ_{E}^{∗}(c), M)}

for f ∈ S, is epimorphic in E.

2.18. Remark. It is clear (from the definition of atomic topology) that if J is the atomic cotopology on C then a model M ∈ 𝕋-mod(E) is J-homogeneous if and only if for each arrow f: c → d in C, the arrow

\xymatrix{Hom_{𝕋-mod(E)}^{E}(γ_{E}^{∗}(cod(f)), M) \ar[r]^{Hom_{𝕋-mod(E)}^{E}(γ_{E}^{∗}(f),M)} & Hom_{𝕋-mod(E)}^{E}(γ_{E}^{∗}(c), M)}

is an epimorphism in E. In this case we will simply say ‘homogeneous’ instead of ‘Jhomogeneous’.

We observe that if the Morita-equivalence ξ for 𝕋 is canonical then the model M_{F} is J-homogeneous if and only if F is J-continuous.

We thus obtain the following theorem.

2.19. Theorem. Let 𝕋 be a theory of presheaf type and J a Grothendieck topology on f.p.𝕋-mod(Set)^{op}. Then the topos Sh(f.p.𝕋-mod(Set)^{op}, J) classifies the J-homogeneous 𝕋-models; that is, for any quotient 𝕋′ of 𝕋, the 𝕋′-models are exactly the J-homogeneous 𝕋-models in any Grothendieck topos if and only if

• 𝕋′ is classified by the topos Sh(f.p.𝕋-mod(Set)^{op}, J) and

• the diagram in ℭ𝔞𝔱

\xymatrix{𝕋′-mod(E) \ar[r]^{≃} \ar[d]^{i_{𝕋′}^{E}} & Geom(E, Sh(f.p.𝕋-mod(Set)^{op}, J)) \ar[d]^{i∘−} \\ 𝕋-mod(E) \ar[r]^{≃}_{χ^{E}} & Geom(E, [f.p.𝕋-mod(Set), Set])}

commutes (up to invertible natural equivalence) naturally in E ∈ 𝔅𝔗𝔬𝔭, where χ is a canonical Morita-equivalence for the theory 𝕋,

i : Sh(f.p.𝕋-mod(Set)^{op}, J) ↪ [f.p.𝕋-mod(Set), Set]

is the canonical geometric inclusion and

i_{𝕋′}^{E} : 𝕋′-mod(E) ↪ 𝕋-mod(E)

are the obvious inclusions for the quotient 𝕋′.

Specializing the theorem to the case of the atomic topology gives the following result.

2.20. Corollary. Let (C, J) be an atomic site and 𝕋 a theory classified by the topos [C^{op}, Set]. Then the topos Sh(C, J) classifies the homogeneous 𝕋-models.

Proof. This follows immediately from the theorem in view of Theorem 2.16.

Now we want to rephrase in more explicit terms what it means for a model to be J-homogeneous; this will be particularly important for the applications. To this end, we first express the condition that a given family of arrows as in Definition 2.17 is epimorphic as a logical sentence in the internal language of the topos, then we use the Kripke-Joyal semantics to spell out what it means for that sentence to be valid in the topos.

Recall that if E is a cocomplete topos and (f_{i} : C_{i} → C | i ∈ I) is a family of arrows in it indexed by a set I, then this family is epimorphic if and only if the logical formula (∀y ∈ C)(∨_{i∈I}(∃x ∈ C_{i}(f_{i}x = y))) holds in E. Given a class of generators G for E, the validity in E of this sentence is in turn equivalent, by the Kripke-Joyal semantics, to the following statement: for each E ∈ G and y : E → C there exists an epimorphic family (r_{i} : E_{i} → E | i ∈ I) and generalized elements (x_{i} : E_{i} → C_{i} | i ∈ I) such that y ∘ r_{i} = f_{i} ∘ x_{i} for each i ∈ I. By applying this to the families of arrows in Definition 2.17 and by recalling that the objects Hom_{𝕋-mod(E)}^{E}(γ_{E}^{∗}(i(d)), M) are the objects of morphisms from γ_{E}^{∗}(i(d)) to M in \underline{𝕋-mod_{E}}, we obtain the following characterization.

2.21. Theorem. Let E be a locally small cocomplete topos with a class of generators G and 𝕋 be a theory of presheaf type. Given a Grothendieck cotopology J on C := f.p.𝕋-mod(Set), a model M ∈ 𝕋-mod(E) is J-homogeneous if and only if for each cosieve S ∈ J(c), object E ∈ G and arrow y : E^{∗}(γ_{E}^{∗}(i(c))) → E^{∗}(M) in 𝕋-mod(E/E) there exists an epimorphic family (p_{f} : E_{f} → E, f ∈ S) and for each arrow f : c → d in S an arrow u_{f} : E_{f}^{∗}(γ_{E}^{∗}(i(d))) → E_{f}^{∗}(M) in 𝕋-mod(E/E) such that p_{f}^{∗}(y) = u_{f} ∘ E_{f}^{∗}(γ_{E}^{∗}(i(f))).

Notice that if E is the topos Set then by taking as class of generators of Set the class having as its unique element the singleton 1_{Set} we obtain the following result.

2.22. Corollary. Let 𝕋 be a theory of presheaf type. Given a Grothendieck cotopology J on C := f.p.𝕋-mod(Set), a model M ∈ 𝕋-mod(Set) is J-homogeneous if and only if for each cosieve S ∈ J(c) and arrow y : i(c) → M in 𝕋-mod(Set) there exists an arrow f : c → d in S and an arrow u_{f} : i(d) → M in 𝕋-mod(Set) such that y = u_{f} ∘ i(f).

By specializing the theorem and the corollary to the case of the atomic topology one immediately obtains the following results.

2.23. Corollary. Let E be a locally small cocomplete topos with a class of generators G and 𝕋 be a theory of presheaf type. If C := f.p.𝕋-mod(Set)^{op} satisfies the right Ore condition then a model M ∈ 𝕋-mod(E) is homogeneous if and only if for each arrow f : c → d in C^{op}, object E ∈ G and arrow y : E^{∗}(γ_{E}^{∗}(i(c))) → E^{∗}(M) in 𝕋-mod(E/ E), there exists an object E_{f} ∈ E, an epimorphism p_{f} : E_{f} ↠ E and an arrow u_{f} : E_{f}^{∗}(γ_{E}^{∗}(i(d))) → E_{f}^{∗}(M) in 𝕋-mod(E/E) such that p_{f}^{∗}(y) = u_{f} ∘ E_{f}^{∗}(γ_{E}^{∗}(i(f))).

2.24. Corollary. Let 𝕋 be a theory of presheaf type. If f.p.𝕋-mod(Set)^{op} satisfies the right Ore condition then a model M ∈ 𝕋-mod(Set) is homogeneous if and only if for each arrow f : c → d in f.p.𝕋-mod(Set) and arrow y : i(c) → M in 𝕋-mod(Set) there exists an arrow u_{f} : i(d) → M in 𝕋-mod(Set) such that y = u_{f} ∘ i(f):

\xymatrix{i(c) \ar[d]_{i(f)} \ar[r]^{y} & M \\ i(d) \ar@{-->}[ur]_{u_{f}}}

¿From this corollary it is clear that our notion of homogeneous model essentially specializes to that of (weakly) homogeneous model arising in the context of classical Model Theory (cf. [4]); in fact, this link has already been exploited in [1] to obtain a topos-theoretic interpretation of Fraïssé’s construction leading to a variety of new results on homogeneous models and countably categorical theories.

2.25. Remark. We observe that, under the hypotheses of Definition 2.17, for each topos E and object E ∈ E there is an isomorphism

E^{∗}(Hom_{𝕋-mod(E)}^{E}(γ_{E}^{∗}(i(c)), M)) ≅ Hom_{𝕋-mod(E/E)}^{E/E}(γ_{E/E}^{∗}(i(c)), E^{∗}(M))

natural in c ∈ C. Hence, if M ∈ 𝕋-mod(E) is J-homogeneous then E^{∗}(M) ∈ 𝕋-mod(E/E) is also J-homogeneous. This implies that, while dealing with theories 𝕋′ that one wants to prove to satisfy the conditions of Theorem 2.21, one can restrict to argue with generalized elements defined on 1, by the localizing principle. This is illustrated in the following example.

2.26. An example. As an application of Corollaries 2.20 and 2.23, we recover the wellknown representation of the classifying topos for the theory of dense linearly ordered objects without endpoints as the atomic topos Sh(Ord_{fm}^{op}, J), where Ord_{fm} is the category of finite ordinals and order-preserving injections between them and J is the atomic cotopology on it (cf. Example D3.4.11 [5]).

The theory 𝕃′ of dense linearly ordered objects without endpoints is defined over a onesorted signature having one relation symbol < apart from equality, and has the following axioms:

(((x < y) ∧ (y < x)) ⊢_{x,y} ⊥),
(⊤ ⊢_{x,y} ((x = y) ∨ (x < y) ∨ (y < x))),
((x < y) ∧ (y < z) ⊢_{x,y,z} (x < z)),
(⊤ ⊢_{[ ]} (∃x)⊤),
((x < y) ⊢_{x,y} (∃z)((x < z) ∧ (z < y))) and
(x ⊢_{x} (∃y, z)((y < x) ∧ (x < z))) .

The first three axioms give the theory 𝕃 of (decidably) linearly ordered objects. It is well-known that this theory is of presheaf type, and it is easy to see that Ord_{fm} can be identified with the category of finitely presentable 𝕃-models in Set; the classifying topos of 𝕃 is thus equivalent to the functor category [Ord_{fm}, Set]. Notice also that the category Ord_{fm}^{op} satisfies the right Ore condition, and hence we can equip it with the atomic topology J.

A model M ∈ 𝕃-mod(E) is given by a pair (I, R) where I is an object of E and R is a relation on I satisfying the diagrammatic forms of the first two axioms above. We will prove that for each topos E, a model M = (I, R) ∈ 𝕃-mod(E) is homogeneous if and only if it is a model of 𝕃′, that is if (I, R) is non-empty, dense and without endpoints; this will imply (by the corollaries) our thesis.

In one direction, let us prove that if M is homogeneous then (I, R) is dense. For each object E ∈ E, we denote by <_{E} is the order induced by R on Hom_{E}(E, I). By the localizing principle (cf. Remark 2.25), it is enough to prove that if x, y : 1 → I are two generalized elements of I with x <_{1} y then there exists an object E ∈ E, an epimorphism p : E ↠ 1 and an arrow z : E → I such that x ∘ p <_{E} z <_{E} y ∘ p. Consider the arrow f : 2 → 3 in Ord_{fm} defined by f(0) = 0 and f(1) = 2; the arrows x and y induce, via the assignment (0 → x, 1 → y) and the universal property of the coproduct γ_{E}^{∗}(2), an arrow ψ : γ_{E}^{∗}(2) → I in 𝕃-mod(E). From the homogeneity of M we obtain the existence of an object E ∈ E, an epimorphism p : E ↠ 1 and an arrow χ : E^{∗}(γ_{E}^{∗}(3)) → E^{∗}(I) in 𝕃-mod(E/E) such that χ ∘ E^{∗}(γ_{E}^{∗}(f)) = E^{∗}(ψ). Then the composite arrow

E ≅ E^{∗}(γ_{E}^{∗}(1)) ⟶^{E^{∗}(γ_{E}^{∗}(u))} E^{∗}(γ_{E}^{∗}(3)) →^{χ} E^{∗}(I) →^{π_{I}} I,

where u : 1 → 3 is the arrow in Ord_{fm} which picks out the element 1 ∈ 3, gives an arrow z : E → I with the required properties. The verifications that (I, R) is non-empty and without endpoints are similar and left to the reader.

Conversely, we prove that if M ∈ 𝕃′-mod(E) then M is homogeneous. Again, by the localizing principle, this amounts to proving that given an arrow f : n → m in Ord_{fm} and an arrow ψ : γ_{E}^{∗}(n) → I in 𝕃-mod(E), there exists an object E ∈ E, an epimorphism p : E ↠ 1 and an arrow χ : E^{∗}(γ_{E}^{∗}(m)) → E^{∗}(I) in 𝕃-mod(E/E) such that χ ∘ E^{∗}(γ_{E}^{∗}(f)) = E^{∗}(ψ). The arrow ψ can be identified, via the universal property of the coproduct γ_{E}^{∗}(n), with a family (h_{i} : 1 → I | i ∈ n) of generalized elements of I. To find the required arrow χ, we inductively use the fourth or the fifth axioms to obtain, starting from the h_{i}, an object E ∈ E, an epimorphism p : E ↠ 1 and m generalized elements (z_{j} : E → I | j ∈ m) such that for each i ∈ n z_{f(i)} = h_{i} ∘ p and for each j, j′ ∈ m ((j < j′) ⇒ (z_{j} <_{E} z_{j′})). The family (z_{j} : E → I | j ∈ m) then gives rise to an arrow χ : E^{∗}(γ_{E}^{∗}(m)) → E^{∗}(I) in 𝕃-mod(E/E) with the required property.

Acknowledgements: I am grateful to the anonymous referee for his useful suggestions, which have helped improve the readability of this paper.

References

[1] Caramello, O., ‘Fraïssé’s construction from a topos-theoretic perspective’, arXiv:math.CT/0805.2778v3.

[2] Caramello, O., ‘Lattices of theories’, arXiv:math.CT/0905.0299.

[3] Caramello, O., ‘The unification of Mathematics via Topos Theory’, arXiv:math.CT/1006.3930v1.

[4] Hodges, W., Model theory, Encyclopedia of Mathematics and its Applications vol.42 (Cambridge University Press, 1993).

[5] Johnstone, P. T., Sketches of an Elephant: a topos theory compendium. Vol.1, vol. 43 of Oxford Logic Guides (Oxford University Press, 2002).

[6] Johnstone, P. T., Sketches of an Elephant: a topos theory compendium. Vol.2, vol. 44 of Oxford Logic Guides (Oxford University Press, 2002).

[7] Mac Lane, S and I. Moerdijk, Sheaves in geometry and logic: a first introduction to topos theory (Springer-Verlag, 1992).

[8] Paré, R., and D. Schumacher, ‘Abstract families and the Adjoint Functor Theorems’, in Indexed categories and their applications, Lecture Notes in Math. vol. 661 (Springer-Verlag, 1978), 1-125.

DPMMS, University of Cambridge, Wilberforce Road, Cambridge CB3 0WB, UK

Email: O.Caramello@dpmms.cam.ac.uk

This article may be accessed at http://www.tac.mta.ca/tac/ or by anonymous ftp at

ftp://ftp.tac.mta.ca/pub/tac/html/volumes/26/21/26-21.{dvi,ps,pdf}

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. Full text of the journal is freely available in .dvi, Postscript and PDF from the journal’s server at http://www.tac.mta.ca/tac/ and by ftp. It is archived electronically and in printed paper format.

Subscription information Individual subscribers receive abstracts of articles by e-mail as they are published. 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}TEX2e strongly encouraged. Articles should be submitted by e-mail directly to a Transmitting Editor. Please obtain detailed information on submission format and style files at http://www.tac.mta.ca/tac/.

Managing editor Robert Rosebrugh, Mount Allison University: rrosebrugh@mta.ca

TEXnical editor Michael Barr, McGill University: barr@math.mcgill.ca

Assistant TEX editor Gavin Seal, Ecole Polytechnique Fédérale de Lausanne:

gavin seal@fastmail.fm

Transmitting editors

Clemens Berger, Université de Nice-Sophia Antipolis, cberger@math.unice.fr Richard Blute, Université d’ Ottawa: rblute@uottawa.ca Lawrence Breen, Université de Paris 13: breen@math.univ-paris13.fr Ronald Brown, University of North Wales: ronnie.profbrown(at)btinternet.com

Valeria de Paiva: valeria.depaiva@gmail.com

Ezra Getzler, Northwestern University: getzler(at)northwestern(dot)edu Kathryn Hess, Ecole Polytechnique Fédérale de Lausanne : kathryn.hess@epfl.ch Martin Hyland, University of Cambridge: M.Hyland@dpmms.cam.ac.uk Anders Kock, University of Aarhus: kock@imf.au.dk Stephen Lack, Macquarie University: steve.lack@mq.edu.au F. William Lawvere, State University of New York at Buffalo: wlawvere@buffalo.edu Tom Leinster, University of Glasgow, Tom.Leinster@glasgow.ac.uk Ieke Moerdijk, University of Utrecht: moerdijk@math.uu.nl Susan Niefield, Union College: niefiels@union.edu Robert Paré, Dalhousie University: pare@mathstat.dal.ca Jiri Rosicky, Masaryk University: rosicky@math.muni.cz Giuseppe Rosolini, Università di Genova: rosolini@disi.unige.it Alex Simpson, University of Edinburgh: Alex.Simpson@ed.ac.uk James Stasheff, University of North Carolina: jds@math.upenn.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: robert.walters@uninsubria.it R. J. Wood, Dalhousie University: rjwood@mathstat.dal.ca