Basics in category and topos theory

David Janin
UMR LaBRI, Bordeaux INP
Université de Bordeaux
janin@labri.fr

Abstract

Ad hoc selection of elements of category and topos theory for a short series of lectures at Bordeaux University graduate school (EDMI) in Mathematics and Computer Science. Basic notions in posets and monoids are the mere requirement for such a lecture series.

1 Introduction

Categories where first defined by Eilenberg and Mac Lane in the 40s. It is said that Mac Lane wanted to define natural transformations, therefore basic category theory should lay within the definitions (and properties) of category themselves, functors and natural transformations. Everything else could (should) be re-discovered by students ?

Of course many other mathematicians contributed to the theory. We may review in this lecture further notions developed by Yoneda, Kan and Grothendieck. By lack of expertise in the field, we shall give no historical references but, instead, invite the attendee to have a look at one of the following book given as a (very short) selected bibliography:

Aside many other books, other sources are available on the internet.

There is the fairly exhaustive Ncatlab website, for researchers in category theory, as well as various category theoretic entries on Wikipedia. What is better ? To state it simply, Ncatlab is complete but sometimes (very) hard to read as it offers many equivalent definitions for most concepts. On the contrary, Wikipedia tells us what definitions buddies in the street actually know.

Contents

1 Introduction
2 Basics
 2.1 Categories
 2.2 Categories out of categories
 2.3 Graphs vs categories
 2.4 Mono and epimorphisms
 2.5 Functors
 2.6 Presheaves
 2.7 Homfunctors
3 Natural transformations
 3.1 Natural transformations
 3.2 Functor categories
 3.3 Discrete fibrations, presheaves and their element categories
 3.4 Composing natural transformations and functors
4 Diagram, limits and representations
 4.1 Diagrams
 4.2 Constant diagram, cones and natural transformations
 4.3 Representable functors
 4.4 Limits and colimits
 4.5 Exponent in cartesian category
 4.6 Yoneda Lemma
5 Elementary topoi
 5.1 Sub-objects
 5.2 Subobject classifier
 5.3 Power object
 5.4 Elementary topos
 5.5 Grothendieck topologies
 5.6 Sheaves
6 Adjunction
 6.1 Definition and examples
7 Further topics
 7.1 Grothendieck construction

2 Basics

2.1 Categories

Definition 2.1.1 (Category). A category C is defined by a collection of objects C0, a collection of morphisms (also called arrows) C1 with domain and codomain functions dom,cod : C1 C0, a partial binary composition over C1 and identities idA C1, one for each A C0, such that:

for all f,g,h ,C1 and A C0.

Remark 2.1.2. Property (1) says that composition is defined on pairs of co-domain and domain compatible functions. Property (2) says that composition is associative when defined. Property (3) says that identities are local units for arrows.

Exercise 2.1.3. Prove that, for all A C0, the identity idA is the unique morphism such that property (3) holds.

Notation 2.1.4. We may write A C for an object A C0 and f in C for a morphism f C1. We may write f : A CB (or simply f : A B when there is no ambiguity) for f C1 with dom(f) = A and cod(f) = B. The collection of morphisms from A to B, called a homset, can be denoted by HomC(A,B) (or simply Hom(A,B) when there is no ambiguity) or C[A,B].

Remark 2.1.5. The above axioms are depicted in Figure 1 by means of diagrams that are said to commute.


SVG-Viewer needed.


Figure 1: Explicit commuting diagrams for associativity and local unit axioms.


In category theory, it is a general graphical tool to express function compositions equality by means of diagrams, that is, directed graphs which vertices are labeled by objects of a category and edges are labeled by arrows between these objects. A diagram is said to commute when every pair of paths with same source and target define, by composing the functions they traverse, two equal functions.

As there is always the cyclic empty path, implicitly labeled by an identity, the function induced by any cyclic path necessarily equals the identity. Also, function defined by composing connected edges does not need to be explicitly drown. In other words, the associativity and local unit axioms are always assumed in a commuting diagram. In other words, the gray arrows in Figure 1 are generally left implicit. See 2.3.4 and 4.1.1 for more about diagrams in category theory.

Definition 2.1.6. A category C is small when both C0 and C1 are sets. The category C is locally small when Hom(A,B) is a set for every pair of objects A,B C.

Remark 2.1.7. Unless stated otherwise, such as for the category Cat presented below, all categories considered here are locally small.

Example 2.1.8. All notions listed below can be seen as certain type of categories. For each of them, check what are objects, arrows and their composition, and check how the axioms defining these notions relates to the category axioms.

The term local units for identities come from semigroup theory.

Definition 2.1.9 (Isomorphisms). A morphism f : A B in C is an isomorphism, or just iso, when there is f-1 in C such that f f-1 = idB and f-1 f = idA. Two object A,B C are called isomorphic, which is written A~=B when there is an isomorphism f : A B in C.

Exercise 2.1.10. Prove the unicity of inverse.

Example 2.1.11. Examples of locally small categories:

2.2 Categories out of categories

Definition 2.2.1 (Product category). The product C × D of two categories C and D is defined object-wise by taking (C × D)0 = C0 × D0 and (C × D)1 = C1 × D1 with dom(f,g) = (dom(f),dom(g)), cod(f,g) = (cod(f),cod(g)) and (f,g) (f,g) = (f f,g g).

Exercise 2.2.2. Check that the product of two category is indeed a category. What is the product of two monoids ? two groups ? two posets ?

Definition 2.2.3 (Opposite categories). Let C be a category. The opposite category Cop is defined from C by exchanging dom and cod and reversing composition.

Exercise 2.2.4. What is the category (Cop)op ?

Exercise 2.2.5. What is the oppositie category of a monoid ? a group ? a poset ?

Remark 2.2.6. Remember (from college ?) that, in Set, function composition notation gf is sort of reversed when thinking about the order of application. Some may prefer the sequential notation f;g, i.e. apply f and then apply g. Formally, using the sequential composition notation amounts to taking the opposite of the category Set. Of course, we do not expect functions in Set to be reversible. This is just a notational convention.

Definition 2.2.7 (Slice category). Let C be a category and A C. The slice category C∕A induced by A is the category which objects are the arrows of C into A and which arrows from f : B A to g : C A are the arrows h : B C such that f = g h.


SVG-Viewer needed.


Figure 2: Arrows in the slice category C∕A.


Exercise 2.2.8. Check that C∕A is a category.

Definition 2.2.9 (Co-slice category). Let C be a category and A C. The co-slice category A\C induced by A is the category which objects are the arrows of C from A and which arrows from f : A B to g : A C are the arrows h : B C such that h f = g.


SVG-Viewer needed.


Figure 3: Arrows in the co-slice category A\C.


Exercise 2.2.10. Check that A\C is a category.

Definition 2.2.11 (Arrow category). Let C be a category. The arrow category C is the category which objects are the arrows of C and which arrows from f : A B to g : C D are the pairs of arrows (h : A C,k : B D) such that k f = h g.


SVG-Viewer needed.


Figure 4: Arrows in the arrow category C.


Exercise 2.2.12. Check that C is a category.

Definition 2.2.13 (Twisted arrow category). Let C be a category. The twisted arrow category TW(C) is the category which objects are the arrows of C and which arrows from f : A B to g : C D are the pairs of arrows (h : C A,k : C D) such that f = k g h.


SVG-Viewer needed.


Figure 5: Arrows in the twisted category TW(C).


Exercise 2.2.14. Check that TW(C) is a category.

Remark 2.2.15. In most of the definition above there is an abuse of language quite common in category theory that amounts to implicitly assume that the homsets are not necessarily disjoints, but instead, domain and codomain information are implicitly added to arrows whenever needed.

For instance, in the slice category C∕A, saying that h is an arrow from f to g whenever f = g h actually mean that the triple (h,f,g) is the arrow induced by h in C∕A from f to g. Indeed, the same arrow h in C may also induce other arrows, possibly distinct, each of the form (h,f,g) in C∕B whenever f= g′∘ h.

Remark 2.2.16. Mathematicians seem to commonly think that arrows are “going down” as in Figure 2 above. The slice category C∕A is thus often called the category of objects of C above A. Similarly, especially in view of Figure 3 above, the co-slice category A\C is often called the category of objects of C below A.

Of course, this is a convention, and, as a computer scientist, I confess that I tend to think that arrows are “going up” as time is passing. A physicist may disagree thinking of passing time as a phenomenon linked with gravity thus “going down” as well !

Exercise* 2.2.17. The sequential composition notation f;g looks like C programing doesn’t it ? Shall C semantics also be defined by mean of a category ? Think of a C block semantics as a function acting on the memory of the computer with designated variables “in-use”. Translate program constructs (if, else, while-do, do-while, etc…) into semantics function compositions. This looks like a compiler doesn’t it ? Eventually forget about C and use OCaml or Haskell instead.

2.3 Graphs vs categories

Definition 2.3.1 (Graphs). A directed graph G is a quadruple G = V,E,sr,tg : E V with set of vertices V , set of edges E and source/target functions sr,tg : E V .

Let G1 = V 1,E1,sr,tg : E1 V 1and G2 = V 2,E2,sr,tg : E2 V 2be two graphs. A graph morphism φ : G1 G2 is a pair of function φ0 : V 1 V 2 and φ1 : E1 E2 such that preserves sources and targets, i.e. sr φ1 = φ0 sr and tg φ1 = φ0 tg.

Remark 2.3.2 (Type coherence). In the definition above, as in many other places throughout, we may use the same function name for two functions which are unambiguously distinguished by their domain and codomain, i.e. their type. For instance, in the equation sr φ1 = φ0 sr given above, the left occurence of sr is necessarily the one of graph G2 and the right occurence of sr is necessarily the one of graph G1, in order to ensure the type coherence with φ1 and φ0.

Exercise 2.3.3. Proves that graphs and graphs morphisms form a category Graph.

Definition 2.3.4 (Path categories generated graphs). The path category generated by G is the category Path(G) with object V and which arrows the set of paths in G inductively defined by:

for all vertex s V , all edge e E and all (s,w,t),(s,w,t) V × E*× V with E* the free monoid of strings over E.

Exercise 2.3.5. Explicit the domain and co-domain functions in a path category Path(G) and check that all category axioms are indeed satisfied.

Example 2.3.6. The category 0 generated by the empty graph, the category 1 generarated by the one vertex graph, the category 2 generarated by the two vertices, one edge graph, the category 3 generarated by the three vertices, two edges acyclic linear graph, etc…, see Figure 6.


SVG-Viewer needed.


Figure 6: Some elementary finite linear graph.


Notation 2.3.7. By analogy with the category it induces, we shall simply write v G for a vertex v V of the graph G and e : v w in G for an edge e E of the graph G with sr(e) = v and tg(e) = w.

2.4 Mono and epimorphisms

Definition 2.4.1 (Monomorphisms). An arrow f in C is an monomorphism, or just mono, when for all g,h such that f g = f h we necessarily have g = h.

Exercise 2.4.2. Prove that monos in Set are the injective functions.

Definition 2.4.3 (Epimorphisms). An arrow f in C is an epimorphism, or just epi, when for all g,h such that g f = h f we necessarily have g = h.

Exercise 2.4.4. Prove that monos in Set are the surjective functions.

Exercise 2.4.5. Prove that every iso is both a mono and an epi. Find the simplest category into which the converse is false. Hint: think of path categories over a graph.

Remark 2.4.6. Monos and epis are the most general translations in category theory of the notion of injections and surjections in Set. There are more restrictive ones. This often give the feeling that category theory is complex.

But don’t bother. If ever you need such a more restrictive notion, define it yourself, use it to check it is what you need, and eventually check what existing one it corresponds to, as it is very likely it has been defined already.

2.5 Functors

Functors are to categories what morphisms are to algebras.

Definition 2.5.1 (Functors). A functor F : C D is defined as a pair of functions F0 : C0 D0 and F1 : C1 D1 such that:

for all A,B,C C, f : A B and g : B C in C.

Exercise 2.5.2. Prove that the direct image of an iso is an iso.

Exercise 2.5.3. Define the category Cat of (locally smal) categories and functors. Check that the category axioms are satisfied. Is Cat locally small ?

Exercise 2.5.4. What does it mean that two (locally small) categories are isomorphic ?

Exercise 2.5.5. What are the functors between monoids, groups (use 2.5.2), posets, path categories ?

Example 2.5.6. Examples of functors over Set ?

Definition 2.5.7. A functor F : C D is faithfull when any two distinct arrows f,g : A CB are mapped to distinct arrows F(f),F(g) : F(A) DF(B), i.e. the restriction of F to HomC(A,B) is injective for all A,B C.

A functor F : C D is full when for every arrows h : F(A) DF(B) there is an arrow f : A CB such that F(f) = f, i.e. the restriction of F to HomC(A,B) is surjective for all A,B C.

Exercise 2.5.8. Prove that Path, seen as a function from graphs into (small) categories, can be extended into a functor from Graph into Cat. Is such a functor full ? Faithfull ?

Exercise 2.5.9. Given a sub-collection D0 C0 of objects of a category C, how to define a category from D0 ? How to extend the inclusion function from D0 into C0 into a functor. Is this functor faithfull ? Full ? Define the notion of a subcategories and full subcategories.

Remark 2.5.10. Let C be a locally small category. There is the functor incC : C Set by incC(A) = {A} for all A C and incC(f) = A↦→B for every f : A B in C. In other words, every locally small category is isomorphic to a (full) sub-category of Set.

Exercise 2.5.11. Given a functor f : C D in Cat, check that f is also a functor f : Cop Dop.

Definition 2.5.12 (Covariant vs contravariant functors). A functor f : C D is called covariant. A functor f : Cop D (equivalently f : C Dop) is called a contravariant functor f : C D.

Exercise 2.5.13. What are contravariant functors between monoids ? between posets ?

Exercise 2.5.14. Show that ()op can be extended into a covariant functor over Cat. Equivalently, proves that any functor F : C D can also be seen as a functor F : Cop Dop.

2.6 Presheaves

Definition 2.6.1. Let C be a (locally small) category. A functor F : Cop Set is called a presheaf on C.

Exercise 2.6.2. What existing algebraic notion corresponds to a presheaf over a monoid ? a group ?

Exercise* 2.6.3 (Presheaves on posets). Let F : Top P be a presheaf over a poset T. Define P = tT{tF(t). Define (u,x) (v,y) when u v and x = F(u v)(y) for all (tu,x),(v,y) P. Show that is a partial order relation over P. What functor properties guaranty reflexivity and transitivity ? What property guarantee anti-symmetry ?

Let π : P T defined by π(t,x) = x for all (t,x) P. Check that π is monotonic therefore a poset functor. Prove that for all u v and y P such that π(y) = v there is a unique x P such that x y and π(x) = u. Such a kind of functor is called a discrete fibration. See 3.3.2 for a generalization of this construction.

2.7 Homfunctors

Exercise 2.7.1. Let A C. Extend λY.Hom(A,Y ) into a covariant functor from C into Set.

Remark 2.7.2. The functor induced by λY.Hom(A,Y ) is often denoted by Hom(A, _). The function induced by h : B C from Hom(A,C) into Hom(A,B) that maps every f : A B to h f is denoted by Hom(A,f) or, more simply, by h _.


SVG-Viewer needed.


Figure 7: Covariance of Hom(A, _).


Exercise 2.7.3. Let B C. Extend λX.Hom(X,B) into a contravariant functor from C into Set.

Remark 2.7.4. The functor induced by λX.Hom(X,B) is often denoted by Hom(_,B). The function induced by h : A C from Hom(C,B) into Hom(A,B) that maps every g : C B to g h : A B is denoted by Hom(f,B) or, more simply, by _ h.


SVG-Viewer needed.


Figure 8: Contravariance of Hom(_,B).


Exercise 2.7.5. Prove that λ(X,Y ).Hom(X,Y ) can be extended into a functor from Cop ×C into Set.

3 Natural transformations

3.1 Natural transformations

Definition 3.1.1. Let F,G : C D be two functors. A natural transformation α from F to G, denoted by α : F G, is a collection of functions αA : F(A) DG(A), one for each A C, such that, for every arrow f : A CB we have G(f) αA = αB F(f).


SVG-Viewer needed.


Figure 9: Commuting diagram of a natural transformation α.


The collection of natural transformation from F into G is denoted by Nat(F,G).

Definition 3.1.2 (Vertical composition). Let F,G,H : C D. Let α : F G and β : G H be natural transformations. The (vertical) composition β α of α and β is defined by (β α)A = βF(A) αA for all A F.


SVG-Viewer needed.


Figure 10: Vertical composition of natural transformations.


Exercise 3.1.3. Proves that β α : F H is a natural transformation. For such a purpose, draw all the necessary commuting diagrams.

3.2 Functor categories

Definition 3.2.1 (Functor category). The collection Func(C,D) of functors from C into D with natural transformation (composed vertically) is a category called the functor category. This functor category is sometimes also denoted by [C,D].

Exercise 3.2.2. Prove that Func(C,D) is a category. For such a purpose, prove with commuting diagrams that the (vertical) composition is associative and check what are its identities.

Exercise* 3.2.3. What are the mono, epi and iso in the functor category Func(C,D) ?

Definition 3.2.4 (Equivalence of categories). Let C and D be two categories. We say that C and D are equivalent, which is denoted by C D when there are two functors F : C D and G : D C such that G F~=IdC in the functor category Func(C,C) and F G~=IdD in the functor category Func(D,D).

3.3 Discrete fibrations, presheaves and their element categories

Remark 3.3.1. As a special case of a functor category, there is the category Func(Cop,Set) of presheaves on C and natural transformation between them. This category is generally denoted by Psh(C) or ^C.

Definition 3.3.2 (Element categories of presheaves). Let C be a small category and F : Cop Set be a presheaf. The category of element of F, denoted by El(F), is defined by the collection of object

El (F) = ⋃  {A} × F(A)
  0      A∈C
the collection of arrows
El1(F ) = {(f,(A, x),(B,y)) ∈ C1 × El0(F)× El0(F) : f ∈ Hom (A,B ),x = F(f)(y)}
with composition, identities, domain and codomain defined by:

for all arrows (f,(A,x),(B,y)) and (g,(A,x),(B,y) in El(F).

Exercise 3.3.3. What is the element category of the inclusion functor inc : Cop Set of Cop into Set (see 2.5.10) ?

Exercise 3.3.4. Show that the element category El(F) of a presheaf F on a poset T is a poset.

Exercise 3.3.5. What is the element category of a presheaf on a monoid ? A group ?

Exercise 3.3.6. What is the element category of a presheaf on (the path category of) a graph ?

Exercise 3.3.7. Prove that El(F) is indeed a category. The projection of the element category El(F) is defined by π : El(F) C by π(A,x) = A for all object (A,x) El(F) and π(f,(A,x),(B,y)) = f for all arrow (f,(A,x),(B,y)) in El(F). Prove that π is a functor.

Prove π satisfies the additional property that for all Y El(F) and f : A π(Y ) in C there is a unique X El(F) and arrow h : X Y such that π(X) = A and π(h) = f.

Remark 3.3.8. The element category of a functor G : C Set can be defined similarly, though reversing its arrows. The resulting projection is then what is known in category theory as an opfibration.

The projection of the element category of a presheaf is a fibration, a notion formalized below.

Definition 3.3.9 (Discrete fibration). Let C and D be two small categories. A functor F : D C is called a (discrete) fibration when for every Y D for every f : A F(Y ) in C there is a unique X D and h : X Y in D such that F(X) = A and F(h) = f.

Exercise 3.3.10. Prove that for every fibration F : D C there is a presheaf G : Cop Set such that D is isomorphic to El(G) with F~=π.

Remark 3.3.11. The presheaf deriving from a fibration F could be denoted by F-1. Then Exercices 3.3.7 and 3.3.10 suggest that fibrations and presheaves are equivalent notions.

Such an intuition can be turned into a categorical equivalence. We examine below the somewhat more explicit case of the category of element categories of presheaves on C.

Exercise 3.3.12. What is the element category of Hom(A, _) ? What is the element category of Hom(_,B) ?

Exercise* 3.3.13. Let F,G : Cop Set be two presheaves on C a poset and let El(F) and El(G) be their element categories.

Let α : F G be a natural transformation. Let θα : El(F) El(G) defined for every (u,x) El(F) by θα(u,x) = (u,αu(x)) and by θα(f,(u,x),(v,y)) = (f,(u,αu(x)),(v,αv(y))) for all arrows (f,(u,x),(v,y)) in El(F). Prove that θα is a well defined functor that preserve the projection, i.e. π θα = π.

Conversely, let θ : El(F) El(G) be a functor that preserves π. Proves that there is a unique natural transformation α : F G such that θ = θα.

Exercise 3.3.14. Deduce from the above that the category FibD(C) of discrete fibrations over C and projection preserving functors is equivalent to the category Psh(C) of presheaves on C and natural transformations.

Exercise* 3.3.15 (Yoneda embeddings). Prove that both

                        op            o                  op
Y = λY.Hom (_, Y) : C → [C ,Set]  and  Y = λX.Hom  (X, _) : C →  [C, Set]
defines functors. Show that these functors are full and faithfull.

Remark 3.3.16. Observe that the identity IdC : C C is a fibration therefore C is indeed (isomorphic to) the element category El(IdC). To which extent this reformulates Yoneda embedding above within the category El(C) of element category of functor on the category C (or the category Fib(C) of fibration – as defined above – to C).

3.4 Composing natural transformations and functors

Definition 3.4.1 (Horizontal composition). Let F,G : A B and H,K : B C. Let α : F G and β : H K be two natural transformation. The horizontal composition β ⋆ α is defined by (β ⋆ α)A = βF(A) αA for every A A.

Exercise 3.4.2. Prove that β ⋆ α is indeed a natural transformation β ⋆ α : H F K G. For such a purpose, draw all the necessary commuting diagrams. Check that the horizontal composition is associative.


SVG-Viewer needed.


Figure 11: Horizontal composition of natural transformations.


Exercise 3.4.3 (Mixed composition). How behaves the horizontal and vertical compositions of natural transformations when one of the natural transformation is the identity ? In the horizontal case, show it induces a left (or right) composition/action of a functor on a natural transformation.

With F : A B, G,H : B C with α : G H and K : C D we may write αF : G F H F, : K G K H and KαF : K G F K H F for such compositions.


SVG-Viewer needed.


Figure 12: Mixed composition of functors and natural transformations.


Remark 3.4.4. This mixed composition eventually leads to an example of a higher order category that goes out of the scope of the present “basics”.

4 Diagram, limits and representations

4.1 Diagrams

Definition 4.1.1 (diagram). Let C be a category and G a graph with associated path category Path(G). A diagram is a functor F : Path(G) C.

Exercise 4.1.2. Check that a diagram is fully determined by the images of the vertices and the arrows (one arrow path) of G. In other words, a diagram can simply be defined as a labeling of G, its vertices by objects, its edges by (well-typed) arrows.

Definition 4.1.3 (Commutation property). A diagram F : Path(G) C is a commuting diagram when for every pair of paths p1,p2 in Path(G) we have F(p1) = F(p2).

Exercise 4.1.4. Check that, as already mentioned, every composition of functions along a cycle from a vertex in a commuting necessarily equals the identity on the label of that vertex.


SVG-Viewer needed.


Figure 13: Gluing diagrams.


Exercise* 4.1.5. Let G1,G2,G be three graphs and let φ1 : G1 G and φ2 : G2 G be two graph morphisms. Let H1 : Path(G1) Path(G) and H2 : Path(G2) Path(G) be the two induced functors, i.e. H1 = Path(φ1) and H2 = Path(φ2) (see 2.5.8). Let F1 : Path(G1) C and F2 : Path(G2) C be two commuting diagrams. Assume there is a diagram F : Path(G) C such that F1 = F H1 and F2 = F H2 as depicted in Figure 13. Under which (sufficient) conditions the diagram F commute ? Are these conditions necessary ?

4.2 Constant diagram, cones and natural transformations

Definition 4.2.1 (Constant diagram). Let G be a graph and C be a category. Let X C. The constant diagram ΔX : Path(G) C is the diagram induced by ΔX(v) = X and ΔX(e) = idX for all v G and e in G.

Definition 4.2.2 (Cones). Let G be a graph. Let F : Path(G) C be a diagram. A cone on F is an object X C and a collection of arrow αv : X Xv in C, one for each v G such that αw = F(e) αv for all e : v w in G.


SVG-Viewer needed.


Figure 14: Commuting diagrams of a cone (X,αv)vG, one for each edge e : v w in G.


Exercise 4.2.3. Prove that there is a bijection between cone from X C to F and natural transformation from ΔX to F.

Definition 4.2.4 (Co-cones). Let G be a graph. Let F : Path(G) C be a diagram. A co-cone on F is an object X C and a collection of arrow αv : Xv X in C, one for each v G, such that αv = αw F(e) for all e : v w in G.

Exercise 4.2.5. Prove that there is a bijection between co-cones from F to X C and natural transformations from F to ΔX.


SVG-Viewer needed.


Figure 15: Commuting diagrams of a co-cone (X,αv)vG, one for each edge e : v w.


4.3 Representable functors

Definition 4.3.1 (Representable functors). A functor F : C Set is representable when there exists A C such that F~
=Hom(A, _). A representation for F is the pair (A,α) where α : F~
=Hom(A, _) is a natural isomorphism.

Dually, a functor G : Cop Set is representable when there exists B C such that G~
=Hom(_,B). A representation for G is the pair (B,β) where β : G~
=Hom(_,B) is a natural isomorphism.

Exercise 4.3.2. Under which condition the empty functor that maps every object to the empty set and every arrow to the empty arrow is representable as a contravariant functor Hom(_,B) or as a covariant functor Hom(A, _).

Exercise 4.3.3. Prove that the functor Hom(_ × Y,Z) : Set Set is representable for any choice of sets Y and Z.

4.4 Limits and colimits

Definition 4.4.1 (Limit). The limit of a diagram F : G C, when it exists, is a representation

lim F = (B,β)
←-
for the (contravariant) functor Nat(Delta_,F), i.e. Nat_,F) Hom(_,B) via β. By abuse of notation, the object B is often denoted by lim
← -F.

Definition 4.4.2 (Colimit). The colimit of a diagram F : G C, when it exists, is a representation

l-im→ F = (A,α)
for the (covariant) functor Nat(F,Delta_), i.e. Nat(F,Δ_,F) Hom(A, _) via α. By abuse of notation, the object A is often denoted by l-im→F.

Exercise 4.4.3 (Typical limit/colimit shapes). Examine the limits (or the colimits) of diagram on the following graphs:

Rephrase each of the above notions in terms of the existence of certain cones/co-cones (object and arrows) that are universal/co-universal for the corresponding classes of cones/co-cones, i.e. through which these cones/co-cones uniquely factorizes.

Exercise* 4.4.4. Rephrase the general definition of limits (colimits) in terms of the existence of certain cone (co-cone) through which every other cone (co-cone) factorizes.

Exercise 4.4.5 (Limit in Set). Let F : G Set be a diagram. Prove that, we have

       {                                          }
             ∏
l←im- F =  x ∈    F(v) : ∀e : v → w ∈ G1, x[w ] = F(e)(x[v])
            v∈G
where x[v] denotes the vth component of an element x vGF(v).

Exercise* 4.4.6. Generalize the above by proving that a category C that has all (small/finite) products and equalizers has all (small/finite) limits.

Exercise 4.4.7. With F : G Set, examine the validity of the following assertion:

lim F ~= Nat(Δ{*},F )
←-

Exercise 4.4.8 (Colimit in Set). Let F : G Set be a diagram. Prove that, we have

       ∑
li-m→ F =    F (v)∕ ≃F
       v∈G
where vGF(v) = vG{vF(v) is the disjoint sum of the images of the vertices by F, and F is the least equivalence relation over this disjoint sum such that
(v,x ) ≃F (w,F (e)(x))
for all edges e : v w in G and element x F(v).

Remark 4.4.9. Observe the analogy between the disjoint sum definition and the element category construction on a covariant functor. Observe that the equivalence defined above is sort of a categorical congruence (the least one) with respect to the (forward image) arrows of the element category.

Exercise 4.4.10 (Limit from products and equalizers). Let F : C D with small C. Prove that, when it exists, the limit of F is the equalizer of the following two functors:

⟨     ⟩P     ∏           ∏
 πcod(f) f∈C1 :   F (C) →     F (cod(f))
             C∈C        f∈C1
and
⟨         ⟩      ∏          ∏
 f ∘ πdom (f) Pf∈C1 :  F (C ) →     F(cod(f))
                C ∈C        f∈C1
where fi : A AiP is the unique arrow from A into iAi through which the collection of arrows {fi : A Ai}i factorizes. This generalizes the parallel application of set functions from the same set.

Exercise 4.4.11 (Co-limit from co-products and co-equalizers). Let F : C D with small C. Prove that, when it exists, the co-limit of F is the co-equalizer of the following two functors:

⟨ι     ⟩S   : ∑   F(dom(f)) → ∑   F(C)
  dom (f) f∈C1 f∈C              C∈C
                 1
and
⟨        ⟩S     ∑               ∑
 ιcod(f) ∘ f f∈C1 :   F(dom (f)) →     F(C)
               f∈C1             C∈C
where fi : Ai AS is the unique arrow from iAi into A through which the collection of arrows {fi : Ai A}i factorizes. This generalizes the alternative application of a set of functions from the sum of their domain.

Exercise 4.4.12 (Parametrized limit and colimit). Prove that, given F : A×B C, we have

           (    (              ))
 lim F ~= lim   λX.  lim λY.F(X,Y )
A←-×B    ←A-       ←-B
and
           (    (              ))
      ~
 li-m→ F = l-im→   λX.  l-im→ λY.F(X,Y )
A ×B     A         B
for small A and B.

Exercise 4.4.13 (Limits on presheaves). Prove that the category Psh(C) of presheaves on C and natural transformation has all small limits and colimits, i.e. limits and colimits over diagram of the form G Psh(C) for small graphs.

Hint: limits/colimits over presheaves can be computed object-wise. More precisely, given F : D (Cop Set) a diagram on Psh(C), for every C C, let FC : D Set be the diagram on Set defined by FC(D) = F(D)(C) and, for every g : D E in D, FC(g) defined as the Cth component of the natural transformation

F(g) = {FC (g) : F(E )(C ) ⇒ F (D)(C)}C∈C : F (E ) ⇒ F(D)
Check that FC : D Set is indeed a functor. Define then lim
←-F to be the presheaf given by
                    ∏
(lim F)(C) = lim FC ⊆    FC (D)  and  (limF )(f )(x) = {F (D)(f)(xD )}D∈D
 ←-        ← -     D ∈D              ←-
for every f : A B and every x = {xD FB(D)}DD li←m-FB. Check that l←im-F is indeed a presheaf and the limit via the natural transformation given by the projections {πD}DD as depicted in Figure 16.


SVG-Viewer needed.


Figure 16: The limit cone of the presheaf diagram F.


In Figure 16 we also depict another cone from (H,α) to F with α = {αD : H F(D)}DD and, for every D D, αD = {αDC : H(C) F(D)(C)}CC.

4.5 Exponent in cartesian category

Let C be a cartesian category, that is, a category that has a terminal object 1 and binary categorical products A × B for all A,B C.

Exercise 4.5.1. Given f : X Y and g : X′ → Y show that there is a unique arrow f × g : X × X′ → Y × Y through which f π1 : X × X′ → Y and g π2 : X × X′ → Y factorizes via Y × Y , i.e. f π1 = π1 f × g and g π1 = π2 ftimesg.

Definition 4.5.2. Let C be a cartesian category and B,C C. The exponent of C by B in C is a object CB C and a natural isomorphism α : Hom(_ × B,C)~=Hom(_,CB).

When the cartesian category C has all exponent, we say that C is a cartesian closed category.

Exercise 4.5.3. Let P be a poset seen as a category. Prove that for all a,b,c P we have:

Exercise 4.5.4. Let P be a bi-cartesian closed poset, that is, a cartesian closed poset that also has an initial element and all co-product. Prove that for all a,b,c P we have:

Remark 4.5.5. Bi-cartesian closed poset P as above are known in the literature as a Heyting Algebra. This notion plays a fundamental role in logic, especially because of the (intuitionistic) negation defined by ¬a = 0a. Such a negation does not need to be idempotent. Such a notion also arises in topology as quickly detailed below.

Assume that P is the poset of open sets on a topological space X ordered by inclusion. These open sets indeed form a Heyting algebra with finite intersection as meet and arbitrary union as join. Then, the “negation” of every open x P can be defined as the interior of its complement, that is, the greatest open set included into its complement.

Observe that such a topological intuition can also be dualized by considering instead the poset of closed subsets of X ordered by reverse inclusion with finite union as meet and arbitrary intersection as join. In this case, the “negation” of a closed set is the closure of its complement, that is, the least closed subset that contains its complement.

Exercise 4.5.6. Assume that the exponent (CB) is defined. Prove that there exists an arrow eval : CB × B C such that, for all f : A × B × C there is a unique arrow f* : A CB such that eval (f*× idB) = f.

Hint : consider the naturality diagram of α-1 : Hom(_,CB) Hom(_ × B,C) in Figure 17 and take eval = αCB-1(idCB) and f* = α(f).

We see that eval (f*× idB) = f and unicity follows from the fact that α therefore α-1 is a natural isomorphism.


SVG-Viewer needed.


Figure 17: Naturality of α-1 with f* = α-1(f) and eval = αCB-1(idCB).


Exercise 4.5.7. Prove that in Set, the exponent CB = B C, the set of function from B to C, with eval(f,b) = f(b) for all f CB and b BC.

4.6 Yoneda Lemma

The notion of representation plays a key role for defining limits, colimits and exponent. Moreover, the diagram chasing techniques used in Figure 17 is a particular case of a fairly general technique for analyzing or proving representation facts. This technique is known as the Yoneda lemma.

Lemma 4.6.1 (Yoneda). Let F : Cop Set be a functor. Let B C be an object of C. Then the function θ : Nat(Hom(_,B),F) F(B) defined by θ(α) = αB(idB) for every α : Hom(_,B) F is a bijection natural in both B and F, i.e. Nat(Hom(_,B),F) and F(B) are naturally isomorphic via θ.

Proof. Let α : Hom(_,B) F. Let A C and h : A B. This situation is depicted Figure 18.


SVG-Viewer needed.


Figure 18: Naturality of α with θ(α) = αB(idB).


Injectivity. By definition of natural transformation, we have αB(hidA) = F(h)(αA(idA)) that is αA(h) = F(h)(θ(α)) for all h : A B in C. As this holds for arbitrary A C and h Hom(A,B) this means that α is fully determined by θ(α) therefore θ is injective. Surjectivity. Conversely, given b F(B), there is the natural transformation αb defined as the collection of functions {αAb : Hom(A,B) F(A)}AC defined by αAb(h) = F(h)(b) for all A C and h Hom(A,B). The fact it is a natural transformation immediately follows from the fact that F is a contravariant functor. Since, by definition, we have θ(αb) = b this implies that θ is surjective. To be completed. It remains to prove naturality in both B and F. __

Exercise 4.6.2. (Re)prove, using Yoneda Lemma, that y : C (Cop Set) defined by y(C) = Hom(_,C) is a full and faithfull embedding of C into Psh(C).

Exercise 4.6.3. Prove, using Yoneda lemma (see hint below), that the category Psh(C) of presheaves on C and natural transformation is cartesian closed.

Hint, expanded from [3], p 170 : let F,G Psh(C). We look for a presheaf GF Psh(C) such that

Nat(_ × F,G) ~= Nat(_,GF )
For every C C there is the presheaf hC = Hom(_,C) and, by Yoneda Lemma, we have
         F  ~  F
N at(hC,G  )= G  (C )
therefore, by combining the above equivalence, this suggest to define GF by
  F
G  (C) = Nat(hC ×F, G)
for every C C. Then, for every f : A B, we need to define GF(f) : GF(B) GF(A) that is,
GF (f )(α) : hA × F ⇒ G
for every α : hB × F G. In order to simplify notation, clarity, let us write βf = GF(f)(α).

For every C C we must have βCf : Hom(C,A) × F(C) G(C) so, for every g Hom(C,A) and x F(C) we simply put

βfC(g,x ) = αC(f ∘g,x)
which is well typed since f g : C B.

Checking that its is indeed an exponential is left as exercise. The remark below give some hints on how to proceed in proving the expected equivalence Nat(_×F,G)~
=Nat(_,GF); just follow the types !

Remark 4.6.4. In the exercise above, we have defined GF(f) just by making a type analysis, so that the available elements combine correctly, somehow regardless of what actually are these elements. This is a typical type drive reasoning (aka proof) that plays a major role in type-driven programing where the moto is: correctness by well-typeness ! A motto we just have followed in this construction of the exponential in Psh(C).

5 Elementary topoi

We shall briefly survey the notion of topos that arises from the notion of presheaves and sheaves on a Grothendieck site. There is a lot more to be said. The reader is invited to further reading. In this presentation, we follow some elements of MacLane and Moerdijck [5].

5.1 Sub-objects

Let C be a category. Remember that f : A B is a monomorphism when, for all C C, the function f _ : Hom(C,A) Hom(C,B) is injective .

Definition 5.1.1. Let f : B A and g : C A be two monos into A. Define f g when there is h : B C such that f = g h.

Exercise 5.1.2. Prove that h : B C as above is necessarily a monomorphism. Prove that the relation defined above is a pre-order, i.e. it is reflexive and transitive. The relation f g defined when f g and g f is thus an equivalence relation.

Definition 5.1.3 (Subobjects). A subobject of A in C is the equivalence class of a mono [f : B A] under the above pre-order equivalence. The collection of subobject of an object A is denoted by Sub(A).

Exercise 5.1.4 (Subobjects in Set). Show that the inclusion functions incX : X Y for every X Y are canonical representatives of the subobjects (subset) of a set Y .

Exercise 5.1.5 (Subobjects in a poset). Let P be a poset. What are the monos in P ? Let x P. What are the subobjects of x P ?

5.2 Subobject classifier

Definition 5.2.1 (Pullback). Let f : X Z and g : Y Z. The pullback of (f,g) is a pair of arrow (f: X ×ZY X,g: X ×ZY Y ) such that every other pair (f′′ : Z′→ X,g′′ : Z′→ Y ) such that f f′′ = g g′′ uniquely factorizes through (f,g).


SVG-Viewer needed.


Figure 19: Pullback.


Then we say that fis the pull back of g along f and gis the pullback of f along g.

Exercise 5.2.2 (Subobject functor). Assume that C has all pullbacks. Let h : Y X in C. (1). Let f : Z X be a monomorphism and let g : Y ×XZ X the right part of a pullback of (f,h), called the pullback of h along f. Prove that g is mono. (2). Let f: Z′ → X be a monomorphism with f′ ≃ f as subobject. Prove that g: Y ×XZ′→ X is the pullback of h along fif and only if g′≃ g as subobject. (3). Deduce from the above that there is the well defined function Sub(h) : Sub(X) Sub(Y ) that maps every subobject [f : Z X] Sub(X) to [g : Y ×XZ X] Sub(Y ) given by any pullback g of h along f. (4). Check that Sub(idX) = idSub(X) and Sub(h) Sub(h) = Sub(h′∘ h) whenever h′∘ h is defined, therefore, assuming that Sub(X) is a set for all X C, there is the contravariant functor Sub : Cop Set.

Definition 5.2.3. Assume that C has all pullbacks. A subobject classifier is an object Ω C together with a natural isomorphism Sub(_)~=Hom(_,Ω).

Exercise 5.2.4. Assume that C also has a terminal object 1. (1). Assume a subobject classifier ). Let true : 1 Ω defined as α1(id1). Prove that for all mono f : X Y there is a unique Xf : Y Ω such that f is the pullback of true along Xf. (2). Conversely, assume there is true : 1 Ω such that for all mono f : X Y there is a unique Xf : Y Ω such that f is the pullback of true : 1 Ω along Xf : Y Ω. Check that if f′≃ f as a subobject then Xf = Xf. Deduce from the above that ,{αX}XC) is a subobject classifier with αX : Sub(X) Hom(X,Ω) defined for every [f] Sub(X) by αX([f]) = Xf.


SVG-Viewer needed.


Figure 20: The subobject classifier pullback square.


Exercise 5.2.5. What is the subobject classifier in Set ?

Exercise 5.2.6. Is there a subobject classifier in a poset ? In the category Poset of posets and monotone functions ?

Exercise 5.2.7. Prove that a natural transformation α : F G between two presheaves on C is mono/iso if and only if each of its component αC : F(C) G(C) for C C is a injection/bijection.

Definition 5.2.8 (Subfunctor). Let F,G : Cop Set be two functors. We say that F is a sub-functor of G, which is simply denoted by F G, when:

for all objects C,D C and arrows f : C D in C.

Exercise 5.2.9 (Subobjects in Psh(C)). Let F,G : Cop Set. Check that F is a subfunctor of G if and only if there is a injective (aka mono) natural transformation α : F G. Deduce that every subobject of G contains one and only one subfunctor.

Exercise 5.2.10. Prove, using Yoneda Lemma, that Psh(C) has a subobject classifier defined by Ω(C) = {F Hom(_,C)}, that is, the functor that maps every object C to the set of subfunctor of the homset presheaf y(C) = Hom(_,C). In particular, what is the characteristic function XF : G Ω of any subfunctor F G.

5.3 Power object

Let C be a category with all finite limit.

Definition 5.3.1. Let A C. A power object for A C is an object PA C and a natural isomorphism α : Hom(A × _,Ω)~=Hom(_,PA).

Exercise 5.3.2. What is the power object and the associated natural transformation in Set ? Hint: remember that Ω = {0,1} therefore any function f : A × B Ω uniquely determined a relation Rf = f-1(1) A×B. Observe that there are at least two (equivalent) possibilities for defining α.

Exercise 5.3.3. Check that there is the natural isomorphism 1 × B~=B. Deduce that Hom(_,Ω)~=Hom(_,P1) therefore Ω~=P1.

Remark 5.3.4. Let A) be the power-object of A C. By definition of subobject classifier Ω, there is β : Sub(A× _)~
=Hom(A× _,Omega) therefore αβ : Sub(A× _)~
=Hom(_,PA).

Exercise 5.3.5. Following the above remark, describe the power object in Set and the associated natural transformation α β.

Hint : every relation (subobject) R A × B defines a fonction fR : A P(B) defined by fR(a) = {b B : (a,b) R.

Exercise 5.3.6. Let A) be the power-object of A C. Let inA : A×PA Ω defined by inA = αPA(idPA)and let h :A A × PA be the (right part of) the pullback of (inA,idΩ).

Prove that for every monomorphism f : R A × B the morphism XR = α(Xf) : B PA is the unique morphism from B PA such that, given g : A×B the unique morphism given by the universality property of the pullback A, the pair (f,g f) is the pullback of (id × XR,h) as depicted in Figure 21.


SVG-Viewer needed.


Figure 21: Pullback diagram of the power-object PA.


Exercise 5.3.7. With the help of the previous exercise, prove that a power object for A can equivalently be defined as an object ΩA C and a monomorphism A A×ΩA such that for every object B C and monomorphism R A×B there is a unique morphism XR : B ΩA such that R is the pullback depicted in Figure 22.


SVG-Viewer needed.


Figure 22: Characteristic pullback of the power-object ΩA.


Exercise 5.3.8. What are the membership relations and characteristic functions of relations in Set ?

Exercise 5.3.9. What are the power objects, the membership relations and characteristic functions of relations in Poset ?

Exercise 5.3.10. What are the power objects, the membership relations and characteristic functions of relations in a poset P ?

Exercise 5.3.11. What are the power objects, the membership relations and characteristic functions of relations in Psh(C) ?

5.4 Elementary topos

Exercise 5.4.1. Assume that C has all finite limits and exponents and has a subobject classifier Ω. Prove that for every A C, the subobject classifier ΩA is indeed the exponent of Ω by A.

Exercise 5.4.2. Assume that C has all finite limits and power objects. Prove that Ω1 is a subobject classifier and C is cartesian closed.

Definition 5.4.3. An elementary topos is a category C that has all finite limits and power objects or, equivalently, that has all finite limits, exponents and subobject classifier.

Exercise 5.4.4. Check, from exercises above, that both Set and Psh(C) are elementary topoi.

Exercise* 5.4.5 (Co-completion of C). Prove that Psh(C) is co-complete, i.e. it has all small co-limits. Let then F : Cop Set. There is the element category El(F) equipped with the (discrete fibration) projection functor πF : El(F) C. Prove that:

F ~= l-im→ y∘ πF
where y : C Psh(C) is the Yoneda embedding defined by y(C) = Hom(_,C) for every C C.

More generally, prove that, for every functor A : C D where D is co-complete and locally-small, there is, up to isomorphism, a unique functor G : Psh(C) D such that G|y(C)~
=A, i.e. G restricted to the full and faithfull embedding of C into Psh(C) define by y(C) is isomorphic to A.

To which extent this says that y : C Psh(C) is initial among functors from C into (locally small ?) co-complete categories and colimit preserving functors ?

Hint: define G by G(F) = l-im→A πF for every F Psh(C).

Remark 5.4.6. It is said (see [5]) that Yoneda defined the category of elements of a presheaf (in order to prove such a result ?) before Grothendieck defined “his” construction that lifts the category of elements construction to arbitrary functor F : C Cat. This Grothendieck construction, much related with the general notion of fibration, is reviewed at the end of these notes (see [?] for many more details).

5.5 Grothendieck topologies

Let C be a small category.

Definition 5.5.1. A sieve S on C C is a is a “backward closed” collection of arrows of C to C, i.e. for all g : B C in S and f : A B in C then g f : A C in S.

Exercise 5.5.2. Check that a sieve over a poset P on x P is simply a downward closed subset of P below x, i.e. y x for all y P.

Exercise 5.5.3. Check that every sieve S on C C can be seen as a subfunctor FS Hom(_,C) by putting FS(A) = {f S : dom(f) = A} for every A C and FS(f) = _ f : S(B) S(A) for every f : A B.

Conversely, prove that every subfunctor F Hom(_,C) is uniquely determined by the set SF = {f C1 : A C,f S(A)} which is a sieve on C.

In other words, sieves on C and subfunctors of Hom(_,C) are equivalent notions.

Exercise 5.5.4 (Sieve functor). When S is a sieves on C and h : B C is a morphism, prove that

 *
h (S) = {f : A → B ∈ C1 : h ∘f ∈ S}
is a sieve on B.

It follows that there is the functor2 Sieve : Cop Set that maps every object C C to the set of sieves on C and that maps every h : A B to the function over sieves h*.

Check that we indeed have id* = id and f*g* = (g f)*.

Definition 5.5.5. Let C be a category and C C. A Grothendieck topology over C is an assignment of a collection of sieves sieves J(C), one for each C C, such that:

A site is a pair (C,J) where J is a Grothendieck topology over C.

Exercise 5.5.6. Check that the following assignment are Grothendieck topologies:

Exercise* 5.5.7. We have already seen that sieves on x P for a poset P are the downward closed subsets of P below x. A subset X P is directed when X is non empty and for every x,y X there is z X such that x,y z.

A set X P is closed in the Scott topology when X is downward closed and for every Y X directed such that Y exists then Y X. Accordingly, the Scott-closure of a set X P is the least closed subset X P such that X X.

Define for every x P the collection of sieves Js(x) to be the set of all downward closed subset X P such that X = x, the downward closure of x.

Prove that Js is a Grothendieck topology.

Exercise 5.5.8. Let J be a Grothendieck topology. Check J induces a functor J : Cop Set that maps every object C C to the set of sieves J(C) on C and that maps every arrow h : A B in C to the arrow h* restricted to J(B) into J(A). Observe that Ji J (by maximality) and J Jd (by stability) as subfunctors. Are there subfunctors of Jd (that we also named Sieve above) that are not Grothendieck topologies ?

5.6 Sheaves

Definition 5.6.1 (Matching family). Let J be a topology on C and F : Cop Set be a presheaf. Let C C and S J(C) a sieve on C. A matching family for S on F is a collection of element {xf F(A)}f:ACS such that for all g : B A and f : A C S we have xfg = F(g)(xf).

Exercise 5.6.2. We have seen that every sieves on C C can be seen as a subfunctor of Hom(_,C). Check that matching families for S on F can equivalently be defined as natural transformations S F.

Definition 5.6.3 (Sheaf on a site). Let (C,J) be a site. A presheaf F : Cop Set is a sheaf for J when, for any object C C, any sieve S J(C), any matching family {xf}fS of F on S there is a unique x F(C) such that xf = F(f)(x) for all f S. The element x is called the amalgamation of the matching family {xf}fS.

Exercise 5.6.4. Check that every presheaf F : Cop Set is a sheaf for the indiscrete topology on C.

Exercise 5.6.5. Check that if F : Cop Set is a sheaf for a topology J, then, for every C C such that J(C) = , we must have F(C) a singleton. Deduce that every sheaf F for the discrete topology is, up to isomorphism, the constant sheaf Δ{*}.

Theorem 5.6.6. For any topology J on C, the category Sh(C,J) of sheaves for J and natural transformation is an elementary topos.

Exercise 5.6.7. Consider proving the above theorem.

Remark 5.6.8. The converse is not true. A topos that is equivalent to some Sh(C,J) is called a Grothendieck topos. Indeed, such a topos has all small limits and colimits which is not require for an elementary topos.

6 Adjunction

6.1 Definition and examples

Definition 6.1.1. Let F : A B and G : B A. We say that F is the left adjoint of G, equivalently G is the right adjoint of F, a property denoted by F G when there is the isomorphism

             ~
Hom (F (X ),Y)= Hom (X, G(Y))
natural in both X A and Y B.

Exercise 6.1.2. Let P,Q be two posets, f : P Q and g : Q P two isotone functions, i.e. morphisms in Poset. Proves that f g if and only if

      ∧                                ∨
f(x ) =  {y ∈ Q : x ≤ g(y)} and/or g(y) =  {x ∈ P : f (x) ≤ y}
for all x X and y Y . In particular, the function f (resp. g) is uniquely defined by the function g (resp. f).

Exercise 6.1.3. Prove that if F G and F Gthen G and Gare naturally isomorphic. In other words, a left adjoint F defines its right adjoint up to isomorphism.

Similarly, prove that if F G and F′⊣ G then F and Fare naturally isomorphic. In other words, a right adjoint G defines its left adjoint up to isomorphism.

Exercise 6.1.4 (Unit and co-unit). Assume that F G. Taking F(X) for Y yields a isomorphism α : Hom(F(X),F(X))~
=Hom(X,GF(X)). Prove that η : IdA GF defined by ηX = αX(idF(X)) : X G F(X) for every X A is a natural transformation called the unit of the adjunction F G.

Taking instead G(Y ) for X yields a isomorphism β : Hom(FG(Y ),Y ~
=Hom(G(Y ),G(Y )). Prove that ϵ : F G IdB defined by ϵY = β-1(idG(Y )) : F G(Y ) Y for every Y B is a natural transformation called the co-unit of the adjunction F G.

Check that ϵF = IdF and ηG = IdG (see mixed composition of functors and natural transformations).

Exercise 6.1.5 (Adjunction by unit and co-unit). Let F : A B and G : B A. Prove that if there are natural transformations η : IdA G F and ϵ : F G IdB such that ϵF = IdF and ηG = IdG then we necessarily have F G.

7 Further topics

7.1 Grothendieck construction

Definition 7.1.1 (Grothendieck construction). Let F : C Cat be a functor. The Grothendieck category C F is defined with:

with composition defined by (g,G) (f,F) = (g f,G F(g)(F)).

Remark 7.1.2. The soundness of this definition deserves a diagram that is depicted Figure 23.


SVG-Viewer needed.


Figure 23: Type checking the composition (g,G) (f,F) in Grothendieck construction


Exercise 7.1.3. Check that in the case every F(A) is a discrete small category for all object A C, i.e. a set equipped only element identities, and, therefore, F(f) is a set function for all f in C, then C F is the element category El(F) of F.

Exercise* 7.1.4. Study the categorical properties of the first projection π : CF C ? Give sufficient conditions over a functor π : D C for π-1 to induce a functor from C into Cat in such way that D~=C π-1. Are these conditions necessary ?

Exercise* 7.1.5. Recover the usual semi-direct product M N of two monoids M and N via an action α of M on N in terms of a Grothendieck construction of the form M Fα for some well chosen functor Fα : M Cat.

Exercise* 7.1.6. Let F,G : C Cat be two functors. Show that there is a bijection between natural transformations α : F G and functors F : C F C G such that π = π F.

References

[1]   M. Barr and C. Wells. Category Theory for Computing Science, 3rd edition. Centre de Recherche Mathématique (CRM), Montréal, 1999.

[2]   P. Johnstone. Sketches of an Elephant: A Topos Theory Compendium, volume 43,44 of Oxford Logic Guide. Oxford University Press, 2002.

[3]   J. Lambek and P.J. Scott. Introduction to Higher-Order Categorical Logic. Cambridge Studies in Advanced Mathematics. Cambridge University Press, 1988.

[4]   S. Mac Lane. Categories for the Working Mathematician. Number 5 in Graduate Texts in Mathematics. Springer, 1971.

[5]   S. Mac Lane and I. Moerdijk. Sheaves in Geometry and Logic. Universitext. Springer, 1992.