Strongly Preserved Formulas in Topoi

(1)

FACOLT `A DI SCIENZE MATEMATICHE, FISICHE E NATURALI Corso di Laurea in Matematica

Strongly Preserved Formulas

in Topoi

Tesi di Laurea Magistrale

CANDIDATO: Giacomo Tendas

RELATORI: Prof. Andreas R. Blass Prof. Mauro Di Nasso CONTRORELATORE: Prof. Alessandro Berarducci

(2)

(3)

2 Logic in Topoi 21 2.1 First-Order Interpretation . . . 21 2.2 High-Order Interpretation . . . 28 2.3 Rules of Inference . . . 32 3 Geometric Preservation 37 3.1 Geometric Formulas . . . 37 3.2 Inductive Constructions . . . 40 3.3 EFPL Formulas . . . 43 3.4 Transitive Closure . . . 48 4 Classifying Topoi 51 4.1 Classification for Grothendieck Topoi . . . 51

4.2 Classyfing Topoi over a Topos . . . 61

Bibliography 67

(4)

(5)

Introduction

Topoi originated in the 1960’s when Grothendieck found a powerful way to study categories related to algebraic geometry; in his idea every topological space gives a topos, namely the category of sheaves on the space. More generally, given a category C with a “topology” J , the full subcategory of SetsCop

whose objects are exactly J -sheaves is a topos in Grothendieck sense. These are now known as “Grothendieck topoi” and constitute a particular case of “elementary topoi”, introduced by Lawvere and Tierney in 1968-69.

The biggest problem of Grothendieck topoi, in Lawvere idea, was their extremely complex constructs; thus he tried to describe the most relevant aspect of topoi in a much more simple way. Essentially, an elementary topos is a category with a terminal object, all finite products, for each X and Y an object XY such that for every Z

Hom(Y × Z, X) ∼= Hom(Z, XY),

and an object Ω together with an arrow t : 1 → Ω which classifies subobjects, i.e. every monomorphism Y X comes from a pullback

Y 1

X Ω

t

A morphism f :E → F between topoi is defined to be a pair of functors f∗ :E F : f∗

such that f∗ is left-exact and left adjoint to f∗.

The few properties defining a topos allow us to work with (first and higher order) logic and, in particular, model theory. Indeed, given a language L, we define the notion of L-structure U in a toposE simply miming the usual interpretation in Sets: for each sort X (respectively function symbol f and relation R) we have an object XU (respectively morphisms fU and RU, where the last is mono). Moreover, we can define the interpretation of a formula φ(x1, . . . , xn), with free variables xi ∈ Xi, as a

(6)

particular subobject φU of X₁U × · · · × XU

n (here we follow [Joh02]). So we are able to say if a formula is true (i.e. the top element in the Heyting algebra of subobjects) or false (i.e. the bottom element); thus we can introduce the notion of model for a given theory T and hence build the category M od(T, E ) of T-models in E (with a suitable notion of homomorphism).

In this context, some questions arise: which formulas are “preserved” by morphism between topoi? Are there any kind of theories whose models are “preserved” by geometric morphisms?

First we should clarify what we mean by preservation; we say that a formula φ is strongly preserved if for each geometric morphism f :F → E and each structure U inE we have

f∗(φU) = φf∗U, where f∗U is the image-structure of U through f∗.

A class of strongly preserved first-order formulas is easily identified; it is the small-est containing atomic formulas and closed for conjunction, disjunction and existential quantification; these are known as geometric (finitary) formulas.

Following [Bla89b], we can consider a new construction and prove that the class of strongly preserved formulas goes beyond first-order. Given two (suitable) strongly preserved L ∪ {Q}-formulas δ and φ, this construction gives another preserved L-formula

ψ ≡ LET Q(x) ← δ T HEN φ

defined using the least-fixed point of an operator induced by δ. Moreover, ψ turns out to be equivalent to the second-order formula

∀Q (∀x (δ ⇒ Q(x)) ⇒ φ);

thus we can extend the class of geometric formulas to that containing also the new LET . . . T HEN . . . construction; we call the elements of this class EF P L-formulas. As a consequence, we are able to prove the following:

Theorem. Let T be an EF P L theory (i.e. its axioms are sequents of EF P L for-mulas); then each geometric morphism f :F → E induces a functor

f∗: M od(T, E ) → M od(T, F ).

Finally, we talk about classifying topoi for theories; initially we get a result for Grothendieck topoi and geometric theories (i.e. its axioms are sequents of geometric formulas):

Theorem. Let T be a geometric theory; there exists a Grothendieck topos B[T] such that for any other Grothendieck topos E we have an equivalence of categories

(7)

Introduction 3

which is natural in E .

To talk about classifying topoi for EF P L theories we need a difference approach: the equivalence we want to prove will be no more for Grothendieck topoi, but for elementary topoi over a base topos (as done in [Joh77]). The only weaker hypothesis we must assume are some requests of finiteness and the existence of a natural number object in the base topos (i.e. a model of natural numbers):

Theorem. Let L be a finite first-order language, T be a finite theory whose axioms are sequents of strongly preserved formulas and E be a topos with a natural number object. Then T has a classifying topos E [T] over E .

As a corollary we get:

Corollary. For every finite EF P L theory T over a finite language, there exists a topos Sets[T] such that for any Grothendieck topos E there is an equivalence of categories

Top(E , Sets[T]) ∼= M od(T, E ) which is natural in E .

To conclude, as shown in [Bla89a], we prove that the request of a natural number object in the last theorem is necessary.

(8)

(9)

Chapter 1

Basic Definitions

In this first chapter, after an introductory section containing general definitions essential for our purpose, we analyse the properties of elementary and Grothendieck topoi, and of morphisms between them as well.

Precisely, after defining topoi, we give the notion of geometric morphism and prove the first properties involving them and subobjects. Finally, in the last section, we focus on Grothendieck topoi and state some results we need in chapter 4 for the construction of classifying topoi.

1.1 Categorical Background

In this first section we summarize all the necessary features needed to talk about topoi; starting from basic definitions, like limits and exact functors, to more set the-oretic ones, like the notion of subobject and lattice. The reader who is familiar with category theory can skip the first pages and start from the definition of subobject.

Concerning notations, we denote by Sets the category of sets and, given two cat-egories C and D, we write DC for the category of functors between C and D.

Definition 1.1.1. Let C be a category; an object 1 of C is said to be terminal if for each C in C exists an unique arrow C → 1. The dual notion is that of initial object. The terminal object of a category (if it exists) will always be denoted by 1 and the initial by 0.

We are now going to introduce the notion of limit.

Definition 1.1.2. Let I and C be two categories and F : I → C a functor; a cone for F is a pair (X, η) where X is an object of C and η : ∆X → F is a natural transformation (∆X : I → C is the constant functor over X). A limit for F is a

(10)

terminal object in the category of cones over F . Analogously one defines the notion of colimit.

Here comes the definition of equalizer:

Definition 1.1.3. Let f, g : X → Y be two arrows in a category C; the equalizer of f and g is the limit of the diagram X −→ Y ; i.e. a morphism e : E → X suchf,g that f ◦ e = g ◦ e and which is universal with this property: for each u : W → X which satisfies f ◦ u = g ◦ u there exists a unique v : W → E such that the following diagram E X Y W e f g ∃!v _u

commutes. Similarly one defines the dual notion of coequalizer.

Remark 1.1.4. In the category Sets the equalizer of two functions f, g : X → Y exists and corresponds to the set

E = {a ∈ A | f (a) = g(a)} together with the inclusion E A.

Definition 1.1.5. Let C be a category and f : X → S and g : Y → S two morphisms in C; a pullback of f and g over S is a limit of the diagram X −→ Sf ←− Y ; i.e. ang object Z together with two morphisms π1 : Z → X and π2 : Z → Y such that the following Z Y X S π2 g π1 f

commutes and which is universal with this property (i.e. terminal in the category of cones over that diagram). In a similar way we get the dual notion of pushout.

If we consider S equal to 1 (in the definition of pullback) and 0 (in that of pushout), we get the notions of product and coproduct.

Given a functor between two categories, we say that it is left-exact if preserves finite limits, right-exact if preserves finite colimits.

(11)

1.1 Categorical Background 7

Definition 1.1.6. Let F : C → D and G : D → C be two functors in opposite directions; we say that G is right adjoint to F (and that F is left adjoint to G), in symbols F a G, if we have a natural bijection

θ : HomC(X, G(Y )) −→ HomD(F (X), Y ),

namely a bijection such that θ(G(α)◦f ◦β) = α◦θ(f )◦F (β) for all β ∈ HomC(X0, X) and α ∈ HomD(Y, Y0).

We are now going to talk about subobjects and functors that preserve them. A subobject of an object A in a category C is simply defined as an equivalence class of monomorphism B A under the following equivalence relation: f : A D and g : B D are said to be equivalent if there exists an isomorphism h : A→ B with∼ g ◦ h = f .

Now consider the full subcategory of the slice category C/D consisting of monomor-phisms to D and pass to isomorphism classes of objects (note that isomorphism here corresponds exactly to the equivalence relation on monomorphisms that is used to de-fine subobjects); this way we obtain the collection SubC(D) of subobjects of D. This carries a natural partial order induced by the following pre-order on monomorphism: (f : A D) ≤ (g : B D) if there exists h : A → B such that f = g ◦ h.

If the category has pullbacks, coproducts and image factorizations, it is easily seen that we can form finite intersections and unions of subobjects; indeed given two subobjects σi: Yi X, i = 1, 2, of X the intersection

Y1∩ Y2 X is defined as the pullback of σ1 and σ2 and the union

Y1∪ Y2 X is the image of σ1

σ2 : Y1t Y2 → X (the least upper bound of σ1 and σ2 in the poset

Sub(X)). One can also see that there is another, more convenient, description of Y1∪ Y2 given by the pushout:

Y1∩ Y2 Y1

Y2 Y1∪ Y2 see Proposition 1.55 of [Joh77].

An important property that will be satisfied by topoi is the the existence of images: Definition 1.1.7. Let C be a category and let f : C → D be a morphism in C. The image of f , if it exists, is the smallest subobject im(f ) D through which f factors. C is said to have image factorizations if each morphism has an image.

(12)

Lastly, we introduce the notion of Heyting algebra, which will be useful in Chapter 3 to describe the propositional combinations of formulas in topoi.

Definition 1.1.8. A lattice L is a partially ordered set which, considered as a category, has initial and terminal objects and all binary products and coproducts.

Let L be a lattice. Given x, y ∈ L we have x ≤ y if and only if there is an arrow x → y; then the coproduct of x and y is the least upper bound (sup) x ∨ y and the product is the greatest lower bound (inf) x ∧ y. Moreover if 0 and 1 are the initial and terminal objects respectively; then for all x ∈ L we have 0 ≤ x ≤ 1.

Remark 1.1.9. Notice that we can see ∧ and ∨ as operations L × L → L and 0 and 1 as arrows 1 → L, this way (translating the properties defining a lattice in suitable equations over L) one can define a “lattice object” L in a category with finite products.

A complement for x ∈ L is an element ¬x such that x ∧ ¬x = 0 and x ∨ ¬x = 1; if the lattice is distributive with respect to ∨ and ∧, then ¬x (if exists) is unique.

Finally:

Definition 1.1.10. A Heyting algebra H is a lattice which has for each pair of elements x, y an exponential, usually written as x ⇒ y, such that for all z ∈ H, z ≤ (x ⇒ y) if and only if z ∧ x ≤ y.

In other words a Heyting algebra is a poset with all finite products and coproducts which, in addition, has exponential objects (see next section).

1.2 Elementary Topoi and Morphisms

We are now ready to talk about topoi, certain categories that resemble that of Sets:

Definition 1.2.1. A category E is called an (elementary) topos if 1. E has all finite limits, i.e. E has pullbacks and a terminal object;

2. for each object X ofE we have an exponential functor (−)X :E → E which is right adjoint to the functor (−) × X;

3. there exists an object Ω ofE and a morphism 1−→ Ω (called “true”) such that,t for each monomorphism σ : Y X in E , there is a unique φσ : X → Ω making

(13)

1.2 Elementary Topoi and Morphisms 9 Y 1 X Ω t σ φσ a pullback diagram.

Definition 1.2.2. If a category C satisfies (1) and (2) we say that it is cartesian closed. If there exists an object Ω like in (3) we say that it (together with the arrow t) is a subobject classifier for C and we call φσ the classifying map of σ. Examples 1.2.3.

The category Sets is a topos with subobject classifier 2 = {0, 1}, exponentials XY := {f | f : Y → X}

and classifying maps given by the characteristic maps of a subset.

If E1 and E2 are topoi, then the cartesian product E1 ×E2 is a topos with (X1, X2)(Y1,Y2)= (X₁Y1, X₂Y2) and subobject classifier given by (Ω1, Ω2). If E is a topos and X is an object of E , then the slice category E /X is a

topos where products are pullbacks over X in E and the subobject classifier is Ω × X π2

−→ X. The existence of exponentials is less simple and requires the pullback functor (see the following pages); a proof can be found in [Joh77]. Before proceeding with the remaining definitions, we prove that topoi have image factorization.

Theorem 1.2.4 (Kelly-Tierney). Any morphism f : X → Y in a topos can be factored as an epimorphism followed by a monomorphism (the image of f ); the fac-torization is unique up to isomorphism. As a consequence, every topos has image factorizations.

Proof. (sketch) Consider the diagram

R X Y Q a b f q i

where (a, b) is the kernel pair of f (i.e. the pair of morphisms coming from the pullback of f along itself) and q is the coequalizer of (a, b). q is an epimorphism by definition, it remains to show that i is a monomorphism; for this we remind to [Joh77] Theorem 1.52.

(14)

Another very important result on topoi is the following (again a proof can be found in [Joh77]).

Theorem 1.2.5. A topos has finite colimits (and hence an initial object). Moreover, if it has infinite colimits of a particular type, then it has the corresponding colimits. Now we need to introduce some important functors that we will use in the next chapters to describe the internal logic of a topos.

Let us fix a toposE and let f : X → Y be a morphism in C; then the operation of pulling back along f yields the pullback functor f∗ :E /Y → E /X. This functor has a left adjoint Σf :E /X → E /Y which is defined by

Σf(Z h

→ X) = (Z → Xh → Y );f

one can also see that f∗ has as well a right adjoint Πf :E /X → E /Y (see [Joh77] Corollary 1.43).

The functors f∗ and Πf preserves the terminal object and monos, so they restrict (respectively) to functors

f−1: Sub(Y ) → Sub(X) and

∀f : Sub(X) → Sub(Y )

such that f−1 a ∀_f (since Sub(X) is a full subcategory of E /X). The functor Σf does not preserve the terminal object, but we can modify it to obtain a left adjoint

∃_f : Sub(X) → Sub(Y )

for f−1 by forming the composite σY ◦ Σf ◦ iX, where iX is the inclusion of Sub(X) inE /X and σY :E /Y → Sub(Y ) sends a morphism Z

h

→ Y to its image considered as a subobject of Y ; in other words ∃f(T Z) = im(T Z

f → Y ).

Remark 1.2.6. Note that the existence of the right adjoint Πf in a suitable category C, implies the existence of exponentials. Indeed, given two objects A, B in C, consider the unique map f : B → 1. If Πf exists, we can apply it to the projection π2 : A × B → B, considered as an object in C/B. The result is an object in C/1 ∼= C such that

HomC(X × B, A) ∼= HomC/B(f∗(X), π2) ∼= HomC(X, Πf(π2))

for each object X of C, where the first isomorphism is given by f −→ (id, 1B) ◦ f and vice versa g −→ πA◦ g. Thus Πf(π2) coincides with the exponential object AB.

(15)

1.2 Elementary Topoi and Morphisms 11

Example 1.2.7. When E = Sets, every f : Z → X can be identified with the collection (f−1(x) | x ∈ X). Thus, if we see the objects of Sets/X (and Sets/Y ) as X-indexed (and Y -indexed) families of sets, we have:

f∗(Sy | y ∈ Y ) = (Sf (x) | x ∈ X) on one side, and

Σf(Sx | x ∈ X) = ( a f (x)=y Sx | y ∈ Y ) Πf(Sx | x ∈ X) = ( Y f (x)=y Sx | y ∈ Y ) on the other.

Thus, the restrictions to subobjects satisfies:

f−1(A) = {x ∈ X | f (x) ∈ A} (i.e. the usual preimage of a set) and

∀_f(B) = {y ∈ Y | ∀z s.t. f (z) = y, z ∈ B} ∃_f(B) = {y ∈ Y | ∃z ∈ B s.t. f (z) = y}.

Proposition 1.2.8. In the diagram

E /X E /Y Sub(X) Sub(Y ) Σf f∗ Πf ∃f f−1 ∀f σX iX iY σY

we have the adjunctions Σf a f∗ a Πf, ∃f a f−1 a ∀f, σ a i, and the equalities (up to natural isomorphism):

f∗◦ iY = iX ◦ f−1, Πf ◦ iX = iY ◦ ∀f and

(16)

Let E be a topos; we now want to introduce the notion of evaluation map and exponential transpose. First of all, if Y is an object of E , we set P(Y ) := ΩY. Looking back at point (2) of Definition 1.2.1, we have, for each objects X, Y, Z ofE , a natural isomorphism:

Hom_E(Y × Z, X) ∼= Hom_E(Z, XY) (1.1) called exponential transpose. In particular, for Z = XY, we can consider the map

ev(Y,X) : Y × XY → X

corresponding to the identity map id_XY (i.e. the counit of the adjunction). If X = Ω,

then we have evY : Y ×P(Y ) → Ω which classifies a subobject of Y × P(Y ) called ∈_Y.

Moreover, if in (1.1) we take Z = 1, each morphism f : Y → X inE corresponds to a “point” 1f : 1 → XY; if X = Ω and A Y is a subobject of Y we call [A] := 1φA : 1 →P(Y ) the name of A.

Remark 1.2.9. Note that there is a natural bijection between Sub(Y ) and arrows 1 →P(Y ), sending each subobject A Y to [A] : 1 → P(Y ). The inverse brings each arrow g : 1 → P(Y ) to the subobject classified by the corresponding arrow G : Y → Ω.

Example 1.2.10. If E = Sets, then P(Y ) is (up to isomorphism) the power set of Y ; moreover ∈Y= {(t, T ) ∈ Y ×P(Y ) | t ∈ T } and [A] : 1 → P(Y ) corresponds to the element A ∈ Sub(Y ) ∼=P(Y ).

We are now going to introduce some operations on the subobject classifier Ω that will be useful in the next chapter.

Let E be a topos and Ω its subobject classifier; we define ∧ : Ω × Ω → Ω as the classifying map of (t, t) : 1 Ω × Ω; this internalizes the operation of forming the intersection of a pair of subobjects of an object of E , i.e. given Yi X (i = 1, 2) with classifying map φi: X → Ω, the following is a pullback diagram:

Y1∩ Y2 1

X Ω

t ∧ ◦ φ

where φ = (φ1, φ2).

Next, ∨ : Ω × Ω → Ω is defined as the classifying map of the union of the two subobjects 1 × t : Ω × 1 Ω × Ω and t × 1 : 1 × Ω Ω × Ω. As in the case of ∧, ∨ internalizes the operations of forming unions.

(17)

1.2 Elementary Topoi and Morphisms 13

Moreover, we can consider the map f : 1 Ω (“false”), which is defined as the classifying map of 0 1; and the unary operation ¬ : Ω → Ω defined as the classifying map of f .

Finally, ⇒: Ω × Ω → Ω is defined to be the classifying map of Ω1 Ω, where the last arrow is the equalizer of π1 : Ω × Ω → Ω and ∧. The external description of ⇒ is less simple: if Yi X is classified by φi (i = 1, 2), then ⇒ ◦(φ1, φ2) classifies the unique largest subobject Z X such that Z ∩ Y1 ≤ Y2 (this corresponds to the Heyting ⇒ operator in the Heyting algebra Sub(X)).

These operations make Ω an “Heyting Algebra” object inE .

Now that we have introduced the objects (topoi) that we use among this essay, we need to introduce a notion of morphism between them; the most natural way is to consider those functors that preserve the structure of the topos:

Definition 1.2.11. Let f : E → F be a functor between topoi; we say that f is a logical functor if it preserves (up to isomorphism) finite limits, exponentials and the subobject classifier.

Example 1.2.12. The inclusion functor F inSets ,→ Sets is logical, as are the projections E1×E2 →Ei.

We will see in the next chapter that morphisms of this kind preserve the “logical” structure of the topos, but we are more interested in another kind of morphism that arises geometrically. We give the definition now but their sense will be clear as soon as we define the notion of Grothendieck Topos.

Definition 1.2.13. Let E and F be topoi. A geometric morphism f : E → F consists of a pair of functors f∗ : E → F and f∗ : F → E (called the direct and inverse images of f ) such that f∗ a f∗ and f∗ is left-exact.

Remark 1.2.14. If f, g : E → F are two geometric morphisms, we define a natural transformation η : f → g simply as a natural transformation of functors η : f∗→ g∗ (which induces a unique ¯η : g∗ → f∗). This way we obtain a 2-category which we call Top; in particular we will indicate with Top(E , F ) the category of geometric morphisms E → F and natural transformations between them.

Example 1.2.15. Given f : X → Y in a topos E , we have already saw that f∗ : E /Y → E /X has left and right adjoint, Σf and Πf respectively; thus the pair

(Πf, f∗) :E /X → E /Y

(18)

Let f : F → E be an arbitrary geometric morphism; then the inverse image functor f∗, being left-exact, preserves monos; hence we obtain a functor:

f_E∗ : Sub_E(E) −→ Sub_F(f∗E)

sending each subobject X E to its inverse image f∗X f∗E in F .

One can see that since f∗ preserves sums, epimorphisms and monomorphisms, then f_E∗ preserves unions and meets; therefore it is a functor of lattices.

Definition 1.2.16. A geometric morphism f :F → E is said to be open when for each object E in E the induced map of subobjects f_E∗ has a left adjoint (fE)!

(fE)!: SubF(f∗E) SubE(E) : fE∗

which is a map of posets and is natural in E (i.e. for each arrow α : E0 → E we have the usual commutative diagram).

Theorem 1.2.17. Let f :F → E be an open geometric morphism; then f∗ preserves universal quantification, i.e. for each morphism α : E → E0 and each subobject A E in E the identity f∗(∀αA) = ∀f∗_(α)(f∗A) holds.

Proof. The equality f∗(∀αA) = ∀f∗_(α)(f∗A) is equivalent to requiring the

commuta-tivity of the following diagram:

Sub_E(E) Sub_F(f∗E)

Sub_E(E0) Sub_F(f∗E0) f_E∗ ∀f∗_α ∀α f∗ E0

Now, if f is open, f_E∗ and f_E∗0 have left adjoints (f_E)_!and (f_E0)_!; hence the preceding

diagram commutes iff the one obtained from that by adjunction Sub_F(f∗E0) Sub_E(E0)

Sub_F(f∗E) Sub_E(E) (f_E0)!

α−1 (f∗α)−1

(fE)!

commutes, but this expresses exactly the naturality of the adjunction (f−)!.

Remark 1.2.18. The inequality f∗(∀αA) ≤ ∀f∗_(α)(f∗A) holds for each geometric

mor-phism f : F → E . Indeed, by definition, we have the inequality α−1∀αA ≤ A, but f∗ preserves monos and pullbacks; thus (f∗α)−1f∗(∀αA) = f∗(α−1∀αA) ≤ f∗A and by adjointness we conclude.

(19)

1.3 Sheaves and Grothendieck Topoi 15

1.3 Sheaves and Grothendieck Topoi

In this section we introduce a particular kind of topoi that arise geometrically from the theory of sheaves; we will use them in the last chapter, as in chapter 3 we focus only on elementary topoi.

Before proceeding with the definition, we introduce the notion of Grothendieck topology and of sheaf over such a topology.

Let C be a small category; we say that a family R of morphisms in C with codomain U is a sieve on the object U if (α : V −→ U ) ∈ R implies (α ◦ β : W −→ U ) ∈ R for any β : W −→ V in C; we also say that this family is saturated with respect to U . Definition 1.3.1. Let C be a small category; a Grothendieck topology on C is defined by specifying for each U in Ob(C), a set J (U ) of sieves on U (called covering sieves of the topology) such that:

1. for any U , {α | cod(α) = U } ∈ J (U );

2. if R ∈ J (U ) and f : V −→ U is an arrow in C, then the sieve f∗(R) := {α : W −→ V | f ◦ α ∈ R} ∈ J (V );

3. if R ∈ J (U ) and S is a sieve on U such that, for each f : V −→ U ∈ R we have f∗(S) ∈ J (V ), then S ∈ J (U ).

Such a category with a Grothendieck topology J is called a site and is denoted by (C, J ).

Example 1.3.2. If X is a topological space we can consider the category O(X) whose objects are the open subsets of X and the arrows between them are given by inclusions. It follows that a sieve for O(X) is a downward-closed collection of open sets; moreover, if we define J (U ) as the collection of sieves on U which cover U , we get a Grothendieck topology and hence a site (O(X), J ).

Definition 1.3.3. A basis for a Grothendieck topology on a category C with pull-backs is a function K which assigns to each object C a collection K(C) of families of morphisms with codomain C, such that:

1. if f : C0→ C is an isomorphism, then {f : C0→ C} ∈ K(C);

2. (stability) if {fi: Ci → C | i ∈ I} ∈ K(C), then for any g : D → C, the family {f_i : Di → D | i ∈ I} (where fi is the pullback of fi along g) is in K(D); 3. (transitivity) if {fi : Ci → C | i ∈ I} ∈ K(C) and for each i ∈ I we have a

family {gij : Dij → Ci | j ∈ Ii} ∈ K(C), then

(20)

A basis K generates a topology J on C defined by

S ∈ J (C) ⇐⇒ ∃ R ∈ K(C) s.t. R ⊆ S;

it is easy to check that J is a Grothendieck topology. Notice also that if J is a given (Grothendieck) topology on C, there is a maximal basis K which generates J , precisely

R ∈ K(C) ⇐⇒ {f ◦ g | f ∈ R, dom(f ) = cod(g)} ∈ J (C).

Thus, we are allowed to often refer to a topology on a category even when it is clear that what we really mean is a basis for a topology.

Example 1.3.4 (The dense topology).

Let P be a poset and for r ∈ P let Dr := {q ∈ P | q ≤ r}. For any fixed p ∈ P , a subset D ⊆ Dp is said to be dense below p if for all r ≤ p, D ∩ Dr 6= ∅. The dense sieves form a topology on P by

J (p) := {D | D ⊆ Dp and D is a dense sieve below p}.

This topology can also be defined for an arbitrary category C: let S be a sieve; then S ∈ J (C) iff for any f : D → C there exists g : E → D such that f ◦ g ∈ S. Then J is a topology on C and will be called the (¬¬)-topology.

Remark 1.3.5. In a site (C, J ) each sieve R on U can be identified with a sub-presheaf of the representable functor hU = HomC(−, U ), namely the presheaf

V −→ {α ∈ R | dom(α) = V }

in the category SetsCop (note that this category has pullbacks). We use this identi-fication in defining sheaves for a topology.

Definition 1.3.6. Let (C, J ) be a site, F a presheaf on C (i.e. an object of SetsCop). We say F is a J-sheaf if, for every object U and every R ∈ J (U ), each morphism R → F in SetsCop has exactly one extension to a morphism hU → F ; and F is a J-separated presheaf if it satisfies the above condition with “exactly one” replaced by “at most one”.

We denote the full subcategory of SetsCop whose objects are J -sheaves by Sh(C, J ) (or simply Sh(C) if J is obvious from the context).

Finally:

Definition 1.3.7. A categoryE is called a Grothendieck topos if there exists a site (C, J ) such thatE is equivalent to Sh(C, J).

(21)

Example 1.3.8. Let X be a topological space and J the topology on O(X) defined in Example 1.3.2; then the Grothendieck topos Sh(O(X), J ) coincides with the category Sh(X) of (usual) sheaves on X.

Example 1.3.9 (Zariski topos). Consider the category Ring of rings, we define a topology J on Ringop _{this way: given an object A and a sieve S in Ring}op _{over A,} we set S ∈ J (A) if and only if S contains a finite family

{φ_i : A → Asi | 1 ≤ i ≤ n}

op

of canonical inclusions φi : A → Asi (Asi is the localization of A along the element

si) and such that {s1, . . . , sn} is a finite set of generators of A (meaning that the si’s generate the improper ideal A).

Thus one defines the Zariski topos Zar := Sh(Ringop_{, J ), we will see in chapter 4} that this topos classifies the theory of local rings.

It is rather important to observe that the category Ringop is equivalent to the that of “affine schemes” (i.e. topological spaces of the form Spec(A) for a ring A, together with a particular sheaf of rings, see [Liu02]); in this context covers of the topology J corresponds to open principal covers of the topological space. Moreover for any affine scheme X, the Yoneda embedding enables us to regard X as an object of Zar; hence we can consider the slice topos Zar/X. This and the topos Sh(X) are called respectively the big and the little topos of X, the importance of these two objects is discussed in [AGV73].

Now we state an important result about Grothendieck topoi, the proof is long and technical, so will be omitted.

Theorem 1.3.10. Let C a small category and J a Grothendieck topology on C; then the inclusion i : Sh(C, J ) → SetsCop has a left-exact left adjoint

a : SetsCop → Sh(C, J ) called sheafification functor.

Proposition 1.3.11. Any Grothendieck topos is an elementary topos.

Proof. (Sketch) Let (C, J ) be a site and E = Sh(C, J); the idea is to first show that SetsCop is a topos, and next that the same holds for the full subcategoryE .

About SetsCop_{, it has finite limits as they are calculated pointwise and Sets has all} finite limits; for exponentials we set

(22)

this definition is forced because if YX exists, by adjunction it must satisfy YX(U ) ∼= Hom(hU, YX) ∼= Hom(hU × X, Y ). Analogously we must have

Ω(U ) ∼= Hom(hU, Ω) ∼= {sub-presheaves of hU} ∼= {sieves on U }. And this definition has the required properties.

Concerning Sh(C, J ), it has finite limits and exponentials because the limit in SetsCop of any diagram of sheaves is still a sheaf and, if X and Y are sheaves, YX (in SetCop) is still a sheaf. About the subobject classifier, we define Ω(U ) as the set of those subobjects of a(hU) which are sheaves (where a : SetsC

op

→ Sh(C, J ) is the sheafification functor).

Remark 1.3.12. As a consequence, for each site (C, J ), the pair (i, a) : Sh(C, J ) → SetsCop is a geometric morphism between topoi.

Example 1.3.13. Here we explain why geometric morphisms are called like this. The idea is that, in the particular case of topoi of sheaves on topological spaces, they arise naturally from continuous functions between the spaces (i.e. from a geometric setting). Let X and Y be two topological spaces and f : X → Y a continuous function between them; we are going to construct a geometric morphism f : Sh(X) → Sh(Y ). First of all, given a sheaf F over X and a point x ∈ X, we define the stalk Fx of F at x as the colimit

F_x:= lim U 3xF (U ).

Now, if F is a sheaf on X we can define (f∗F )(V ) := F (f−1(V )); this yields a functor f∗ : Sh(X) → Sh(Y ). To define f∗, we see a sheaf G on Y as a local homeomorphism pG : G → Y (where G =`_y∈Y Gy comes with the ´etal´e topology, see [Joh77], and pG is the projection to Y ) and set f∗(G) as the sheaf corresponding to f∗(G) → X in the pullback diagram

