Keywords: Universal elements, universal arrows, representations 3. Universal elements, universal arrows, representations

Basic notions

Corollary 2.15. Let C be a locally small category. Then, ∀ , ∈ Ob C , : → is an isomorphism ⇔ Hom C (-, ) : Hom C (-, ) → Hom C (-, ) is an isomorphism.

Corollary 2.16. Let C be a locally

Introduction

This course will introduce category theory from an adjunction-driven point of view, which is somewhat unusual.

This course is a modest introduction to category theory, written as the first author discovered this topic while starting his PhD.

Note that this document is obviously not exhaustive. This non-exhaustivity comes from the context of the PhD; the first author did not need to learn about n-categories or categorical logic, so there is nothing about it here.

This document is also intended to be the starting point of a book. However, it is currently in an early stage (see Section 14 to convince yourself that this document needs more work to be done).

Also note that this Crash Course has nothing to do with Bartosz Milewski's Crash Course in Category Theory.

The arrow is an epimorphism, or is epic, if, for all , :

→ , • = • ⇒ = :

Example 1.12 (Epis and monos in Sets). In Sets, suppose : → is monic. Let , ∈ such that ( ) = ( ). Let and be the functions: :

1 -→ ↦ -→ and :

1 -→ ↦ -→

As is monic, we have

• = • ⇒ = ⇒ = .
Conversely, if is injective, then for all , :

→ , if • = • , then for all ∈ , • ( ) = • ( ) which by injectivity means ( ) = ( ) and then = . Now, if : → is epic, let ( ) : → 2 be the characteristic function of ( ) (the image of ), and let cste 1 : → 1 be the constant function. We have ( ) • = cste 1 • , which by epicity gives ( ) = cste 1 , and thus = ( ), from which we deduce the surjectivity. If : → is surjective, let , : → such that • = • . For all ∈ , there exists an such that = ( ) and • ( ) = • ( ) = ( ) = ( ), which gives = , and is epic.

In summary, in Sets, monomorphisms are exactly injective functions, and epimorphisms are exactly surjective functions.

Example 1.13 (Epis and monos in a proset). In a proset category ( , ), every arrow is monic and epic. This is due to the unicity of the arrow between two objects. Note that, here, the arrows that are both monic and epic, are not necessarily isomorphisms.