f∗(G) G

X Y

pG

f

One can show that f∗ is left-exact and f∗ a f∗; thus we obtain the desired geometric morphism.

It is worth to mention here that, if X and Y are sober spaces (e.g., Hausdorff spaces), then all geometric morphisms between their sheaf topoi come from continuous maps between the spaces.

Example 1.3.14. As an application of the preceding example we can consider a continuous function 1 → X (here with 1 we mean the singleton) which identifies

(23)

a point x of the topological space X; thus we have the corresponding geometric morphism x : Sets ∼= Sh(1) → Sh(X). It is easily seen that for each sheaf F on X, x∗(F ) = Fx is the stalk of F at the point x, conversely, for every set S, x∗(S) is the skyscraper sheaf on x:

x∗(S)(U ) =

S x ∈ U 1 x /∈ U

Remark 1.3.15. Every Grothendieck topos E admits a unique (up to isomorphism) geometric morphism γ_E :E → Sets. The direct image is the global-section functor, i.e.

Hom_E(1, ) :E → Sets, while the inverse image functor is given by

S −→a s∈S

1.

This makes Sets a terminal object of the category GTop of Grothendieck topoi (full subcategory of Top).

The following results will be useful in the construction of classifying topoi in Chap-ter 4.

Proposition 1.3.16. Let C be a small category andE be a Grothendieck topos; then for any functor F : C →E the functor RF :E → SetsC

op

defined for all objects E of E and C of C by:

RF(E)(C) := HomE(F (C), E), (and similarly for morphisms) has a left adjoint ⊗CF : SetsC

op

→E . Definition 1.3.17.

1. Let C and E be like in the Proposition; a functor F : C → E is said to be flat if ⊗CF is left-exact.

2. Let J be a topology on C; we say that a functor F : C → E is J-continuous if sends covering sieves of C to colimit diagrams inE .

We denote by F lat(C,E ) the category of flat functors and by F lat_J(C,E ) the full subcategory of J -continuous flat functors.

Theorem 1.3.18 (Diaconescu). For any site (C, J ) and any Grothendieck topos E there is an equivalence of categories

Top(E , Sh(C, J)) ∼= F lat_J(C,E )

which is natural in E . Moreover if C has finite limits, a functor C → E is flat iff it is left-exact.

(24)

Proof. (Sketch). We only give an idea of how to construct the equivalence. Given a geometric morphism f :E → Sh(C, J) we can consider the composition ˜f :E → SetsCop of f with the inclusion Sh(C, J ) → SetsCop. Let now y : C → SetsCop be the Yoneda embedding; thus we can consider the functor F := ˜f∗◦ y : C →E . One can prove that this is flat and J -continuous; hence we have defined:

Top(E , Sh(C, J)) −→ F lat_J(C,E ).

Conversely, let F : C →E be any flat and J-continuous functor; then we can define ˜

f∗ := RF : E → SetsC

op

. By Proposition 1.3.16 this functor has a left adjoint ˜

f∗ := ⊗CF , which is left-exact as F is flat; hence we get a geometric morphism ˜

f : E → SetsCop. Now, because F is J -continuous, ˜f factors through the inclusion Sh(C, J ) → SetsCop; thus we get a geometric morphism f : E → Sh(C, J) which defines the inverse of the equivalence.

As a consequence we get:

Corollary 1.3.19. Let (C, J ) be a site such that C has finite limits and let E be a Grothendieck topos. There is an equivalence of categories between geometric mor-phismsE → Sh(C, J) and J-continuous left-exact functors C → E :

Top(E , Sh(C, J)) ∼= ConLex(C,E )

Definition 1.3.20. Let C be a category and {si : Ci → C | i ∈ I} a family of morphisms in C over a fixed object C of C; we say that this family is epimorphic if for any two arrows f, g : C → D in C, g ◦ si= f ◦ si for all i ∈ I implies g = f .

The following constructions will be used only in Theorem 4.1.4 and they are not indispensable for a general comprehension of the main results.

Given a functor F : Cop → Sets the category of elements R F has as objects the pairs (C, x) where C is an object of C and x is an element of F (C), and as arrows (C, x) → (D, y) the arrows f : C → D in C such that F (f )(y) = x.

Moreover, we say that a small category C is filtered if C has at least one object;

for any objects C, D of C there exists an object E and two arrows f : C → E and g : D → E;

for any arrows f, g : A → B in C there exists an arrow h : B → C such that h ◦ f = h ◦ g.

In conclusion we state:

Proposition 1.3.21. A functor F : Cop→ Sets is flat if and only if its category of elements R F is filtered. Moreover, every flat functor F : C → Sets defined over a site (C, J ), is J -continuous iff sends covering sieves to epimorphic families in Sets.

(25)

Chapter 2

Logic in Topoi

In this chapter we shall examine the relation between topoi and logic. Starting from interpretations for a given (first or higher order) language and up to the definition of truth and model. A structure will be identified by a functor from the language (i.e. from sorts, relations and function symbols) to the considered topos; moreover, in such a structure, we will identify each formula with a particular subobject. Two formulas with the same free variables will be the subobjects of the same object; hence we will be able to compare them and to say when a sentence is true.

The first section is devoted to first-order logic, used mainly for geometric theories; in section 2.2 we focus on higher-order logic, which allows us to extend the results of section 3.1. Finally, in section 2.3, we exhibit the rules of inference valid in the internal language of a topos.

2.1 First-Order Interpretation

We start this section recalling briefly what a first order language L is; for a more detailed treatment we remind to [Joh02]. Such a language is given by a collection of “sorts” (X, Y, ...), a collection of “relation symbols” (R, S, ...) and one of “function symbols” (f, g, ...). Each relation (function) symbol is given together with the sorts of its arguments (and of its output). So, if R is any n-ary relation symbol (n ≥ 0), we write R ⊆ X1× ... × Xn (X1, ..., Xn being its sorts); if f is a function symbol we write f : X1 × ... × Xn → Y . We also assume that each sort of the language has infinitely many variables x1, x2, ... of that sort.

Given a such a language L we can build up terms and formulas in the usual way: Each variable or constant of sort X is a term of sort X; if t1, ..., tn are terms of

sorts X1, ..., Xn and f : X1, ..., Xn→ Y is a function symbol, then f (t1, ..., tn) is a term of sort Y .

(26)

If R ⊆ X1 × ... × Xn is a relation symbol and ti are terms of sort Xi, then R(t1, ..., tn) is an atomic formula; if t, t0 are terms of the same sort, then t = t0 is an atomic formula.

Generic formulas are obtained from atomic formulas using connectives ∧, ∨, ⇒, ¬, >, ⊥ (where the last two are 0-ary connectives) and quantifiers for any sort X.

Remark 2.1.1. Note that we don’t need to introduce constant symbols as they are 0-ary functions, in particular we write c ∈ X or c : 1 → X to indicate that c is a constant of sort X. Moreover we treat > and ⊥ (true and false respectively) as 0-ary connectives; hence we don’t need to define them as atomic formulas.

Now, given a topos E and a language L we want to define an interpretation U of L inE (i.e. an L-structure), we can do this just rearranging the usual interpretation in Sets.

Thus, an L-structure U is given by an object XU of E for each sort X of L, a subobject

RU X1U× ... × X U n

for each relation symbol R ⊆ X1× ... × Xn of L and an arrow fU : X₁U× ... × X_nU → YU

inE for each function symbol f : X1× ... × Xn→ Y .

Given an interpretation U like above, we can define for each term t(x1, ..., xn) of sort Y , with free variables among the xi ∈ Xi, an arrow tU : X1U × ... × XnU → YU by induction on the construction of t:

if t = xi, then tU is the projection X1U× ... × XnU → XiU;

if t = c is a constant of sort Y , then tU _{= c}U_{◦!, where ! is the terminal arrow} X₁U× ... × XU

n → 1;

if t = f(t1, ..., tk), then tU = fU◦ (tU1, ..., tUk).

Next, we define for each formula φ(x1, ..., xn) with free variables xi ∈ Xi a subob-ject

φU := {(x1, ..., xn)|φ}U X1U× ... × XnU inE , by induction on the construction of φ:

if φ is t(x1, ..., xn) = s(x1, ..., xn), then φU is the equalizer of the arrows tU and sU inE :

(27)

2.1 First-Order Interpretation 23 if φ is R(t1, . . . , tk) with each ti of sort Yi and with free variables among

x1, . . . , xn of sort X1, . . . , Xn, then φU is the pullback: {(x1, . . . , xn) | φ}U RU X₁U × · · · × X_nU (t Y₁U× · · · × Y_nU U 1, . . . , t U k)

>U _{and ⊥}U _{are respectively the top and bottom elements of the Heyting algebra} given by the subobjects of X1× · · · × Xn;

if φ is obtained from simple formulas using connectives ∧, ∨, ⇒, ¬, then φU is defined interpreting connectives with the corresponding operations on the Heyting algebra of subobjects of X1× · · · × Xn;

finally, for quantifiers, we define

(∀x ∈ Xφ(x1, . . . , xn, x))U := ∀π(φ(x1, . . . , xn, x)U) and

(∃x ∈ Xφ(x1, . . . , xn, x))U := ∃π(φ(x1, . . . , xn, x)U) where π : X₁U × · · · × XU

n × X → X1U × · · · × XnU is the projection and ∀π, ∃π are those of Proposition 1.2.8.

Remark 2.1.2. We write φU instead of {(x1, . . . , xn) | φ}U whenever there is no risk of confusion, this notation will be used mostly in the next chapter.

Definition 2.1.3. We say that a formula φ = φ(x1, . . . , xn) is valid in a structure U if {(x1, . . . , xn) | φ}U is the maximal subobject of X1U × · · · × XnU, in this case we write

U φ.

For a theory T over a language L, a model of T in a topos E is an interpretation M in E such that all axioms of T are valid in M.

Like in the case of Sets, we can define the notion of homomorphism H : U → U0 between two structures over a language L in a topos E . Such an homomorphism is given by arrows

HX : XU → XU

0

inE , for each sort X, respecting the interpretation of relations and function symbols in the following sense: for each relation symbol R ⊆ X1× · · · × Xn in L, the map HX1 × · · · × HXn must send R

U _{into R}U0

(28)

RU X₁U× · · · × XU n

RU0 X₁U0× · · · × X_nU0 HX1× · · · × HXn

and for each function symbol f : X1× · · · × Xn → Y in L the following diagram commutes X₁U× · · · × XU n YU X₁U0× · · · × X_nU0 _YU0 fU HY HX1× · · · × HXn fU0

This allows us to define the category Str(L,E ) of all L-structures in E ; also each L-theory T gives rise to the full subcategory M od(T, E ) of T-models in E .

Let now F :E → F be any left-exact functor; we would like to define a map F : M od(T, E ) −→ M od(T, F ),

first let us show that such a map exists between L-structures; namely that if U is a structure of the language L inE , then it can be transported to a structure F (U) in F . On sorts it is simply defined by

XF (U ):= F (XU), and, if R ⊆ X1× . . . Xn is a relation symbol of L, we set

RF (U ):= F (RU) X1F (U )× · · · × X F (U ) n ,

we are allowed to do this since F preserves products and monomorphisms. The same procedure works for function symbols f : its interpretation fF (U ) inF is the unique arrow on the left such that the following square commutes

X₁F (U )× · · · × XnF (U ) F (X1U) × · · · × F (XnU) F (X1U × · · · × XnU) YF (U ) F (YU) = ∼= F (fU₎ fF (U ) =

Therefore, for a constant c ∈ X, cF (U ): 1 → XF (U )inF is defined as the composition 1 ∼= F (1)F (c

U₎

−→ F (XU) = XF (U ).

Clearly this construction transports homomorphisms in E to homomorphisms in F ; thus we obtain a functor from the category of the L-structures in E to that of L-structures inF .

(29)

2.1 First-Order Interpretation 25

Example 2.1.4. We want to describe how formulas are interpreted in a sheaf topos over a topological space. For this, let X be a topological space, E = Sh(X) be the topos of sheaves on X. Consider a first-order language L, an L-structure U inE and a formula φ(x) with x of sort F ; we prove that for each U ⊆ X open

{x | φ}U(U ) = {s ∈ F (U ) | ∀V ⊆ U open s|V ∈ {x | φ}ΓV(U ) ⊆ F (V )} as subsheaf of F , where ΓV : Sh(X) → Sets is the V -sections functor (which is left-exact as it has a left-adjoint, the constant-sheaf functor) and {x | φ}ΓV(U ) _{is the}

usual interpretation in Sets.

The proof proceeds by induction on the complexity of φ: for atomic formulas the equality follows as ΓV preserves products and equalizers, for ∧ and ∨ it is trivial. Concerning ⇒ and quantifiers, the conclusion will follow immediately (assuming the induction hypothesis) from the following:

if φ ≡ (γ ⇒ δ), then s ∈ {x | φ}U_{(U ) iff}

for all V ⊆ U open, s|V ∈ {x | γ}U implies s|V ∈ {x | δ}U; if φ ≡ (∃y γ(x, y)) (y of sort G), then s ∈ {x | φ}U_{(U ) iff}

{V ⊆ U open | ∃t ∈ G(V ) (s|_V, t) ∈ {(x, y) | γU} is a cover of U ; if φ ≡ (∀y γ(x, y)) (y of sort G), then s ∈ {x | φ}U_{(U ) iff}

for all V ⊆ U open, and all t ∈ G(V ) one has (s|V, t) ∈ {x | γ}. For a proof we refer to [MM92] Theorem VI.6.1.

Let now T be an L-theory; as mentioned we would like to restrict the induced functor F : Str(L,E ) −→ Str(L, F ) to

F : M od(T, E ) −→ M od(T, F ),

but that’s not possible in general, there is no reason why the validity of the axioms of T should be preserved (see Example 2.1.9). We will need to have stronger hypothesis on F or to restrict T to a a particular subclass of formulas.

Remark 2.1.5. If F is a logical functor, then we have the desired restriction. Indeed F preserves all the construction used in the previous definitions; thus it preserves the validity of all the formulas.

(30)

Now consider a geometric morphism f :F → E ; we will prove that in a particular case its inverse image preserves the validity of all the formulas in a given structure of E .

Let φ(x1, . . . , xn) be an L-formula with free variables xi ∈ Xi and U be a L-structure inE . We can apply f∗ to the subobject

{(x1, . . . , xn) | φ}U X1U × · · · × X U n; this way we obtain another subobject

f∗({(x1, . . . , xn) | φ}U) f∗(X1U × · · · × XnU) ∼= X f∗_U

1 × · · · × Xf

∗_U

n .

On the other hand one can use directly the structure f∗U inF and obtain a (possibly different) subobject: {(x₁, . . . , xn) | φ}f ∗_U X1f∗U × · · · × X f∗_U n . When f is open these two subobjects coincide:

Theorem 2.1.6. Let f : F → E be a geometric morphism and U be a L-structure in E with induced interpretation f∗U in F . If f is open, then for any formula φ(x1, . . . , xn),

f∗({(x1, . . . , xn) | φ}U) = {(x1, . . . , xn) | φ}f

∗_U

. Proof. We proceed by induction on the complexity of φ.

The case of atomic formulas. Consider first a term t(x1, . . . , xn) of sort Y ; then, as f∗preserves products, we obtain (once again by induction on the complexity of t) the commutative square:

f∗(X₁U× · · · × X_nU) f∗(YU) X₁f∗U × · · · × Xnf∗U Yf ∗_U f∗(tU) ∼ = ∼ = tf∗U

Thus, since f∗ also preserves pullbacks and equalizers, follows immediately from the definitions, that the following

f∗({(x1, . . . , xn) | R(t1, . . . , tk)}U) = {(x1, . . . , xn) | R(t1, . . . , tk)}f

∗_U

f∗({(x1, . . . , xn) | t = t0}U) = {(x1, . . . , xn) | t = t0}f

∗_U

hold for every term and relation symbol in L. Hence we are done with atomic formulas.

(31)

2.1 First-Order Interpretation 27 Let’s consider the case of 0-ary connectives. Since f∗ _{preserves the top and}

bottom elements of Sub(X₁U × · · · × X_nU), we have

f∗({(x1, . . . , xn) | >}U) = {(x1, . . . , xn) | >}f ∗_U , f∗({(x1, . . . , xn) | ⊥}U) = {(x1, . . . , xn) | ⊥}f ∗_U .

If φ ≡ (ψ ∧ δ) or φ ≡ (ψ ∨ δ) and the theorem holds for ψ and δ, then it also holds for φ as f∗ preserves meets and sup of subobjects; i.e. for any two subobjects A and B of any object E of E we have f∗(A ∧ B) = f∗(A) ∧ f∗(B) and f∗(A ∨ B) = f∗(A) ∨ f∗(B).

Let φ be (∃x ∈ X ψ) and the theorem be true for ψ; it is enough to prove that f∗ preserves existential quantification along any map; i.e. that for any α : E → E0 and any subobject A ⊆ E, f∗(∃αA) = ∃f∗_(α)f∗(A) holds. And this

is true since ∃αA is the image of the composite A E → E0, and f∗ preserves images.

Let φ be (∀x ∈ X ψ); then the equality follows from Theorem 1.2.17 since f is open.

If φ ≡ (ψ ⇒ δ), then it enough to prove that for any subobjects A, B of an object E we have (A ⇒ B) = ∀α(A ∧ B) where α : A E is the inclusion. For this, let C be any subobject of E; then: C ≤ ∀α(A ∧ B) if and only if α−1(C) ≤ (A ∧ B). But α−1(C) = A ∧ C and A ∧ C ≤ A ∧ B iff A ∧ C ≤ B iff C ≤ (A ⇒ B).

Finally, if φ ≡ (¬ψ) the statement follows from the preceding point since for each subobject A of E we have ¬A = (A ⇒ 0) and f∗ preserves the initial object 0.

Remark 2.1.7. One can show that, if E is cocomplete, the converse of this theorem is also true; i.e. if f :F → E is a geometric morphism such that for any first-order language L, any L-structure U in E and any formula φ(x1, . . . , xn), the identity in the theorem holds, then f must be open.

As a consequence of the previous theorem, a sentence φ which is valid in a structure U in the topos E remains valid in the induced structure f∗U in F ; thus we have: Corollary 2.1.8. For any theory T in the language L, any open geometric morphism f :F → E induces a functor between the categories of T-models:

(32)

Example 2.1.9. Let us show that not every first-order formula is preserved by a geometric morphism. For this, we consider the theory T obtained from Ring adding the axiom

∀x(¬∃y(xy = 1) ⇒ x = 0); (2.1)

we want to find a model of T which is not preserved. Note that T in Sets is equivalent to the theory of fields (i.e. Ring plus ∀x(x = 0 ∨ ∃y(xy = 1))).

Consider an Hausdorff topological space X and the topos E = Sh(X) of sheaves over X; in E we take the sheaf RX of continuous functions from X to R. We know that for every point x ∈ X the inclusion {x} ,→ X induces a geometric morphism x : Sets → Sh(X) (see Example 1.3.14) such that x∗(F ) = Fx is the stalk of F at x. We will show that RX is a model of T but in general x∗(RX) is not; in particular we prove that (2.1) is the only not preserved axiom of T.

The easy part is to prove that x∗(RX) = RX,x is not a model of T, i.e. that RX,x is not a field. But RX,x is the set of germs around x, which in general is only a local ring (the maximal ideal Mx being the set of germs [f ] such that f (x) = 0). For example if X = R, x = 0, then [idR] is a non zero element of Mx.

To conclude we prove that RX is a model of T; the only interesting part is the validity of (2.1) (the other axioms are easy to verify): first we observe that

{x | ∃y(xy = 1)}RX

is the subsheaf of RX of continuous functions with value in R \ {0} (see Example 2.1.4); thus F := {x | ¬∃y(xy = 1)}RX _{satisfies, for each open U ⊆ X,}

F (U ) = {f ∈ C0_{(U, R) | ∀ V ⊆ U open ∃x ∈ V s.t. f (x) = 0}} = {f ∈ C0(U, R) | f−1(0) is dense in U }

The assumption of X being Hausdorff implies F (U ) = {0} for each U ; thus F = {x | x = 0}RX_{. Hence (2.1) is true and R}

X is a model of T.

2.2 High-Order Interpretation

We are now going to explain how to interpret high-order logic in a topos; we will use only second-order logic, even so, it is worth mentioning the general construction as shown in [Joh02].

Definition 2.2.1. A language L for high-order logic is defined by specifying a set L-Sort of sorts, a set L-Fun of function symbols and a set L-Rel of relation symbols as in the preceding section, together with a set L-Typ of types obtained recursively from the following list:

(33)

2.2 High-Order Interpretation 29

1. (basic types) each sort is a type;

2. (product types) there is a distinguished type 1 and if A and B are types, then A × B is a type;

3. (function types) if A and B are types, the [A → B] is a type; 4. (power types) if A is a type, thenP(A) is a type.

We use the following notation to identify the types we are considering; to each function symbol f ∈ L-Fun we assign an order pair (A, B) of elements of L-Typ, as in the first-order case, we write f : A → B to indicate that f has the pair of types (A, B). Similarly, each relation symbol R ∈ L-Rel has a type in L-Typ, and we write R A to indicate that R has type A. We will also write Ω for the particular type P(1).

Remark 2.2.2. Because our language contains the product type constructor, we can suppose all function and relation symbols to be unary, also we can further restrict our function symbols to be constants (function symbols of type (1, B) for some B), since a function symbol f : A → B can be replaced by f : 1 → [A → B]. And we can replace all primitive relation symbols by constants as well: a relation R A becomes a constant [R] : 1 → P(A). So we can suppose to only have constant symbols and types.

Now we should present the recursive clauses for the construction of terms and formulas separately (but recursively together) in the two following definitions. We will suppose to have only constant symbols and we won’t consider list types (for the general construction see [Joh02]).

Notation: Only in this section we write t : A, instead of t ∈ A, to indicate that t has type A. We do this to better distinguish them from the atomic formula (s ∈At). We shall come back to the usual notation in Chapter 4.

Definition 2.2.3. Let L be an higher-order language. The collection of terms over L is defined recursively, together with the type of each term and the (finite) set F V (t) of free variables of each term t, by the following clauses:

1. for each type A we have a stock of variables x : A and F V (x) = {x}; 2. we have a distinguished term ∗ : 1 with F V (∗) = ∅;

3. if s : A and t : B, then there exists hs, ti : A × B, F V (hs, ti) = F V (s) ∪ F V (t); 4. if t : A × B then π1(t) : A and π2(t) : B, both with the same free variables of t;

(34)

5. if t : B and x is a variable of type A, then (λx : A.t) : [A → B] and F V (λx : A.t) = F V (t) \ {x};

6. if s : [A → B] and t : A then s(t) : B and F V (s(t)) = F V (s) ∪ F V (t);

7. if ϕ is a formula and x is a variable of type A, then {x : A | ϕ} : P(A) and F V ({x : A | ϕ}) = F V (ϕ) \ {x}.

Definition 2.2.4. The atomic formulas over L are of two kinds:

if s and t are terms of the same type A, then (s =A t) is an atomic formula and F V (s =At) = F V (s) ∪ F V (t);

if s : A and t : P(A), then (s ∈A t) is an atomic formula with free variables F V (s ∈At) = F V (s) ∪ F V (t).

The compound formulas over L are built up from the atomic formulas exactly as in the the first-order case using connectives ∧, ∨, ⇒, ¬ and quantifiers for any type A. Once again we treat > and ⊥ as 0-ary connectives; hence we don’t need to define them as atomic formulas.

We normally omit the type subscripts from =A and ∈A whenever it is clear from the context.

Now we are ready to define the notion of L-structure in a toposE :

Definition 2.2.5. Let L be a high-order language and E an elementary topos; a L-structure U inE is defined by specifying a function

L-Sort → Ob(E ),

which we denote A → AU and which we extend to a function L-Typ → Ob(E )

in the canonical way: 1U is the terminal object 1, (A × B)U is the product AU× BU, [A → B]U = (BU)AU and (P(A))U is the power object P(AU). In addition, U is required to specify a morphism fU : AU → BU _{for each function symbol f in L, and a} subobject RU AU for each relation symbol R ⊆ A of L (in view of our simplifying assumptions, we have just constant symbols).

Remark 2.2.6. Note that in this case, in contrast to the first-order case, we cannot define the notion of a homomorphism of L-structures. The reason is simple: the power object functor is controvariant, and the exponential functor (A, B) → BA is controvariant in the first variable, so if we are given a family of morphisms AU → AV for each sort A, we will not in general obtain morphisms AU → AV _{for each type A.}

(35)

2.2 High-Order Interpretation 31

The interpretations of terms and formulas in a L-structure U in a topos E are defined like in the first-order case:

Definition 2.2.7. Let U be a L-structure in a topos E ; we assign to each term t = t(x) of type B an interpretation tU : AU₁ × · · · × AU

n → BU (where A1, . . . , An is the string of types of the variables in x), and to each formula ϕ = ϕ(x) a subobject ϕU AU1×· · ·×AUn, by the following clauses (in which we write AUfor AU1×· · ·×AUn):

1. if t is a variable xi, then tU is the projection πi; 2. if t is ∗, then tU is the unique morphism AU → 1;

3. if B = B1× B2 and t is hr, si, then tU is (rU, sU) : AU −→ B1U× B2U ∗; 4. if t is π1(s) where s ∈ B × C, then tU is AU

sU

−→ BU× CU π1

−→ B (and similarly for π2(s));

5. if B = [C → D] and t is λz.s (where z does not appear in x), then tU is the exponential transpose of (s(x, z))U : AU × CU −→ DU;

6. if t is r(s) where r : [C → B], then tU is AU (r

U_,sU₎

−→ (BU)CU × CU −→ Bev U; 7. if B = P(C) and t is {z : C | ϕ} (where z does not appear in x), then tU is

the exponential transpose of the characteristic map of ϕ(x, z)U AU × CU; 8. if ϕ is the atomic formula (s ∈B t), then ϕU AU is the subobject obtained

by pulling back the universal relation ∈_BU BU ×P(BU) along AU (s U_,tU₎

−→ BU ×P(BU);

9. the interpretations of the others atomic formulas and of all compound formulas are defined exactly as in the first order case.

We say that an L-structure U satisfies a sequent ∀x(φ(x) ⇒ ψ(x)) if ϕU ≤ ψU _in Sub(AU), and we say that U is a model of a theory T over L (considered as a set of sequents over L) if it satisfies all the sequents in T.

Definition 2.2.8. LetE be a topos. We define the Mitchell-B´enabou language L_E as the higher-order language whose sorts and function symbols are the objects and morphisms of E , and whose relation symbols are monomorphisms in E . This language has an associated canonical L_E-structure U_E, which interprets each sort (resp. function/relation symbol) of L_E with the corresponding object (resp. mor-phism/monomorphism) of E .

(36)

Example 2.2.9. Let f : X → Y be a morphism inE and A Y a subobject of Y with characteristic map φA: Y → Ω and let [A] : 1 →P(Y ) be its name. Then we have the following commutative diagram in E :

{x : X | f (x) ∈ [A]}UE ∈Y 1

X YX × X ×P(Y ) Y ×P(Y ) Ω

(1f, idX, [A]) (ev, id) _ev

Where the squares are pullback diagrams by definition; moreover the composition of the arrows above gives φA◦ f = φf−1_(A) and thus we obtain:

f−1(A) = {x : X | f (x) ∈ [A]}UE

as expected.

2.3 Rules of Inference

To conclude this chapter we briefly talk about the rules of inference which can be used in the internal logic of topoi.

Notation: for brevity we write φ `xψ for the sequent ∀x(φ(x) ⇒ ψ(x)); moreover in the following list t is an arbitrary term; φ, ψ, θ are formulas; and α, β are terms of the same exponential type. When writing e.g. φ[t/y] `xψ[t/y] it is assumed that φ[t/y] and ψ[t/y] are formulas with no free variables apart from x; so the term t must have the same type as the variable y and no other free variables. As usual, the notation φ[t/y] is understood to include a convention to avoid binding free variables in t.

1. Order φ `xφ;

φ `xψ and ψ `xθ implies φ `xθ; φ `x,y ψ implies φ[t/y] `xψ[t/y]. 2. Equality

> `x(t = t); (t = t0_{) `}

x(φ[t/y] ⇒ φ[t0/y]);

(37)

2.3 Rules of Inference 33 (∀y α(y) = β(y)) `x(α = β);

3. Products > `xhπ1(t), π2(t)i = t; > `xπi(ht1, t2i) = ti for i = 1, 2; 4. Exponents > `x(λx.t)(x) = t; > `xλx.α(x) = α; 5. Elementary Logic ⊥ `xφ; φ `x>; φ `x¬ψ iff (φ ∧ ψ) `x⊥; θ `xφ and θ `xψ iff θ `x(φ ∧ ψ); (θ ∨ φ) `xψ iff θ `xψ and φ `xψ; (θ ∧ φ) `xψ iff θ `x(φ ⇒ ψ);

θ `x,yφ iff θ `x(∀y φ), where y is not free in θ; (∃y θ) `xφ iff θ `x,y φ, where y is not free in φ; 6. Membership relation

> `w(w = {x : A | x ∈Aw}) where w is a variable of typeP(A); (y ∈A{z : A | φ}) a`x,yφ[y/z].

This family corresponds exactly to the deduction system of intuitionistic higher-order logic, namely classical logic and type theory except for the rule of excluded middle; the last holds only if the topos is boolean, i.e. every subobject is comple-mented.

The following Soundness Theorem is not difficult to prove, but requires time and some technical observations; for a proof see [Joh02].

Theorem 2.3.1. Let T be an higher-order theory over a language L. If a sequent σ is derivable in T using the rules just mentioned, then it is satisfied in any model M of T in a topos E .

(38)

Theorem 2.3.2 (Completeness). Let T be a higher-order theory and σ a sequent over the language of T. If σ is satisfied in all models of T in topoi, then it is derivable in T.

As a consequence we get a result for “preserved” formulas asserting that, for them, intuitionistic and classical logic coincides.

First we clarify the concept of preserved formula:

Definition 2.3.3. We say that a formula φ(x1, . . . , xn) is strongly preserved if f∗(φU) = φf∗U

for each geometric morphism f :F → E and each structure U in E .

Next, we need an important result that we are only going to state; a proof can be found in [Joh77].

Theorem 2.3.4 (Barr). Let E be a topos; then there exists a boolean topos B and a surjective geometric morphism

p :B → E .

Where, with surjective we mean that p∗ is faithful, or equivalently that it reflects isomorphisms.

Finally, we are ready to prove the following:

Corollary 2.3.5. Let T be a theory whose models are preserved by geometric mor-phisms, i.e. for each f : F → E the inverse image f∗ induces a functor f∗ : M od(T, E ) → M od(T, F ). If a sequent ∀x(φ(x) ⇒ ψ(x)) of two strongly preserved formulas is deducible from T in classical higher-order logic, then it is also deducible form T in intuitionistic higher-order logic.

Proof. By Theorem 2.3.2 it is enough to prove that the sequent is true in each model of T in a topos. Thus, let E be given and M be a model of T in E . By Barr’s theorem there exists a surjection p :B → E with B boolean; moreover, since T-models are preserved by geometric morphisms, p∗M is a model of T in B. As classical logic is internally valid in boolean topoi and, by hypothesis, ∀x(φ(x) ⇒ ψ(x)) is deducible from T in classical higher-order logic, ∀x(φ(x) ⇒ ψ(x)) holds in p∗M. This means that the inclusion

(φ ∧ ψ)p∗M φp∗M

is an isomorphism inB. But this inclusion is exactly the image of (φ ∧ ψ)M φM

(39)

2.3 Rules of Inference 35

under p∗ (since both φ and ψ are strongly preserved) and p∗ reflects isomorphisms. It follows that

(φ ∧ ψ)M φM

(40)

(41)

Chapter 3

Geometric Preservation

We are now going to study which kind of formulas are strongly preserved and when models of a certain theory T are preserved by geometric morphisms; i.e. when for each f :F → E we have an induced functor

f∗ : M od(T, E ) → M od(T, F ).

Starting from a class of first-order formulas, we define geometric theories and prove the preservation property for them (first section); then we consider the higher-order class of EF P L formulas and define the notion of EF P L theory (sections 3.2 and 3.3). Again, we get a preservation theorem for EF P L logic. Finally, in section 3.4, we prove that transitive-closure logic is preserved by geometric morphisms as a con-sequence of previous results.

3.1 Geometric Formulas

We start this section presenting a class of first-order formulas preserved by inverse images of geometric morphisms:

Definition 3.1.1. Let L be a first-order language; an L-formula φ is said to be geometric if it can be obtained from atomic formulas by conjunction ∧, disjunction ∨, and existential quantification. More precisely, the collection of geometric formulas is the smallest collection of formulas such that:

1. the atomic formulas R(t1, . . . , tn), t = t0, >, and ⊥ are geometric formulas; 2. if φ and ψ are geometric formulas, then so are φ ∧ ψ and φ ∨ ψ;

3. if φ(x1, . . . , xn) is a geometric formula, then, for each sort X and x ∈ X, so is the formula ∃x ∈ X φ(x1, . . . , xn).

(42)

Thus we get the following:

Theorem 3.1.2. Let f :F → E be a geometric morphism, let U be an interpretation of the language L in E and f∗U be the induced interpretation in F . Then any geometric formula φ(x1, . . . , xn) is strongly preserved, i.e.

f∗(φU) = φf∗U.

[Where equality is that as subobjects of X₁f∗U× · · · × Xnf∗U ∼= f∗(X1U × · · · × XnU)]. Proof. The proof is by induction on the construction of the formula φ, and is identical to the first part of the proof of Theorem 2.1.6, in which we did not use the assumption that f is open.

Remark 3.1.3. A formula φ is said to be weakly preserved if for each geometric morphism f :F → E we have

f∗(φU) ≤ φf∗U (3.1)

as subobjects of X₁f∗U× . . . Xnf∗U.

Thus, a theory T consisting only of weakly preserved axioms induces a functor f∗ : M od(T, E ) → M od(T, F )

for each geometric morphism as above. Indeed if φ is weakly preserved and has truth value 1 in a structure M in E (i.e. φ is valid in M), then inequality (3.1) implies that φf∗M = 1; hence φ is valid in f∗M.

We are going to show in Corollary 3.1.5 that every theory like those in the following definition, is composed of weakly preserved formulas.

Definition 3.1.4. A theory T in the language L is said to be a geometric theory if all its axioms are of the form

∀x1, . . . , xn(φ(x1, . . . , xn) ⇒ ψ(x1, . . . , xn))

where φ and ψ are geometric formulas, with free variables among x1, . . . , xn. Corollary 3.1.5. For a geometric theory T, each geometric morphism f : F → E induces a functor f∗ : M od(T, E ) → M od(T, F ).

Proof. Let M be a model of T in E ; we need to show that each axiom of T is valid in the structure f∗M. Consider δ ∈ T; then δ ≡ ∀x1, . . . , xn(φ(x1, . . . , xn) ⇒ ψ(x1, . . . , xn)) with xi ∈ Xi, and δ is true in a structure U iff φU ≤ ψU as subobjects of X₁U×· · ·×XU

n. By hypothesis φM≤ ψM; hence, as f∗ preserves monos, f∗(φM) ≤ f∗(ψM) in f∗(X₁U) × · · · × f∗(X_nU). Now, as φ and ψ are geometric, by Theorem 3.1.2 follows that φf∗M≤ ψf∗_M

(43)

3.1 Geometric Formulas 39

Example 3.1.6. All axioms of the theory Ring of rings are of the form ∀x1, . . . , xn(t(x1, . . . , xn) = t0(x1, . . . , xn))

which can be rewritten as geometric formulas

∀x₁, . . . , xn(> ⇒ (t(x1, . . . , xn) = t0(x1, . . . , xn)));

therefore Ring is a geometric theory; analogously the theory of fields obtained adding to Ring the additional axiom

∀x(x = 0 ∨ ∃y(xy = 1))

is geometric. On the other hand the theory T in Example 2.1.9 (which is very similar to that of fields) is not geometric and, as we saw, is not preserved by geometric mor-phism. This means in particular that the theory of fields in topoi can be axiomatized in several non equivalent ways.

Remark 3.1.7. If we restrict to cocomplete topoi (i.e. topoi with all colimits) and we allow the logic to be infinitary we can extend the class of geometric formulas: Definition 3.1.8. The class of geometric infinitary formulas is the the smallest collection of formulas containing the atomic ones and closed for existential quantifi-cation, conjunction and infinite disjunction W.

Firstly we must show that infinitary disjunction can be interpreted in a cocomplete topos; this follows immediately from the fact that for each object X of such a topos, Sub(X) has all small unions (i.e. is a cocomplete Heyting algebra).

The next step is to prove that geometric infinitary logic is still preserved by geometric morphism: if f : F → E is a geometric morphism between cocomplete topoi; then f∗ is right exact (being the left adjoint of f∗). Hence it preserves all small colimits, and thus infinite joins of subobjects. This means exactly that it preserves infinite disjunctions.

As an example we can consider the theory T of torsion abelian groups obtained adding to the theory of abelian groups the axiom

_ n≥0

(nx = 0)

Strongly Preserved Formulas in Topoi