Remark 1.14 (Epis and monos in other categories). In most "structured sets" categories, for example, in Monoids, in Groups, in Lin F , the monomorphisms are exactly the injective morphisms. However, the epimorphisms are not exactly the surjective morphisms. For more information, see [ From Remark 1.12, we deduce that a function in Sets is an isomorphism if and only if it is both monic and epic. However, the "if and only if" does not hold for most categories (see Example 1.13 or [1, Section 2.1.1, pp32-33] for an example). What does hold is the following: Corollary 1.16. If : → is an isomorphism, then is both a monomorphism and an epimorphism.

We now go back to studying a bit more about categories. We consider here the size of categories, which might be a concern of a reader with set-theoretic background.

Nothing in Definition 1.1 implies that Ob C or Mor C should be sets (nor should be Hom C ( , )). In fact, Ob Sets is not a set. In that sense, categories can be as big as possible. However, in the scope of this course, we will only use somewhat small categories, in the following sense. Definition 1.17 (Small, locally small and large categories [2]). A category C is small if both Ob C and Mor C are sets; otherwise, it is large.

A category C is locally small if, for all objects , ∈ C , the Hom-set Hom C ( , ) is a set.

Example 1.18. Sets is large but locally small.

Example 1.19. If ( , ) is a proset, then it is a small (thus locally small) category.

Example 1.20. The following example is inspired from set-theory. If is the -th set of the von Neumann hierarchy [3, Definition 2.1, p. 95], and if is a limit ordinal, then we define the category by:

IMTA-RR-2019-01-SC 5/127

Basic notions

Objects: An object in is any set ∈ Morphisms: A morphism in is any function : → for , ∈

Identities: An identity morphism is an identity function id : → Composition: The composition law for morphisms is the usual composition of functions

We can see as a truncated Sets category. The category is a small category.

Example 1.21. For an example of a large, non-locally small category, see [4].

Remark 1.22. Small categories are locally small (because "sets contain sets").

In this course, we will consider locally-small categories, for a reason explained later. For now, we continue with a few more basic notions.

We also define mappings somewhat similar to functions, or homomorphisms, between categories.

Definition 1.23 (Functor [1]). Let C and D be categories.

A functor : C → D is a mapping from C to D such that:

∀ ∈ Ob C , ( ) ∈ Ob D ∀ : → ∈ Mor C , ( ) : ( ) → ( ) ∈ Mor D ∀ ∈ Ob C , (1 ) = 1 ( ) ∀ : → , : → ∈ Mor C , ( • ) = ( ) • ( )
In other words, a functor : C → D sends the objects (resp. morphisms) in C to objects (resp. morphisms) in D, preserving domains and codomains of morphisms, as well as identities and composition.

Example 1.24 (Functors between prosets). If ( 1 , 1 ) and ( 2 , 2 ) are prosets, then a functor between those two categories is a monotone function such that 1 ⇒ ( ) 2 ( ).

Example 1.25 (Forgetful functors). Every category of structured sets C , for example C = Lin F or C = Fields, comes with a functor : C → Sets that "takes away the structure". For example, if C = Lin F , then it sends a vector space to its underlying set. Such a functor generally has interesting properties as well (but we will have to wait until Section 5.7).

One can interpret a functor C → D as a way to have the picture of the category C into the category D ( [1]). It is the idea behind diagrams as we will see in Section 7.

Remark 1.26. It is important to note here that the image of a category by a functor is not necessarily a category. Consider the following functor:

( ) ↦ → ( ) = ( ) ( ) ( ) ( )
In the domain category, there is no composite • because the domain of is not the codomain of . However, in the image of the functor, we have an arrow ( ) whose domain coincides with the codomain of ( ). If it were a category, it would need a composite arrow (?) = ( ) • ( ), which doesn't exist in the first category.

Of course, we can complete the image of a functor and make it a category.

Sometimes, we come across some functors that behave strangely. Namely, sometimes a functor : C → D may send : → to ( ) : ( ) → ( ) (note the inversion). We will give an example of such a functor. What is happening, is that is actually not a functor C → D but somehow defined on a similar, but "reversed" category of C . Definition 1.27 (Opposite category [1]). Let C be any category. We call opposite, or dual category of C , denoted by C op , the following category:

Objects: An object in C op is an object in C

Morphisms: An arrow : → in C op is an arrow : → in C

Identities: An identity in C op is an identity in C

Composition: The composition law in C op is the same as in C

Basically, the opposite category C op is the same category as C , with inverted arrows.

If a functor : C → D sends : → to ( ) : ( ) → ( ), then is not actually defined on C but rather on C op : : C op → D. However, it is often simpler to consider only functors on C , hence the following notions: Two examples of such functors are the following:

Definition 1.29 (Covariant Hom-set functor [5]). Let C be a (locally small) category, and let ∈ C be an object.

The mapping Hom C ( ) -:

C -→ Sets ↦ -→ Hom C ( , )
defines the covariant Hom-set functor. It sends an object ∈ C to the set Hom C ( , ) of arrows from to , and an arrow : → to the arrow Hom C ( , ) : Hom C ( , ) → Hom C ( , ) in Sets. Definition 1.30 (Contravariant Hom-set functor [5]). Let C be a (locally small) category, and let ∈ C be an object.

The mapping Hom C (-, ) :

C op -→ Sets ↦ -→ Hom C ( , )
defines the contravariant Hom-set functor.

It sends an object ∈ C op to the set Hom C ( , ) of arrows from to , and an arrow : → to the arrow Hom C ( , ) : Hom C ( , ) → Hom C ( , ) in Sets.

Remark 1.31. Their names are not stolen: → Hom C ( ) is a covariant functor and → Hom C ( ) is a contravariant functor.

Note that both Hom-set functors imply C to be locally small. As stated a few paragraphs before, all the categories we will encounter in this course are locally small, unless stated otherwise, because we will often need this functor to be defined.

IMTA-RR-2019-01-SC

7/127

Basic notions

Also note that along this course, we will encounter lots of examples of contravariant functors. This notion may look confusing. With a bit of practice, it is no more a problem.

We continue and end this section with a final basic notion of category theory, namely, natural transformations, which are a kind of mappings between functors. Definition 1.32 (Natural transformation [1]). Let C and D be two categories, and let , : C → D be functors. A natural transformation : → consists of a collection of morphisms in D ( : ( ) → ( )) ∈Ob C such that, for all , ∈ C , and for all ℎ : → , the following square commutes:

( ) ( ) ( ) ( ) ℎ (ℎ) (ℎ) (1)
For each object ∈ C , the morphism is called the -component of . The natural transformation : → can be written in the following diagram:

C D

We denote by Nat ( , ) the collection of all natural transformations between and .

Depending on the context, and for the sake of readability, the -component of a natural transformation can be written as above ( as an index) or ( ) ( as a parameter). Natural transformations can be seen as a way to extract the parameters , and ℎ from ( ), ( ) and (ℎ) and input them into , while preserving arrows. It's a variable substitution.

Remark 1.33. Consider two functors , : C → X , and their respective (categorified) images Im ( ) and Im ( ). A natural transformation : → may be seen as a functor ˆ : Im ( ) → Im ( ) such that:

1. for all object ∈ C , ˆ ( ( )) = ( ) ( ˆ preserves the objects) 2. for all arrow : → ∈ C , ˆ ( ( )) = ( ) with ( ) : ( ) → ( ) and ( ) : ( ) → ( ) ( ˆ preserves the arrows)

ˆ makes the natural transformation diagram (Diagram 1) commute

Note that this view of natural transformations is not standard, but it may help some readers to grasp this notion.

Before introducing the notion of natural isomorphism, we need to make something clear on the nature of natural transformations. Natural transformations are morphisms between functors. Besides, if , : C → D are two functors, then the notation Nat ( , ) actually stands for Hom Func(C ,D) ( , ); however Nat ( , ) is usually more convenient.

Using Definition 1.35 (functor category), and Definition 1.7 (isomorphism), we deduce the definition of a natural isomorphism: Definition 1.36 (Natural isomorphism [1]). Let , : C → D be functors. A natural isomorphism : → is a natural transformation that is an isomorphism in the functor category Func (C , D).

It is easy to see that:

Lemma 1.37. A natural transformation : → is a natural isomorphism whenever the -components : ( ) → ( ) are isomorphisms.

This lemma gives a useful description of what a natural isomorphism is. It makes it easier to look for an inverse. We will use this lemma in the following section. This lemma does not exactly hold for monic or epic natural transformations. In fact, we have only one implication.

Proposition 1.38. Let X and C any categories. Let , : X → C be two functors and let : → be a natural transformation between those two functors.

If for all ∈ X , : ( ) → ( ) is monic (resp. epic), then so is : → .

Proof. Suppose that each -component is monic. The proof is similar when we are considering epic components.

Consider , :

→ such that • = • . ⇔ ( ) ( ) ( )
In terms of components, this means that for all ∈ X , we have

• = • .
As every component is monic, this gives = , and then = . Thus, is monic.

Surprisingly, the converse does not hold in general. In fact, it needs some more properties about the codomain category, but this is far beyond the scope of this crash course.

We have now introduced the basic notions of category theory: categories, hom-sets, isomorphisms, monomorphisms, epimorphisms, opposite categories, (covariant or contravariant) functors, natural transformations. We can now move on to the next section, in which we introduce the very first important result about category theory.

IMTA-RR-2019-01-SC

9/127 2. Yoneda lemma

Yoneda lemma

Given a functor : C → Sets, can we transform it into a Hom-set functor? The answer is provided by the Yoneda lemma. The Yoneda lemma is based on a natural transformation, as illustrated by the following series of figures.

Diagrame incomplet !!!! (C ) (Sets) • ( ) ( ) ( ) • Hom C ( ,-) Hom C ( ,-) Hom C ( , ) ( ) ( )• ( ) ( )

Diagrame incomplet !!!!

The Yoneda lemma is surprisingly treated as a full theorem. However, the Yoneda lemma requires lemmas.

Lemma 2.1 (The simplest representation lemma). Let X , C be categories, and let : X → C be a functor.

1. ∀ ∈ Ob C , ∀ : → ∈ Mor X , ∀ ∈ Hom C ( , ( )) , Hom C ( , ( )) ( ) = ( ) • 2. ∀ ∈ Ob X , ∀ : → ∈ Mor X , ∀ ∈ Hom X ( , ) , • = Hom X ( , ) ( ) 3. ∀ ∈ Ob X , ∀ : → ∈ Mor X , = Hom X ( , ) (id )
Proof. 1. By direct application of the definitions of a functor (Definition 1.23) and of the covariant Hom-set functor (Definition 1.29):

Hom C ( , ( )) : Hom C ( , ( )) -→ Hom C ( , ( )) ↦ -→ Hom C ( , ( )) ( )
where Hom C ( , ( )) ( ) is the morphism such that: then (id ) is the unique element ∈ ( ) such that:

( ) ( ) Hom C , ( (
∀ ∈ Ob X , ∀ ∈ Hom X ( , ) , ( ) = ( ) ( )
Proof. Let ∈ Ob X , and let ∈ Hom X ( , ).

By simplest representation lemma (Lemma 2.1, item 3), we have:

= Hom X ( , ) (id )
Thus:

( ) = (Hom X ( , ) (id )) = ( • Hom X ( , )) (id )
Besides, : Hom X ( , -) → is a natural transformation; thus using Definition 1.32, diagram 1 with = Hom X ( , -) and = , we have:

• Hom X ( , ) = ( ) •
which yields:

( ) = ( ( ) • ) (id ) = ( ) ( (id ))
Hence the result. Now we have to prove that = (id ) is unique with that property. Let ∈ ( ) such that ∀ ∈ Ob X , ∀ ∈ Hom X ( , ) , ( ) = ( ) ( ) = ( ) ( ). Using = and = id yields:

(id ) ( ) = (id ) ( ) id ( ) ( ) = id ( ) ( ) = Lemma 2.3. Let X , C

be two categories and let

: X → Sets be a functor. Let ∈ Ob X and ∈ ( ).

The mapping = Hom X ( , ) -→ ( ) ∈Ob X defined by:

: Hom X ( , ) -→ ( ) ↦ -→ ( ) ( )
is a natural transformation such that (id ) = .

IMTA-RR-2019-01-SC 11/127

Yoneda lemma

Proof. We need to prove that, for any : → ∈ Mor X , the following square commutes:

Hom X ( , ) ( )

Hom X ( , ) ( ) Hom X ( , ) ( )
that is, we want:

∀ : → , • Hom X ( , ) = ( ) •
Let : → be an arrow in X . For all ∈ Hom X ( , ) = dom (Hom X ( , )):

• Hom X ( , ) ( ) = ( • ) (2)
= ( • ) ( ) (3)
= ( ) • ( ) ( ) (4)
= ( ) • ( ) (5)
Equation 2 is due to the simplest representation lemma (Lemma 2.1-2); Equations 3 and 5 are due to the definition of and Equation 4 comes from the definition of a functor (Definition 1.23).

Besides:

(id ) = (id ) ( ) = id ( ) ( )

=

Definition 2.4 (The natural isomorphism). Let X be a category, let : X → Sets be a functor and let be an object in Ob X . We define:

, :

Nat (Hom X ( , -) , ) -→ ( ) ↦ -→ (id )
The natural isomorphism is the mapping : , → , .

Definition 2.5 (The natural isomorphism). Let X be a category, let : X → Sets be a functor and let be an object in Ob X . We define:

, :

       ( ) -→ Nat (Hom X ( , -) , ) ↦ -→ , = , , : Hom X ( , ) -→ ( ) ↦ -→ ( ) ( ) ∈Ob X
The natural isomorphism is the mapping : , → , .

Please note that those two natural isomorphisms are standard in the demonstrations of the Yoneda lemma; however their notation isn't. We highlight those two ismorphisms because they will have several occurrences in the current course. [2]). Let X be a category, let : X → Sets be a functor and let be an object in Ob X .

Then, Nat (Hom X ( , -) , ) ( ).

Proof. Let : X → Sets and let ∈ Ob X .

[Inverse]

We first prove that is the inverse of . Then, we will prove that both are natural transformations. Let ∈ ( ).

, • , ( ) = , , = , , (id ) (6)
=

The transition 6 ⇒ 7 comes from Lemma 2.3. Similarly, let ∈ Nat (Hom X ( , -) , ). Note that, according to Lemma 2.2, is:

= : Hom X ( , ) -→ ( ) ↦ -→ ( ) ( (id )) ∈Ob X Thus: , • , ( ) = , ( (id ))
= , (id ), :

Hom X ( , ) -→ ( ) ↦ -→ ( ) ( (id )) ∈Ob X =
Consequently, and are mutually inverses. We only have to check their naturalities.

[ is a natural transformation in ]

Let : → be a natural transformation. We want to check if the following diagram commutes:

Nat (Hom X ( , -) , ) ( ) Nat (Hom X ( , -) , ) ( ) Nat(Hom X ( ,-), ) , , Let ∈ Nat (Hom X ( , -) , ). , • Nat (Hom X ( , -) , ) ( ) = , ( • ) = ( • ) (id ) = ( (id )) = • , ( ) IMTA-RR-2019-01-SC 13/127
2. Yoneda lemma which gives the expected result.

[ is a natural transformation in ]

Recall that is contravariant in . Let : → ∈ Mor X . We want to check if the following diagram commutes:

Nat (Hom X ( , -) , ) ( ) Nat (Hom X ( , -) , ) ( ) Nat(Hom X ( ,-), ) , ( ) ,
The arrows Nat (Hom X ( , -) , ) and ( ) are inverted because is supposed to be contravariant in .

Let ∈ Nat (Hom X ( , -) , ).

On the one hand:

, • Nat (Hom X ( , -) , ) ( ) = , ( • Hom X ( , -)) = ( • Hom X ( , -)) (id ) = • Hom X ( , ) (id ) = (id • ) = ( )
On the other hand, note that is also a natural transformation. Thus, for : → in X op (note that we are in the opposite category), the following diagram does commute:

Hom X ( , ) ( )
Hom X ( , ) ( ) Hom X ( , ) ( )
In particular: ( ) • = • Hom X ( , ), which gives:

( ) • , ( ) = ( ) ( (id )) = • Hom X ( , ) (id ) = (id • ) = ( ) = , • Nat (Hom X ( , -) , ) ( )
Consequently, is natural in both its parameters and .

[ is a natural transformation in ]

The idea is similar to . Let : → be a natural transformation. We want to prove that Nat (Hom X ( , -) ,

) • , = , • . Let ∈ ( ). , • ( ) = , ( )
IMTA-RR-2019-01-SC 14/127

2. Yoneda lemma and:

Nat (Hom X ( , -) , ) • , ( ) = Nat (Hom X ( , -) , ) , = •
, where • is the natural transformation:

• = • , , : Hom X ( , ) -→ ( ) ↦ -→ ( ( ) ( )) ∈Ob X (8) = • , , : Hom X ( , ) -→ ( ) ↦ -→ ( ) • ( ) ∈Ob X (9) = , ( ) = , • ( )
The transition 8 ⇒ 9 is due to the naturality of .

[ is a natural transformation in ]

Let : → be a morphism in X . We want Nat (Hom X ( , -) ,

) • , = , • ( ). Let ∈ ( ): Nat (Hom X ( , -) , ) • , ( ) = Nat (Hom X ( , -) , ) , = , • Hom X ( , -)
where , • Hom X ( , -) is the following natural transformation:

, • Hom X ( , -) = , , • Hom X ( , ) : Hom X ( , ) -→ ( ) ↦ -→ , , ( • ) ∈Ob X However: , , ( • ) = ( • ) ( ) = ( ) ( ( ) ( ))
which yields:

, • Hom X ( , -) = , ( ) ( ) = , • ( ) ( )
Consequently, is natural in both its parameters and .

[Conclusion]

Both and are natural transformations in and , and they are mutually inverses. As a consequence, and are natural isomorphisms between Nat (Hom X ( , -) , ) and ( ).

IMTA-RR-2019-01-SC

15/127 2. Yoneda lemma Remark 2.8. As stated in Definition 1.35, Nat (Hom X ( , -) , ) corresponds to the Hom-set: Hom Func(X ,Sets) Hom X op ( Note that it's X op and not X , because the natural isomorphism is contravariant in .

Remark 2.9. The Yoneda lemma has a central role due to its various meanings and consequences.

1. First, depending on the "size" of X , we have different interpretations. If X is small, then Nat (Hom X ( , -) , ) is a set because Sets X becomes locally small. If X is locally small, then it says nothing on Sets X . However, the Yoneda lemma states that Nat (Hom X ( , -) , ) is always a set. If X is non-locally small, then the functor Hom X ( , -) doesn't exist and the Yoneda lemma doesn't hold there.

2. Secondly, from a set-theoretic point of view, the Yoneda lemma states that there are not that many natural transformations: there are exactly card ( ( )) natural transformations Hom X ( , -) → , as each of these natural transformations is entirely determined by one element in ( ).

3. Thirdly, according to the Yoneda lemma, if = Hom X ( , -): The dual version of the Yoneda lemma is as follows:

Nat (Hom C ( , -) , Hom C ( , -)) Hom C ( , ) (
Lemma 2.10 (Contravariant Yoneda lemma). Let X be a category, let : X op → Sets be a contravariant functor and let be an object in Ob X . Then, Nat (Hom X (-, ) , ) ( ).

The functor → Hom X ( , -) has good properties. Let's spend some time studying them.

Definition 2.11 (Yoneda embedding [1]). Let C be a category. The Yoneda embedding is the functor:

: Difference between injective on arrows and faithful?

       C op -→ Func (C , Sets) ↦ -→ Hom C ( , -) : → ↦ -→ Hom C ( , -) : Hom C ( , -) → Hom C ( , -) Remark
Proposition 2.14. The Yoneda embedding is an actual embedding.

Proof. The injectivity on objects is easy. Suppose ( ) = ( ); then:

( ) = ( )
Hom C ( , -) = Hom C ( , -) ⇒ Hom C ( , ) = Hom C ( , )
Those two sets are equal. Thus, id ∈ Hom C ( , ) ⇒ id ∈ Hom C ( , ) ⇒ = . Thus, is injective on objects.

As noted in Remark 2.9-3, the Yoneda lemma implies that:

Nat (Hom C ( , -) , Hom C ( , -)) Hom C ( , ) Hom Sets C op ( ( ), ( )) Hom C ( , )
Proposition 2.6 also states that the following natural transformation is an isomorphism:

( ), :

Hom C ( , ) -→ Hom Sets C op ( ( ), ( )) ↦ -→ ( ),
where is:

( ), = ( ), , : Hom C ( , ) -→ ( ) ( ) ↦ -→ ( ) ( ) ( ) ∈Ob C = ( ), , : Hom C ( , ) -→ Hom C ( , ) ↦ -→ Hom C ( , ) ( ) ∈Ob C = ( ), , : Hom C ( , ) -→ Hom C ( , ) ↦ -→ • ∈Ob C
We compare with what ( ) is:

( ) = ( ) : ( ) ( ) -→ ( ) ( ) ↦ -→ ( ) ( ) ∈Ob C = ( ) : Hom C ( , ) -→ Hom C ( , ) ↦ -→ Hom C ( , ) ( ) ∈Ob C = ( ) : Hom C ( , ) -→ Hom C ( , ) ↦ -→ • ∈Ob C = ( ),
Consequently:

IMTA-RR-2019-01-SC 17/127 2. Yoneda lemma ( ), = Hom C ( , ) -→ Hom Sets C op ( ( ), ( )) ↦ -→ ( )
which yields that is full and faithful.

Using the Yoneda lemma (both covariant and contravariant) and the fact that the Yoneda embedding is an embedding, one can show the following corollaries: Introduction lol. Definition 3.1 (Universal element [2]). Let C be a category, and : C → Sets a functor.

The pair ( * , * ) ∈ Ob C × ( * ) is a universal element for if the natural transformation , * ( * ) : Hom C ( * , -) → is an isomorphism. The answer to the second question is easy: no, the Yoneda embedding doesn't have a universal element, because it is a functor C → Func C op , Sets . However, for ∈ C , its -component ( ) : C op → Sets could have one.

We are looking for a pair ( * , * ) such that:

( ), * ( * ) = : Hom C ( * , ) -→ ( ) ( ) ↦ -→ ( ) ( ) ( * ) ∈Ob C = : Hom C ( * , ) -→ Hom C ( , ) ↦ -→ Hom C ( , ) ( * ) ∈Ob C = : Hom C ( * , ) -→ Hom C ( , ) ↦ -→ • * ∈Ob C
What could the pair ( * , * ) be for ( ), * ( * ) to be an isomorphism? There is one obvious answer: take ( , id ).

But is this answer unique? Probably not. But is it unique up to isomorphism? The answer to this question lies in Proposition 3.5. Before, we have to show an intermediate proposition.

Remark 3.3. If the functor : C → Sets is contravariant, then the universal element is a pair ( * , * ) such that op , * ( * ) : Hom C (-, * ) → , where op , : ( ) → Nat (Hom C (-, ) , ) is the dual of , . Proposition 3.4 (Universal mapping property [5]). Let C be a category and : C → Sets a functor.

The pair ( * , * ) is a universal element for if and only if

∀ ∈ Ob C , ∀ ∈ ( ), ∃! ∈ Hom C ( * , ) = ( ) ( * ).
Proof. Using Definition 3.1: 1. there is a unique 0 ∈ Hom C ( 0 , 1 ) such that ( 0 ) ( 0 ) = 1 .

( * , * ) is a universal element for ⇔ , * ( * ) = , * * , : Hom X ( * , ) -→ ( ) ↦ -→ ( ) ( * ) ∈Ob X is an isomorphism ⇔∀ ∈ Ob C , , * * , : Hom X ( * , ) -→ ( ) ↦ -→ ( ) ( * ) is an isomorphism ⇔∀ ∈ Ob C , ∀ ∈ ( ), ∃! ∈ Hom C ( * , ) = ( ) ( * )
2. there is a unique 1 ∈ Hom C ( 1 , 0 ) such that ( 1 ) ( 1 ) = 0 .

3. there exists a unique 0 ∈ Hom C ( 0 , 0 ) such that ( 0 ) ( 0 ) = 0 . However, id 0 also has this property, so 0 = id 0 .

4. there exists a unique 1 ∈ Hom C ( 1 , 1 ) such that ( 1 ) ( 1 ) = 1 . However, id 1 also has this property, so 1 = id 1 .

Now let us study 0 • 1 and 1 • 0 . Combining items 1 and 2, we have:

( 0 ) ( ( 1 ) ( 1 )) = ( 0 ) ( 0 ) ( 0 ) • ( 1 ) ( 1 ) = 1 ( 0 • 1 ) ( 1 ) = 1 ( 10
)
( 1 ) ( ( 0 ) ( 0 )) = ( 1 ) ( 1 ) ( 1 ) • ( 0 ) ( 0 ) = 0 ( 1 • 0 ) ( 0 ) = 0 (11)
As id 0 (resp. id 1 ) is the unique arrow such that id 0 ( 0 ) = 0 (resp. id 1 ( 1 ) = 1 ), we deduce from Equation 10 (resp. from Equation 11) that 1 • 0 = id 0 (resp. 0 • 1 = id 1 ). Consequently, 0 is the isomorphism described in the proposition. [2]). Let X , C be two categories. Let : X → C be a functor and let ∈ Ob C . A universal arrow from to is a pair # , , where # ∈ Ob X and ∈ Hom C , # , such that, for all ∈ Ob X , for all ∈ Hom C ( , ( )), there exists a unique ∈ Hom X # , such that = ( ) • .

In the following, this unique will be denoted # , such that: = # • . Here is a diagram that sums up the idea behind universal arrows:

(X ) # (C ) # ( ) # ( # )
Lemma 3.13. Let X , C be two categories. Let : X → C be a functor and let ∈ Ob C .

If # , is a universal arrow from to , then # = id # .

Proof. The arrow # is the unique arrow that verifies:

= # • . Of course, = id # • , so id # = # .
Proposition 3.14. Let X , C be two categories. Let : X → C be a functor and let ∈ Ob C .

1.

# , is a universal arrow from to ⇔ Hom C ( , (-)), # ( ) is a natural isomorphism.

2. If for all ∈ Ob C , there exists ∈ Ob C and a natural isomorphism : Hom X ( , -) → Hom C ( , (-)), then , id is a universal arrow from to .

Proof. [Item 1]

By definition of a universal arrow # , , for all ∈ Ob X , for all ∈ Hom C ( , ( )), there exists a unique ∈ Hom X # , such that = ( ) • ; equivalently, for all ∈ Ob X , the function:

: Hom X # , -→ Hom C ( , ( )) ↦ -→ ( ) •
is an isomorphism; that is, those are the components of Hom C ( , (-)), # ( ), which is a natural isomorphism.

[ Proof. This proposition directly follows from Definitions 3.1 (universal element) and 3.12 (universal arrow). In fact, by definition of a universal element for Hom C ( , (-)), the following natural transformation should be an isomorphism:

Hom C ( , (-)), # ( ) = : Hom C # , -→ Hom C ( , ( )) ↦ -→ Hom C ( , ( )) ( ) ∈Ob C
By simplest representation lemma (Lemma 2.1), we have:

Hom C ( , ( )) ( ) = ( ) • By definition of a universal arrow, ∀ ∈ Ob X , ∀ ∈ Hom C ( , ( )) , ∃! = ( ) • = ( )( ). Thus,
∈ Mor Sets is a bijection, thus an isomorphism; consequently, the natural transformation

Hom C ( , (-)),
( ) is also an isomorphism.

Remember that universal elements are defined for a functor C → Sets, and not just for a functor between any two categories. The converse proposition is a bit less general. Proposition 3.16. We denote by 1 the set P (∅) = {∅} = 1 where ∅ is the empty set. For any set , for any ∈ , we define:

: 1 -→ ↦ -→
Let X be a category, let : X → Sets be a functor. If ( * , * ) is a universal element for , then * , ( * ) * is a universal arrow from 1 to .

Proof. By Proposition 3.4, if ( * , * ) is a universal element for , then ∀ ∈ X , ∀ ∈ ( ), ∃! ∈ Hom X ( * , ) such that:

= ( ) ( * ) ⇔ ( ) (0) = ( ) ( * ) * (0) ⇔ ( ) = ( ) • ( * ) * Consequently, we have: ∀ ∈ X , ∀ ( ) ∈ Hom Sets (1, ( )) , ∃! ∈ Hom X ( * , ), ( ) = ( ) • ( * ) *
, which yields that * , ( * ) * is a universal arrow from 1 to .

We sum up the results into this theorem:

Theorem 3.17. Let X be a category, and let : X → Sets be a functor.

1. ( * , * ) is a universal element for ⇔ * , , * ( * ) is a representation of . 2. ( * , * ) is a universal element for ⇔ * , ( * ) * is a universal arrow from 1 of . 3. ( * , ) is a representation of ⇔ ( * , (id )
) is a universal element for .

4.

# , is a universal arrow from to ⇔ # , is a universal element for Hom Sets ( , (-)).

IMTA-RR-2019-01-SC 22/127 4. Towards adjunctions

Towards adjunctions

Definition 4.1 (Left adjoint -from universal arrows). Let X , C be two categories. Let : X → C be a functor. We suppose that for all ∈ Ob C , there exists a universal arrow # , from to . The left adjoint of , denoted by * , is the mapping:

* :        C -→ X ↦ -→ # : → ↦ -→ # •
Let's study some properties of the left adjoint.

Lemma 4.2. Let X , C be two categories. Let : X → C be a functor, and let * be the left adjoint of .

For any ∈ Hom C ( , ), * ( ) is the unique solution in ∈ Hom X # , # to the equation:

• = ( ) • . Proof. We have • ∈ Hom C , #
. By definition of a universal arrow # , from to , there exists a unique # • ∈ Hom ( ) such that:

• = # • • = ( * ( )) • .
Proposition 4.3. Let X , C be two categories. Let : X → C be a functor, and let * be the left adjoint of .

The left adjoint * : C → X is a functor.

Proof. The mapping * sends objects (resp. arrows) in C to objects (resp. arrows) in X . Using Lemma 3.13, we check the behaviour of * on identity arrows: * (id ) = # •id = # = id # As for the composition, let : → and : → . By definition of * , we have:

• = ( * ( )) • • = ( * ( )) • • • = ( * ( • )) • (12)
But also:

• • = ( ( * ( )) • ) • = ( * ( )) • ( • ) = ( * ( )) • ( * ( )) = ( * ( ) • * ( )) (13

Towards adjunctions

Proof. We need to check if, for each : → , the following diagram commutes:

( * ( )) ( * ( )) ( * ( ))
That is, we need to check whether ( * ( )) • = • , which is the result of Lemma 4.2.

Proposition 4.5. Let X , C be two categories. Let : X → C be a functor, and let * be the left adjoint of . For all ∈ X , for all ∈ C , we define:

, :

Hom X ( * ( ), ) -→ Hom C ( , ( )) ↦ -→ ( ) •
The mapping : , ↦ → , is a natural isomorphism Hom X ( * (-), -) → Hom C (-, (-)), contravariant in and covariant in .

Proof. For ∈ C , ,-: Hom X ( * ( ), -) → Hom C ( , (-)) is the same function as ,-= Hom C ( , (-)), * ( ) ( ) which we know is a natural isomorphism (cf. Proposition 3.14, item 1).

For ∈ X , we study -, : Hom X ( * (-) , ) → Hom C (-, ( )). Let : → , we want the following diagram to commute:

Hom X ( * ( ) , ) Hom C ( , ( ))
? Hom X ( * ( ) , ) Hom C ( , ( ))

Hom X ( * ( ), ) , Hom C ( , ( ))
, (Note that -, is supposed to be contravariant in ).

Let ∈ Hom X ( * ( ) , ). On the one hand:

, • Hom X ( * ( ) , ) ( ) = , ( • * ( )) = ( • * ( )) •
while on the other hand:

Hom C ( , ( )) • , ( ) = Hom C ( , ( )) ( ( ) • ) = ( ) • • = ( ) • ( * ( )) • = ( • * ( )) • = , • Hom X ( * ( ) , ) ( )
Thus, -, is a natural transformation. Note that each component in of -, = , ∈Ob C is an isomorphism (because Hom C ( , (-)), * ( ) ( ), for any ∈ Ob C , is a natural isomorphism), thus so is -, .

IMTA-RR-2019-01-SC

24/127

Towards adjunctions

Proposition 4.6. Let X , C be two categories. Let : X → C be a functor, and let * be the left adjoint of . If : C → X is a functor for which there exists a natural isomorphism : Hom X ( (-), -) → Hom C (-, (-)), then there exists a unique natural isomorphism : → * ; in other words, the left adjoint is unique up to a unique isomorphism.

Proof. Let : C → X such that : Hom X ( (-), -) → Hom C (-, (-)) is a natural isomorphism.

For all ∈ C , we have ,-= Hom C ( , (-)), ( ) ( ) for some : → ( ( )) =

, ( ) id ( ) . We deduce from Proposition 3.14-2 that is a left adjoint for . As * and are left adjoints for , then ( ( ), ) and ( * ( ), ) are universal arrows from to (Definition 4.1), so ( ( ), ) and ( * ( ), ) are also universal elements for Hom C ( , (-)) (Proposition 3.15). According to Proposition 3.5, there exists a unique isomorphism : * ( ) → ( ) such that ( ) ( ) = . We now have to show that = ( ) ∈Ob C is natural in . We have the following diagram:

( ( )) ( * ( )) ( ( )) ( * ( )) ( ( )) ( ) ( * ( )) ( )
where the following subdiagrams commute:

( ( )) ( * ( )) ( ) ( ( )) ( * ( )) ( )
due to the construction of and:

( ( )) ( * ( )) ( ( )) ( * ( )) ( ( )) ( * ( ))
due to the naturality of : Id C → • and :

Id C → • * .
By diagram chasing, we have:

( ) • ( ( )) • = ( * ( )) • ( ) • ( • ( )) • = ( * ( ) • ) • • ( ) = * ( ) •
The last equation is due to , being an isomorphism. This equation makes the following diagram commute:

IMTA-RR-2019-01-SC 25/127
4. Towards adjunctions

( ( )) * ( ) ( ) * ( ) ( ) * ( ) which makes = ( ) ∈Ob C natural in .
Definition 4.7 (Adjunction -official). Let X , C be two categories. Let : X → C and : C → X be two functors. The 3-tuple ( , , ) is called an adjunction whenever is a natural isomorphism : Hom X ( (-), -) → Hom C (-, (-)).

We also say that is left adjoint to and is right adjoint to . We will refer to as the adjunctor of and .

If ( , , ) is an adjunction, we may write or

( ) → → ( ) ( ).
The following lemma proves that if ( , , ) is an adjunction, then is actually left adjoint to as defined in Definition 4.1. In fact, both definitions are equivalent. Lemma 4.8. Let X , C be two categories. Let : X → C and : C → X be two functors.

⇔ there exists a natural transformation :

Id C → • such that ∀ ∈ Ob C , ( ( ),
) is a universal arrow from to .

Proof. [Proof of ⇐]

Suppose that we have a :

Id C → • such that ∀ ∈ Ob C , ( ( ),
) is a universal arrow from to . According to the definition of a left adjoint, corresponds to a left adjoint on objects. We have to check if, for all ∈ X , for all : → , ( ) is the unique solution in ∈ Hom X ( ( ), ) to the equation:

• = ( ) • (14)
The natural transformation : Id C → • makes the following diagram commute:

( ( )) ( ( )) ( ( ))
which proves that ( ) is indeed a solution to Equation 14. The uniqueness of the solution comes from the definition of a universal arrow (Definition 3.12).

Consequently, is a left adjoint to . By Proposition 4.5, we can define a from that is a natural isomorphism Hom X ( ( ), ) → Hom C ( , ( )). Finally, ( , , ) is an adjunction.

[Proof of ⇒] Suppose , and suppose ( , , ) is an adjunction. Define to be the natural transformation with components:

= , ( ) id ( ) ∈ Hom C ( , ( ( )))
The natural isomorphism appears to be unamed in most references. However, in the rest of this course, it may be convenient to give it a name. Please note that nobody but the authors give this name to that isomorphism.

IMTA-RR-2019-01-SC

26/127

Towards adjunctions

The naturality of comes from the naturality of = , ∈C , ∈X in both its variables. The naturality in gives, when : → , for ( ) : ( ) → ( ) ∈ X :

Hom X ( ( ), ( )) Hom X ( , • ( ))
Hom X ( ( ), ( )) Hom X ( , • ( ))

, ( )

Hom X ( ( ), ( )) Hom X ( , • ( )) , ( )
while the naturality in gives, for : → :

Hom X ( ( ) , ( )) Hom X ( , • ( ))
Hom X ( ( ), ( )) Hom X ( , • ( ))

, ( )

Hom X ( ( ), ( )) Hom X ( , • ( )) , ( )
From the first diagram, we obtain:

, ( ) • Hom X ( ( ), ( )) id ( ) = Hom X ( , ( • ) ( )) • , ( ) id ( ) , ( ) • ( ) = ( • ) ( ) • , ( ) id ( ) (15)
and from the second diagram:

, ( ) • Hom X ( ( ), ( )) id ( ) = Hom X ( , • ( )) • , ( ) id ( ) , ( ) • ( ) = , ( ) id ( ) • (16)
Combining Equations 15 and 16, we obtain:

( • ) ( ) • , ( ) id ( ) = , ( ) id ( ) • ( • ) ( ) • = •
which proves that is a natural transformation.

We have to show that each ( ( ), ) is a universal arrow from to . We have a natural isomorphism ,-: Hom X ( ( ), -) → Hom C ( , (-)); so according to Proposition 3.14, ( ), , ( ) id ( ) = ( ( ), ) is a universal arrow. Besides, is a left adjoint to . Definition 4.9 (Unit of an adjunction). Let ( , , ) be an adjunction.

The unit of the adjunction ( , , ) is the natural transformation :

Id C → • such that ∀ ∈ Ob C , = , ( ) id ( ) .
We will define the dual notion of a counit. However, we will not construct it explictly as we did the unit (that is, using universal arrows, then left adjoints), because it is not that interesting. We will first compute the inverse of the adjunctor .

Note that Lemma 4.8 proves that Definitions 4.1 and 4.7 are not only equivalent, but also that we can construct the unit from the adjunctor and conversely. The same goes from the counit that we will define right after the following lemma.

IMTA-RR-2019-01-SC

27/127

Towards adjunctions

Lemma 4.10. Let ( , , ) be an adjunction. For all ∈ Ob C , define = , ( ) id ( ) . Then, , is:

, :

Hom X ( ( ), ) -→ Hom C ( , ( )) ↦ -→ ( ) • For all ∈ Ob X , define = -1 ( ), id ( ) . Then, -1
, is:

-1

, :

Hom C ( , ( )) -→ Hom X ( ( ), ) ↦ -→ • ( )
Proof. By naturality of and -1 , and for : → ( ) and : ( ) → , the following two diagrams commute:

Hom X ( ( ) , ( )) Hom C ( , • ( ))
Hom X ( ( ), ) Hom C ( , ( ))

, ( )

Hom X ( ( ), ) Hom X ( , ( )) , Hom C ( ( ) , ( )) Hom X ( • ( ) , ) Hom C ( , ( )) Hom X ( ( ), ) -1 ( ) , Hom C ( , ( )) Hom X ( ( ) , ) -1 ,
Suppose we have , ( ) = (or equivalently -1 , ( ) = ). Those two diagrams combine into this one:

Hom X ( ( ) , ( ))
Hom C ( ( ) , ( ))

Hom C ( , • ( )) Hom X ( • ( ) , )
Hom C ( , ( )) Hom X ( ( ), )

, ( )

Hom X ( ( ) , ) -1 ( ) , Hom C ( , ( )) Hom X ( , ( )) Hom X ( ( ), ) -1 ,
, Firstly, with id ( ) ∈ Hom X ( ( ), ( )), we have:

IMTA-RR-2019-01-SC 28/127 4. Towards adjunctions -1 , • Hom C ( , ( )) • , ( ) id ( ) = Hom X ( ( ), ) id ( ) -1 , ( ) • , ( ) id ( ) = • id ( ) -1 , ( ( ) • ) =
Secondly, with id ( ) ∈ Hom C ( ( ), ( )), we have:

, • Hom X ( ( ), ) • -1 ( ), id ( ) = Hom C ( , ( )) id ( ) , • -1 ( ), id ( ) • ( ) = id ( ) • , ( • ( )) =
The first calculation shows that , ( ) = ( )• and the second shows that -1 , ( ) = • ( ). Lemma 4.11. Let X , C be two categories. Let : X → C and : C → X be two functors.

⇔ there exists a natural transformation : • → Id X such that ∀ ∈ Ob X , ∀ ∈ Ob C and ∀ : ( ) → , there exists a unique arrow : → ( ) such that:

• ( ) = .

Proof. [Proof of ⇒] If , then let ( , , ) be the adjunction. We have -1 , : Hom X (-, (-)) → Hom X ( (-), -). Define = ( ) ∈Ob X to be:

= -1 ( ), id ( )
A diagram chasing very similar to the one in the proof of Lemma 4.8 shows that is a natural transformation.

Let ∈ Ob X , let ∈ Ob C and let : ( ) → . The existence and unicity of the : → ( ) such that

• ( ) = comes from the bijectivity of -1 , as the equation is also: -1 , ( ) = . Of course, that is = , ( ) = ( ) • .

[Proof of ⇐] Define:

, :

Hom C ( , ( )) -→ Hom X ( ( ), ) ↦ -→ • ( )
The definition of states that each , is an isomorphism. Now we have to prove that = , ∈Ob C , ∈Ob X is natural (but contravariant) in and (covariant) in .

Hom X ( , ( ))

Hom X ( ( ) , ) ? Hom X ( , ( )) Hom X ( ( ) , ) , Hom X ( , ( )) Hom X ( ( ), ) ,
For ∈ Hom X ( , ( )), we have:

Hom X ( ( ) , ) • , ( ) = • ( ) • ( ) , • Hom X ( , ( )) ( ) = • ( • )
So is natural in . As for the naturality in :

IMTA-RR-2019-01-SC 29/127

Towards adjunctions

Hom X ( , ( )) Hom X ( ( ) , )

?

Hom X ( , ( )) Hom X ( ( ) , ) , Hom X ( , ( )) Hom X ( ( ), ) , Let ∈ Hom X ( , ( )): , • Hom X ( ( ) , ) ( ) = • • ( ) Hom X ( , ( )) • , ( ) = • ( ( )) • ( ) Don't forget that is a natural transformation • → Id X .
Thence, we have the following commutative diagram:

• ( ) • ( ) • ( )
which gives:

• = • ( ( ))
and finally:

• • ( ) = • ( ( )) • ( ) , • Hom X ( ( ) , ) ( ) = Hom X ( , ( )) • , ( )
Thus, is a natural transformation in both and ; each component is an isomorphism, so is a natural isomorphism Hom C (-, (-)) → Hom X ( (-), -); so -1 is a natural isomorphism Hom X ( (-), -) → Hom C (-, (-)).

For all ∈ Ob C , define = -1 , ( ) id ( ) . By Proposition 3.14, item 2, we know that ( ( ), ) is a universal arrow from to , which makes the left adjoint of by Lemma 4.8. Definition 4.12 (Counit of an adjunction). Let ( , , ) be an adjunction.

The counit of the adjunction ( , , ) is the natural transformation :

• → Id X such that ∀ ∈ Ob X , = -1 ( ), id ( ) .
The notion of adjunction appears everywhere in mathematics. As this notion is very important, we need to give many examples. Example 4.14 (Isomorphisms). Let C , X be categories, and let : C → X be an isomorphism between those categories. Then . In fact, : ( ) → ∈ X ⇔ -1 ( ) : → -1 ( ) and : -1 ( ) → ⇔ ( ) : → ( ).

For the adjunction , -1 , , the adjunctor has components:

IMTA-RR-2019-01-SC 30/127

Towards adjunctions

, :

Hom X ( ( ), ) -→ Hom C , -1 ( ) ↦ -→ -1 ( )
while for the second adjunction -1 , , , the adjunctor has components:

, :

Hom X -1 ( ), -→ Hom C ( , ( )) ↦ -→ ( ) = -1 ,
The units and counits are the identity natural transformations. Identities: An identity morphism is an arrow → Composition: If 0 → 1 and 1 → 2 are two arrows, then there is one arrow 0 → 2 Note that there is only one arrow between two objects (real numbers) 0 , 1 ; if 0 < 1 then Hom R ( 0 , 1 ) contains only one arrow, while Hom R ( 1 , 0 ) is empty. Similarly, there is only one arrow → , and it is the identity. Finally, the composition law on arrows comes from the transitivity of the order relation .

Let : R → R be the functor: : → + with > 0. Let's check if is actually a functor. If 0 → 1 , then 0 1 , which gives 0 + 1 + , thus ( 0 ) → ( 1). If → then ( ) → ( ). Finally, if 0 → 1 and 1 → 2 then ( 0 ) → ( 1) and ( 1 ) → ( 2) and ( 0 ) → ( 2 ) (by transitivity of ). Now suppose you have 0 , 1 ∈ R such that:

( 0 ) 1 ⇔ 0 + 1 ⇔ 0 1 1 - Define : R -→ R ↦ -→ 1 1 -
. Then is left adjoint to . The adjunctor transforms arrows ( 0 ) → 1 to arrows 0 → ( 1 ). The unit and counit are the identity natural transformations Id R → Id R .

Example 4.16 (Decreasing linear function). We can build a similar example of adjunctor using R = (R, ) and its opposite category R op = (R, ).

Let R op = (R, ) be the category of the totally ordered set R, equipped with the usual order on real numbers.

Objects

Towards adjunctions

Note that (R, ) is actually the opposite category of (R, ). Let : R op → R be the functor: : → + with < 0. Let 0 , 1 ∈ R such that:

( 0 ) 1 ⇔ 0 + 1 ⇔ 0 1 1 - ⇔ 0 ( 1 )
We can define the same as in the previous example; and is again left adjoint to . The adjunctor transforms arrows ( 0 ) → 1 in R op to arrows 0 → ( 1 ) in R. The unit and counit are the identity natural transformations as = -1 .

Example 4.17 (Image and inverse image of a function). Let : → be a function between two sets and . The two categories will be the partially ordered sets X = (P ( ) , ⊆) and Y = (P ( ) , ⊆) equipped with the usual inclusion of sets.

Define the three functors:

: X -→ Y ↦ -→ ( ) = { ( ) | ∈ } : Y -→ X ↦ -→ -1 ( ) = { ∈ | ( ) ∈ } * : X -→ Y ↦ -→ ∈ | -1 ({ }) ⊆
The functor gives the image of a subset of , gives the inverse image of a subset of and * gives the subset of inverse images of singletons of elements of . We let the reader check that those three functions are actually functors.

Suppose we have ( ) → . For all ∈ , ( ) ∈ ( ) ⊆ , so for all ∈ , ∈ -1 ( ) = ( ), which gives ⊆ ( ). Conversely, suppose we have → ( ). For all ∈ , ∈ ( ) = { ∈ | ( ) ∈ }, so for all ∈ , ( ) ∈ , which gives ( ) ⊆ .

We have :

( ) ⊆ ⇔ ⊆ ( )
The adjunctor transforms arrows ( ) → to arrows → ( ). Note that ⊂ • ( ) but there is in general no reason why should be equal to • ( ) (except if is injective). Consequently, the unit of the adjunction is:

= : -→ • ( ) ↦ -→ ⊆
Similarly, note that • ( ) ⊂ but there is in general no reason why • ( ) should be equal to (except if is surjective), so the counit is:

= : • ( ) -→ ↦ -→ ⊆
Besides, we also have * . In fact, suppose we have ( ) ⊆ . Then, ∀ ∈ , -1 ({ }) ⊂ ( ) ⊂ , so ∀ ∈ , ∈ * ( ), hence ⊆ * ( ). Conversely, if ⊆ * ( ) then ∀ ∈ ( ), we have:

IMTA-RR-2019-01-SC 32/127 4. Towards adjunctions ∈ ( ) ⇒ ( ) ∈ ⊂ * ( ) ⇒ ( ) ∈ ∈ | -1 ({ }) ⊆ ⇒ -1 ({ ( )}) ⊆ ⇒ ∈
So we have ( ) ⊆ . The adjunctor * transforms arrows ( ) → to arrows → * ( ).

Before computing the unit and counit, note that, for ⊂ : * ( ( )) = * -1 ( )

= ∈ | -1 ({ }) ⊆ -1 ( ) = ∈ | ∀ ∈ -1 ({ }) , ( ) ∈ = { ∈ | ∈ ∧ ∃ ∈ , = ( )} = ∩ ( ) ⊆
The interpretation is the following: * ( ( )) is the biggest subset of that contains only images by . Again, * ( ( )) has no reason to be equal to , except if is surjective.

Also, for ⊂ :

( * ( )) = -1 ( * ( )) = { ∈ | ( ) ∈ * ( )} = ∈ | ( ) ∈ ∈ | -1 ({ }) ⊆ = ∈ | -1 ({ ( )}) ⊆ = { ⊆ | ( ) ⊆ ( )} ⊇
The interpretation of ( * ( )) is as follows: ( * ( )) is the biggest subset of that gives ( ). Again, ( * ( )) has no reason to be equal to , except if is injective.

In this case, the unit and counit are not easy to write. In fact, we will need to create an equivalence relation over , for example = mod ⇔ ( ) = ( ). Then we will need a section function that sends an equivalence class to its representative. Such a choice of section function should be chosen to be compatible with what we want from the unit and counit. 1. The whiskering of and , denoted by • , is the natural transformation:

• : • → • with components ( ( ) : • ( ) → • ( )) ∈C .
2. The whiskering of and , denoted by • , is the natural transformation:

• : • → • with components ( ) : • ( ) → • ( ) ∈C .
IMTA

( • ) • = • ( • ) Id C • = • ( • ) = ( • ) • • Id C = Remark 4.
• • • • • • • • Proof.
For ∈ C , consider the following "implemented" diagram:

( ( )) ( ( )) ( ( )) ( ( )) ( ) ( ) ( ) ( )
This diagram commutes because is a natural transformation → and is an arrow ( ) → ( ). Proposition 4.23 (Triangle identities). Let X , C be two categories. Let : X → C and : C → X be two functors. Let : Id C → • and : • → Id X be natural transformations.

The tuple ( , , , ) is an adjunction iff the following triangles commute:

• • • id • • • • id • Proof. [Proof of ⇒] Suppose ( , , ,
) is an adjunction. According to Lemma 4.10, we can compute the adjunctor from the unit and counit:

, :

Hom X ( ( ), ) -→ Hom C ( , ( )) ↦ -→ ( ) • -1 , : Hom C ( , ( )) -→ Hom X ( ( ), ) ↦ -→ • ( )
Also, from Definition 4.9 and 4.12, we deduce the triangle identities:

IMTA-RR-2019-01-SC 34/127 4. Towards adjunctions = , ( ) id ( ) ⇔ -1 , ( ) ( ) = id ( ) ⇔ ( ) • ( ) = id ( ) ⇔ ( • ) • ( • ) = id ( ) = -1 ( ), id ( ) ⇔ ( ) , ( ) = id ( ) ⇔ ( ) • ( ) = id ( ) ⇔ ( • ) • ( • ) = id ( ) [Proof (in place of -1
) from , and we prove that is the inverse of :

, : Hom X ( ( ), ) -→ Hom C ( , ( )) ↦ -→ ( ) • , : Hom C ( , ( )) -→ Hom X ( ( ), ) ↦ -→ • ( )
And then, for : ( ) → , we have:

, • , ( ) = • ( ( ) • )
This is equal to due to the following diagram:

( ) • • ( ) • ( ) ( ) ( ) id ( ) • ( ) ( )
The left-hand triangle commutes because of the triangle identities; the right-hand square commutes because it represents the naturality of : • → Id X .

The converse equality is similarly proven:

, • , ( ) = ( • ( )) •
which is equal to according to the following diagram:

( ) • ( ) • • ( ) ( ) ( ) id ( ) • ( ) ( )
The left-hand square commutes because is a natural transformation, and the right-square commutes because of the triangle identities.

Thus, and are both natural isomorphisms (the proof of naturality is not interesting and is left to the reader) and are inverses of each other.

IMTA-RR-2019-01-SC

35/127

Towards adjunctions

We finally give a third definition of adjunction: Definition 4.24 (Adjoint -triangle identities). Let X , C be two categories. Let : X → C and : C → X be two functors. Let : Id C → • and : • → Id X be natural transformations.

The tuple ( , , , ) is called an adjunction if the following triangles commute:

• • • id • • • • id • (17)
In the rest of this book, the left-hand diagram will be referred to as the "left-adjoint triangle identity" (because it mainly concerns , the left adjoint) and the right-hand diagram will be referred to as the "right-adjoint triangle identity" (because it mainly concerns , the right adjoint). Note however that the usage of this terminology is specific to this book. Other categorists will understand but might have come to other terms to refer to these triangles.

IMTA-RR-2019-01-SC

36/127

5. Zoo of adjunctions

Zoo of adjunctions

Adjunctions are a huge part of category theory. In this section, we present a bunch of adjunctions and non-adjunctions. Most of them are examples or counterexamples of questions that the authors had at some point.

What is the difference between an adjunction and an equivalence of categories?

We start with a counterexample that we think is important to see. Rather, this is an ambiguity, and maybe a doubt, that is worth removing. In short: equivalences of categories are NOT adjunctions. We need some definitions before showing this counterexample.

Definition 5.1 (Equivalence of categories). Let C and X be two categories, with functors : X → C and : C → X . The pair ( , ) is an equivalence of categories when there exist two natural isomorphisms •

Id X and • Id C .
It is easy to see that:

Proposition 5.2. The equivalence of categories is an equivalence relation.

The crucial thing to see here, is that an equivalence of categories is not the same as an isomorphism. In fact:

Proposition 5.3. Let : C → X be an isomorphic functor. Then , -1 is an equivalence of categories.

The converse is false; there are examples of equivalences of categories that are not isomorphisms. This is because equivalences of categories ("same worth") do not tell the same thing as isomorphisms ("same form"). Let us introduce a few notions as an example of the intuition that we will explain. Example 5.7. In a preorder category, the skeleton is the partial order on the equivalence classes of its elements.

In the previous examples, we refered to "the" skeleton of a category. This is due to the following proposition:

Proposition 5.8. The skeleton of a category is unique up to isomorphism.

Proof. Let : S ↩→ C and : S ↩→ C be two inclusion functors from two skeletons of C to C .

Let : S → S be the following functor. For ∈ S , we have ∈ C , and there is a unique ∈ S such that . We call ( ) that = ( ). Also, choose (Axiom of Choice!) an isomorphism : → ( ) ∈ C for each ∈ S . Then, for each : → ∈ S ⊂ C , define ( ) = • • -1 . Then : S → S is an isomorphism. Some authors, like [START_REF] Riehl | Category theory in context[END_REF], consider this unicity up to isomorphism to be part of the definition of a skeleton. The existence of a skeleton depends on the Axiom of Choice:

IMTA-RR-2019-01-SC 37/127

Zoo of adjunctions

Proposition 5.9. Assuming the Axiom of Choice, every category has a skeleton.

Proof. For each equivalence class of objects (under the relation "is isomorphic to"), using a choice function, choose one representative, and keep the same morphisms between any two objects. Then the resulting category is a skeleton of its base category. Here are two links between skeletons and equivalences of categories.

Proposition 5.11. A category is equivalent to its skeleton.

Proof. The pair consisting of the inclusion functor and a left inverse of it is an equivalence of categories.

Lemma 5.12. Two equivalent skeletal categories are isomorphic.

Proof. Let C and X be two equivalent skeletal categories; let ( , ) be the pair of functors witnessing the equivalence. Then • Id X and • Id C . However, in a skeletal category, for all ∈ C , we have:

• ( ) Id C ( ) = ⇒ • ( ) = .
Similarly, for all ∈ X , • ( ) = . Of course, by naturality, this is also true for arrows in both categories:

• ( ) • ( ) • ( ) = = • ( ) • ( ) • ( ) = =
Then, we have • = Id C and • = Id X , hence the result. Theorem 5.13. Two categories are equivalent ⇔ they have isomorphic skeletons.

Proof of ⇒. By transitivity of the equivalence of categories, if C and X are equivalent, then their skeletons are also equivalent. By Lemma 5.12, equivalent skeletons are isomorphic.

Proof of ⇐. Let C and X be two categories with isomorphic skeletons. Isomorphic skeletons are also equivalent, due to Proposition 5.3. According to Proposition 5.11, a category is equivalent to its skeleton; by transitivity of the relation of equivalence of categories, C and X are equivalent.

Remark 5.14. An interpretation of this theorem is the following. In order to prevent confusion, we call "isomorphism class" an equivalence class of the relation "is isomorphic to". This is a relation on objects of a category. Two objects are in the same isomorphism class if they are isomorphic.

Isomorphic categories are categories that are "exactly the same": same number of objects, same number of arrows. Equivalent categories are categories that have the same number of arrows but not necessarily the same number of objects in each isomorphism class of objects.

The skeleton of a category has only one object. Given the skeleton (C ) of a category C , we can make a coproduct of that skeleton with itself, and then add one isomorphism between objects that are the same. Then, the resulting category (C ) × 2 would have two objects in each class of isomorphisms. This category (C ) × 2 is equivalent, but not isomorphic, to both C and (C ). This construction can be made with any cardinal number, or even, different cardinal numbers per isomorphism class.

In pictures, the following categories are equivalent, but not isomorphic: The following properties are easy to see: Proposition 5.16. Let ( , , , ) be an adjoint equivalence. Then:

IMTA-RR-
1. ( , , , ) is an equivalence of categories 2.
, , -1 , -1 is also an adjoint equivalence

(both and are left and right adjoints of the other)

We can now procede to three counterexamples.

Theorem 5.17 (Informal). We can find examples and counterexamples of the following statements:

1. Adjunctions may or may not be equivalences 2. Equivalences may or may not be adjunctions, but any equivalence can be turned into an adjoint equivalence

If then ( , ) may or may not be an equivalence

Proof. Of course, taking = -1 yields examples of the positive statements in the theorem. The goal here is to show that this is not generally the case, by finding counterexamples.

[Proof of 1] The adjunction -× (-) is obviously not an equivalence, as the counit eval : × → is not invertible.

[Proof of 2] Basically, an equivalence doesn't need to satisfy the triangle identities. The fact that an equivalence can be turned into an adjoint equivalence will be proven in a next theorem.

[Proof of 3] This example comes from Tom Leinster's answer on MathOverflow. Now consider the terminal category C 1 with one object 0 and one identity arrow id 0 .

Consider a functor : C → C 1 . Its left adjoint : C 1 → C needs to verify:

Hom C ( (0), ) Hom C 1 (0, ( )) Hom C 1 (0, 0) = {id 0 } 1
Necessarily, (0) needs to be the initial object of C . Similarly, the right adjoint of needs to map 0 to the terminal object of C .

IMTA-RR-2019-01-SC

39/127

Zoo of adjunctions

Note that Vect, the category of vector spaces and linear maps, has a zero object: the vector space of dimension 0 is both initial and terminal. So, the right and left adjoints of a : Vect → C 1 are equal. In Vect, we have , and Vect is trivially non-equivalent to C 1 (cf. Remark 5.14 for an intuition on why these two categories are non-equivalent).

Lemma 5.18. Let ( , , , ) be an equivalence of categories. If it verifies one triangle identity (Definition 4.24), then it verifies the other.

Proof. We give the proof for one triangle identity. Suppose and verify the following triangle identity:

• • id (18)
For ∈ X , we have the following natural transformation diagram:

( ) • • ( ) ( ) • • ( ) • • • • ( ) • • ( ) ( ) • ( ( ) ) ( ) ( ) ( • ( ) ) (19)
The composite of the left and bottom arrows are actually the composition by (adding one on the left) and whiskering by (adding one on the right) of the assumed triangle identity:

• ( ( )) ( ) • • • ( ( )) • • ( ) • ( ( ) ) ( ( ) ) id • • ( ) ( ) ( • ( ) )
Which gives

( ) • ( ) = id • • ( ) .
Then, and are natural isomorphisms, so are their respective whiskerings. We deduce the second triangle identity:

( ) • ( ) = id • • ( ) ( ) • ( ) • ( ) -1 = id • • ( ) • ( ) -1 ( ) = ( ) -1 ( ) • ( ) = id
The proof is similar for the other triangle identity, although it requires two more natural transformation diagrams and a more subtle, but not too subtle, argument.

Remark 5.19. This lemma is from nLab. However, I do not understand the demonstration as I cannot read string diagrams. I prove the result differently. Proposition 5.20. If ( , , , ) is an equivalence, then there exists a unique 0 such that ( , , , 0 ) is an adjoint equivalence.

IMTA-RR-2019-01-SC 40/127

Zoo of adjunctions

Proof. Define 0 to be:

-1 -1 0
And consider the natural transformation diagram:

-1 -1

Gluing both diagrams together, it is easy to see that the following diagram commutes, and thus proves a triangle identity. This proof ends this subsection about the differences and links between adjunctions and equivalences.

An example of adjunction: inverse image of a function

Consider a function : → , and being sets. Define -1 to be the following functor:

-1 : P ( ) -→ P ( ) ↦ -→ -1 ( ) where P ( ) and P ( ) are seen as their partially-ordered counterparts. This functor has both a left adjoint and a right adjoint. The left adjoint is pretty easy to see. We are looking for an : P ( ) → P ( ) such that:

Hom P ( ) ( ( ), ) Hom P ( ) , -1 ( ) Let ∈ P ( ) and ∈ P ( ). We are looking for an ( ) such that ( ) ⊂ if and only if ⊂ -1 ( ). This happens when is the direct image of : : ↦ → ( ). What are the unit and counit of this adjunction? The right adjoint is less commonly seen. It is a functor : P ( ) → P ( ) such that ⊂ ( ) if and only if -1 ( ) ⊂ . That is, for a ∈ ⊂ ( ), we have { } -1 ⊂ . In fact, ( ) is defined as:

( ) = ∈ -1 ({ }) ⊂
If ⊂ , then ( ) is the smallest set of 's whose fibers by are in . I don't know if this set has a name.

Here we have a chain of three adjoint functors. The reader might wonder if there are longer chains of adjoints. The following sections give answers to this question.

How long can a chain of adjoints be? Part 1: a chain of five adjoints

+ Units and counits?

How long can a chain of adjoints be? Part 2: a chain of adjoints for any odd integer

These strings of adjoints depend on a few notions that we will only introduce here without too many details. Definition 5.21 ((Augmented) simplex category). The augmented simplex category, denoted by Δ , is the full subcategory of Cat consisting of finite totally ordered sets together with monotonic maps between them.

The simplex category, denoted by Δ, is the full subcategory of Δ consisting of non-empty finite totally ordered sets together with monotonic maps between them. Some authors use the skeleta of Δ and Δ . In that case, an object in (the skeleton of) Δ is a poset ( , ), where is the ordinal {0, 1, . . . , -1}, including the trivial (empty) order (0, ). An object in (the skeleton of) Δ is also a poset ( , ), without the trivial order (0, ).

When we consider the skeletal versions of Δ, morphings of Δ can be decomposed into finite compositions of the following elementary maps: Definition 5.22 (Face and degeneracry maps). Let > 0 and ∈ .

The -th face map for is the following functor:

:

         -1 -→ ↦ -→ if < + 1 if
The -th degeneracy map for is the following functor:

IMTA-RR-2019-01-SC 42/127

Zoo of adjunctions

:

         + 1 -→ ↦ -→ if < -1 if
These maps verify the simplicial identities: Proposition 5.23 (Simplicial identities). Let > 0. Then the maps and degeneracy maps verify the following identities:

+1 • = +1 • -1 for 0 < • +1 = • +1 +1 for 0 < • +1 =          • -1 -1 for 0 < < Id for ∈ and ∈ { , + 1} -1 • -1 for 0 < + 1 <
Proof. This is basic arithmetic.

The simplex category has uses that are way beyond the scope of this course (see quelque chose for more information). What matters to us is the following: Proof. This is a case-by-case analysis based on the definition of the functions. We prove +1 ; the other proof is in the same vein.

Consider Hom ( ), and Hom +1 , +1 ( ) . We have four cases:

> <
Case 1 Case 2 Case 3 Case 4

1. If and < , then ( ) = and +1 ( ) = . In that case, the equivalence Hom ( ), Hom +1 , +1 ( ) is obvious.

If > and < , then

( ) = -1 and +1 ( ) = . In that case, we have > -1 > hence the equivalence Hom ( -1, ) Hom +1 ( , ).

If

and , then ( ) = and +1 ( ) = + 1. We have < + 1, hence the equivalence: Hom ( , ) Hom +1 ( , + 1).

If > and

, then ( ) = -1 and +1 ( ) = +1. Then the equivalence Hom ( ), Hom +1 , +1 ( ) is obvious. + Units and counits? Theorem 5.25 (Informal). For each odd integer = 2 + 1, there is a chain of adjoints:

+1 -1 +1 -1 . . . 0 +1 0
We do not know of any similar result for even numbers. Cf la première réponse à cette question.

IMTA-RR-2019-01-SC

43/127

5. Zoo of adjunctions

How long can a chain of adjoints be? Part 3: an infinite chain of adjoints

There are other examples of infinite chains of adjoints (for example: this one) but we prefer this one, which requires not much side knowledge.

A logical adjunction

L'adjonction ∃ ?? ∀ 5.7. Forgetful and free functors

Other simple examples

Of course, this section could not be exhaustive. In the preface of the first edition of [5], Mac Lane wrote about Chapters III to V: "The slogan is "Adjoint functors arise everywhere."" So of course we cannot make a complete list of all things that happen to be adjoint functors, because there are loads of them. In this subsection, we introduce less epic examples of functors, without proof.

Initial and terminal objects

Sets and Rel: relations and powerset

Consider the category Rel whose objects are sets and whose arrows are the relations (not just functions). We let the reader check that this actually defines a category. There is an obvious inclusion functor : Sets → Rel. We also have the powerset functor P : Rel → Sets that sends a set to its powerset P ( ). Then, P. This adjunction comes with a lot of structure. The unit of the adjunction → P ( ( )) sends an element to its singleton ↦ → { }. The counit (P ( )) → sends a subset ⊂ to what? I don't get it.

Inclusion of preorders into Cat

Let Pre the category of preorders and monotone maps between them. Consider Cat, the category of small categories and functors between them. There is an obvious inclusion functor : Pre ↩→ Cat, because preorders are examples of small categories. This inclusion functor has a left adjoint : Cat → Pre. It is a nice exercise to find what that left adjoint is. We give the solution in the next paragraph.

The left adjoint takes a small category C , and turns it into a preorder with the following rule: for a category C ∈ Cat, (C ) is the preorder defined by ⇔ there is an arrow → in C . The unit : Id Cat → • maps a category to its preorder and the counit : • → Id Pre maps a preorder-ified preorder (thus a preorder) to itself; it is the identity.

A last word on adjunctions

In the following, these are purely non-mathematical thoughts and opinions on adjunctions.

When trying to understand adjunctions, I read and heard that they were fundamental not only in category theory, but also in mathematics, and why not, in life in general. However, many new-comers have a hard time figuring out what adjunctions say, while regular category-theorists just throw lots of (beautiful!) examples that prove that they arise everywhere.

Let me give an alternative opinion.

IMTA-RR-2019-01-SC 44/127

Zoo of adjunctions

Adjunctions are thought as a weak form of equivalence of categories. As such, we would expect that adjunctions state something about the two categories that they make "weakly equivalent". They do not. Adjunctions do say something about categories, but only on arrows, and in a hard-to-parse, hard-to-think, hard-to-use way (think about the identity Hom C ( ( ), ) Hom X ( , ( ))). Otherwise, they don't say much about the two categories. The exception is, adjoint equivalences, which say something about categories, but more from being equivalences than adjunctions.

What is true though, is that they say something about the functors that they (ad)join. Adjunctions are a way to associate functors together in a unique way (left and right adjoints are unique up to isomorphism, thanks to the Yoneda lemma). We can also use this unicity in order to define a functor in terms of another. But that's it. The interpretation of this association is too context-dependent for one to extract the meaning of two functors being adjoints. They make good theorems, and it always fills one with wonder when they discover that two known functors, functions, mathematical things, are left or right adjoints of the other (this was the goal of this section). But that's it.

In fact, the fact that they arise everywhere (and they do arise everywhere) is also a hint about the other fact that they tell nothing. Otherwise, they would say much more than what currently appears in books.

The wise conclusion is that, adjunctions are beautiful flowers in the landscape of category theory (or mathematics, or life) but apart from their omnipresence, they say nothing about the soil they grew on (even flowers may say something about the acidity of the earth, the humidity, even wind or bugs).

Of course, this opinion is strictly personal, but this is how I would answer the questions "what is the use of adjunctions?" or "what do adjunctions say about category theory (or mathematics, or life)?". Adjunctions may be beautiful, but unless you really want to study them, or if you came across adjunctions while studying category theory, just do not spend too much time on it. Category theorists think they are important, because you encounter them everywhere, but they carry no information and almost no property other than the unique association of two functors.

IMTA-RR-2019-01-SC

45/127

6. Objects with some universality in them

Objects with some universality in them

A word about the UMP. Definition 6.1 (Product [1]). Let C be a category and let and be objects in C .

The product of and is 3-tuple ( × , , ) where × is an object in C , and : × → and : × → are two arrows, such that, for all object with two arrows : → and : → , there exists a unique arrow : → × such that • = and • = , that is, such that the following diagram commutes:

× We call ,
projections, and we denote by = ( , ).

The definition of the product can be interpreted as follows. Given three objects , , , the "shorter" path from to and at the same time, always passes through × . In a sense, × is an "optimised" link to and . Example 6.2. In Sets, the product is the usual cartesian product of sets, and the projections are the usual projections ( , ) ↦ → and ( , ) ↦ → . Example 6.3. In a preorder category ( , ), the product × of two elements and verifies × and ×

, and for all , we have × . In fact, × = inf ( , ).

Proposition 6.4. Let C be a category and let and be objects in C . The product × is unique up to isomorphism.

Proof. Let ( × , , ) and ★ , ★ , ★ be two products of and . By definition of both products, there exists unique , ★ such that the following diagram commutes:

★ × ★ ★ ★
We then have:

★ • • ★ = ★ = ★ • id ★ and ★ • • ★ = ★ = ★ • id ★ . The following diagram commutes: ★ ★ ★ ★ ★ • ★ ★ ★ ★ ★ id ★
By uniqueness condition, we have • ★ = id ★ . A similar reasonning yields ★ • = id × ; then and ★ are isomorphisms.

IMTA-RR-2019-01-SC

46/127

Objects with some universality in them

Consequently, it is natural to mention "the" product of two objects, instead of "a" product.

The definition of a product can be generalized from = 2 to any ∈ N. When = 1, the product of 1 is just 1 and the projection 1 : 1 → 1 is the identity. When = 0, the empty product is an object * such that for all objects , there exists a unique arrow : → * (we will see later that this is the terminal object). Note that depending on the category C , not all pairs ( 1 , 2 ) may have a product. Definition 6.5 (Category with finite products). The category C is said to have finite products if ∀ ∈ N, ∀ ( ) ∈ , the product ∈ exists.

The product of categories can also be defined. However, it is not always a product in the category of categories (if such a thing exists). It is still useful for further definitions. Remark 6.7. We can define the category Cat of small categories, where the morphisms are the functors between small categories. In that case, if C and D are small categories, then the product C × D is an actual product in this category. Besides, any two categories give birth to a product category, however this product is not necessarily an actual product in the categorical sense.

Before checking on the dual notion of the product, let us have a look at the behaviour of the covariant and contravariant Hom-set functors in relation to the product. Proposition 6.8. Let C be a category with finite products. Then there is a natural isomorphism:

Hom C ( , × ) Hom C ( , ) × Hom C ( , )
in , and .

Proof. As a product, there is a unique : Hom C ( , × ) → Hom C ( , ) × Hom C ( , ) such that the following diagram commutes:

Hom C ( , × ) Hom C ( , ) Hom C ( , ) × Hom C ( , ) Hom C ( , ) Hom C ( , ) Hom C ( , ) Hom C ( , ) Hom C ( , )
Conversely, given ( , ) ∈ Hom C ( , ) × Hom C ( , ), by definition of the product × , there is a unique : → × such that the following diagram commutes:

× • •
IMTA-RR-2019-01-SC 47/127

Objects with some universality in them

Besides, = , : → × , so we define:

, , :

Hom C ( , ) × Hom C ( , ) -→ Hom C ( , × ) ( , ) ↦ -→ ,
By a reasonning similar to the one in the proof of Proposition 6.4, we have , , = -1 , so , , is a bijection.

The naturality is easy to check; let : → :

Hom C ( , ) × Hom C ( , ) Hom C ( , × ) Hom C ( , ) × Hom C ( , ) Hom C ( , × ) Hom C ( , )×Hom C ( , )
, ,

Hom C ( , × ) , ,
We check that the diagram commutes:

, , • Hom C ( , ) × Hom C ( , ) ( , ) = , , ( • , • ) = • , • Hom C ( , × ) • , , ( , ) = Hom C ( , × ) , = , • = • , •
The other naturalities are as easy to check.

This property is not specific to the Hom-set functor. Definition 6.9 (Preserving products). The functor : C → D is said to preserve products when, for all , ∈ Ob C , if × exists, then ( × ) ( ) × ( ).

Proposition 6.10. The covariant Hom-set functor Hom C ( , -) preserves products.

A similar question could be asked about the contravariant Hom-set functor: is there a natural isomorphism Hom C ( × , ) → Hom C ( , ) × Hom C ( , )? In fact, the answer is no. The right isomorphism is this one: Proposition 6.11. Let C be a category with finite products. Then there is a natural isomorphism:

Hom C ×C (( , ), ( , )) Hom C ( , ) × Hom C ( , )
in , and .

The proof is very similar to that of the covariant Hom-set functor. Combining Proposition 6.8 and Proposition 6.11, we have: Proposition 6.12. Let C be a category with finite products. Then there is a natural isomorphism:

Hom C (( , ), ( , )) Hom C ( , × )
in , and . In other words, the diagonal functor: IMTA-RR-2019-01-SC 48/127

6. Objects with some universality in them

Δ 2 :        C -→ C × C ↦ -→ ( , ) ↦ -→ ( , )
is right adjoint to the product functor -× -: C × C → C . Remark 6.13. The unit of the adjunction Δ 2 × is:

: → ×
and the counit is:

, : ( × , × ) → ( , )
The dual notion of that of a product is the coproduct: Definition 6.14 (Coproduct). Let C be a category and let and be objects in C .

The coproduct of and is 3-tuple ( + , , ) where + is an object in C , and : → + and : → + are two arrows, such that, for all object with two arrows : → and : → , there exists a unique arrow : + → such that the following diagram commutes:

+

We call , injections, although they do not need to be injective. Example 6.15. In Sets, the coproduct + corresponds to the disjoint union of and , for example defined as

+ = {( , 0) | ∈ } ∪ {( , 1) | ∈ }
with injections being: : → ( , 0) : → ( , 1) Example 6.16. In a preorder category ( , ), the coproduct + is the supremum: + = sup ( , ).

It is easy to see that: Proposition 6.17. Let C be a category and let and be objects in C .

( + , , ) is a coproduct in C if and only if ( + , , ) is a product in C op .

Corollary 6.18. The coproduct is unique up to isomorphism.

The proof of the following is very similar to the proof of Proposition 6.8. We will just give the natural isomorphism to consider. Proposition 6.19. Let C be a category such that for all , , the coproduct + exists. Then, there is a natural isomorphism:

Hom C ( + , ) Hom C ×C (( , ), ( , ))
In other words, the diagonal functor Δ

Hom C ( + , ) -→ Hom C ×C (( , ), ( , )) ↦ -→ ( • , • )
Then it is not hard (but quite long) to prove that , , defines a natural transformation Hom C (-+ -, -) → Hom C ×C ((-, -), Δ(-)).

The unit is:

, : ( , ) → ( + , + ) and the counit is:

: + →
In summary: Theorem 6.20. + Δ 2 ×. Definition 6.21 (Exponential [1]). Let C be a category with finite products, and let , be objects of C .

An exponential of and is a pair , where is an object in C and : × → , such that, for any arrow : × → , there exists a unique arrow : → such that the following diagram commutes:

× × ×id
The arrow is called evaluation; the arrow is the (exponential) transpose of .

Remark 6.22. Let's consider the category of sets C = Sets.

Let , be two sets; their exponential is = Hom Sets ( , ) (note that this is specific to Sets). Let : × → be a function. As a function in two variables, : , ↦ → ( , ) can also be seen as a function : ↦ → ( , -) : ↦ → ( , ). The operation : ↦ → ( , -) is a function → , it is called curryfication; however, the operation , ↦ → ( ) is a function , → called evaluation. The exponential of two sets and is the pair , where = Hom Sets ( , ) and is the function:

: × -→ , ↦ -→ ( )
Thus, for all : × → , we have • ( × id ) ( , ) = ( ( , -), ) = ( , ). The goal of the exponential is to generalise these notions of curryfication and evaluation to other categories. Proposition 6.23. Let C be a category with finite products. We also suppose that exists for all objects , ∈ C .

Let be an object of C . Let and be the functors:

:        C -→ C ↦ -→ × : → ↦ -→ × id : × → × IMTA-RR-2019-01-SC 50/127
6. Objects with some universality in them

:        C -→ C ↦ -→ : → ↦ -→ : → Then .
Proof. We let the reader check that and actually are functors. We want to prove that there is a natural isomorphism with components:

, : Hom C , → Hom C ( × , )
For fixed and , we consider the exponential , . Let : × → ; then by definition of the exponential , there exists a unique : → such that =

• × id . Consequently, there is a bijection:

, : Hom C , -→ Hom C ( × , ) ↦ -→ • × id
As for the naturality of , let : → :

Hom C , Hom C ( × , ) ? Hom C , Hom C ( × , ) Hom C ( , ) , Hom C ( × , )
, For ∈ Hom C , , we have:

Hom C ( × , ) • , ( ) = Hom C ( × , ) • • ( × id ) = • ( × id ) • ( × id ) = • ( • × id ) , • Hom C , ( ) = , ( • ) = • ( • × id ) = Hom C ( × , ) • , ( )
Thus the diagram commutes.

As for the naturality in , let : → :

Hom C , Hom C ( × , ) ? Hom C , Hom C ( × , ) Hom C ( , ) , Hom C ( × , )
, Let be the evaluation that comes with . For ∈ Hom C , , we have:

IMTA-RR-2019-01-SC 51/127
6. Objects with some universality in them

Hom C ( × , ) • , ( ) = • • ( × id ) , • Hom C , ( ) = , • = • • × id
Consider the following diagram:

× × ? × ×id • ×id • ×id
The following subdiagrams commute:

× × ×id • × × × ×id • ×id • ×id
We deduce that the following diagram commutes too:

× × × × ×id ×id • ×id
which proves the equality:

• • × id = • • ( × id ) ⇔ , • Hom C , ( ) = Hom C ( × , ) • , ( )
and thus the naturality of in .

The inverse natural isomorphism -1 is the adjunctor between and .

Corollary 6.24. The exponential is unique up to isomorphism.

Proof. Consequence of the unicity of the right adjoint up to isomorphism.

IMTA-RR-2019-01-SC 52/127

6. Objects with some universality in them Remark 6.25. In Sets, the two functors and would be:

:

           C -→ C ↦ -→ × : → ↦ -→ × id : × -→ × , ↦ -→ ( ( ), ) :            C -→ C ↦ -→ : → ↦ -→ : -→ ↦ -→ • Remark 6.
26. If the category C has all exponentials , for all , ∈ Ob C , then : ( ) ∈Ob C is the counit of the adjunction . In fact, using the seen in the proof of Proposition 6.23, we have

( ), id ( ) = • id ( ) , id = .
The counit is less obvious. It is a natural transformation = : → ( × ) with components such that the following diagram commutes:

× ( × ) × × ×id id × × Definition 6
.27 (Initial and terminal object [2]). Let C be a category, and let , be objects of C . The object is called initial when, for every ∈ Ob C , there is only one arrow → . The initial object is often denoted by 0.

The object is called terminal when, for every ∈ Ob C , there is only one arrow → . The terminal object is often denoted by 1.

Example 6.28. In Sets, any singleton { } is a terminal object, because there is only one function → { } for every set (the constant function ↦ → ). Besides, the empty set ∅ is the unique initial object; for set-theoretic reasons, there is only one function ∅ → (the empty function). Example 6.29. If ( , ) is a preorder, then the initial object is the minimal object min ( ) (if it exists) and the terminal object is the maximum max ( ) (if it exists). Proposition 6.30.

1. Let C be a category with initial object . The initial object is unique up to unique isomorphism.

Let C be a category with terminal object . The terminal object is unique up to unique isomorphism.

Proof. [Proof of 1]

Let and be two initial objects. Then there is only one arrow → , : → , : → and → . We have • : → , but the only arrow → is id so • = id . Similarly, we have • = id , so and are isomorphisms between and .

[Proof of 2]

Same as with the initial objects. Proof. For the equivalence × 1, it suffices to show that is also a product of and 1. For any : → , there is a unique arrow ! : → 1. So, there is a unique arrow such that the following diagram commutes:

1 ! id !
and that is = . So and × 1 are both products of and 1, so they are equivalent. The same proof, with reverse arrows, yields that + 0 . As for the exponential, consider the adjunction Hom C , 1 Hom C ( × 1, ) Hom C ( , ). By Corollary 2.17, we have 1 . (Proof without Yoneda? Only by diagam chase? Exponentials are not unique up to iso, apparently.) Proposition 6.33. Let C be a category and let : C → Sets. Then there is a natural isomorphism Hom Sets (1, ( )) ( ), natural in both and .

Proof. Recall that in Sets, 1 = {0}.

Let ∈ C , we define the mapping:

, :

Hom Sets (1, ( )) -→ ( ) ↦ -→ (0)
Of course, , is a bijection (isomorphism between sets): ∈ ( ) then there is exactly one function : 1 → ( ) such that (0) = .

As for the naturality in , if : → then we chekc if the following diagram commutes:

Hom Sets (1, ( )) ( ) ?
Hom Sets (1, ( )) ( )

Hom Sets (1, ( )) , ( ) ,
For ∈ Hom Sets (1, ( )):

In fact I don't really understand this proof. It comes from [1, p. 47], and is supported by https://math.stackexchange.com/questions/1991522/terminal-objects-as-nullary-products. I don't find the proof convincing because I feel like we can define the product of objects, for 2, or even = 1. However, = 0 seems like using the definition for a borderline case. As everyone seems to agree to this lemma (probably because it can be proven from elsewhere, using other tools), I mention it.

IMTA-RR-2019-01-SC

54/127

6. Objects with some universality in them

( ) • , ( ) = ( ) ( (0)) , • Hom C (1, ( )) ( ) = , ( ( ) ( )) = ( ) ( ) (0) = ( ) • , ( )
hence the naturality in .

Then, for a fixed ∈ C , if : → is a natural transformation, we need to check if the following diagram commutes:

Hom C (1, ( )) ( ) ? Hom C (1, ( )) ( ) Hom C (1, ) , ,
For ∈ Hom C (1, ( )), it does:

• , ( ) = • (0) , • Hom Sets (1, ) ( ) = , ( • ) = • (0) = • , ( ) Definition 6
.34 (Cartesian closed category [2]). The category C is called Cartesian closed whenever the following three conditions hold:

1. There is a terminal object 1

2. C has finite products 3. For all objects , ∈ Ob C , the exponential exists Example 6.35. The category Sets is Cartesian closed.

Recall from Section 1 the notions of epimorphisms and monomorphisms. The following notion of equaliser gives an example of monomorphism (and its dual notion is an example of epimorphism). In fact, it also gives a characterisation of isomorphisms. Definition 6.36 (Equalisers [1]). Let C be a category, and let , : → be two arrows.

An equaliser of and is a pair ( , ) with ∈ C and : → , such that • = • and, for all : → such that • = • , there exists a unique : → such that the following diagram commutes:

IMTA-RR-2019-01-SC 55/127
6. Objects with some universality in them Example 6.37. (From [1]). In Sets, given two functions , : → , their equaliser is ( , ) where = { ∈ | ( ) = ( )} and : → is the canonic inclusion.

Example 6.38. In a preorder category ( , ), there is at most one arrow → . Thus, the equaliser of , : → , with = is their domain together with its identity , id .

Proposition 6.39. The equaliser is unique up to isomorphism.

Proof. Let ( , ) and ( , ) be equalisers of and . There exist unique : If is an epimorphism then is an isomorphism.

Proof. Suppose is epic. As an equaliser, we have the following diagram:

and as an epimorphism, we deduce that • = • ⇒ = . Thus, the identity id : → verifies •id = •id . Consequently, there exists a unique : → such that the following diagram commutes:

IMTA-RR-2019-01-SC 56/127
6. Objects with some universality in them id from which we deduce • = id . The same occurs with :

→ : id = • • id We know that = • id = • ( • ) = ( • ) • = id • .
As an equaliser, is monic, so • = id ; is an isomorphism and -1 = .

We deduce from this proposition what a monic epimorphism (or an epic monomorphism, or monic/epic) lacks to be an isomorphism: Corollary 6.42. Let : → be any arrow. The arrow is an isomorphism ⇔ is an epic equaliser.

Take the arrows and reverse them; you get the definition of a coequaliser: Definition 6.43 (Coequalisers [1]). Let C be a category, and let , : → be two arrows.

A coequaliser of and is a pair ( , ) with ∈ C and : → , such that • = • and, for all : → such that • = • , there exists a unique : → such that the following diagram commutes: By duality, the following proposition holds: Proposition 6.44. The coequaliser is unique up to isomorphism. Proposition 6.45. Let ( , ) be a coequaliser of , : → .

Then is epic. Proposition 6.46. Let ( , ) be a coequaliser of , : → . If is a monomorphism then is an isomorphism. Corollary 6.47. Let : → be any arrow. The arrow is an isomorphism ⇔ is a monic coequaliser. Example 6.48. In Sets, take , : → . Let be the relation such that ∀ ∈ , ( ( ), ( )) ∈ , and let ¯ be the smallest equivalence relation containing . Consider / , , where / is the quotient of by the equivalence relation , and is the function that sends an element of to its equivalence class. Then, / , is the coequaliser of and .

For more details, see [2, Section 9.4.1, pp 278-279].

IMTA-RR-2019-01-SC 57/127

6. Objects with some universality in them Example 6.49. Just as in Remark 6.38, as there is only one arrow between any two objects, the coequaliser of , : → is their codomain: , id .

We finish our presentation of the constructions with some universality in them, with pullbacks, and their dual, pushouts. Definition 6.50 (Pullback [1]). Let C be a category. Let : → and : → be arrows with same codomain.

The pullback of and is a 3-tuple ( × , , ) such that the following diagram commutes: × and such that, for all ( , , ) such that the following diagram commutes:

there is a unique arrow : → × such that = • and = • , that is, such that the triangles and squares commute: × Example 6.51 (Pullbacks in Sets). In Sets, let : → and : → be two functions. Their pullback ( × , , ) is:

× = { ∈ P (P ( ∪ )) | • ( ) = • ( )} {( , ) ∈ × | ( ) = ( )}
with projections : × → and : × → . Note that there is the idea of "equalising" two functions. As we will see in a following proposition, there is a link between equalisers and pullbacks, and the explicit construction is based on this idea.

Consider the special case where and are inclusion mappings (that is: functions of the form :

-→ ↦ -→ for ⊂ and :

-→ ↦ -→ for ⊂ ). The pullback of and is then:

IMTA-RR-2019-01-SC 58/127
6. Objects with some universality in them

× = { ( , ) ∈ × | = } = {( , ) ∈ × } { ∈ } ∈ = ∩
The intersection of sets consists in a pullback of inclusion mappings in Sets.

Example 6.52 (Pullbacks in a preorder). In a preorder category ( , ), as there is at most one arrow between two objects, we don't need to check that any diagram commutes. In fact, the pullback is exactly the same as a product; that is, a pullback between → and → is × = × = inf ( , ).

Proposition 6.53. Pullbacks are unique up to isomorphism.

Proof. This proof is similar to the ones for products, coproducts, equalisers, coequalisers.

Let us study some more properties related to pullbacks. For example, pullbacks allow for a different characterisation of monomorphisms in a category. Proposition 6.54. Let : → be an arrow. Then the following propositions are equivalent:

1. is a monomorphism 2. The pullback of with itself exists and is ( , , ) with = 3. The pullback of with itself exists and is ( , id , id )

Proof. [(1) ⇒ (3)] Suppose is a monomorphism. Then for all , : → such that • = • , we have = .

Then consider the triple ( , id , id ). Consider the following diagram:

1 2 id id such that • 1 = • 2 .
As is monic, then 1 = 2 and the unique is = 1 = 2 and ( , id , id ) is the pullback of with itself.

[(2) ⇒ (1)] Suppose ( , , ) is the pullback of with itself. Let be as in the following pullback diagram:

IMTA-RR-2019-01-SC 59/127
6. Objects with some universality in them

1 2 such that • 1 = • 2 .
By definition of a pullback, the unique verifies: 1 = • = 2 , hence the monicity of .

[(3) ⇒ (2)] Obvious.

Proposition 6.55. Consider the following diagram:

1 1 1 2 2 2 1 1 2 2 Suppose that ( 1 , 1 , ) is the pullback of with 2 . Then ( 1 , 1 , ) is the pullback of with 2 ⇔ ( 1 , 1 • 1 , ) is the pullback of with 2 • 2 .
Suppose the right-hand square is a pullback; then the left-hand square is a pullback if and only if the whole rectangle is a pullback.

Proof. By diagram chase.

This result proves sometimes to be useful, when some objects are defined in terms of pullbacks. More properties of pullbacks will come later. For now, let us just focus on the links between pullbacks, equalisers, products and terminal objects. Lemma 6.56. Let C be a category with products and equalisers. Let : → and : → be arrows.

Let ( × , , ) be the product of and , ∈ C , : → × , : → and : → , as in the following diagram.

×

We suppose that =

• and =

• . The rest of the diagram is not supposed to commute otherwise.

( , ) is an equaliser of • and • ⇔ ( , , ) is a pullback of and .

IMTA-RR-2019-01-SC 60/127

6. Objects with some universality in them Proof. Suppose ( , ) is an equaliser of • and • . Let ( , , ) such that : → , : → and • = • . By definition of the product × , there is a unique : → × such that the two upper triangles commute: × Now, we have:

• = • ( • ) • = ( • ) •
As ( , ) is an equaliser of • and • , there exists a unique : → such that • = . Consequently, we have:

• = • • = • • =
Similarly, for , we have • = . In summary, for any ( , , ) such that • = • , there is a unique : → such that • = and • = ; thence, ( , , ) is a pullback of and . Conversely, suppose ( , , ) is a pullback of and ; we have: • = • . By definition of the product × , there is a unique : → × such that the two upper triangles commute:

×

We already have = • and = • , so that unique is . Let ( , ) be such that : → × and • • = • • . Such a induces arrows = • and = • ; we have:

• = • As ( , ,
) is a pullback of and , there is a unique : → such that = • and =

• . We deduce:

IMTA-RR-2019-01-SC 61/127
6. Objects with some universality in them

= • ⇒ • = • • = • ⇒ • = • •
which yields:

( • , • ) = ( • • , • • ) ( , ) • = ( , ) • • id × • = id × • • = •
To be an equaliser, there is one thing missing:

• • = • • .
This can be deduced from: Let be any object and let : → and : → be any arrows from to and . By definition of a terminal object, there is a unique arrow ! : → 1, so ! is:

• = • • • = • • Corollary 6.
! =! • =! •
Then qualifies for the existence of a unique : → × 1 such that the two triangles commute, as in the following diagram:

× 1 1 ! !
Thus, × 1 is a product of and . Lemma 6.59. Let C be a category.

If C has pullbacks and finite products, then C has equalisers.

Proof. The proof again consists in finding the right pullback that will be the equaliser. As C has products, we define × . The pullback of (id , id ) : → × and ( , ) : → × exists and is such that:

IMTA-RR-2019-01-SC 62/127

6. Objects with some universality in them

(id , id ) • = ( , ) • ( , ) = ( • , • ) ⇒ • = • as in the diagram: × ( , ) (id ,id )
The universality of the equaliser comes from that of the pullback.

Finally, the dual notion of a pullback is a pushout: Definition 6.60 (Pushout [5]). Let C be a category. Let : → and : → be arrows with same domain.

The pushout of and is a 3-tuple ( + , , ) such that the following diagram commutes: 6. Objects with some universality in them Example 6.61 (Pushout in Sets). In Sets, consider the functions : → and : → . Then their pushout + is identified with a subset of + ; in fact, it is:

+ = ( + ) /≡
where ≡ is the smallest equivalence relation on + such that for all ∈ , ( ) ≡ ( ).

Another interesting special case is the following. In Example 6.51, we defined the intersection ∩ of two sets and . This intersection comes with trivial inclusion mappings : ∩ -→ ↦ -→ and : ∩ -→ ↦ -→ , so we can compute its pushout.

∩ + ∩

We have + ∩ = ( + ) /≡ where ≡ is the smallest equivalence relation such that for all ∈ , ( ) ≡ ( ). In our case, ( ) = ( ) = , so ≡ is simply the equality =. This means that, in the coproduct, which is a disjoint union in Sets, the pushout doesn't contain duplicates of the same element if is in both and . Thus, the pushout + ∩ is simply the union ∪ .

Example 6.62 (Pushout in a preorder). Just as pointed in Example 6.52 about pullbacks, in a preorder, the pushout is exactly the same as a coproduct.

The notions of equalisers and pullbacks will appear again in the rest of this course. The other two (coequalisers and pushouts) are introduced for the sake of completeness (and duality).

IMTA-RR-2019-01-SC

64/127

7. Your only colimit is yourself

Your only colimit is yourself

Products/coproducts, initial/terminal objects, equalisers/coequalisers, pullbacks/pushouts are examples of the broader notion of limit. There are three ways to introduce limits, as illustrated in [2, Par. 9.2.6, p270]. We choose to introduce the limits using the characterisation with diagrams.

Definition 7.1 (Diagram [START_REF] Leinster | Basic Category Theory, ser[END_REF]). Let C , I be categories. A diagram in C of shape I is a functor I → C . The category I is called the index category and it is usually (but not always!) small. If I is finite, then the diagram is said finite.

In the following, the objects of I will be denoted by , , , . . . while the values of the functor : I → C will be denoted by , , , . . . . As explained in Section 1, a functor gives the picture of a category into another. A diagram I → C is no more than that: just a picture of the category I into the category C , hence the name. The diagonal functor Δ is the functor C → C I such that:

1. For all object ∈ C , Δ( ) is the diagram:

Δ :        I -→ C ↦ -→ → ↦ -→ id 2. For all arrow : → ∈ C , Δ( ) : Δ( ) → Δ( ) is the natural transformation Δ( ) = -→ ∈I (each component Δ( ) is a copy of ).
In summary, the functor Δ( ) "collapses" the category I into one element . For example, if I is the following five-element category: (You can check that this actually is a coproduct.) Define the preorder over such that: ( , ) ( , ) iff there exists some : → such that ( )( ) = . Let ∼ be the equivalence relation generated by this preorder.

Then, the colimit of the diagram is the quotient set:

Colim ( ) = /∼= ∈Ob I /∼
The natural transformation is composed of the inclusion maps

→ ∈Ob I /∼.
Note that the coproduct of two sets corresponds to the special case where card (Ob I ) = 2 and there is no arrow between the two objects, so that the equivalence relation ∼ is only the equality. . Note that we saw in Example 6.16 that the coproduct of a subset of a preorder was exactly its supremum. In fact, in a preorder, the arrows between two objects do not matter at all when computing colimits. This is because there is always at most one arrow between any two objects. Thus, in a preorder, the colimits are exactly the coproducts. Remark 7.8. Let (Colim ( ) , ) be a colimit. By definition, it is a universal arrow from to Δ, so for all ∈ Ob C , for all : → Δ( ), there is a unique : Colim ( ) → such that: → such that = Δ( ) • .

= Δ( ) • (
We gave a characterisation of a colimit ( , ) based on some property of . There is also a characterisation of a colimit based on the object . Proof. Let : → . We need to check if the following diagram commutes:

Δ(0) ( ) Id C ( ) 0 = Δ(0) ( ) Id C ( ) 0
Δ(0) ( ) Id C ( ) id 0
We have • : 0 → . By definition of an initial element, there is a unique arrow : 0 → ; thus, = • id 0 = • . Besides, this natural transformation is unique due to the uniqueness of the arrows . The statement with the terminal objects has a similar proof. As this is true for any , we conclude that is a morphism of cocones : → . By Proposition 7.12, is initial in Cocones (Id C ), so the arrow is = id . The second step consists in showing the unicity of some arrow → . Let : → ; the following diagram commutes: Then + is the colimit of the diagram :

Id C ( ) Δ( )( ) = Id C ( ) Δ( ) ( ) Id C ( ) Δ
       2 -→ C 0 ↦ -→ 1 ↦ -→
, where 2 is the category with two objects 0, 1 and no morphism between those two.

Proof. Note that for all ∈ C , the cocone : → Δ( ) has only two components : → and : → . Besides, if + exists, then there is a unique : + → such that = • and = • ; in other words, ( + , ), where :

→ Δ( + ) is the natural transformation with components and , is the colimit of .

We now introduce the dual notion of a colimit, namely that of a limit. We will need to introduce cones (the dual notion of cocones) as well. Definition 7.17 (Limit). Let C , I be categories. Let Δ : C → C I be the diagonal functor and let : I → C be a diagram. The pair (Lim ( ), ) is the limit diagram for when for all ∈ Ob C , for all : Δ( ) → , there is a unique : → Lim ( ) such that =

• Δ( ). We say that C has finite limits if every diagram : I → C with finite index category I has a limit. The limit of can be defined explicitly as:

Lim ( ) = ( ) ∈Ob I ∈ ∈Ob I ∀ : → , ( ) ( ) =
And the natural transformation is composed of each projection ∈Ob I → . Again, the product is a special case of limit, when I is the category with only two objects and no arrow between them, so that the condition ∀ : → , ( ) ( ) = is vacuously true.

Example 7.20. In a preorder category ( , ), the diagram : I → defines a sub-order, and the limit of that diagram, if it exists, is the inf of all 's: Lim ( ) = inf ∈Ob I . Just as colimits (see Example 7.7), arrows between objects do not matter when computing limits. The limit of a diagram in a preorder is exactly the same as the product of its components. Remark 7.21. Using the same diagram as in the last example in Remark 7.8, and using the duality, a limit illustrates this way: We define the category Cones ( ) of cones to as the following category: The dual statement is also true:

Proposition 7.29. The following constructions are colimits:

1. An initial object in C is the colimit of the empty diagram : ∅ → C , with ∅ as the empty category:

Your only colimit is yourself

So in fact products, equalisers, terminal objects, pullbacks are special cases of limits (and their duals are special cases of colimits). Before exploring another link between those constructions, let us give two other instances of limits and colimits that may be useful in example-building. Remark 7.30. Consider the category D with only one object (and the identity morphism).

A diagram : D → C may be identified to the single object (0) = 0 . It is easy to see that 0 is its own limit and colimit. Let ( , ( 1 , 2 )) be a cone to , and suppose has a limit (Lim ( ) , ( 1 , 2 )).

1 2 Lim ( ) Colim ( ) 1 2 ( ) 1 1 2 2 1 2
The limit Lim ( ) is such that there is a unique arrow : → Lim ( ) such that:

= • ( = 1, 2) 2 = ( ) • 1 2 = ( ) • 1
A cone to defines two arrows 1 : → 1 and 2 : → 2 such that 2 = ( ) • 1 . So, given a cone ( , ( 1 , 2 )) to , there is a unique arrow 1 : → 1 such that the diagram commutes. In fact, 1 , (id 1 , ( )) is the limit of . With the same reasonning, it is easy to see that 2 , ( ( ), id 2 ) is the colimit of . This is a better way to state this remark (better for memory): considering an arrow → , is its limit and is its colimit. The limit is the domain, and the colimit is the codomain of the arrow. Remark 7.32. Categories may or may not have all limits or all colimits, maybe for some diagrams and not others. However, diagrams from the one-object and the two-object categories always have a limit and a colimit in any category.

There is another, stronger link between products, equalisers, terminal objects and pullbacks. A similar link exists between their dual counterparts, see Theorem Define = ( = • ) ∈I . By definition of ( , ), we have:

( ) • • = •
which proves that is a natural transformation Δ (Lim ( )) → (there is only one arrow to check). We now prove that ( , ) is the limit of the diagram : I → C . Let : Δ( ) → be a cone to ; we have ( ) • = . Consider the function Π : → ∈I such that ∀ ∈ I ,

• Π = . We have:

( ) • = ( ) • • Π = • Π
As ( , ) is an equaliser of ( ) • and , there exists a unique : → such that • = Π , from which we infer, for all ∈ I :

• = Π • • = • Π • = ⇒ • Δ( ) =
So ( , ) is the limit of . Now suppose I is any finite category with only two non-identity arrow 0 : 0 → 0 and 1 : We also define the following arrows:

0 = ( 0 ) • 0 1 = ( 1 ) • 1 0 = 0 1 = 1 = ( 0 , 1 ) = ( 0 , 1 )
As C has equalisers, consider the equaliser ( , ) of :

∈I → 0 × 1 and : ∈I → 0 × 1 .
The proof is very similar to the previous one. If : Δ( ) → is a cone to , then we define Π to be the concatenation of the components of : ∀ ∈ I , = • Π . We check that • Π = • Π using the fact that is a natural transformation. As ( , ) is an equaliser, there exists a unique : → such that • = Π , and we conclude that • Δ( ) = Π , with = ( = • ) ∈I (which is a natural transformation Δ( ) → ). Finally, ( , ) is the limit of .

As the final case, let I be any finite category. Again, C has finite products, so we define ∈I and its projections . As the set of arrows in I is also finite, we can consider all arrows : → ∈ Mor I and define the product : → ∈Mor I , that is, the product of all codomains of all arrows in I . For 0 : 0 → 0 , the projection of index 0 will be denoted 0 :

: → ∈Mor I → 0 .

We now define:

, : ∈I → : → ∈Mor I such that, for all : → ∈ Mor I , we have:

• = ( ) • = ( ) • dom • = = cod
Let ( , ) be an equaliser of and ; the rest of the proof is very similar to the previous two ones.

We can now bring together all the lemmas that we disseminated throughout the last two sections, and prove: (2 ⇒ 1) By Lemma 6.58, pullbacks and terminal object give products, while by Lemma 6.59, pullbacks and products give equalisers.

(1 ⇒ 3) By Lemma 7.33, products and equalisers give limits.

(3 ⇒ 1) By Proposition 7.28, products and equalisers are special cases of limits.

Of course, the dual theorem is also true: Theorem 7.35. Let C be any category. The following propositions are equivalent:

1. C has finite coproducts and coequalisers 2. C has pushouts and an initial object

C has finite colimits

Note that the theorems we mentionned with limits used any index category, be it small or large. Some results we proved only for finite limits, but, for example, Proposition 7.34 generalises to any cardinality (and thus, for any small category): Theorem 7.36. Let be a cardinal and let C be any category.

C has all products of cardinality and equalisers ⇔ C has all limits of cardinality . In other words, C has all small products and equalisers ⇔ C has all small limits. Remark 7.37 (Historical interlude). Among the many ways to introduce limits and colimits, we wanted to introduce the following version (for a source of that version, see [8, Exposé 1, section 2, page 9]).

Let : I → C be a diagram. The limit of that diagram will be defined as the following functor:

Lim ( ) : C op -→ Sets ↦ -→ Hom C I (Δ( ), )

and the colimit will be:

Colim ( ) : C -→ Sets ↦ -→ Hom C I ( , Δ( ))
In other words, the limit (resp. colimit) of a diagram will be the functor that sends to the set of cones from to that diagram (resp. the set of cocones from that diagram to ). A diagram I → C has a (co)limit in the form of a functor C op → Sets or C → Sets. Now assume that Lim ( ) the functor is represented by an object ( ) ∈ C (see Definition 3.6 for the definition of representable functor). Then for a fixed , we have:

Hom C ( , ( )) Hom C I (Δ( ), )
That is, for a cone : Δ( ) → , we have a unique arrow → ( ) that makes the right diagrams commute... The representation ( ) is exactly the limit Lim ( ) of in the sense of Definition 7.17! Similarly, the representative of Colim ( ) will be the colimit Colim ( ) of .

IMTA-RR-2019-01-SC

77/127

As is the pullback of and , there is a unique arrow : 0 → such that • = 0 • 0 and • = 0 . With the same reasonning, we have a unique : → 0 such that 0 • = -1 0 • and 0 • = . We then have to prove that = -1 ; this is because there is a unique arrow id : → such that the diagram commutes; from which we deduce • = id and • = id .

As stated in Remark 10.8, in Sets, subobjects can be grouped into equivalence classes, the representative of a given equivalence class being the cardinal of the subobjects. The collection of cardinals lower than a certain other cardinal is a set, while the collection of all subobjects generally is not. This is then easier, and more practical, not to refer to the collection of all subobjects SubObj (Sets), but rather, to the set of the equivalence classes of the subobjects: In the rest of this course, we will refer to equivalence classes of subobjects, instead of bare subobjects. So, a set of subobjects is to be understood as the set of equivalence classes of subobjects.

IMTA
Remark 10.12. As noticed in Proposition 10.10, the pullbacks of equivalent subobjects are equivalent. So, in a category with pullbacks, given an arrow : → , for any subobject : → of , there is a subobject :

→ of such that the following square is a pullback:

For an arrow : → , there is some function that sends any subobject of to one subobject of in a way that gives the above pullback. This function is denoted as SubObj C ( ) : SubObj C ( ) → SubObj C ( ) (beware of the inversion!). Definition 10.13 (Subobject functor). Let C be a category with pullbacks.

The subobject functor SubObj C (simply written SubObj when there is no doubt about the category) is the contravariant functor: We now generalise the notion of characteristic function with the following definition. Definition 10.14 (Subobject classifier). Let C be a category with all finite limits.

A subobject classifier in C is a pair (Ω, ) where Ω ∈ Ob C and : 1 → Ω such that, for all ∈ C , and for any :

→ subobject of , there is a unique arrow : → Ω such that the following diagram is a pullback:

1

Ω

The arrow : → Ω is called the classifying arrow for and is generally written .

In fact, an equivalence class in this case, might not be a set. For example, in Sets, the collection of all subobjects of R of cardinality ℵ 0 is not a set. As a consequence, the collection of equivalence classes is not a set, as a set can only contain sets, at least in the set-theoretic sense (hereditarily: sets contain sets that contain sets and so on; there should not be any proper class in between). However, each representative is a cardinal, and there is only a set of cardinals below some cardinal. It is then more correct to refer to SubObj C ( ) as the set of representatives.

IMTA-RR-2019-01-SC

98/127

Sets-like categories

In a sense, the subobject classifier is a "universal subobject".

Proposition 10.15. Let C be a category with a subobject classifier (Ω, ).

The subobject classifier is unique up to isomorphism.

Proof. Let (Ω, ) and (Ω , ) be two subobjects classifiers.

Note that an arrow 1 → is necessarily monic (since there is only one arrow to the terminal object). So, : 1 → Ω is a subobject of Ω. By definition of a subobject classifier, there exist unique 1 : Ω → Ω and 1 : Ω → Ω such that following diagram commutes:

1 1 1 Ω Ω Ω id 1 id 1 1 1
As there is a unique arrow Ω → Ω, which already is id Ω (same for Ω ), we deduce that 1 = 1 -1 .

Example 10.16. What could the subobject classifier be in Sets? For now, let us justify the notation . Suppose the simplest case. Consider a set , a subset of (an actual subset, not only a subobject), and its canonical inclusion morphism : → .

The terminal object in Sets is any one-element set; take the set-theoretic 1 = {0}. Besides, there is a unique arrow ! : → 1. We are looking for Ω and : 1 → Ω. Let's be explicit: ! and are the functions:

! : -→ 1 ↦ -→ 0 : 1 -→ Ω 0 ↦ -→
where is some element in Ω.

As a subobject classifier, the following square is a pullback:

1

Ω !
Let us observe the diagram in explicit terms. The function is such that, for all ∈ :

• ( ) = •! ( ) ( ) = (0) ( ) =
That is, for each ∈ , the function gives the same constant . Now take another subset ⊂ with its inclusion mapping : → and its terminal arrow ! : → 1. We also suppose that • = •! . As is a pullback, there is a unique : → such that the following diagram commutes:

IMTA-RR-2019-01-SC 99/127 10. Sets-like categories

1 Ω ! !
For all ∈ , we have:

( ) = • ( )
= ( ) so does not "alter" ; it is an inclusion mapping: ⊂ . So, for all ⊂ such that, for all ∈ , we have ( ) = , we deduce that ⊂ . Such a behaviour indicates that should be the characteristic function of , Ω = 2 = {0, 1} and : 0 ↦ → 1 (the constant function that assigns 1 to its unique element 0).

In fact, we can check that (2, 0 ↦ → 1) is the subobject classifier of Sets. In fact, the subobject classifier is designed to generate classifying arrows, which are the categorical generalisation of characteristic functions. Proposition 10.17. Let C be a category with all finite limits.

C has a subobject classifier (Ω, ) ⇔ the subobject functor SubObj C is representable.

Proof. By definition of a subobject classifier, for all , for all : → ∈ SubObj C ( ) subobject of , there is a unique arrow : → Ω such that the following diagram is a pullback:

1 Ω ! By definition of the subobject functor, = SubObj( ) ( ). By Proposition 3.4, (Ω, ) is a universal element of SubObj, and by Theorem 3.17, Ω, SubObj,Ω ( ) is a representation of SubObj. We finish the section with the notion of a power object. Definition 10.20 (Power object). Let C be a category with finite limits. Let ∈ C .

The power object of is a pair (P ( ) , ) where P ( ) is an object of C and : → × P ( ) is a subobject of × P ( ), such that, for all ∈ C , for all subobject ℎ : → × of × , there is a unique : → P ( ) such that the following diagram is a pullback:

× × P ( ) ℎ id ×
IMTA-RR-2019-01-SC 100/127 10. Sets-like categories Remark 10.21. In terms of sets, the power object P ( ) is the powerset of (the set of all subsets of ). The object is interpreted to be a family of subsets of (a subset of P ( )). The interpretation of : → × P ( ) will come later.

Finally, the pullback functor is easier to see. Remember that, in Sets, the pullback between : → and : → is the set × = {( , ) ∈ × | ( ) = ( )} (cf. Example 6.51). The pullback functor * sends : → to the projection of × to : * ( ) : × -→ ( , ) ↦ -→ One may wonder where appears in the construction of * ( ); just remember the above definition of × in Sets.

Proposition 11.33. Let E be a topos. Then every slice of E is a topos as well.

Proof. Let ∈ Ob E . By Corollary 11.30, the slice category E / has finite limits. We now have to show that every object has a power object. So, the proof can be found in [10, Chapter IV, Section 7, Theorem 1, p190] and in [9, Chapter 5, Section 2, Theorem 2.1, p149], but I don't want to spend too much time on it. The proofs are very long. We will just admit this proposition.

Corollary 11.34. A topos is locally Cartesian closed.

Proof. In fact, as every slice of a topos is a topos, then in particular, each slice of a topos is Cartesian closed.

The fact that a topos is locally Cartesian closed is crucial in theoretical computer science and logic, because it means that any topos has an internal type theory.

Let us sum up the properties of a topos that we have seen:

1 ,

 1 Section 2.1, pp30-31]. Proposition 1.15. Let : → and : → such that • = id . Then is monic while is epic.Proof. Let , :→ such that • = • , then • • = • • ⇒ = , so is monic. Let , : → such that • = • , then • • = • • ⇒ = , so is epic.

Definition 1 .

 1 28 (Covariant and contravariant functor). A functor : C → D is called covariant if it sends : → to ( ) : ( ) → ( ). A functor : C → D is called contravariant if it sends : → to ( ) : ( ) → ( ), or equivalently, if : C op → D is a covariant functor.

Definition 1 .Definition 1 .

 11 34 (Composition of natural transformations). Let C , D be categories, and let , and be functors C → D. If : → is the natural transformation = ( ) -→ ( ) ∈C and : → is the natural transformation = ( ) -→ ( ) ∈C then the composition of by is • : → , defined by 35 (Functor category [1]). Let C and D be two categories. The functor category, denoted by Func (C , D), or by D C , is the following category: Objects: The objects are the functors : C → D Morphisms: A morphism between two functors and is a natural transformation : → = ( ) -→ ( ) ∈C Identities: An identity on a functor is the identity natural transformation id = ( ) The composition law in Func (C , D) is defined in Definition 1.34.

  gives Hom C ( , ( )) ( ) = ( ) • , hence the result. 2. Consequence of first part of the lemma with C = X , = Id C , = and = . 3. Consequence of second part of the lemma with = and = id .

  Note the inversion) As stated in the previous paragraph, each element in Hom C ( , ) characterises one natural transformation in Nat (Hom C ( , -) , Hom C ( , -)). Consequently, any natural transformation Hom C ( , -) → Hom C ( , -) is determined by an arrow → using the application seen in the proof of the Yoneda lemma. Consequently, the only arrows Hom C ( , ) → Hom C ( , ) are of the form Hom C ( , ) for some : → .

Remark 3 . 2 .

 32 When one sees Definition 3.1, the two natural questions should be: Is this universal element unique? Does the Yoneda embedding have a universal element?

)Proposition 4 . 4 .

 44 Equations 12 and 13, together with Lemma 4.2, yield: * ( • ) = * ( ) • * ( ) Let X , C be two categories. Let : X → C be a functor, and let * be the left adjoint of .The mapping = ( :→ • * ( )) is a natural transformation : Id C → • * .IMTA-RR-2019-01-SC 23/127

Example 4 .

 4 13 (Identity). Let C be a category. Then the identity functor Id C : C → C is both left and right adjoint of itself; and Id -,-: Hom C (Id C (-), -) → Hom C (-, Id C (-)) is the adjunctor. The unit and counit are: , : Id C → Id C .

Example 4 .

 4 15 (Increasing linear function). Let R = (R, ) be the category of the totally ordered set R, equipped with the usual order on real numbers.Objects: An object in R is a real number ∈ R Morphisms: There is an arrow 0 → 1 if and only if 0 1

: 1 Identities:

 1 An object in R op is a real number ∈ R Morphisms: There is an arrow 0 → 1 if and only if 0 An identity morphism is an arrow → Composition: If 0 → 1 and 1 → 2 are two arrows, then there is one arrow 0 → 2 IMTA-RR-2019-01-SC 31/127

Example 4 .

 4 18 (Galois connections). The previous three examples are special cases of monotone Galois connections. Every Galois connection between two posets is an adjunction.Further examples of adjunctions will appear in the rest of the text, and we even propose a zoo of adjunctions in the next section.

Definition 4 .

 4 19 (Whiskering). Let , : C → C and , : C → D be functors, and let : → and : → be natural transformations.

Definition 5 . 4 (Definition 5 . 5 (

 5455 Skeletal category). A category C is said skeletal when, for all objects , ∈ C , ⇒ = . Skeleton of a category). Let C be a category. A skeleton of C , denoted by (C ) is a full, skeletal subcategory of C such that the inclusion functor : (C ) ↩→ C verifies:∀ ∈ C , ∃ ∈ (C ) ,Example 5.6. In Sets, the skeleton is the class of cardinals: two isomorphic sets in Sets are simply sets with the same cardinality.

However: Proposition 5 . 10 .

 510 Every preorder category has a skeleton. Sketch of proof. Cf. Example 5.7.

5 .

 5 Which gives a triangle identity 0 • = id ; by Lemma 5.18, we have an adjoint equivalence. Finally, suppose ( , 1 ) also satisfies the triangle identities. Then, we have the following natural transformation diagramZoo of adjunctions which yields 0 = 1 and hence the unicity of 0 .

Proposition 5 .

 5 24. Let ∈ Δ, and ∈ . Then +1 +1 +1 .

  Consider the terminal category C 1 , consisting of only one object and only one identity morphism. Consider the functor : C → C 1 for some category C . Then, has a left (resp. right) adjoint ⇔ C has an initial (resp. terminal) object, and that left (resp. right) adjoint is init : C 1 → C (resp. term : C 1 → C ) which sends the unique object of C 1 to the initial (resp. terminal) object of C . The unit : Id C → term • has components : → 1 (the unique arrow from the UMP of the terminal object) and the counit : • term → Id C 1 consists in the only one arrow in C 1 .

Definition 6 . 6 (

 66 Product of categories). Let C and D be two categories. We define the category of pairs, or the product category C × D by: Objects: An object in C × D is a pair ( , ) where ∈ Ob C and ∈ Ob D Morphisms: A morphism in C × D is a pair ( , ) : ( , ) → ( , ) where : → ∈ Mor C and : → ∈ Mor D Identities: An identity morphism is a pair (id , id ) Composition: The composition law for morphisms is pairwise: ( , ) • ( , ) = ( • , • ) (using the composition laws of C and D)

  2 : ↦ → ( , ) is left adjoint to the coproduct functor -+ -: C × C → C . IMTA-RR-2019-01-SC 49/127 6. Objects with some universality in them Proof. If : + → then by definition of the coproduct, there are two arrows : → + and : → + such that = • + • ( • can be seen as the restriction of to ). Consider the mapping: , , :

Lemma 6 . 1 × 1 .

 611 31. If C has finite products, then C has a terminal object. IMTA-RR-2019-01-SC 53/127 6. Objects with some universality in them Proof. For any finite sequence of objects ( ) ∈ there is a product ∈ together with projections : ∈ → . If = 0, we have an object 1 with no projections, such that for all ∈ C , there is a unique arrow ! : → 1 such that no diagram commutes . Proposition 6.32. Let C be a category. If C has a terminal object 1, then Dually, if C has an initial object 0, then + 0 .

  → and : → such that = • and = • , as in the following diagram: Thus, we have: = • = • • , which gives the following diagram: • • • id By unicity of the arrow → which makes the diagram commute, we have • = id . A similar reasoning yields • = id . Proposition 6.40. Let ( , ) be an equaliser of , : → . Then is monic. Proof. Let , : → such that • = • . • = • By definition of an equaliser, we have • • = • • , so there exists a unique : → such that • = • = • . By unicity of , we have = = , hence is monic. Proposition 6.41. Let ( , ) be an equaliser of , : → .

+

  and such that, for all ( , , ) such that the following diagram commutes: there is a unique arrow : + → such that = • and = • , that is, such that the triangles and squares commute:+The arrows : → + and : → + are often called the inclusion mappings, just like in the coproduct.IMTA-RR-2019-01-SC63/127

Definition 7 . 2 (

 72 Category of diagrams). Let C , I be categories. The category of diagrams in C of shape I is the functor category Func (I , C ) = C I . Definition 7.3 (Diagonal functor). Let C , I be categories.

Definition 7 . 4 (

 74 also see Δ( ) as a sequence of copies of , indexed by the objects of I . Here, the arrows of I don't matter, as they always become id . If I is a category with two objects, then Δ( ) = ( , ). A better view of the action of Δ( ) is the following diagram: IMTA-RR-2019-01-SC 65arrows in the right diagram are identity arrows. Colimit). Let C , I be categories. Let Δ : C → C I be the diagonal functor and let : I → C be a diagram. The pair (Colim ( ), ) is the colimit diagram for when (Colim ( ) , ) is a universal arrow from to Δ. Remark 7.5. We have Colim ( ) ∈ Ob C , : → Δ (Colim ( )); that is, is a natural transformation between the two diagrams : I → C and Δ (Colim ( )) : I → C . Example 7.6. In Sets, a diagram : I → Sets is a functor that defines a small subcategory inside Sets. One might say it's a graph whose nodes are sets and whose arrows are functions such that the composite of two function is still an arrow in the graph. Note that, for all arrow : → in I , the arrow ( ) : → is a function between sets. Define = ∈Ob I to be the coproduct in Sets of all 's. For the sake of clarity, let us explicitly define this coproduct as: = ∈Ob I = {( , ) | ∈ Ob I , ∈ }

Example 7 . 7 .

 77 In a preorder category ( , ), the diagram : I → defines a sub-order, and the colimit of that diagram, if it exists, is the sup of all 's: Colim ( ) = sup ∈Ob I

Definition 7 . 10 (

 710 20) Note that : → Δ( ) is: IMTA-RR-2019-01-SC 66/127 7. Your only colimit is yourself = ( : ( ) → Δ( ) ( )) ∈I = ( : → ) ∈I and is: = ( ( ) : → Δ (Colim ( )) ( )) ∈I = ( ( ) : → Colim ( )) ∈I Finally, for : Colim ( ) → , we have Δ( ) = ( : Colim ( ) → ) ∈I . Thus, Equation 20 rewrites: ( : → ) ∈I = ( : Colim ( ) → ) ∈I • ( ( ) : → Colim ( )) ∈I : → Δ ( ) and : → Δ (Colim ( )) are natural transformations, the following diagrams commute: commute.We see some cone-like figures in red and orange, the base of which is the diagram with the 's. W call these figures cocones from to . Definition 7.10 makes it more formal.If follows from the previous remark that: Proposition 7.9. Let C , I be categories. Let Δ : C → C I be the diagonal functor and let :I → C be a diagram. Let ∈ Ob C and : → Δ ( ). The pair ( , ) is a colimit diagram for ⇔ ∀ ∈ Ob C , ∀ : → Δ( ), ∃! ∈ Hom C ( , ) such that ∀ ∈ Ob I , = • .Proof. See Remark 7.8. Otherwise, it follows from the definition of a colimit. The notion of cocone was introduced in Remark 7.8. Here is the formal definition: Category of cocones). Let C , I be categories. Let : I → C be a diagram. The category Cocones ( ) of cocones from contains: Objects: The objects are the natural transformations : two cocones. An arrow : → is an arrow : → such that the following diagram commutes: Identities: An identity morphism is an arrow id : → Composition: The composition law for morphisms is the composition law for morphisms in C . Example 7.11. In a preorder category, a cocone from to exists if and only if is an upper bound of the 's. Note that the colimit is the least upper bound of the 's. This fact is made formal in the following proposition. Proposition 7.12. Let C , I be categories. Let : I → C be a diagram. Let Cocones ( ) be the category of cocones from . Let ∈ C and : → Δ ( ). ( , ) is a colimit diagram for ⇔ is an initial object in Cocones ( ). IMTA-RR-2019-01-SC 68/127 7. Your only colimit is yourself Proof. Using Proposition 7.9, the proof is easy: is an initial object in Cocones ( ) ⇔∀ ∈ Ob C ∀ : → Δ( ), ∃! : → ⇔∀ ∈ Ob C ∀ : → Δ( ), ∃! : → such that ∀ ∈ Ob I = • ( ) ⇔∀ ∈ Ob C ∀ : → Δ( ), ∃! : → such that = Δ( ) • ⇔ ( , ) is a universal arrow from to Δ ⇔ ( , ) is a colimit diagram for Corollary 7.13. ( , ) is a colimit diagram for ⇔ is a cocone which is universal: for any cone : → Δ( ), ∃! :

Lemma 7 . 14 .

 714 If 0 is the initial object of C , then the unique arrows : 0 → define the unique natural transformation : Δ(0) → Id C . If 1 is the terminal object of C , then the unique arrows ! : → 1 define the unique natural transformation : Id C → Δ(1).

Proposition 7 .

 7 15. Let C be a category and let∈ Ob C . is terminal in C ⇔ is the colimit of Id C . Proof. [Proof of ⇒]Suppose is terminal in C . By Lemma 7.14, there is a unique natural transformation : Id C → Δ( ). This natural transformation is of course a cocone from to Id C .Let : Id C → Δ( ) be a cocone from to for some object ∈ C . We are looking for an so that the following diagram commutes: ! If = , we have: IMTA-RR-2019-01-SC 69/127 7. Your only colimit is yourself ! There is a unique arrow ! : → , and ! = id . Then, we have: = •! = . Consequently, is a morphism of cocones; but if : → 1 is another morphism of cocones, the following diagram commutes: id which gives = id • = = , hence the unicity of the . Finally, ( , ) is the colimit of Id C . [Proof of ⇐] Let ( , ) be the colimit of Id C . The first step consists in proving that is id . For all : → , the following diagram commutes: In particular, if = :

Remark 7 .

 7 18. We have Lim ( ) ∈ Ob C , : Δ (Lim ( )) → ; that is, is a natural transformation between the two diagrams Δ (Lim ( )) : I → C and : I → C . Example 7.19. As stated in Example 7.6, in Sets, a diagram : I → Sets is a functor that defines a small subcategory inside Sets.

4 Definition 7 .

 47 22 (Cone). Let : I → C be a diagram.

0 2 .

 2 A coproduct + in C is the colimit of the diagram : C 2 → C , with C 2 being the category with two objects and no arrow between those two: + 3. A pushout of : → and : → is the colimit of the diagram : C 3 → C , where C 3 is the category described below: + 4. A coequaliser of , : → is the colimit of the diagram : C 4 → C where C 4 is the category described below: IMTA-RR-2019-01-SC 73/127

Remark 7 .

 7 31. Consider the category D consisting in two objects and one arrow:• •Consider a diagram : D → C ; its image will be an arrow ( ) : 1 → 2 . What could be the limit and colimit of this diagram?

Theorem 7 .

 7 34. Let C be any category. The following propositions are equivalent: 1. C has finite products and equalisers 2. C has pullbacks and a terminal object 3. C has finite limits Proof. (1 ⇒ 2) By Corollary 6.57, products and equalisers give pullbacks, while by Lemma 6.31, having all finite products gives a terminal object. IMTA-RR-2019-01-SC 76/127 7. Your only colimit is yourself

  -RR-2019-01-SC 97/127 10. Sets-like categories Definition 10.11 (Set of subobjects). Let C be a category.For ∈ Ob C , we define SubObj C ( ) to be the set of all equivalence classes of subobjects of ; more explicitly:SubObj C ( ) = Ob SubObj (C ) /≡where ≡ is the equivalence of subobjects (Definition 10.4).

  SubObj C ( ) : → ↦ -→ SubObj C ( )where SubObj C ( ) is the set of subobjects (Definition 10.11) and SubObj C ( ) : SubObj C ( ) → SubObj C ( ) is the function introduced in Remark 10.12.

Corollary 10 .

 10 18. If the subobject functor SubObj C is representable, then its universal element is (Ω, ). Corollary 10.19. SubObj C (-) Hom C (-, Ω).

Theorem 11. 35 (

 35 Properties of a topos). Let E be a topos. Then E has all the following properties: It has all finite limits It has all finite colimits It has all exponentials Every object has a power object It has a subobject classifier It is Cartesian closed It is locally Cartesian closed Its slices are Cartesian closed Its slices are locally Cartesian closed Its slices are topoi Its isomorphisms are exactly the monic/epic It has all epi-mono factorisations IMTA-RR-2019-01-SC 116/127

  The mappings and are both actual natural isomorphisms, covariant in and contravariant in , and they are inverse of each other.

	Corollary 2.7 (Yoneda lemma

IMTA-RR-2019-01-SC 12/127 2. Yoneda lemma Proposition 2.6.

  The functor is saidfaithful if ∀ , ∈ Ob C , , is injective. (b) The functor is said full if ∀ , ∈ Ob C , , is surjective.3. The functor is called an embedding if it is injective on objects, full and faithful.

	2. Yoneda lemma
		(a)
	in C	2.12. Note that the Yoneda embedding is defined C op , and ( ) has the direction of ∈ C op .	op . Thus, : → in C becomes : →
	Definition 2.13 (Injective, surjective, full, faithful, embedding [1]). Let : C → D be a functor.
	1. (a) The functor is said injective (resp. surjective) on objects if Ob : Ob C → Ob D is injective
		(resp. surjective).
		(b) The functor is said injective (resp. surjective) on arrows if Mor : Mor C → Mor D is
		injective (resp. surjective).
	2. For all , ∈ Ob C , define the mapping:
		, :	Hom C ( , ) -→ Hom D ( ( ), ( )) ↦ -→ ( )
	IMTA-RR-2019-01-SC		16/127

Proposition 3.5. Let

  C be a category, and : C → Sets a functor. If ( 0 , 0 ) and ( 1 , 1 ) are universal elements for , then there exists a unique isomorphism : 0 → 1 such that ( ) ( 0 ) = 1 .

	3. Universal elements, universal arrows, representations
	Proof. If ( 0 , 0 ) and ( 1 , 1 ) are universal elements for , then by Universal Mapping Property (Proposi-
	tion 3.4):
	IMTA-RR-2019-01-SC	19/127

Corollary 3.11. Representations of a functor are unique up to isomorphism. Definition 3.12 (Universal arrows

  ) be a universal element for ; it follows from Definition 3.1 that , * ( * ) : Hom C ( * , -) → is a natural isomorphism. Thence, * , , * ( * ) is a representation of . Let ( * , ) be a representation of . By Proposition 2.6, we have = , * ( * (id * )).Besides, by definition of a representation, =, * ( * ( * )) is an isomorphism, which gives that ( * , * (id * )) is a universal element for .

	3. Universal elements, universal arrows, representations
	Proof of Lemma 3.9.
	Definition 3.6 (Representable functor). Let C be a category, and : C → Sets a functor.
	A representation of is a pair ( The functor is said representable if such a representation exists.
	Remark 3.7. As in Remark 3.3, a representation of a contravariant functor is a pair ( * , ) such that
	: Hom C (-, * ) → is a natural isomorphism.
	Lemma 3.8. Let C be a category, and : C → Sets a functor.
	If ( Lemma 3.9. Let C be a category, and : C → Sets a functor.
	If ( * , ) is a representation of , then ( * , * (id * )) is a universal element for .
	Theorem 3.10. Let C be a category, and : C → Sets a functor.
	There exists a universal element for ⇔ is representable.
	Theorem 3.10 is an immediate consequence of the two previous lemmas. Besides, the two lemmas give
	a way to convert a universal element into a representation.
	Proof of Lemma 3.8. Let ( IMTA-RR-2019-01-SC	20/127

* , ) where: * ∈ Ob C is called the representing object of : Hom C ( * , -) → is a natural isomorphism. * , * ) is a universal element for then * , , * ( * ) is a representation of . * , *

Proposition 3.15. Let

  When seeing the definitions of universal elements and arrows, we wonder what could be the link between both. In fact, universal arrows and universal elements are two very close notions. X , C be two categories. Let : X → C be a functor and let ∈ Ob C .

	3. Universal elements, universal arrows, representations
	If	# ,	is a universal arrow from	to , then	# ,	is also a universal element for
	Hom C ( , (-)).
	Item 2]
	Let ∈ C and ∈ X .
	We have	∈ Ob C and a natural isomorphism : Hom X ( , -) → Hom C ( , (-)). We have
	= Hom C ( , (-)),	id	, which by Item 1 yields that	,	id	is a universal arrow
	from to .
	IMTA-RR-2019-01-SC				21/127

  21. Proposition 4.20 simply states that whiskering (on the left or on the right) can be seen as a (left or right) monoid action of the monoid of functors (with composition) over the class of natural transformations. In other words, whiskerings and compositions are "associative" in a sense.

	Proposition 4.22. Let ,	: C → C and , : C → D be functors, and let :	→	and
	: →	be natural transformations.
	Then the following diagram commutes:

  This chapter is still about adjunctions, but we needed these notions in order to introduce the following: Definition 5.15 (Adjoint equivalence). Let C and X be two categories, with functors : X → C and : C → X . A pair of functors ( , ) is called an adjoint equivalence when ( , , , ) is an adjunction, and the unit : Id C → • and counit : • → Id X are natural isomorphisms.

	5. Zoo of adjunctions
	*		*	*	*	*	*	*
	*		*	*	*	*	*	*
		.	.
	*	*	*	*	*	*	*	*
	*		*	*	*	*	*	*
	2019-01-SC							38/127

  Let C be a category. If C has pullbacks and a terminal object, then C has finite products. Proof. Let , ∈ Ob C . There are unique arrows ! : → 1 and ! : → 1. Let ( × 1 , , ) be the pullback of ! and ! .

57. If a category has finite products and equalisers, then it has pullbacks.

Lemma 6.58.

  , hence the unicity of . Note that defines one arrow → for each ∈ Ob C ; so, for each ∈ Ob C , there is only one arrow → , so is terminal. Let C be a category and let , ∈ Ob C such that the coproduct ( + , , ) exists.

	7. Your only colimit is yourself
	Proposition 7.16.
	( ) ( )	id
	id
	which gives = IMTA-RR-2019-01-SC	70/127

  The composition law for morphisms is the composition law for morphisms in C . Remark 7.23. Note that a cocone is from the diagram to the object , while a cone is from the object to the diagram . Example 7.24. In a preorder category, a cone from to exists if and only if is a lower bound of the 's. Just like in Example 7.11, note that the limit is the greatest lower bound of the 's. This fact is made formal in Proposition 7.25. Remark 7.27. Colimits are the initial objects of the category of cocones (Proposition 7.12), while the terminal object of a category is the colimit of the identity functor (Proposition 7.15). Dually, limits are the terminal objects of the category of cones (Proposition 7.25), while the initial object of a category is the limit of the identity functor (Proposition 7.26). Try not to confuse!In the following, we mention the other limit diagrams; the proof is essentially the same as Proposition 7.16. → and : → is the limit of the diagram : C 3 → C , where C 3 is the index category described below: ×4. An equaliser of , : → is the limit of the diagram : C 4 → C where C 4 is the index category described below:

	7. Your only colimit is yourself 7. Your only colimit is yourself
	Objects: The objects are the natural transformations : Δ( ) → = called cones from to 3. A pullback of :	-→	∈Ob I	for ∈ Ob C ,
	Morphisms: Let : is an arrow : →	-→ such that the following diagram commutes: and : -→ be two cones. An arrow : → ∈Ob I ∈Ob I
	Identities: An identity morphism is an arrow id : →
	Composition: Proposition 7.28. The following constructions are limits:
	1. A terminal object in C is the limit of the empty diagram : ∅ → C , with ∅ as the empty category:
		1
	2. A product × in C is the limit of the diagram : C 2 → C , with C 2 being the index category with
	two objects and no arrow between those two:
		×
	IMTA-RR-2019-01-SC IMTA-RR-2019-01-SC				71/127 72/127

As the dual notion of colimit, we have the dual characterisations of limits: Proposition 7.25. Let C , I be categories. Let : I → C be a diagram. Let Cones ( ) be the category of cones to . Let ∈ C and : Δ ( ) → . ( , ) is a limit diagram for ⇔ is a terminal object in Cones ( ).

Proof. Similar to the proof of Proposition 7.12.

Proposition 7.26. Let C be a category and let ∈ Ob C . is initial in C ⇔ is the limit of Id C .

Proof. Similar to the proof of Proposition 7.15.

  7.35. Your only colimit is yourself Proof. (The proof written here is a resolution of [2, Exercise 3, Section 2.13, Chapter 9])We will start the proof with one special case of index category. We then give a hint for a second special case. Those two proofs generalise to any index category.Suppose I is any finite category with only one non-identity arrow : → . It will then look like this

	category:
	*	*	*
		*		*
	*
	*		*	*
	*		*
	Now let : I → C be any diagram.
	As C has finite products, the product	with arrows :
	∈

Lemma 7.33. Let C be any category. If C has finite products and equalisers, then C has finite limits. IMTA-RR-2019-01-SC 74/127 7. ∈I → exists. As C has equalisers, consider the equaliser ( , ) of ( ) • and . ∈I ( )•

  1 → 1 .Note that no assumption is made about 0 and 1 being distinct; we only suppose that 0 ≠ 1 and 0 ≠ 1 ; otherwise they would compose and give birth to a third arrow.For a diagram : I → C , we also build the product

	7. Your only colimit is yourself
	It will then look like this category:
	*	*	*
		*		*
	*
	*		*	*
	*		*
	IMTA-RR-2019-01-SC			75/127

∈I

with its projections : ∈I → .

Limits and adjunctions

We will now study some properties of adjunctions and their behaviour with regards to limits.

We start with a remark. We saw in Theorem 6.20 that + Δ 2 ×. There is a more general statement, that we mention but will only give a sketch of proof.

Let C be a category with finite limits, and let I be any finite category. The mappings:

Lim (-) :

are in fact functors. What is best, is that if Δ I : C → C I is the diagonal functor of shape I , then we have: Theorem 8.1. Colim (-) Δ I Lim (-) Sketch of proof. This can be deduced from the definitions of a limit (resp. of a colimit), due to the existence and unicity of the arrow → Lim ( ) (resp. Colim ( ) → ) whenever we have a cone Δ I ( ) → (resp. a cocone → Δ I ( )). This gives the bijectivity between Hom C I (Δ I ( ), ) and Hom C ( , Lim ( )) (resp. Hom C (Colim ( ) , ) and Hom C I ( , Δ I ( ))). We then have to check that this defines a natural transformation. The (contravariant) naturality in is easy, due to the definition of Δ I , while the naturality in requires a bit more attention not to confuse between cones and a natural transformation : → .

The main question we will tackle in this section is the following. Suppose we have a functor : C → D. Does it have an adjoint? How to know if it does or not? And if it does, how to find it?

A first step may be to look at some properties of adjoints. We deduce from Definition 4.1 and Theorem 3.17 that: Proposition 8.2. Let : C → Sets be functors. has a left adjoint ⇔ for all ∈ C , Hom Sets ( , (-)) has a universal element.

Another interesting property of adjoints is described right after the following definition. Just as some functors preserve products (see Definition 6.9), some functors preserve limits: Definition 8.3 (Preserving limits and colimits). Let I be an index category, and let C , D be categories.

We say that the functor : C → D preserves all limits (resp. small limits; resp. finite limits) when, for all index category (resp. small index category; resp. finite index category) I , for all diagram : I → C , if the limit (Lim ( ) , ) exists, then ( (Lim ( )) , ( )) is the limit of the diagram • .

Dually, we say that the functor : C → D preserves all colimits (resp. small colimits; resp. finite colimits) when, for all index category (resp. small index category; resp. finite index category) I , for all diagram : I → C , if the colimit (Colim ( ) , ) exists, then ( (Colim ( )) , ( )) is the colimit of the diagram • . Proof. By Theorem 7.34, it suffices to show that Hom C ( , -) preserves finite products and equalisers. We already know from Proposition 6.10 that Hom C ( , -) preserves binary products. For it to preserve finite products, we need to show that it preserves the terminal object. If is the terminal object in C then Hom C ( , ) contains only one arrow (the unique arrow → in C ). Consequently, Hom C ( , ) 1 (where 1 is the terminal object of Sets) and Hom C ( , -) preserves the terminal object.

IMTA-RR-2019-01-SC

78/127

Limits and adjunctions

Now, let ( , ) be the equaliser of , : → . For all : → such that • = • , there is a unique : → such that the following diagram commutes:

The hom-set functor preserves the diagram (this is a property of functors). We need to check whether (Hom C ( , ) , Hom C ( , )) is an equaliser of Hom C ( , ) and Hom C ( , ). Let ℎ : → Hom C ( , ) such that Hom C ( , ) • ℎ = Hom C ( , ) • ℎ as in the diagram:

Hom C ( , ) Hom C ( , )

Hom C ( , )

We need to find a : → Hom C ( , ) such that Hom C ( , ) • = ℎ. Let ∈ . We have ℎ( ) : → and:

So, the equaliser in C applies here: there is a unique ( ) : → such that • ( ( )) = ℎ( ). Define to be: :

-→ Hom C ( , ) ↦ -→ ( )

Then, by construction, for all ∈ , ℎ( ) = • ( ( )) = (Hom C ( , ) • ) ( ) and is unique. Consequently, (Hom C ( , ) , Hom C ( , )) is still an equaliser.

Corollary 8.5. Representable functors preserve all finite limits.

The dual version of this theorem is the following: Proposition 8.6. The contravariant Hom-set functor Hom C (-, ) sends finite colimits to finite limits.

Proof. We have to show that the contravariant sends the initial object to the terminal object, the coproduct to the product, and the coequalisers to equalisers.

We have Hom C (0, ) 1 because there is only one arrow 0 → (definition of an initial object). Let : → and : → be two arrows; by definition of the coproduct + , there is a unique : + → such that the following diagram commutes: + This exactly says that there is a bijection (an isomorphism in Sets):

IMTA-RR-2019-01-SC 79/127

Limits and adjunctions

, :

This isomorphism is natural in + :

Seeing the coproduct as a colimit, we deduce that the following diagram commutes: We have:

The naturality in is similar. Finally, as for seeing that the contravariant Hom-set functor sends coequalisers to equalisers, the proof is very similar to showing that the covariant Hom-set functor preserves equalisers.

In fact, these theorems are not only true for finite limits, but also for small limits. As there is something I don't understand here, because a product of any set of sets could be empty (without the Axiom of Choice) (but always exists?) , we will trust Awodey [1, Chapter 5, Proposition 5.25, p107] and admit the following proposition and corollaries: Proposition 8.7. Let C be a category with small limits and let ∈ Ob C .

The covariant Hom-set functor Hom C ( , -) preserves all small limits.

IMTA-RR-2019-01-SC 80/127

Limits and adjunctions

Corollary 8.8. Representable functors preserve all small limits. Proposition 8.9. The contravariant Hom-set functor Hom C (-, ) sends small colimits to small limits.

Proposition 8.10 (Right Adjoints Preserve Limits [2], [1]). Let ( , , ) be an adjunction. Then preserves colimits and preserves limits.

This proposition is commonly refered to as the the "RAPL" ("Right Adjoints Preserve Limits").

Proof. Suppose : C → X , : X → C and let : I → X be a diagram with a limit Lim ( ).

For ∈ C , we have:

Lim (Hom C ( ( ), (-)))

The first and third equations are due to the adjunction, while the second and fourth are due to the preservation of limits by the Hom-set functor (Proposition 8.4). As a consequence of Yoneda Lemma (Corollary 2.17), we deduce:

Similarly, if : I → X has a colimit Colim ( ), and for ∈ X :

Lim (Hom C ( (-), ( )))

Which also gives (by Corollary 2.18):

Definition 8.11 (Complete category). A category C is said complete (resp. cocomplete) when it has all small limits (resp. all small colimits).

Example 8.12. The category Sets is complete and cocomplete. Of course Sets has all finite limits (because it has products, equalisers, a terminal object and pullbacks) and colimits (because it has coproducts, coequalisers, an initial object and pushouts), but in the rest of this course, we will just admit that Sets has all small limits and colimits.

Definition 8.13 (Continuous functor). A functor : C → D is called continuous (resp. cocontinuous) if it preserves all small limits (resp. all small colimits).

Example 8.14. The covariant Hom-set functor is continuous but not cocontinuous.

We now move towards the next important theorem: the adjoint functor theorem. There are a few details to expand before.

IMTA-RR-2019-01-SC

81/127

Limits and adjunctions

Definition 8.15 (Weakly initial [START_REF] Leinster | Basic Category Theory, ser[END_REF]). Let C be any category.

A set * = { ∈ Ob C | ∈ } of objects in C is a weakly initial set when for all ∈ C , there is an ∈ such that there is an arrow → . "There exists a set of objects that connects to any other object of the category" or "there is a (nonnecessarily connected) subgraph that is connected to the rest of the category", or "there is some weakly initial subset of objects". Lemma 8.16 ([7], [1]). Let C be a locally small, complete category.

C has an initial object ⇔ There is a weakly initial set of objects in C

Proof. If C has an initial object, then any set containing that initial object is weakly initial. Suppose that ( ) ∈ is a weakly initial set in C . Consider the category C defined by: Objects: The objects of C are the for ∈

Identities: An identity morphism of an object is an identity morphism id ∈ C

Composition:

The composition law for morphisms is the usual composition in C

It is easy to see that C is a small subcategory of C . Then, the inclusion mapping:

:

is a functor; or rather, as C is small, is a small diagram. As C is complete, it has a limit Lim ( ).

We now show that Lim ( ) is initial. Clearly, for all ∈ C , there is an arrow : → . As Lim ( ) is the limit of , there is also an arrow : Lim ( ) → , so for all ∈ C , there is an arrow: Lim ( ) → , but this arrow is not necessarily unique.

Let , : Lim ( ) → be two arrows, and let ( , ) be an equaliser of and . There is an ∈ such that:

Besides, by unicity of the arrow Lim ( ) → Lim ( ), we deduce that:

which gives:

Consequently, there is a unique arrow Lim ( ) → for any ∈ C ; so Lim ( ) is an initial object.

IMTA-RR-2019-01-SC

82/127

Limits and adjunctions

Definition 8.17 (Comma-category). Let : C → X and : D → X be two functors.

The comma-category ( | ) is the category described below:

Objects: The objects of ( | ) are triples ( , , ) such that : ( ) → ( ), ∈ C and ∈ D Morphisms: A morphism ( , , ) → ( , , ) is a pair ( , ) such that : → , : → and the following square commutes:

Identities:

The identity morphism of an object ( , , ) is the pair (id , id )

Composition:

The composition law for morphisms is the usual composition ( ,

If is the diagonal functor Δ( ) for some ∈ C , then the comma-category is written ( | ) and simplifies to: If X is locally small, then the comma-category ( | ) is also locally small.

Proof. Just note that, for any , ∈ X , Hom C ( , ) is a set. Also, note that Hom C (( , ) , ( , )) ⊂ Hom C ( , ). Proof. Let us recall the definition of a universal arrow from to : it is a pair # , such that:

# ∈ X and : → # for all ∈ X , for all : → ( ), there is a unique : # → such that = ( ) •

An initial object in ( | ) is a pair ( , ) where ∈ X and : → ( ) such that for all object ( , ) ∈ ( | ), there is a unique arrow such that the following triangle commutes:

Both definitions are equivalent, hence the result. We can finally prove the following version of the Adjoint Functor Theorem, as it appears in [1]: Note that if the category X is small (instead of only locally small) then the condition on the weakly initial set is useless. We then have the following corollary: Corollary 8.24. Let X be small (not only locally small) and complete. Let : X → Sets be a functor. This is powerful because it means that we can, in a sense, add some structure to a Set in order to make it a group or a ring (not exactly because axiom of choice)

If : -Models → Sets is the forgetful functor, then there is an adjoint : Sets → -Models such that, for all ∈ Sets, for all ∈ -Models, we have:

The adjoint of is called the free functor. In short, the free functor : Sets → -Models is the functor that maps a set to a structure "generated" by that set (for example, if is the theory of vector spaces, then the free functor will consider that a given set is a basis, and will build a vector space using this basis).

See MacLane Chapter IV, pp87-88 for a list of adjoints, some of them being between forgetful and free functors.

According to nLab: A general way to construct free functors is with a transfinite construction of free algebras (in set-theoretic foundations), or with an inductive type or higher inductive type (in type-theoretic foundations). Remark 8.26. Consider two categories Sets C and D, and a functor : Sets C → D. Suppose we want to find : D → Sets C the right adjoint of (we suppose that such an adjoint exists). We will study the behaviour of on objects and arrows.

Let ∈ D; we have ( ) ∈ Sets C : it is a contravariant functor ( ) : C → Sets. By Yoneda Lemma, for some ∈ C , we have:

where the second equation is the definition of an adjunction. The simplest choice of ( ) should be:

So we have the behaviour of ( ) on objects. On arrows : → , we suppose that ( ) is a functor C → Sets; so, by Yoneda lemma, the following diagram should commute:

8. Limits and adjunctions

where ( ), is the Yoneda isomorphism Nat (Hom C ( ,-) , ( )) → ( ) ( ) and ( ), is its inverse (cf. Definitions 2.4 and 2.5).

We deduce a (brutal) formula for ( ) ( ):

Finally, we want the behaviour of ( ). For ∈ C , we have:

So we have now described the functor : D → Sets C in terms of functors and natural transformations whose expression we know.

In the same vein of the Adjoint Functor Theorem, the following proposition is sometimes useful when we have to prove that some functor has a right adjoint.

In the special case where we only have finite limits, we have the converse to Proposition 6.23 (exponential is right adjoint to product). Proposition 8.27. Let C be a category with all finite limits, and ∈ C . Let be the functor:

Then, there exists a right adjoint to ⇔ for all , the exponential exists.

Proof. The proof falls beyond the scope of this course. See [2, Chapter 13, Section 13.3, Exercise 5, p359] for an exercise that will guide you into the proof of ⇒.

Note that Proposition 6.23 is exactly ⇐. This proposition will be useful later in order to prove that some functor in a category with finite limits, has a right adjoint.

IMTA-RR-2019-01-SC

86/127 9. Monads

Monads

Monads are yet another concept of category theory; basically, it is a functor from a category to itsef, together with two natural transformations that follow some rules. Monads have links with adjunctions and reciprocally; however, they are not equivalent.

Definition 9.1 (Monad). A monad on C is a triple ( , , ) such that:

1. : C → C is a functor 2. : Id C → is a natural transformation, called the unit 3. : • → is a natural transformation, called the multiplication and the following diagrams commute:

The square diagram is sometimes referred to as the "associativity" diagram, and the bi-triangle one is sometimes called the "identity" diagram. Both names are not random. In fact, a monad is a generalisation of the notion of monoid in the form of a functor.

is an endofunctor (a functor from C to itself) that sets a framework for the monoid-looking structure given by the multiplication and the unit , that behave as expected from them, according to the diagrams.

If there is no ambiguity, we refer to as monad, instead of the whole triple ( , , ). Just like adjunctions, examples of monads are legion. We are not going to make a whole section just for monads. We will just give a few examples. For now, the utility and context in which these monads appear will be intentionally left unexplained, but will be revealed as we progress through the section.

Example 9.2. The functor : Sets → Sets defined by: :

where 1 is the terminal object and + denotes the coproduct, is a monad. Its unit = ( ) ∈Sets and multiplication = ( ) ∈Sets are:

where 0 is the unique element of 1 (it appears twice in + 1 + 1 and only once in + 1). This example may be extended by replacing 1 with any given set ∈ Sets.

Example 9.3. If is a set, denote by < the set of finite sequences over , that is, < = ∈ . The following functor is a monad:

:

and the components of its multiplication = : ( < ) < → < ∈Sets send a nested tuple to its concatenation (we may also call this operation "flatten"): : 0 0 , . . . , 0 0 , . . . , 0 , . . . , ↦ → 0 0 , . . . , 0 0 , . . . , 0 , . . . , Example 9.4. Let ( , , * ) be a monoid.

The functor : → × , equipped with the natural transformations with components:

is also a monad.

Example 9.5. Fix a set . As seen in Proposition 6.23, the exponential (-) is right adjoint to the product -× , and the evaluation : × → is in fact a component of the counit of that adjunction. As mentioned in Remark 6.26, the unit is made of the arrows : → ( × ) that are the curryfications of id × . In short, : → ( ↦ → ( , )). For a given set ∈ Sets, define the following natural transformation with components:

where is a function : ↦ → ( 1 ( ), 2 ( )), with, for all ∈ , 1 ( ) ∈ ( × ) and 1 ( ) ∈ . Then, the functor ↦ → ( × ) , equipped with the unit of the product-exponential adjunction and the multiplication defined above, is a monad. This last example is in fact an application of the following proposition: Proof. The identity diagram derives from the triangle identities of adjoints (cf. Definition 4.24). Composing the left-adjoint triangle with on the left and composing the right-adjoint triangle with on the right, we obtain:

Gluing the two triangles on the common arrow • • yields the identity diagram of a monad. Then, consider an arrow : • ( ) → ; as is a natural transformation : • → Id X , the following square commutes:

9. Monads which yields:

and by composing the previous diagram with on the left, and on the right, we obtain the associativity diagram of the monad.

Of course, monads generate categories. We will see two of these categories: Definition 9.7 (Eilenberg-Moore category). Let ( , , ) be a monad on C . The Eilenberg-Moore category associated with ( , , ), denoted C , is the following category:

Objects: An object is a pair ( , ) where ∈ C and : ( ) → ∈ C such that the following diagrams commute:

Morphisms: An arrow : ( , ) → ( , ) is an arrow : → ∈ C such that the following diagram commutes:

Identities: The identity of ( , ) is an identity id

Composition: The composition of arrows is the composition in C

An object of the Eilenberg-Moore category C is often called an algebra over or -algebra. As stated before, monads generalise the idea of a monoid. Algebras over a monad generalise the notion of module over a ring. is actually an object of Sets (making the right diagrams commute). It is also easy to see that monoid morphisms translate to an arrow in Sets . Now, each object ( , : < → ) of Sets can also be seen as a monoid. In fact, define * as the restriction of to 2 , and take = (()) (the image by of the empty tuple); then, it is easy to see that ( , * , ) follow the axioms of monoids. Then, a morphism in Sets is easily seen as a monoid morphism.

What this example claims is the following: Sets Monoids, the isomorphism being the one we described above. Definition 9.9 (Free and forgetful functor associated with a monad). Let ( , , ) be a monad.

The free functor associated with , denoted by Free , is the following functor:

Free :

The forgetful functor associated with , denoted by Forget , is the following functor:

Forget :

In a sense, the free functor "creates", or "enforces", the structure of the monad, while the forgetful functor "forgets", or "nullifies", the structure of the monad.

The reader having read Sections 4 or 5 knows that examples of adjunctions include free/forgetful pairs. This is the reason why: Proposition 9.10. Let ( , , ) be a monad.

Then, Free Forget .

Proof. We must compute the adjunctor:

However, first note that Forget • Free = , so the unit of that adjunction will be the unit of the monad. By Lemma 4.10, the adjunctor is written , ( , ) : ↦ → Forget ( ) • . We have obviously defined a natural transformation; we have to check that this defines a bijection.

Let us give the inverse of . Let ∈ Hom C , Forget ( , ) ; as Forget ( , ) = , and ( , ) ∈ C , the following diagram commutes:

This diagram shows that • ( ) is an arrow ( ) → ( , ). Therefore, it suggests that for a given : → Forget ( , ), the corresponding arrow in C should be • ( ), which should be the inverse of , ( , ) . Define , ( , ) : ↦ → • ( ).

Then let : ( ) → ( , ); we have the following diagram:

The square commutes because is an arrow ( ( ), ) → ( , ) and the triangle commutes due to half of the identity diagram of a monad. We thus have:

As for the converse, note that the image of Diagram 23 by Forget is:

In the following diagram, the square commutes because : Id C → is a natural transformation, and the triangle commutes because ( , ) is an object of an Eilenberg-Moore category:

Using this diagram, we have:

Thence, is a natural isomorphism, and an adjunctor, and Free Forget .

Definition 9.11 (Eilenberg-Moore adjunction). Let ( , , ) be a monad. The adjunction Free Forget is called the Eilenberg-Moore adjunction of . In order to set the notations, we denote by and the unit and counit of that adjunction.

Remark 9.12. We can also deduce from the proof of Proposition 9.10 that the unit of the adjunction is = , that is, the unit of the monad, and the counit is defined by:

IMTA-RR-2019-01-SC 91/127

Monads

So, every time we have a monad, we have an adjunction, and every time we have an adjunction, we have a monad! However, there is no bijection between monads and adjunctions, as many adjunctions can give the same monad, and a monad gives rise to two adjunctions. Definition 9.13 (Category of adjunctions). Let ( , , ) be a monad on C .

The category of adjunctions associated to , denoted by Adj ( ), is the following category:

Objects: Objects are the adjunctions ( : C → X , , , ) such that

Identities: Identities are the identity functors

Composition: The composition is the usual composition of functors Remark 9.14. In [5, section 7, chapter VI, page 99], there are two more conditions; in fact, that = , or equivalently, that = , which is necessarily the case here, because we are considering a category of adjunctions that generate the same given monad. In Definition 9.13, we are considering the special case where from the book is here, and from the book is Id C here. Proposition 9.15. Let : ( , , , ) → ( , , , ) be an arrow in Adj ( ) for a given ( , , ). Denote by : Hom X ( (-), -) → Hom C (-, (-)) and : Hom X ( (-), -) → Hom C (-, (-)) the corresponding adjunctors.

Then:

1. For all ∈ C and ∈ X , the following diagram commutes:

Hom X ( • ( ) , ( ))

2. For all ∈ C and ∈ X , the following diagram commutes:

Hom X ( • ( ) , ( ))

Proof. [Proof of Item 3] Item 3 is obvious, as we are in a category of the form Adj ( ), so:

from which we deduce = .

[Proof of Item 1] Let : ( ) → be an arrow. Then, ( ) is an arrow • ( ) → ( ), and using Lemma 4.10, we have:

) and = • , we have:

[Proof of Item 2] It is equivalent to Item 1.

[Proof of Item 4]

In the diagram of Item 2, set = ( ), and choose id ( ) . We then have:

hence the result.

The Eilenberg-Moore adjunction (Definition 9.11) is a specific object in that category: Proposition 9.16. Let be a monad and Free Forget its Eilenberg-Moore adjunction. Then Free , Forget , , is the terminal object of Adj ( ).

Proof. Let ( , , , ) be an adjunction C X . We are looking for a unique arrow : X → C such that Forget • = . This gives the hint that ( ) should be of the form ( ( ), ) and for : → , ( ) should be ( ). As should be an arrow : ( ) → ( ) that verifies the diagrams of Definition 9.7, and in particular, the triangle identity, a good candidate for seems to be ( ).

Define:

We let the reader check that actually is a functor, that Forget • = and that • = Free . We have the existence; we now have to check the unicity.

Let : X → C be another functor such that Forget • = and • Free = . For ∈ X , we have Forget • ( ) = ( ). As seen above, for ∈ X , ( ) will be of the form ( ( ), ) where : ( ) → ( ), and for : → , ( ) needs to be ( ). The only potential difference between and lies in the comparison of the arrow in the pair ( ( ), ), in that could be different to ( ). Now, we have:

Sets-like categories

Besides adjoints, elementary topoi (plural of "topos" in Greek) are the second big part of this course. Before exploring this notion, we have to introduce some amount of notions around the following theme: introduction of set-like elements in categories.

We start with the categorical equivalent of a subset.

In Sets, when ⊂ , if : → is the inclusion, then ( , ) is an equaliser, and is a monomorphism.

In several categories based on sets (for example, the category of groups, the category of graphs, the category of rings; of "sets with structure"), when we have ⊂ , if : → is a monic inclusion (that is, "an inclusion that respects the structure"), then ( ) is a sub-"set with structure" (for example, a subgroup, a subgraph, a subring...) of . The subobjects of R are any injections : → R. Consequently, the subobjects of R are not only the (inclusions of) subsets of R but also any injection from to R where card ( ) card (R).

Note that if card ( ) card (R), then there are card R injections from → R, and each injection is a different subobject. As the collection of all sets with a certain cardinality is large (not a set) we deduce that SubObj Sets (R) is a large category (but locally small, according to the next proposition). → ; as SubObj C ( ) is a preorder, there is at most one arrow between two subobjects, so • = id . Similarly, • = id , so = -1 and .

If

, then let : → be an isomorphism; we deduce that ⊂ . Also, -1 is an isomorphism, so ⊂ , and ≡ .

Corollary 10.6. Equivalent subobjects have isomorphic domains.

Remark 10.7. If ( , ) is the equaliser of , : → , then is a subobject of (cf. Proposition 6.40).

Remark 10.8. In SubObj Sets (R), take : → R and : → R. If ≡ , then there is a bijection between both; equivalently, card ( ) = card ( ). Consequently, the equivalence classes of the subobjects of R are the cardinals card (R). If you consider a category Sets with the Continuum Hypothesis, then

If Sets respects the axiom of choice, then this is true for any set: the equivalence classes of the subobjects of a set are the cardinals card ( ).

Proposition 10.9. Let C be a category. Let : → be an arrow, and let : → be a subobject of .

Suppose that the following diagram is a pullback:

Then : → is also a subobject of . In other words: the pullback of a subobject is a subobject (or more generally: the pullback of a monomorphism is a monomorphism).

Proof. Suppose there are two arrows , : → such that • = • .

By the universality of the pullback, the arrow : → is unique, so = . Thus, is monic.

Proposition 10.10. Let C be a category. Let : → be an arrow, let : → and 0 : 0 → be subobjects of .

Suppose that the two following squares are pullbacks:

Proof. Let 0 be the isomorphism 0 : 0 → . Consider the following diagram:

As 0 : 0 → is an isomorphism between subobjects, we have • 0 = 0 . We then deduce from the diagrams 27 that:

Let C be a category with finite limits. Let ∈ C . The power object of is unique up to isomorphism.

Proof. Let (P ( ) , ) and ( , ) be two power objects of .

Considering the unicity of , , id P ( ) and id , and noticing that each adjacent two pullbacks are pullbacks, we have = -1 . Proposition 10.23. Let C be a category with finite limits. Let ∈ C with a power object P ( ).

For all ∈ C , Hom C ( , P ( )) SubObj C ( × ) naturally in .

Proof. By definition of a power object, there is a bijection : Hom C ( , P ( )) → SubObj C ( × ). Let : → be an arrow; we check wether the following diagram commutes:

We want:

Let : → P ( ); there is a unique subobject ℎ : → × such that the following is a pullback:

Besides, SubObj C ( × ) (ℎ ) is defined as the unique ℎ that makes the following diagram a pullback:

IMTA-RR-2019-01-SC 101/127

Sets-like categories

We deduce:

Then:

where ℎ is the unique arrow such that the following diagram is a pullback:

Note that the above diagram decomposes into this:

(The arrow → can be obtained knowing that the right square is a pullback.) By Proposition 6.55, if the right square ( × P ( )) ( × ) and the outer rectangle ( × P ( ))( × ) are pullbacks, then the left square ( × ) ( × ) is also a pullback; by unicity of ℎ (from Diagram 29) and ℎ (from Diagram 28), we deduce that ℎ = ℎ , which let us conclude:

In Sets, we know that P ( ) 2 (because each characteristic function → 2 defines a subset of and conversely). There is a similar result with the categorical equivalents of a subobject classifier and the power object.

Elementary topoi

We can now introduce topoi. We will first see the general notion of elementary topoi (which we will simply call topoi) and we will then study the notion of a Grothendieck topos.

Definition 11.1 (Elementary topos (1) [1]). An elementary topos (or topos for short) is a category E that has finite limits, all exponentials, and a subobject classifier.

Definition 11.2 (Elementary topos (2) [2]). An elementary topos (or topos for short) is a category E that is cartesian closed, has finite limits, and a representable subobject functor.

Definition 11.3 (Elementary topos (3) [START_REF] Barr | ser. Reprints in Theory and Applications of Categories[END_REF]). An elementary topos (or topos for short) is a category E that has finite limits and such that every object has a power object.

Of course:

Proposition 11.4. The three definitions of a topos are equivalent.

In fact, it is easy to see that (2) ⇔ (1) ⇒ (3); however (3) ⇒ (1) requires some more work. Let us just admit this proposition.

Example 11.5. As we have seen through this course, Sets has finite limits, all exponentials, a subobject classifier, every set has a powerset: Sets is an elementary topos. In fact, topoi are thought as categories that "roughly" behave like Sets.

As a first property of elementary topoi, we give the following theorem, but will not prove it as it is far from the scope of this course.

Proposition 11.6. A topos has finite colimits.

Proof. According to [2, Theorem 15.2.8, p389], this is very hard to prove, and the demonstration requires many notions that are beyond the scope of this course. We will just admit this theorem.

Proposition 11.7. Let E be a topos. A monomorphism in E is an equaliser.

Proof. According to the definition of a subobject classifier (Ω, ), a monomorphism :

→ is indeed the equaliser of : → Ω and ! • .

Proposition 11.8. Let E be a topos. The isomorphisms in E are exactly the monic/epic.

Proof. By Corollary 1.16, every isomorphism is both monic and epic; this is true in any category. The converse comes from the topos-ness of E . In a topos, all monomorphisms are equalisers, thus all monic/epic are epic equalisers, and by Proposition 6.42, all epic equalisers are isomorphisms. Definition 11.9 (Image of an arrow [START_REF] Maclane | Sheaves in Geometry and Logic[END_REF]). Let : → be an arrow.

We say that factors through : → when there exists : → such that = • . The image of is a monomorphism : → such that factors through , and for all monomorphism , if factors through , then so does .

Remark 11.10 (Explicit definition). The image of is a monomorphism : → such that there exists : → such that = • , and for all monomorphism : → , if there exists : → such that =

• , then there exists : → such that = • . In a sense, the image of is the "smallest" subobject of through which can factor.

In Sets, the image of a function : → is the inclusion mapping ( ) → . Definition 11.11 (Epi-mono factorisation). Let : → be an arrow in a category C .

An epi-mono factorisation of is a pair ( , ) where : → is a monomorphism and : → is an epimorphism such that = • .

A category C is said to have epi-mono factorisations when every arrow has an epi-mono factorisation.

IMTA-RR-2019-01-SC 104/127

Elementary topoi

In Sets, this property is very easy to see. Let : → ; then we can define : → ( ) (the restriction of to its image) and then : ( ) → as the inclusion function. Then is epic (i.e. a surjection) and is monic (i.e. an injection). As said before, topoi generalise in a sense the category of sets; and the following proposition holds: Proposition 11.12. Let E be a topos. Then E has epi-mono factorisations.

Proof. We need the fact that a topos has colimits. Let : → be a function; the pushout of with exists: and • = • . Let ( , ) be the equaliser of and ; there exists a unique such that = • :

We now show that is the image of . Suppose =

• for some monic : → . As we are in a topos, the monic is an equaliser of some , : → , as in the diagram:

As • = • , and using the fact that is a pushout of with itself, there is a unique arrow : → such that = • and = • , as in the following diagram:

Now, we have:

being the equaliser of and , there is a unique : → such that = • ; so is indeed the image of .

IMTA-RR-2019-01-SC

105/127

Elementary topoi

The only fact to prove now is the epicness of . To do so, let us introduce and explain the following diagram:

We have proven that every arrow factors through some monomorphism thanks to some pushout; then there are two arrows , :

→ such that and are the pushout of with itself, and there exist : → and a monomorphism : → such that = • , and is the equaliser of and .

First, let us focus on and . We have = • = • • ; so factors through • , which is monic (composition of monomorphisms is monic). As is the image of , also does: there exists a : → such that = • • ; as is monic, we deduce:

as is also monic; but as • = id and • = id , we deduce that is an isomorphism. Now, consider and , the pushout of with itself, with being the equaliser of and . As is an isomorphism, we have = . Now let , :

→ be such that • = • ; as and are a pushout of with itself, there exists a unique such that: and = • = • = . Thus, is epic.

For the following property of a topos, let us get back to slice categories. We did not introduce slice categories as such, but rather, comma-categories (Definition 8.17). Definition 11.13 (Slice category). Let C be a category, and let ∈ C be an object.

The slice category of C over , simply written C / , is the following category: Proof. The proof is quite easy. Define the functors:

:

Then clearly is the inverse of ; thus defines an isomorphism between C and C /1.

Another obvious fact is that any slice category has a terminal object:

Proposition 11.16. In the slice category C / , id is the terminal object.

Proposition 11.17. Let C be a category and be an object in C . Consider the following diagram:

Proof. Just compare the universal properties of (as a pullback) and (as a product).

Let us spend some time studying examples of slice categories, as they will turn crucial in our understanding of some properties of topoi.

Example 11.18 (Slice category in a preorder). Consider the preorder ( , ). Let ∈ ; what does slice category / look like? It is the following category:

Objects: The objects are the arrows q : → ; that is, the objects are the pairs q = ( , ) such that .

Morphisms:

The arrows x : q → q are such that the following diagram commutes:

x q q That is, arrows x : q → q are simply pairs ( , ) such that .

IMTA-RR-2019-01-SC 107/127

Elementary topoi

Identities: The identity morphism of q : → is simply the reflexivity rule of a partial order.

Composition:

The composition law for morphisms is the transitivity of the preorder.

In summary, the slice category of a preorder / is a truncated version of the preorder , made with only the objects that are below (which have arrows that target ) (in red in the following diagram). Let us start from the easy questions. What is the size of Sets/ ?

The objects of Sets/ are all the functions : → . As there are always card ( ) card( ) > card ( ) functions between and , for each set , there are card ( ) card( ) arrows → . Thus, Sets/ is a large category.

As for the morphisms; an arrow : → between : → and :

→ is an arrow : → with some additional properties (the commutative triangle). We deduce that Hom ( , ) ⊂ Hom ( , ). Therefore, Sets/ is locally small, because Sets is.

Another question one may ask is: can we have two arrows : → and : → and ≠ , that is, two different arrows from the same source? Consider the following functions:

where 2 = {0, 1} (the set-theoretic natural number 2). They are different functions and thus, different objects in Sets/2.

There is also an arrow between them. The successor function:

is an arrow succ : mod 2 → dom 2 in Sets/2.

IMTA-RR-2019-01-SC 108/127

Elementary topoi

Intuitively, the slice category Sets/ is a kind of "zoom" on how "sees" Sets. This zoom somehow individualises the arrows that target ; in fact, mod 2 and dom 2 are indiscernible in Sets (they are arrows from the same source N) while in Sets/2, they are different objects. Now consider the functions:

where mod 2 is the obvious extension of mod 2 : N → 2 to N → 3 (we could have used different symbols but it was only making the notations inconvenient).

Is there an arrow : mod 2 → mod 3 ? That is, a function such that mod 2 = ( ) mod 3. The function mod 2 : N → N (extension of mod 2 ) does the job, but there are an infinity of functions that would do the job as well, for example:

What about an arrow : mod 3 → mod 2 ? That is, a function such that mod 3 = ( ) mod 2. Such a function does not exist, because there is no such that mod 2 = 2 mod 3 = 2 (note that we are not considering Z/(2Z), so the modulo operation only applies once). We conclude that there is no arrow mod 3 → mod 2 .

What condition makes it possible to have an arrow between two functions : → and : → ? The previous example becomes obvious once we see that mod 2 (N) mod 3 (N). Consequently, there cannot be arrows mod 3 → mod 2 . This seems to be the condition we are looking for. In fact, we can show that, in Sets/ , there is an arrow : → between : → and :

→ if and only if ( ) ⊂ ( ). As a corollary, there are arrows : → and : → if and only if ( ) = ( ).

In other words, the slice category induces a preorder on the functions that target : for : → and :

→ , we have ⇔ ( ) ⊂ ( ). This preorder gives the general structure of a slice category Sets/ . We will see in another example (Example 11.32) another interpretation of a slice category in Sets.

Remark 11.20 (Slice of slice). Let C be a category and : → be an arrow in C .

Consider the category C / . The arrow : → is an object in C / . We can keep "slicing" the category. Let's have a closer look at (C / ) / .

An object in (C / ) / is an arrow : → ∈ Mor C / , that is, such that the following triangle commutes: The composition functor of , or dependent sum relative to , written Σ , is the following functor:

11. Elementary topoi Remark 11.23. Note that, in the definition of the composition functor, for : → , we have the following diagram:

which gives, by composition by : Consequently, an arrow ∈ C / is also an arrow ∈ C / .

Definition 11.24 (Pullback functor). Let C be a category with all pullbacks, and let : → be an arrow in C .

The pullback functor * is the following functor:

where, for : → , * ( ) is such that the following square is a pullback: * ( )

and for an arrow : → , * ( ) is the unique arrow → between pullbacks such that the following diagram commutes: * ( ) * ( ) * ( ) Proposition 11.25. Let C be a category with pullbacks. Let : → be an arrow in C .

Then, Σ * ; that is, the composition functor is left adjoint to the pullback functor.

Proof. Let : → and : → . We have to check that there is a natural isomorphism:

IMTA-RR-2019-01-SC 111/127

Elementary topoi

Let ∈ Hom C Σ ( ), ; the following square commutes:

By definition of * ( ), the following diagram is a pullback; as a consequence, there is a unique : → such that the diagram commutes: * ( ) So, for all ∈ Hom C / Σ ( ), , there is a unique ∈ Hom C / ( , * ( )) such that the above diagram commutes; in other words, the mapping , : ↦ → is a bijection .

We now have to check the naturality in and . Let : → be an arrow in C / ; thus makes the following diagram commute:

We have to check whether the following diagram commutes:

Hom C / Σ ( ), Hom C / ( , * ( ))

, Let ∈ Hom C / Σ ( ), ; makes the following diagram commute:

So:

In fact the formula establishes the reverse bijection, but this bijection will do.

IMTA-RR-2019-01-SC 112/127 11. Elementary topoi

where is the unique arrow → that makes the following diagram commute: * ( )

Then:

where is the unique arrow → such that • = • and * ( ) • = , as in the following diagram:

By chasing diagram 31 and using the equations given by diagram 30, we see that:

By unicity of , we must have = • , hence the equality:

Which gives the naturality in . The naturality in is very similar and is left to the reader.

IMTA-RR-2019-01-SC

113/127

Elementary topoi

The adjunction Σ * may sometimes be completed with a third functor Π , called the dependent product functor, that is right adjoint to the pullback functor * . However, this does not occur often; the existence of this right adjoint depends on some property of the category C . The property that matters to us now is the following:

Proposition 11.29. Let C be a category with all pullbacks. Then, C is locally Cartesian closed ⇔ for all arrow , the pullback functor * has a right adjoint Π .

Proof. [Proof of ⇐] Let : → be an arrow, and let Π be its right adjoint.

We have to find the terminal object, the products and the exponentials in C / . By Proposition 11.16, we know that the terminal object in C / is id . By Proposition 11.17, as C has all pullbacks, we know that C / has all products.

Consider the following pullback: * ( ) By Proposition 11.25, the composition functor Σ is left adjoint to the pullback functor * . By Proposition 11.17, the pullback of and in C corresponds to a product in C / . Then:

We deduce the following equivalence of hom-sets:

Then, in C / , by Proposition 6.23 (exponential is right adjoint to product), the exponential can only be = Π ( * ( )). As such an exponential always exists (because * always does, and Π does by assumption), C / is Cartesian closed.

Thus, C is locally Cartesian closed.

[Proof of ⇒] Assume that C is locally Cartesian closed. Then each slice category is Cartesian closed, so each slice category C / of C has products. By Proposition 11.21, a slice of a slice is a slice. By the same reasonning, each slice category (C / ) / of C / has products.

IMTA-RR-2019-01-SC

114/127

Elementary topoi

By Proposition 11.17, each product in (C / ) / is a pullback in C / , so C / has all pullbacks. By Proposition 11.16, each slice category C / has a terminal object id .

Each slice category C / has pullbacks and a terminal object, so by Proposition 7.34, it has all finite limits. By Proposition 8.27, as every slice category has finite limits and exponentials, we deduce that the pullback functor * (in C , that is the "product" functor in C / ) has a right adjoint.

Corollary 11.30. If C has all pullbacks and is locally Cartesian closed, then each slice category C / has finite limits. Definition 11.31 (Dependent product). Let C be a category with all pullbacks and locally Cartesian closed. Let : → be an arrow in C .

The dependent product Π is the right adjoint to the pullback functor * .

Before studying more properties, maybe we should take a break and look at how this functor behaves.

Example 11.32 (Slice category in Sets, again). Consider Sets and some function : → . Let : → be an object in Sets/ . It is a function, indeed, but the point of view that makes more sense in this context is the following. For all ∈ , we can define the set -1 ( ) = { ∈ | ( ) = }. In this case, the function :

→ becomes an -indexed set -1 ( ) ∈ where = ∈ -1 ( ) (coproduct). Then, a morphism ℎ : → in Sets/ is a function between -indexed sets, such that ℎ = ∈ ℎ : -1 ( ) → -1 ( ).

Note that this point of view explains why there cannot be any arrow from : → to : → whenever ( ) ( ). In fact, take ∈ ( )\ ( ); we have -1 ( ) = ∅, so the function As for Π . Let ∈ and : → be an object in C / . We call partial section of for along any function : -1 ( ) → such that the following diagram commutes:

-1 ( ) ⊆ that is, for all ∈ -1 ( ), • ( ) = . Note that is essentially a right inverse of on the reverse image of ∈ by , and such an may not be unique. Also, a partial section along : → requires that -1 ( ) ⊂ ( ); so may not have partial sections for all along , for example if -1 ( )\ ( ) ≠ ∅.

Awodey [1, p233, below Proposition 9.18] states that Π ( ) : → where is:

= : -1 ( ) → | ∈ and is a partial section of for along

and for all : -1 ( ) → ∈ , Π ( ) ( ) = (that is, Π ( ) "projects" a partial section : -1 ( ) → to the base of the inverse image on which the section takes place). For a given ∈ C op , (-, ) is a diagram from I → Sets, and as Sets has all small limits, it has a limit Lim (-, ) , , . Then, if : → ∈ C , then, as is a (contravariant) functor, there is an arrow: (-, ) : (-, ) → (-, ) between cones to and by property of limits, there is a unique arrow Lim (-, ) : Lim (-, ) → Lim (-, ) , such that the following diagram commutes:

IMTA-RR

Lim (-, )

Lim (-, )

, Lim (-, )

, Note that we are considering the right-hand square diagram in C op ; we have the naturality of , in .

There remains to show that Lim (-, ) is indeed a limit. Let : Δ( ) → be a cone to . Here, the diagonal functor is: Δ : PSh (C ) → PSh (C ) I . We are looking for a unique : → Lim (-, -) such that, for all objects ∈ I and ∈ C , the following diagram commutes: ( ) = , , • ( ).

( ) ( )

Such a (unique) ( ) always exists due to the universal property of limits in Sets. We only have to check that this = ( ( )) ∈C is natural in . It is due to the naturality of the other natural transformations and ,-. Finally, is unique due to the uniqueness of each ( ). Thus, for every diagram : I → PSh (C ), there is a limit, and for all ∈ C , Lim ( ) ( ) Lim (-, )

Lim ( (-) ( )).

IMTA-RR-2019-01-SC 117/127

12. Presheaves, sheaves, sheaf topoi

In fact, we proved something stronger:

Corollary 12.3. PSh (C ) has all small limits.

Corollary 12.4. For all , ∈ PSh (C ), × is the functor:

Corollary 12.5. The terminal object in PSh (C ) is the constant presheaf Δ(1) where Δ is the diagonal functor Δ : Sets → PSh (C ).

Proposition 12.6. Let : → be a morphism between two presheaves in PSh (C ).

Then, is monic ⇔ for all ∈ X , : ( ) → ( ) is monic.

Proof. The proof of ⇐ has already been given in Proposition 1.38. Conversely, suppose that is monic. The characterisation of monics by pullbacks (Proposition 6.54 states that the pullback of with itself is ( , id , id ). As limits, and thus pullbacks, are computed objectwise, we deduce that the pullback of each -component : ( ) → ( ) with itself is also a triple ( ), id ( ) , id ( ) , making each component monic.

Remark 12.7. We know that a presheaf category has all small limits. In particular, it has all binary products, so maybe it has exponentials.

Let , ∈ PSh (C ) be presheaves. Suppose their exponential exists; let us study it. By adjunction product/exponential (Proposition 6.23), we know that Hom PSh(C ) ( × , ) Hom PSh(C ) ,

. By Yoneda lemma, we have:

Hom PSh(C ) Hom C (-, ) , ( ) which defines the functor as:

( ) Hom PSh(C ) (Hom C (-, ) × , )

We have to check that this actually defines an exponential; that is, for every : × → , there is a unique ˆ : → such that the following diagram commutes:

Note that : × → is a natural transformation, and as limits (hence, producs) are computed objectwise, the previous diagram becomes:

We define the natural transformation eval as: eval :

IMTA-RR-2019-01-SC 118/127

12. Presheaves, sheaves, sheaf topoi Note that eval is the counit of the adjunction Hom PSh(C ) ( × , ) Hom PSh(C ) , .

Then, note that eval is defined such that eval • id × ˆ ( , ) = eval , ˆ ( ) = ˆ ( ) (id , ) = ( , ) by commutativity of the previous diagrams. We now have to find the expression of ˆ . For now we focus on ˆ ( ). We already know that ˆ ( ) (id , ) = ( , ). For :

→ , the following diagram commutes:

that is:

and in particular, when = id :

which defines ˆ ( ) ( , ) on pairs ( , ) such that = ( ) ( ) (which is enough for our purposes). The naturality of ˆ ( ) in is immediate. Finally, we have defined the exponential in PSh (C ).

Definition 12.8 (Exponential in a presheaf category). Let , be two presheaves in PSh (C ). Their exponential is defined as:

:

Lemma 12.9. A presheaf category PSh (C ) has all exponentials.

Proof. The construction in Remark 12.7 holds for any preasheaves and .

Corollary 12.10. A presheaf category is Cartesian closed.

We could have defined the exponential in a presheaf category, and then prove that the presheaf it defines actually is an exponential, but we prefered showing how the definition naturally made sense.

So, we have all small (thus finite) limits, and all exponentials. The only thing missing is the subobject classifier. To this extend, we define: Definition 12.11 (Sieve [1]). Let C be a small category, and let be an object in C .

A sieve on is a set ∈ Sets such that:

In other words, is a set of (some) arrows of C with codomain (left-hand part of the union), stable by precomposition (right-hand part of the union), that is, for all : → and ∈ , we have • ∈ . Note that doesn't necessarily contain all arrows → .

IMTA-RR-2019-01-SC

119/127

12. Presheaves, sheaves, sheaf topoi Definition 12.12 (Sieve presheaf). Let C be a small category.

For ∈ C , we define Sieve( ) = { ∈ Sets | is a sieve on }.

For : → ∈ C , we define:

The sieve presheaf , written Sieve, is the following contravariant functor: Sieve :

Lemma 12.13. Let C be a small category and let Sieve : C op → Sets be its sieve presheaf. And let Δ(1)

be the terminal object in PSh (C ).

Then there exists : Δ(1) → Sieve such that (Sieve, ) is a subobject classifier of PSh (C ).

Proof. The morphism (natural transformation) is:

That is, is the function that selects the (unique) sieve that contains all arrows whose codomain is (remember that sieves need not contain all arrows). The naturality of is quite obvious once we remember that Δ(1)( ) = 1.

We now have to check that (Sieve, ) is a subobject classifier. Awodey describes the classifying arrow of : → as such that: :

( ) -→ Sieve( ) ↦ -→ { : → | ( ) ( ) ∈ ( )} but I am having trouble finding out that this defines a pullback. I leave the proof for now.

Proposition 12.14. Let C be a small category. Then PSh (C ) is a topos. Proof. By Corollary 12.3, a presheaf category has all small limits; in particular, it has all finite limits. By Lemma 12.9, a presheaf category has all exponentials. Finally, by Lemma 12.13, it has a subobject classifier. Consequently, PSh (C ) deserves its title of topos.

Note that this name is not standard. Proof. The proof is mainly diagram chase. Let 1 + 2 be the coproduct of 1 and 2 , the following diagram commutes for a unique arrow :

IMTA-RR

This ensures that the inclusion maps 1 and 2 actually are arrows in C / .

We denote this = 1 + 2 . We now have to check that this actually defines a coproduct. Let as in the diagram:

The fact that 1 + 2 is a coproduct in C gives that unique arrow : 1 + 2 → such that • 1 = 1 and • 2 = 2 . We than have to check that actually is an arrow in C / , that is, that • = 1 + 2 . In fact, 1 + 2 is the unique arrow 1 + 2 → that makes Diagram 32 commute; • also does, so the equality must hold.

Proposition 13.2 (Coproduct of pullbacks is a pullback). Let C be locally Cartesian closed.

Consider the following diagram: