Introduction. This is Yet Another Text on general nonsense. I had written another one previously, but I was rather unsatisfied about it; in truth, I hadn’t quite understood the full significance of adjoint functors. I now realize that universal problems should better be stated in terms of adjoint functors rather than of universal objects. Also, I will take the opportunity to discuss some more notions, such as the Yoneda embedding, Cartesian closed categories, relations with logic, and so on.

1. Categories. A \underline{category} C is a class ob(C), together with a set Hom(A, B) for each A, B ∈ ob(C) (all these sets being disjoint), and for all A, B, C ∈ ob(C) a composition law

Hom(B, C) × Hom(A, B) → Hom(A, C)

which is associative whenever that makes sense and has a two-sided identity element 1_{A} ∈ Hom(A, A) for each A ∈ ob(C).

When C is a category, the elements of ob(C) shall be called the \underline{objects} of C (or sometimes just the elements of C), and the elements of Hom(A, B) the \underline{arrows} (or \underline{morphisms}) from A to B. If f ∈ Hom(A, B) we also write f: A → B, and we say that A is the \underline{domain} (or \underline{source}) of f, and that B is its \underline{range} (or \underline{target}, or \underline{goal}, or \underline{codomain}). We also write dom f for the domain of f and ran f for its range.

When ob C is a set (rather than a proper class), we say that C is a \underline{small} category. That is just a cavalier way of treating set-theoretical difficulties; some people dispense with them altogether and speak of the “set of sets” without blushing, which is probably a wise thing as we really do not care about these difficulties. Grothendieck invented the concept of “universes” to avoid them. Let us say no more on the subject.

To make the definition of a category more explicit, if α: A → B and β: B → C in a category C, then we have a composite morphism βα: A → C. The associativity states that if α: A → B, β: B → C and γ: C → D then (γβ)α = γ(βα), and we will therefore dispense with the parentheses and write γβα for this morphism. The existence of the unit element states that if α: A → B then 1_{B}α = α and α1_{A} = α. Of course, the unit element is unique.

We now give a few examples of categories.

The category Set is the category whose objects are sets, and whose morphisms are maps between sets. In other words, if A and B are sets, then Hom(A, B) is the set of all maps from A to B. Composition is defined in the usual way, and 1_{A} is the identity on any set A.

The category PSet is the category whose objects are pairs (A, x) with A a (non empty) set and x ∈ A (the “base point”), and whose morphisms are maps of sets which preserve base points. In other words, if (A, x) and (B, y) are pointed sets, then Hom((A, x), (B, y)) consists of those maps f of sets from A to B such that f(x) = y. Here again, composition is defined in the usual way.

The category Top is the category whose objects are topological spaces, and whose morphisms are continuous maps between topological spaces (with composition defined in the usual way). The category HausTop is the category whose objects are Hausdorff (i.e. T_{2}, i.e. separated) topological spaces, and whose morphisms are continuous maps between them. The reader will have no difficulty in defining the categories PTop (pointed topological spaces) and PHausTop (pointed Hausdorff spaces).

The category HomoTop is a little more subtle: its objects are the same as those of Top, but a morphism from A to B in HomoTop is a homotopy equivalence class of continuous maps, rather than just a continuous map. To make this more explicit: two continuous maps f, f′ between A and B are said to be homotopic iff there exists a continuous map Θ from [0, 1] × A to B such that Θ(0, ·) = f and Θ(1, ·) = f′. This defines an equivalence relation on the set Hom_{Top}(A, B) of continuous maps from A to B, and we let Hom_{HomoTop}(A, B) be the quotient of Hom_{Top}(A, B) by this equivalence relation. Since homotopy is compatible with composition, we get a composition map on morphisms of HomoTop by declaring that the composition of the homotopy class of g and that of f is the homotopy class of gf. The category HausHomoTop is defined in the obvious way. In defining the categories PHomoTop and PHausHomoTop, we have to be more careful; namely, we impose that homotopies preserve base points (that is, two morphisms of pointed topological spaces f: (A, x) → (B, y) and g: (A, x) → (B, y) are deemed homotopic iff there exists Θ such as above, with the additional condition that Θ(t, x) = y for all t ∈ [0, 1]).

For 0 ≤ r ≤ ω (which means r ∈ ℕ, r = ∞ or r = ω), we define the category C^{r}Man whose objects are (paracompact separable) C^{r} manifolds and whose morphisms are C^{r} maps between these (C^{ω} means “real analytic”). There is also a category HolMan whose objects are complex analytic (i.e. holomorphic) manifolds, and whose morphisms are holomorphic maps between them.

Moving from topology to algebra, we have a category Group, whose objects are groups and whose morphisms are group homomorphisms (with composition defined in the usual way). We also have a category AbGroup whose objects are abelian groups and whose morphisms are group homomorphisms (an abelian group homomorphism is the same thing as a group homomorphism).

The category Ring has (general noncommutative) rings (with unit element) as objects, and ring homomorphisms (preserving unit elements) as morphisms. The category ComRing has commutative rings as objects and ring homomorphisms as morphisms. We could also define a category PsRing of rings without unit element and similarily for ComPsRing.

If G is a given group, then we have a category GSet of G-sets (sets upon which G acts, also called representations of G), with maps preserving the action (“G-homomorphisms”) as morphisms (in other words, a morphism from A to B is a map of sets f from A to B such that f(g · x) = g · f(x) for all x ∈ A). This category is not to be confused with the category GrpSet whose objects are pairs (G, S) with G a group and S a G-set, and whose morphisms (G, S) → (H, T) are pairs f = (f_{♮}, f_{♯}), where f_{♮} is a group homomorphism from G to H, and f_{♯} is a map of sets from S to T such that f_{♯}(g · x) = f_{♮}(g) · f_{♯}(x) for all g ∈ G and x ∈ X.

Similarily, if R is a ring, we have a category RMod of (left) R-modules with linear maps as morphisms. We can, for example, identify (in a sense that will be made precise later) the categories ℤMod and AbGroup. The category RMod is not to be confused with the category RingMod whose objects are pairs (R, M) with R a ring and M an Rmodule, and whose morphisms (R, M) → (S, N) are pairs (f_{♮}, f_{♯}) with f_{♮}: R → S a ring homomorphism and f_{♯}: M → N a homomorphism of abelian groups that also satisfies f_{♯}(ax) = f_{♮}(a) f_{♯}(x) for all a ∈ G and x ∈ M. The reader will have no difficulty in defining the category ComRingMod of modules over commutative rings.

We leave it to the reader to define the categories RAlg (of R-algebras) for a commutative ring R, RComAlg (of commutative R-algebras) and ComRingComAlg (of commutative algebras over commutative rings). We note that RComAlg can be identified with the category of commutative ring homomorphisms R → A with a morphism from R → A to R → B being a homomorphism A → B that makes the obvious triangle commute (this is an example of a “coslice” category, see below). Similarily, we can identify ComRingComAlg with the category of commutative ring homomorphisms R → A (only this time R varies) with a morphism from R → A to S → B being a pair of ring homomorphisms R → S and A → B that make the obvious rectangle commute (this will be generalized when we define functor categories).

Let us also not forget the category Field of fields whose morphisms are inclusions of fields (we recall that a morphism of fields is always an inclusion — we also recall that the zero ring is not a field). For p prime or p = 0, we also have the category Field_{p} of fields of characteristic p. There is also a category ACField of algebraically closed fields and similarily one can define ACField_{p}.

In homological algebra, one is led to define the category GradAbGroup of graded abelian groups, that is, ℤ-sequences of abelian groups with ℤ-sequences of group homomorphisms as morphisms. More important is the category ∂AbGroup whose objects are complexes of abelian groups, that is, ℤ-sequences (K_{n}) of abelian groups with homomorphisms ∂_{n}: K_{n} → K_{n−1} between them such that ∂_{n}∂_{n+1} = 0 for every n, and whose morphisms are chain maps, that is, ℤ-sequences (f_{n}) of abelian group homomorphisms f_{n}: K_{n} → K′_{n} which commute with the boundary operator, that is ∂′_{n}f_{n} = f_{n−1}∂_{n} for each n. We say that two such chain maps (f_{n}) and (g_{n}) are homotopic iff there exists a ℤ-sequence (s_{n}) of abelian group homomorphisms s_{n}: K_{n} → K′_{n+1} such that f_{n} −g_{n} = ∂′_{n+1}s_{n} +s_{n−1}∂_{n} for each n. This is an equivalence relation compatible with composition, and we therefore get a category Homo∂AbGroup of complexes of abelian groups with homotopy classes of chain maps as morphisms.

Let us also not forget ordered structures: there is a category POSet whose objects are partially ordered sets (“posets”), and whose morphisms are maps of sets that preserve order; in other words f: A → B is a morphism of posets iff x ≤ y implies f(x) ≤ f(y) for all x, y ∈ A. If instead we impose that f(x) ≤ f(y) iff x ≤ y, then we get the definition of an increasing function, and if we use them as morphisms we get the category IPOSet. Of course, we can use totally ordered sets instead of partially ordered sets as objects, and then we get the categories TOSet and ITOSet.

To move to a little more exotic things, for those who know what it means, if X is a topological space, then we have a category XPreSheaf of presheaves (of sets) on X, and a category XSheaf of sheaves (of sets) on X. And of course we have categories AbGroupXSheaf (sheaves of abelian groups on X), RingXSheaf (sheaves of rings on X), and so on. There is also a category RingedSpace of ringed spaces (topological spaces with a sheaf of rings on them), and if (X, O) is a ringed space, a category OModSheaf of (sheaves of) O-modules. Another important category is the category of schemes Scheme.

Another little anecdotical example: the category Frame is the category whose objects are posets which admit finite meets (i.e. infema) and arbitrary joins (i.e. suprema), the meet operation being distributive over the join. Morphisms of frames are maps which preserve the meet and join operations (and hence the order too). (Think of a frame as the set of open sets on some kind of generalized topological space — called a locale.)

All those examples should persuade that categories abound in mathematics, in the sense that many objects of interest to mathematicians congregate in categories. However, there are many other kinds of categories, which do not at all look like “sets with some kind of structure on them”. We now give some examples of those.

The simplest kind of category is, of course, the empty category: it has no objects and no arrows. We shall write it 0. The next simplest example is the category with just one object, •, and one arrow 1_{•}: • → • (composition is defined without trouble). We shall write it 1.

More generally, if S is any set, we can view S as a category C in the following way: the objects of C are just the elements of S, and the only morphisms are the identity morphisms. Such categories are called discrete categories.

As a generalization of this, suppose S is a preordered set, that is, a set with a reflexive and transitive relation ⪯ on it. We make S into a category C by letting the objects of C be the elements of S, and Hom(A, B) consist of one element exactly when A ⪯ B, otherwise be empty. Composition is defined in the only possible way (if A ⪯ B ⪯ C then the composite of the unique arrow A → B and the unique arrow B → C is the unique arrow A → C). One important case of this is the case when S is actually a complete boolean algebra (or Heyting algebra); for, as we shall see, the category thus obtained is then cartesian closed.

At the opposite end of the spectrum, so to speak, are the group categories: if G is a group, then we can make it into a category C by declaring that C has exactly one object •, and that Hom(•, •) is precisely G, with composition being defined as multiplication on G (and of course 1_{•} is the identity element of G). More generally, we can consider categories all of whose arrows are isomorphisms (see below); such categories can be identified with an algebraic structure that is very much like a group except that multiplication is not always defined: such structures are called groupoids. In order to avoid the unpleasant definition of a groupoid, we shall define a groupoid to be a small category in which all arrows are isomorphisms.

Now suppose Γ is a graph (here, this means an arbitrary set of points, and an arbitrary set of arrows between these points); then we may form the free category C generated by Γ: the objects of C are the points of Γ, and the arrows of C are freely generated by the arrows of Γ: for any finite sequence f_{k}: A_{k} → A_{k+1} of arrows of Γ (possibly empty, in which case we are creating an identity arrow) create an arrow f_{n} ⋯ f_{1}: A_{1} → A_{n+1} in C, and let composition be defined in the obvious way (there are no non trivial relations between arrows).

While we’re talking of graphs, here is a little more terminology: a category C is called \underline{strongly connected} iff Hom(A, B) is non empty for any objects A, B ∈ ob C. It is called \underline{weakly connected} or simply “connected” iff for any objects A, B of C there exist objects A_{0}, …, A_{n} of C with A_{0} = A and A_{n} = B such that for each i either Hom(A_{i}, A_{i+1}) or Hom(A_{i+1}, A_{i}) is non empty (we may of course suppose it is the one for even i and the other for odd i).

To take a more exotic example, suppose we have an axiomatic system Σ in a possibly intuitionistic logic. We define a category by letting the objects be the propositions in Σ, and the arrows A → B be the proofs of B starting from A, composition being defined in the obvious way. This does form a category, but it is not very interesting (essentially because no arrow other than the identity is invertible); it can be made more interesting if we indentify some proofs. For example, one may want to identify all proofs of T (the tautologically true statement) from starting from A, for any A; or to identify, given proofs f: C → A and g: C → B, the proof obtained by composing f ∧ g: C → A ∧ B and A ∧ B → A, with the proof f; and so on (of course, each of these identifications imposes some identifications on composites). It turns out, not surprisingly, that if we start with an aristotelian propositional calculus and we do all the identifications as seem natural, and further quotient out isomorphic objects (see below), then we are just left with (the category of) the Lindenbaum algebra of our formal system.

To return to more familiar grounds, we now proceed to describe some operations that can be performed on categories.

First, if (C_{i})_{i∈I} is a family of categories (I can be taken to be a proper class, but who cares), then we have a category C = ∐_{i∈I} C_{i}, the \underline{disjoint sum} of the categories C_{i}, defined as follows: ob C is the disjoint union of the ob C_{i}, and Hom_{C}(A, B) is Hom_{C_{i}}(A, B) if both A, B are objects of C_{i}, empty otherwise. Composition is defined in the obvious way. Thus, a discrete category (see above) is just the disjoint sum of copies of 1. Of course, if the family I has a finite number of elements, we write C_{1} ⨿ ⋯ ⨿ C_{n} for ∐_{i=1}^{n} C_{i}.

More important, if C is a category, then we have a category C^{op}, called the \underline{opposite category} of C, defined as follows: objects of C^{op} are just objects of C, and arrows of C^{op} are arrows of C, but they go the other way, in the sense that for all objects A and B,

Hom_{C^{op}}(A, B) = Hom_{C}(B, A)

and composition is defined as follows: fg in C^{op} is just gf in C. Trivially we have (C^{op})^{op} = C.

Generally, the opposite category of a nice, concrete, category, does not look nice or intuitive at all; in fact, it looks completely artificial in most cases. Still, the category of affine schemes is (equivalent to) the opposite category of the category of rings. Also, the category Locale of locales, defined as the opposite category to the category Frame of frames, is rather similar to the category of topological spaces.

If (C_{i})_{i∈I} is a family of categories, then we have a category C = ∏_{i∈I} C_{i}, the \underline{product} of the categories C_{i}, defined as follows: an object of C is a family (A_{i})_{i∈I}, with each A_{i} an object of C_{i}, and a morphism (A_{i}) → (B_{i}) is a family (f_{i}), where f_{i}: A_{i} → B_{i} is an arrow of C_{i}. Of course, if the family I has a finite number of elements, we write C_{1} × ⋯ × C_{n} for ∏_{i=1}^{n} C_{i}. If the C_{i} are all equal to a fixed category C_{0}, then we can write C_{0}^{I} for the product of the C_{i}. The careful reader will have noticed, for example, that the category GradAbGroup defined above is none other than AbGroup^{ℤ} = ∏_{k∈ℤ} AbGroup. Also notice that if all the terms of a disjoint sum ∐_{i∈I} C_{0} are equal, then we can identify the disjoint sum in question with I × C_{0}, where the set I is identified with its corresponding discrete category.

More generally, if C and D are categories (the latter being small), then there is a category C^{D} whose objects are functors (see below) D ⇝ C, and whose morphisms are natural transformations between functors. This does not come in conflict with the previous definition of C^{I} if I is a set, provided we do the obvious identifications. Notice in particular, for what it’s worth, that C^{0} = C^{∅} = 1 (where the equal signs really stand for canonical identifications), and C^{1} = C^{{•}} = C (ditto). More interestingly, C^{D⨿D′} can be identified with C^{D} × C^{D′} and C^{D×D′} with (C^{D})^{D′}.

If C is a category and J is an object of C, then we can form a category C ↓ J, the \underline{slice} category of C over J (or “with J as base object”, or simply J-objects): objects of C ↓ J are arrows A → J in C, and arrows in C ↓ J are arrows above J; in other words, a morphism between A → J and B → J is a morphism A → B (in C) which makes the obvious diagram commute. Composition is defined in the obvious manner. Note that J itself can be considered as an object of C ↓ J, namely the identity map 1_{J}: J → J.

In the same manner, we leave it to the reader to define the \underline{coslice} category J ↑ C, whose objects are morphisms J → A in C.

Finally, if C is a category, we can define a category C^{mor}, the category of morphisms of C, whose objects are arbitrary morphisms A → A′ in C, a morphism in C^{mor}, say, between A → A′ and B → B′, being a pair of morphisms of C, A → B and A′ → B′, that make the obvious square commute. The reader who already know what a functor is will have noticed that this category is nothing else than the category C^{•→•}, where • → • stands for the category with two objects and exactly three arrows (of which two are the identity).

We finish this section with an important notion: if C and D are categories, such that the objects of D are a subclass of the objects of C, and that for every A, B ∈ ob D the set Hom_{D}(A, B) is a subset of Hom_{C}(A, B), then we say that D is a \underline{subcategory} of C. If moreover Hom_{D}(A, B) = Hom_{C}(A, B) for all A, B ∈ ob D, then we say that D is a \underline{full} subcategory of C. Note that for any subclass of the class of objects of C, there is exactly one full subcategory of C whose objects are these objects (we say that it is the full subcategory determined by these objects).

For example, PSet is a subcategory of Set, but it is not full. In the same way, Top is a subcategory of Set, but it is also not full (“not every map between topological spaces is continuous”). On the other hand, AbGroup is a full subcategory of Group, and ComRing of Ring, and again TOSet of POSet. Note however that HomoTop is not a subcategory of Top; indeed, the morphisms of HomoTop are equivalence classes of morphisms of Top, and not particular morphisms (if that made sense, we should say that it is a full but not faithful subcategory — instead, we will say that there is a full bijective functor that is not faithful, see below).

2. Kinds of arrows.

An \underline{isomorphism} in a category C is an arrow f: A → B such that there exists g: B → A verifying gf = 1_{A} and fg = 1_{B}. In this case, the objects A and B are said to be \underline{isomorphic}, and we write A ≅ B, sometimes f: A ≅ B or f: A →^{∼} B. Of course, it is equivalent to require that there exist g, g′: B → A such that gf = 1_{A} and fg′ = 1_{B} (because then g = gfg′ = g′). If we impose only the existence of g: B → A such that gf = 1_{A}, we say that the arrow f is \underline{retractable}, and we say that g is a \underline{retraction} of f. Similarily, if we impose only the existence of g: B → A such that fg = 1_{A}, we say that the arrow f is \underline{sectionable}, and that g is a \underline{section} of f.

An arrow f: A → B is called a \underline{monomorphism} when for any two arrows g and g′ of target A and common source, the equation fg = fg′ implies g = g′. Similarily, an arrow f: A → B is called a \underline{epimorphism} when for any two arrows g and g′ of source B and common target, the equation gf = g′f implies g = g′. Two monomorphisms f: A → B and f′: A′ → B are said to be isomorphic iff there exists α: A → A′ an isomorphism such that f = f′α; this is clearly an equivalence relation, and an equivalence class of monomorphisms with target B is called a \underline{subobject} of B. Moreover, a retractable morphism is a monomorphism and any monomorphism isomorphic to a retractable morphism is itself retractable. Therefore, it makes sense to ask whether the monomorphisms defining a subobject are retractable; in this case, we shall say that the subobject is a \underline{retract}. Two epimorphisms f: A → B and f′: A → B′ are said to be isomorphic iff there exists β: B → B′ an isomorphism such that f′ = βf; this is clearly an equivalence relation, and an equivalence class of epimorphisms with source A is called a \underline{quotient object} of A. Moreover, a sectionable morphism is an epimorphism and any epimorphism isomorphic to a sectionable morphism is itself sectionable. Therefore, it makes sense to ask whether the epimorphisms defining a quotient object are retractable; in this case, we shall say that the quotient object is a \underline{section} (hopefully this double use of the word “section” will not cause any confusion). A category in which all subobjects are retracts (i.e. every monomorphism is retractable) is called \underline{semisimple}, and one in which all quotient objects are sections (i.e. every epimorphism is sectionable) is called \underline{cosemisimple}.

If C is an arbitrary category, then we have a category C̄, the \underline{reduced category} of C, defined in the following way: choose once and for all representatives of each isomorphism class of objects in C, and let C̄ be the full subcategory defined by these representatives. Now in fact the category C̄ does not depend, up to isomorphism (to be defined later), on the actual choice of the representatives, so it makes sense to call it simply C̄. One may also say that the objects of C̄ are isomorphism classes of objects of C, but defining the morphisms is then very, very slippery (for example, one may be tempted to define morphisms by identifying f: A → B with f′: A′ → B′ iff there exist isomorphisms α: A → A′ and β: B → B′ such that f′α = βf, but unfortunately that is simply wrong, for then any automorphism of A gets identified with 1_{A}, an undesirable phenomenon). We will later see that the categories C and C̄ are equivalent, and in fact that they are the archetype of equivalent categories.

We now describe what the various notions defined above for some of the “classical” categories that we presented earlier.

In Set, an isomorphism is just a bijection, a monomorphism is an injection and an epimorphism is a surjection. Thus, every every epi is sectionable (that is the Axiom of Choice), meaning that the category Set is cosemisimple. Not every mono is retractable, however, because the unique map ∅ → B has no retraction if B is not empty (that is the unique example). A subobject of a set is what is ordinarily known as a subset, and a quotient object is what is ordinarily known as a partition (i.e. an equivalence relation). The reduced category of Set is (for example) the category of ordinals with arbitrary maps of sets as morphisms. :-(For example, let us prove the statement about epimorphisms. It is clear that a surjective map is epi. Now if f: A → B is epi, and x ∈ B, consider the two maps g and g′ from B to {0, 1} which send x to 0 and 1 respectively, and the rest of B to 0. Since g ≠ g′ we must have gf ≠ g′f, and therefore g′f is not the constant zero map, so f takes the value x.:-)

In PSet, an isomorphism is just a bijection preserving base points; a monomorphism (resp. epimorphism) is an injection (resp. surjection) preserving base points. A subobject of a pointed set is a subset with the same base point, and a quotient object of a pointed set is a partition, with the class of the base point as base point. The category PSet is semisimple (the ridiculous phenomenon of Set does not occur) and cosemisimple.

Now consider the category Top. Isomorphisms in this category are homeomorphisms. Monomorphisms are injective continuous maps and epimorphisms are surjective continuous maps. :-(It is evident that an injective map is mono; on the other hand, if f: A → B is mono and x ≠ y in A, consider the two maps g, g′ from {•} to A which take • to x and y respectively: since g ≠ g′ we must have fg ≠ fg′ and that means f(x) ≠ f(y), so f is injective. That a surjective map is epi is also obvious. Now if f: A → B is epi, and x ∈ B, consider the two maps g and g′ from B to {0, 1} with the coarse topology which send x to 0 and 1 respectively, and the rest of B to 0. Since g ≠ g′ we must have gf ≠ g′f, and therefore g′f is not the constant zero map, so f takes the value x.:-) A subobject of a space B is not just a subspace of C since a mono map need not be a homeomorphism on its image (i.e. an embedding); rather, a subobject of B is a subset of B with a topology which is finer than the topology it inherits from B. Similarily, a quotient object of A is a quotient set of A with a topology which is coarser than the quotient topology. In Top, not all monomorphisms are retractable (the example from Set will work, or, to take a more interesting one, the injection of the unit circle in the closed unit disk is not retractable), and not all epimorphisms are sectionable (the projection of the graph of a discontinuous function on its abscissa axis is an example).

The case of HausTop is a little more delicate. Whereas it is true (with the same proof) that a monomorphism is an injective continuous map, it is not true that all epimorphisms are surjective. Rather, an epimorphism is a dominant continuous map, i.e. one whose image is dense. :-(If the image D of f: A → B is dense, and gf = g′f, then g, g′ coincide on D; but since B is Hausdorff the set of points where they coincide is closed, so it is all of B. On the other hand, if the closure F of the image of f is not all of B, then let C be the space obtained by gluing two copies of B along F (that space is Hausdorff because F is closed) and let g, g′ be the two canonical maps B → C: we have g ≠ g′ but gf = g′f so that f is not epi.:-) Just as Top, the category HausTop is neither semisimple nor cosemisimple, and the same examples will do.

In the category Group, isomorphisms are what is generally meant by that term, and monomorphisms are injective morphisms. Epimorphisms are indeed the same thing as surjective morphisms, but that is not trivial at all. :-(It is obvious that a surjective morphism is epi. The hard part is the converse. Let f: A → B be a group homomorphism with image H, and let C be the amalgam of B with itself along H, g, g′ the two canonical maps B → C. Then we have gf = g′f; but on the other hand g = g′ iff H = B, which finishes the proof. Of course, the hard part is the existence of the amalgam. The careful reader will have noted that this proof is similar to the one given for the category HausTop. This is not fortuitous, and the general notion of an amalgamated sum (in this case, a cokernel pair) shoud clear things up.:-) Thus, in Group, a subobject and a quotient object are what we normally mean by that (that is, subgroup and quotient group respectively). We can also characterize retracts and sections: a subgroup A ≤ B is a retract iff there exists a normal subgroup H of B such that B is semidirect product of H by A. :-(The “if” part is clear. Now let us suppose that the canonical injection f: A → B has a retraction g: B → A, and let H be the kernel of the latter. Then it is obvious that H⊴B and H ∩ A = {1}. But we also have HA = B, because every x ∈ G can be written as the product of xg(x)^{−1} and g(x) with the former belonging to H and the latter to A. This implies that G is semidirect product of H and A.:-) Similarily, a quotient object A ↠ A/H of A is sectionable iff A is semidirect product of H by some subgroup (we leave it to the reader to prove this assertion). As it is well known that not all extensions are semidirect products, the category Group is neither semisimple nor cosemisimple.

We will not treat the case of AbGroup separately, but rather the more general case of RMod, where R is a (not necessarily commutative) ring. Clearly, an isomorphism in RMod is an isomorphism of R-modules. A monomorphism is an injective linear map and an epimorphism is a surjective linear map. :-(As usual, one direction is obvious. If f: A → B is mono, and x ≠ 0 in A, consider the two maps g, g′ from R (viewed as a left module over itself) to A taking 1 to x and 0 respectively: they are unequal, and therefore fg ≠ fg′, from which one deduces f(x) ≠ 0. If f: A → B is epi, and N is its image, consider the two maps g, g′ from B to B/N which are respectively the canonical and the zero map: since gf = g′f we must have g = g′, so N = B.:-) Subobjects and quotient objects therefore correspond to sub and quotient modules respectively. To say that a subobject A → B is a retract means that the short exact sequence of R-modules 0 → A → B → A/B → 0 splits, in other words that A is a direct summand of B. Similarily, to say that a quotient object A → B is a section means that its kernel is a direct summand of A. Thus, the category RMod is semisimple iff it is cosemisimple, and that is exactly what it means for the ring R to be semisimple (hence the name).

Now let us look at the category ComRing: an isomorphism is just what you think. A monomorphism is an injective morphism. :-(One way is obvious. If f: A → B is mono, and x ≠ 0 in A, consider the two maps g, g′ from ℤ[X] to A taking X to x and 0 respectively: they are unequal, and therefore fg ≠ fg′, from which one deduces f(x) ≠ 0.:-) An epimorphism A → B is a morphism such that (one of) the canonical map(s) B → B ⊗_{A} B is an isomorphism. :-(Suppose f: A → B is epi, and let g, g′ be the two canonical maps B → B ⊗_{A} B. We have gf = g′f so g = g′. Now that means that x ⊗ 1 = 1 ⊗ x for every x ∈ B. But then x ⊗ y = xy ⊗ 1 so that the multiplication map B ⊗_{A} B → B is an isomorphism which is the inverse isomorphism to g = g′. Conversely, suppose that the two canonical maps B → B ⊗_{A} B are isomorphisms, and let g, g′ be homomorphisms B → C such that gf = g′f. Then by the universal property of the tensor product there exists h: B ⊗_{A} B → C such that both g, g′ are obtained by composing h with the canonical morphisms B → B ⊗_{A} B. Since in our case they are equal, it follows that also g = g′ and hence f is epi.:-) Surjective morphisms are of course epi, but they are not the only ones; localizations are also epi, for example.

In the category Field, all arrows are monomorphisms (morphisms of fields are always injective). A morphism k ↪ K (we can always assume k is a subfield of K) of fields is an epimorphism iff any two embeddings of K in some larger field L that agree on k agree on K (that is just stating the definition). Now I claim that in this case K/k is algebraic. :-(Indeed, we can write k ↪ k(t_{i}) ↪ K ↪ K̄ with k(t_{i}) a purely transcendental extension of k, K an algebraic extension of k(t_{i}) and K̄ an algebraic closure of K; if K has positive transcendence degree over k then there is a non trivial automorphism σ of k(t_{i}) over k (for example, given by t_{0} ↦ −t_{0} if t_{0} is one of the variables). This extends to a non trivial automorphism σ^{∗} of K̄ over k. Now 1K̄ and σ^{∗} agree on k but do not agree on K (as indeed they do not even agree on k(t_{i})), a contradiction.:-) So now we know that K/k is algebraic. I claim moreover that K/k is purely inseparable. :-(Indeed, if not then there exist distinct embeddings of K in an algebraic closure of K that are equal on k (recall that the number of such embeddings is precisely the separable degree of K over k), a contradiction again. Thus, an epimorphism is an algebraic purely inseparable extension. Now conversely, assume K/k is algebraic and purely inseparable, and that we are given two embeddings of K in a field L that coincide on k. Clearly we can suppose that L is algebraic over K, and then that it is an algebraic closure of K; but then the result is obvious.:-) So finally, we have proved that epimorphisms in the category of fields correspond to algebraic purely inseparable extensions. The only monomorphisms in Field that are retractable, and the only epimorphisms that are sectionable are isomorphisms (indeed, a monomorphism that is retractable is not just epi but actually surjective, and since it is also injective, it is an isomorphism).

Now let us turn to the category TOSet. It is easy to verify that monomorphisms in TOSet are injective order preserving function. Also, epimorphisms are surjective order preserving functions. :-(That surjective implies epi is clear. Now suppose f: A → B is epi, and let x ∈ B. Consider the two maps g, g′: B → {0, 1} (where {0, 1} has the usual order on it) given by g(t) = 1 iff t ≥ x and g′(t) = 1 iff g > x. Then g ≠ g′ and so gf ≠ g′f which implies that x is in the image of f.:-) In other words, a subobject of a toset is a subset with the induced order and a quotient object is a quotient by an “appropriate” equivalence relation (in other words, every equivalence class is convex, i.e. it contains any point between two points that it contains). It is clear that every epimorphism is sectionable. Retractable monomorphisms are harder to grasp: here is one characterization. A monomorphism f: A → B (thus identifying A with a subset of B with the induced order) is retractable iff for every m ∈ B the set {x ∈ A: x ≥ m} has an infemum in A. :-(First suppose f is retractable, and let g be a retraction: g: B → A is order preserving and is the identity on A. Let m ∈ B and put S = {x ∈ A: x ≥ m}. For every x ∈ S we have x ≥ m so x = g(x) ≥ g(m), and hence g(m) is a lower bound for S in A. Now suppose s is another such lower bound. If s > g(m) then g(s) > g(m) so that s > m and then s ∈ S, so that s is the least element of S and so S indeed has a greatest lower bound (namely s). On the other hand, if s ≤ g(m) for all lower bound s of S then g(m) is the greatest lower bound and again S has a greatest lower bound. This proof is rather cunning: it is not always true that g(m) is the infemum of S, but if it is not then S has a least element, which is even better! For the converse, suppose the property satisfied. We let g(m) be the greatest lower bound in A of S = {x ∈ A: x ≥ m}. Then g is order preserving, and if m ∈ A then it is obvious that g(m) = m.:-) For a counter-example, the rationals are not an (order-)retract of the reals.

In a groupoid category, the only morphisms are the isomorphisms, and they are obviously mono, epi, retractable and sectionable. This applies in particular to discrete categories and group categories. If a preordered set is made into a category, then all morphisms are mono and epi, but the only retractable or sectionable morphisms are the isomorphisms (which, if the preordered set was actually partially ordered, are the identities).

3. Simple universal properties.

We now turn to the study of the most common universal properties. The general study of all universal properties will be done later on.

The most important universal construction is the product, so we start with that. Let C be a category, and (X_{i})_{i∈I} a family of objects of C. By a \underline{product} of the (X_{i}) we mean an object X of C and a family (p_{i})_{i∈I} of morphisms p_{i}: X → X_{i} that satisfy the following (“universal”) property: if (f_{i})_{i∈I} is a family of morphisms f_{i}: T → X_{i}, then there exists a unique morphism f: T → X such that f_{i} = p_{i}f for every i ∈ I.

We shall frequently say that X is a product (rather than the pair (X, (p_{i})_{i∈I})); moreover, we say that p_{i}: X → X_{i} are the \underline{canonical morphisms} (or \underline{projections}, or some similar such term).

An important thing is that if a product exists, it is unique up to canonical isomorphism, in the following sense: if (X, (p_{i})) and (Y, (q_{i})) are two products of the (X_{i}), then by the universal property of X there exists an arrow q: Y → X such that q_{i} = p_{i}q for every i, and by the universal property of Y there exists an arrow p: X → Y such that p_{i} = q_{i}p for every i. But then p_{i} = p_{i}qp for every i, and so by the (uniqueness part of the) universal property of X, we have qp = 1_{X}, and similarily we have pq = 1_{Y}. Thus p and q are reciprocal isomorphisms between X and Y, and they are compatible with the projections in the sense that q_{i} = p_{i}q and p_{i} = q_{i}p for every i. Moreover, it is clear that they are the only such isomorphisms. Thus, if it exists, we can speak of the product. We write it ∏_{i∈I} X_{i}, and if I is finite, we write X_{1} × ⋯ × X_{n} instead of ∏_{i=1}^{n} X_{i}.

If the product of an arbitrary (set indexed) family of objects exists in C, we say that C “has arbitrary (small) products”. If the product of a finite family of objects exists, we say that C “has finite products”.

One particularily important product is the product of the empty family, if it exists: it is an object X such that for any object T there exists a unique arrow T → X. Such an object is also called a (the) \underline{terminal} (or \underline{universal}, or \underline{universally attracting}) object. It is normally written 1 (if this causes no ambiguity). The product of a family with just one member, of course, exists in any category, and is just that member itself.

There are a couple of nice properties of products. To name a few:

X × (X′ × X′′) = X × X′ × X′′ = (X × X′) × X′′
X × X′ = X′ × X

1 × X = X = X × 1

∏_{i∈I} ∏_{j∈J} X_{ij} = ∏_{(i,j)∈I×J} X_{ij}

where each equal sign is actually a canonical isomorphism (but anyhow each term only exists up to canonical isomorphism), and whenever one side exists then so does the other one. This is all quite trivial; for example, to verify that X × (X′ × X′′) = X × X′ × X′′, it suffices to verify that X × (X′ × X′′) (with the obvious projection maps) actually is a product of X, X′, X′′, and that is extremely easy.

Naturally, if all the factors of a product are equal (isomorphic) to a single object X_{0}, then the product is written X_{0}^{I}. We have X_{0}^{0} = 1, X_{0}^{1} = X_{0}, and X_{0}^{n} is called the n-th power of X_{0}.

One word of warning: one may be tempted to think that the p_{i} are epimorphisms or sectionable or some kind of thing. That is not true in general, as the example of the cartesian product of a non empty set with an empty set will show. However if the category C satisfies the property that Hom(A, B) is non empty for any two objects A, B, then the p_{i} are sectionable (hence epi). Indeed, let i ∈ I; for each j ∈ I with j ≠ i, choose a map f_{j}: X_{j} → X_{i}, and let f_{i}: X_{i} → X_{i} be the identity. Then there is a unique map f: X_{i} → X such that f_{j} = p_{j}f and in particular 1_{X_{i}} = p_{i}f, which show that f is a section of p_{i}.

Now let us tour briefly the “classical” categories to see whether they have products. The archetypal example is Set: it has arbitrary products, and the categorical product

of a family of sets is just the cartesian product. That is obvious. And so are the other examples that we will give. In the category PSet, the product is the cartesian product, the base point of the product being the point which projects to the the base point on each component. In the category Top, arbitrary products exist, and they are just the ordinary (Tychonoff) cartesian product. The same is true in HausTop, HomoTop and HausHomoTop. In the categories Group, AbGroup, Ring, ComRing, PsRing, RMod, GSet, and a couple of other ones too, products are just ordinary cartesian products with termwise operations. Even in the categories C^{r}Man and HolMan (which are otherwise pretty nasty categories on the whole) finite products exist. In the category POSet, arbitrary products exist: the underlying set to ∏_{i∈I} X_{i} is the cartesian product of the underlying sets, and the order is defined by (x_{i}) ≤ (y_{i}) iff x_{i} ≤ y_{i} for all i. In the category TOSet, on the other hand, almost no product exists, and the same holds for the category Field (the latter does not even have a terminal object).

On a discrete category, a product exists iff all its factors are equal, and then the product in question is also equal to the factor in question. In a group category, the unique object admits powers other than 1 iff the group is trivial. If a partially ordered set is made into a category, then the product of a family is but its greatest lower bound (infemum).

Having seen the product, we now move to the coproduct. That is extremely easy: the coproduct of a family of objects of C is the product in C^{op}. In other words: let (X_{i})_{i∈I} be a family of objects of C. By a \underline{coproduct} (or \underline{sum}, or \underline{free sum}) of the (X_{i}) we mean an object X of C and a family (j_{i})_{i∈I} of morphisms j_{i}: X → X_{i} that satisfy the following (“(co)universal”) property: if (f_{i})_{i∈I} is a family of morphisms f_{i}: X_{i} → T, then there exists a unique morphism f: X → T such that f_{i} = fj_{i} for every i ∈ I.

We will not repeat for the coproduct all that we said for the product. Of course, the coproduct, when it exists, is unique up to canonical isomorphism. We write ∐_{i∈I} X_{i} for the coproduct of the X_{i}. The coproduct of the empty family (if it exists) is called the (a) \underline{initial} (or \underline{couniversal} or \underline{universally repelling}) object, and is frequently written 0. The coproduct ∐_{i=1}^{n} X_{i} of a finite family is written X_{1} ⨿ ⋯ ⨿ X_{n}, and we have all the evident identities. The j_{i} are not mono in general, but they are retractable (hence mono) if all the Hom(A, B) are non empty.

In the category Set, the coproduct is the disjoint union. In the category PSet, the coproduct is the disjoint union but with base points identified. In the categories Top, HausTop, HomoTop and HausHomoTop, the coproduct is the disjoint union with the obvious structure. In the categories C^{r}Man, countable coproducts exist and they are the disjoint sum of manifolds (we have to limit ourselves to the countable case since our manifolds are assumed separable). In the category POSet, the coproduct is the disjoint union, with elements from two different terms being non comparable. In the algebraic categories, things are a little less pleasant. In Group, coproducts exist (arbitrary ones as a matter of fact, but let us stick to finite ones for simplicity) and they are the free group product. In the category Ring, coproducts exist, but they are something ghastly, and I do not know their name (“braided tensor products” perhaps ?). In the category ComRing, coproducts exist, and finite coproducts are tensor products over ℤ (infinite ones are the inductive limit of all the finite tensor products), and this applies mutatis mutandis to RComAlg (replace ℤ by R). In the category RMod (this case includes AbGroup as already noted) arbitrary coproducts exist and they are the ordinary direct sum (note that therefore finite products and coproducts coincide). Here again, the categories TOSet and Field behave badly, as they do not have any interesting coproducts.

We finish products and coproducts by noting one last interesting fact: in the example of a formal system made into a category given previously (with all the appropriate identifications made), the product of propositions A_{1}, …, A_{n} is A_{1}∧⋯∧A_{n} (corresponding to the fact that proving A_{i} from B for each i is the same as proving A_{1} ∧ ⋯ ∧ A_{n} from B), and similarily their coproduct is A_{1} ∨ ⋯ ∨ A_{n}.

Now let us turn to equalizers and coequalizers. If C is a category, and f, f′ ∈ Hom(A, B), then an \underline{equalizer} of f, f′ is a morphism e: E → A such that fe = f′e and that is universal among such morphisms, in other words if g: T → A satisfies fg = f′g then there exists a unique u: T → E such that g = eu. The universal property implies that the equalizer is unique up to canonical isomorphism (we leave that as an exercice to the reader, since it shall be proven later on in the more general setting of projective limits). Moreover, the equalizer is a monomorphism. :-(Indeed, if eh = eh′ then since feh = f′eh it follows by the uniqueness part of the universal property that h is the only morphism u such that eh = eu, and so h = h′.:-) And we can therefore consider it as a subobject of A, which is then unique, not just up to isomorphism.

In the category Set, the equalizer of f, f′: A → B is the subset of A consisting of the points of A where f and f′ coincide. The same is true in PSet, in Top and HausTop (with the induced topology on the subset in question), in Group, Ring, ComRing, RMod, etc (with the induced algebraic structure), and in POSet and TOSet.

A coequalizer, of course, is an equalizer in the opposite category: if f, f′ ∈ Hom(A, B), then a \underline{coequalizer} of f, f′ is a morphism e: B → E such that ef = ef′ and that is universal among such morphisms, in other words if g: A → T satisfies gf = gf′ then there exists a unique u: E → T such that g = ue. The universal property implies that the coequalizer is unique up to canonical isomorphism. Moreover, it is an epimorphism, and we can therefore consider it as a quotient object of B, which is then unique, not just up to isomorphism.

In the category Set, the coequalizer of f, f′: A → B is the quotient of B by the equivalence relation generated by the pairs (f(x), f′(x)) for x ∈ A. Similarily, in Group, the coequalizer of f, f′: A → B is the quotient of B by the normal subgroup generated by the f(x) f′(x)^{−1} for x ∈ A. In RMod, the coequalizer of f, f′: A → B is the quotient of B by the image of f − f′. In ComRing (resp. Ring), the coequalizer of f, f′: A → B is the quotient of B by the ideal (resp. two-sided ideal) generated by the f(x) − f′(x).

Another important universal construction is that of pullbacks and pushouts, also called respectively fiber(ed) products and amalgamated sums. We start with the fibered product. There are several ways to describe it, and we enumerate a few, leaving to the reader to show that they are equivalent. We only consider the fibered product of two objects over a third (the only case which really ought to be called a pullback), leaving the obvious generalization to the reader (or to later in the general formalism of projective limits). Let C be a category and s_{1}: X_{1} → Y and s_{2}: X_{2} → Y be two Y -objects (that is, two morphisms with a common goal Y). We say that a Y -object s: X → Y, together with two projection maps p_{1}: X → X_{1} and p_{2}: X → X_{2}, is a (the) \underline{fibered product} of s_{1} and s_{2}, or of X_{1} and X_{2} over Y (relative to the morphisms s_{1} and s_{2}), or any similar terminology iff any of the following equivalent conditions are satisfied:

1) s = s_{1}p_{1} = s_{2}p_{2} and it is the universal such morphism, in the sense that if f_{1}: T → X_{1} and f_{2}: T → X_{2} are morphisms such that s_{1}f_{1} = s_{2}f_{2} then there exists a unique f: T → X verifying f_{1} = p_{1}f and f_{2} = p_{2}f.

2) s is the product of s_{1} and s_{2} in the slice category C ↓ Y, p_{1} and p_{2} being the projections of this product.

3) p_{1}: X → X_{1} is the universal map over s_{2} with target X_{1}; in other words, if t: T → X_{1} is an arrow and we have a morphism t → s_{2} in C^{mor}, then it factors uniquely through (p_{2}, s_{1}): p_{1} → s_{2} with the second part of the factor being the identity 1_{X_{1}}. s is then the obvious map s = s_{1}p_{1} = s_{2}p_{2}.

4) (Assume that the product Z = X_{1} ×X_{2} exists, and q_{1}: Z → X_{1} and q_{2}: Z → X_{2} are its canonical projections.) The map e: X → Z obtained from p_{1} and p_{2} by the universal property of Z is the equalizer of s_{1}q_{1} and s_{2}q_{2}, s is s_{1}q_{1}e = s_{2}q_{2}e and p_{1}, p_{2} are q_{1}e, q_{2}e.

Of course, the fibered product, when it exists, is unique up to a canonical isomorphism that commutes with the projections.

We also say that p_{1} is the \underline{pullback} of s_{2} along s_{1}, or that the diagram

\begin{matrix}X & ⟶^{p_{2}} & X_{2} \\ p_{1}↓ & □ & ↓s_{2} \\ X_{1} & ⟶^{s_{1}} & Y \end{matrix}

is \underline{cartesian} (that is the meaning of the little square in the middle). The notation for the fibered product is X = X_{1} ×_{Y} X_{2} (that is not very correct, of course, since it does not specify which morphisms X_{1} → Y and X_{2} → Y are used, but in practice it rarely leads to confusion).

We mention a rather important fact: suppose that the diagram

A ⟶^{f} B ⟶^{g} C
u↓  v↓  w↓
A′ ⟶^{f′} B′ ⟶^{g′} C′

is commutative, and that the right hand square is cartesian. Then the left hand square is cartesian iff the outer rectangle is so. :-(Suppose the left hand square is cartesian, and let T be a test object in C, and h: T → A′ and z: T → C be morphisms such that wz = g′f′h. Then by the cartesianness of the right square, there is a (unique) y: T → B such that z = gy and f′h = vy. This in turn, by the cartesianness of the left square, determines a (unique) x: T → A such that y = fx and h = ux. So we have found an x: T → A such that z = gfx and h = ux. If we now have two such x, call them x_{1}, x_{2}, then letting y_{i} = fx_{i}, since z = gy_{i} and f′h = vy_{i}, the uniqueness part of the cartesianness of the right square gives y_{1} = y_{2}, and this in turn gives x_{1} = x_{2} by the uniqueness part of the cartesianness of the left square. This finishes the proof of the fact that the rectangle is cartesian. Conversely, assume that the rectangle is cartesian, and let T be a test object in C, and h: T → A′ and y: T → C be morphisms such that vy = f′h. Put z = gy. Then we have wz = g′f′h, so by the cartesianness of the rectangle there exists a (unique) x: T → A such that gfx = z and ux = h. But then we have gy = z = gfx, and vy = f′h = f′ux = vfx, and by the uniqueness part of the cartesianness of the right square, this implies y = fx, so that we have found x: T → A such that y = fx and h = ux. If we now have two such x, call them x_{1}, x_{2}, then fx_{1} = y = fx_{2} so a fortiori gfx_{1} = gfx_{2}, and since also ux_{1} = h = ux_{2}, by the uniqueness part of the cartesianness of the rectangle, we get x_{1} = x_{2}.:-) This result goes by the name of the “pasting lemma”.

We note a few identities concerning fibered products, leaving to the reader to state them rigorously and prove them (and possibly prove some other, similar, ones, too).

X ×_{Y} X′ = X′ ×_{Y} X
X ×_{1} X′ = X × X′
X ×_{X} X′ = X′
X ×_{Y} (Y ×_{Z} W) = X ×_{Z} W

(the last identity is just the pasting lemma).

A little more terminology: if p: X → S is a morphism and f: S′ → S is another morphism, then the pullback of p along f (if it exists) is sometimes written p_{S′}: X_{S′} → S′ (if no confusion is possible), and called the map “obtained from p by applying the change of base S′ → S”. For those who have read the section below on functors, the map f determines a covariant functor from the category C ↓ S of S-objects to the category C ↓ S′ of S′-objects: if X → Y → S is a morphism of S-objects then it determines a morphism X_{S′} → Y_{S′} → S′ of S′-objects.

If Φ is a class of morphisms of C (or, what amounts to the same, a property that morphisms of C can have), we say that Φ is “stable under base change” iff for every f: S′ → S and every p: X → S in Φ, the pullback p_{S′}: X_{S′} → S′ of p along f belongs to Φ. For example, monomorphisms remain monomorphisms after an arbitrary base change. :-(Suppose p: X → S is a monomorphism, f: S′ → S an arbitrary morphism, and we must show that p_{S′}: X_{S′} → S′ is a monomorphism. But if h, h′: T → X_{S′} are such that p_{S′}h = p_{S′}h′, then letting h_{S}: T → X be the composite of h: T → X_{S′} and of the canonical map g: X_{S′} → X, and similarily for h′_{S}, we have ph_{S} = fp_{S′}h = fp_{S′}h′ = ph′_{S}, so h_{S} = h′_{S}. That is, we have gh = gh′ and also ph = ph′. By the uniqueness part of the universal property of pullbacks, that implies h = h′, what was to be shown.:-)

If h: X → Y is any morphism in a category C, then we can consider the pullback of h along itself (provided it exists, of course): this two morphisms p_{1}, p_{2}: X ×_{Y} X → X, called the \underline{kernel pair} of f. We have hp_{1} = hp_{2}, and if f_{1}, f_{2}: T → X satisfy hf_{1} = hf_{2} then there exists a unique f: T → X ×_{Y} X such that p_{1}f = f_{1} and p_{2}f = f_{2}. The interest of the kernel pair is that p_{1} (or p_{2}) is an isomorphism iff h is a monomorphism. :-(If h is a monomorphism then it is easy to check that X itself, with the projections 1_{X}, 1_{X}: X → X, constitutes a fibered product of X with iself over Y. By the uniqueness of the fibered product, it follows that p_{1}, p_{2} are isomorphisms. Conversely, if p_{1} is an isomorphism, then we may identify X ×_{Y} X with X by means of p_{1} (note that we are not yet saying that p_{2}: X → X must be the identity, or even an isomorphism), and the uniqueness clause in the universal property of the fiber product assures that for f: T → X, the arrow hf determines f, and thus h is mono. Retrospectively, we see that p_{2}: X → X is the identity.:-) This property somehow explains the name “kernel pair”.

Some more terminology: if f: X → Y is a morphism in C, then by the universal property of X ×_{Y} X (if it exists), there exists a unique map Δ_{f}: X → X ×_{Y} X such that p_{1}Δ_{f} = p_{2}Δ_{f} = 1_{X}. By what we have just seen, Δ_{f} is an isomorphism iff f is a monomorphism, and in all cases, Δ_{f} is certainly retractable. We call Δ_{f} the \underline{diagonal morphism} associated to f. More generally, if X → Y and X′ → Y are Y - objects and u: X → X′, then the unique arrow Γ_{u}: X → X ×_{Y} X′ such that p_{1}Γ_{u} = 1_{X} and p_{2}Γ_{u} = u is called the \underline{graph} of u (over Y or some such phrase); the diagonal is the graph of the identity.

In the category Set, the fiber product of two morphisms s_{1}: X_{1} → Y and s_{2}: X_{2} → Y is X = {(x_{1}, x_{2}): s_{1}(x_{1}) = s_{2}(x_{2})}, with the maps p_{1}: (x_{1}, x_{2}) ↦ x_{1} and p_{2}: (x_{1}, x_{2}) ↦ x_{2}. We leave the case of the other customary categories to the reader (they are all very similar — and follow quite trivially from the products and the equalizers).

Of course, by dualizing all that concerns fibered products, we get the notion of an amalgamated sum. If s_{1}: Y → X_{1} and s_{2}: Y → X_{2} are morphisms, then their amalgamated sum (if it exists) is a morphism s: Y → X together with “injection” morphisms j_{1}: X_{1} → X and j_{2}: X_{2} → X, such that for any morphisms f_{1}: X_{1} → T and f_{2}: X_{2} → T verifying f_{1}s_{1} = f_{2}s_{2}, there exists a unique f: X → T such that f_{1} = fj_{1} and f_{2} = fj_{2}. We write X = X_{1} ⨿_{Y} X_{2}. We also say that j_{1} is the \underline{pushout} of s_{2} along s_{1}. The dual notion to a cartesian square is that of a cocartesian square, the dual notion to a kernel pair is that of a cokernel pair. There is also a codiagonal morphism Δ_{f}^{∗}: X ⨿_{Y} X → X associated to a morphism f: Y → X. However, one does not usually consider cographs.

Amalgamated sums are a more delicate matter in the usual categories. In the category ComRing, for example, the amalgamated sum is the tensor product. In the category Group, it is what is usually called the amalgam of two groups. In the category Set, the amalgamated sum of s_{1}: Y → X_{1} and s_{2}: Y → X_{2} is the quotient of X_{1} ⨿ X_{2} (disjoint union) by the equivalence relation generated by the (s_{1}(y), s_{2}(y)) for y ∈ Y.

Now, that is about enough universality for the moment, and we move to a more relaxing topic.

4. Functors.

We now have a rather good idea of what a category is, and we move on to describe what morphisms (to be quite accurate, I should say 1-morphisms) between them are.

Let C and D be two categories. Then a (covariant) \underline{functor} 𝔉 from C to D, in symbols 𝔉: C ⇝ D, is a map (also written 𝔉) from ob C to ob D, together with, for every A, B ∈ ob C, a map (also written 𝔉) from Hom(A, B) to Hom(𝔉A, 𝔉B), such that 𝔉1_{A} = 1_{𝔉A} for all A ∈ ob C, and if f: A → B and g: B → C in ℭ then 𝔉(gf) = (𝔉g)(𝔉f). In other words, a functor is a map on the objects together with a map on the arrows which satisfy the obvious relations.

If 𝔉: C ⇝ D is such that Hom(A, B) → Hom(𝔉A, 𝔉B) is injective (resp. surjective) for every A, B ∈ ob C, then we say that 𝔉 is \underline{faithful} (resp. \underline{full}). A functor is said to be \underline{injective} (resp. \underline{surjective}) iff it is so on the objects; more importantly, a functor 𝔉: C ⇝ D is said to be \underline{essentially injective} (resp. \underline{essentially surjective}) iff 𝔉A ≅ 𝔉B implies A ≅ B (resp. for all B ∈ ob D there exists A ∈ ob C such that B ≅ 𝔉A). Obviously, a full and faithful functor is essentially injective.

If D is a subcategory of C, then we have a canonical faithful and injective functor ℑ: D ⇝ C; it is full iff D is a full subcategory of C.

If 𝔉: C ⇝ D and 𝔊: D ⇝ E are functors, then there is a functor 𝔊𝔉: C ⇝ E, defined in the obvious way, namely: (𝔊𝔉)A = 𝔊(𝔉A) for any object A of C (and we therefore write 𝔊𝔉A) and (𝔊𝔉)f = 𝔊(𝔉f) for any object f of C (and we therefore write 𝔊𝔉f). This composition of functors is associative whenever that makes sense, and for each category C there is a functor 1_{C}: C ⇝ C which is the identity on the objects and the morphisms, and which acts as a two-sided unit element for composition. Thus the class Category of categories (say of small categories to avoid set-theoretical difficulties) forms a category with functors as morphisms. For this reason, if C and D are categories, the class of functors from C to D is sometimes written \underline{Hom}(C, D), or even Hom(C, D); still, the notation D^{C} is more common (and we shall later see how to make it into a category). Of course, two categories C and D are said to be isomorphic iff they are so in Category, that is iff there exist functors 𝔉: C ⇝ D and 𝔊: D ⇝ C such that 𝔊𝔉 = 1_{C} and 𝔉𝔊 = 1_{D}. We write C ≅ D. We shall later define a weaker notion (equivalence of categories) which turns out to be more important.

We note one more little point: if 𝔭: C ⇝ D is a functor and U an object of D, then the \underline{fiber} of 𝔭 over U, sometimes written 𝔭^{−1}(U), and sometimes even C_{U} if no confusion is possible (highly unlikely, I’d say), is the subcategory of C whose objects are those which go to U in D, and whose morphisms are those which go to 1_{U} in D (it is in general not a full subcategory of C). More generally, one can define the inverse image by 𝔭 of a subcategory E of D (in the obvious way: objects are those which go to objects of E and ditto for morphisms). The case of 𝔭^{−1}(U) is the particular case when U is identified with the discrete subcategory of D whose only object is U.

If C and D are two categories, functors from the category C^{op} to the category D are particularily important; enough for them to merit a special name: they are called \underline{contravariant} functors from C to D. In contrast, ordinary functors from C to D are called \underline{covariant}, and any functor is always assumed to be covariant unless mention of the contrary. Note that functors from C^{op} to D can be identified (in the obvious way) with functors from C to D^{op}. We shall do so (and similarily identify functors from C to D with functors from C^{op} to D^{op}); in this way, a covariant or contravariant functor from C to D can be composed with a covariant or contravariant functor from D to E, and the result is covariant or contravariant according as the two functors had same or different variances. We let the reader fill in the details, and state and prove all the obvious propositions.

Similarily, one can define functors of several variables: if C_{1}, …, C_{n} and D are categories, a functor C_{1} × ⋯ × C_{n} ⇝ D is called a (covariant) functor of n variables ranging respectively C_{1}, …, C_{n}, to D (or with values in D). Similarily, one can define functors in several variables, covariant in some and contravariant in the others. We leave the details to the reader. We note in particular that by fixing one of the variables in a functor of n variables we obtain a functor of the n − 1 other variables in the obvious way (well, perhaps this is not so obvious; for example, if 𝔉: C × D ⇝ E, and A ∈ ob C then we define the functor 𝔣 = 𝔉(A, —) by letting 𝔣(B) = 𝔉(A, B) for B ∈ ob D and 𝔣(f) = 𝔉(1_{A}, f) for f: B → B′ a morphism in D).

If C is one of the categories PSet, Top, HausTop, Group, AbGroup, Ring, ComRing, Field, RMod, etc. we have a functor 𝔉: C → Set, called the \underline{forgetful} functor, which takes an object of C to the underlying set, and a morphism of C to the underlying map of sets. This functor is faithful. A \underline{concrete category} is a category together with a faithful functor to the category Set. Similarily, there are (partially) forgetful functors such as Group → PSet or Ring → AbGroup, but these are less interesting in many ways, and unless otherwise specified, the forgetful functor is always the one which goes to Set.

If C is any category, then we have a very important functor of two variables of C, contravariant in the first and covariant in the second, with values in Set, namely the functor Hom(—, —), defined in the obvious way on the objects, and on the morphisms by

Hom(f, g): Hom(A, B) → Hom(A′, B′)
α ↦ gαf

if g: B → B′ and f: A′ → A (note the direction of the latter arrow: Hom is contravariant in the first variable) in C. We shall see that partial maps y(B) = Hom(—, B) (the “Yoneda embedding”) and Hom(A, —) are particularily important.

A similar functor is this: suppose C is a category which admits finite products, and consider the functor — × — of two covariant variables in C with values in C, defined as follows: A × B is the product of A and B, and if f: A → A′ and g: B → B′ are morphisms, then f × g is the unique morphism u: A × B → A′ × B′ such that p′_{1}u = fp_{1} and p′_{2}u = gp_{2} where p_{1}: A × B → A, p_{2}: A × B → B, p′_{1}: A′ × B′ → A′ and p′_{2}: A′ × B′ → B′ are the projection morphisms. Such a morphism exists by the universal property of A′ × B′. We leave it to the reader to likewise define the functor — ⨿ — (with the same variables and variances) in a category which admits finite coproducts.

Other classical examples of functors come from algebraic topology and cohomology theory. For example, the \underline{homology functor} is a functor H: Homo∂AbGroup ⇝ GradAbGroup defined by H_{n}K = ker ∂_{n}/ im ∂_{n+1} and the evident (?) action on morphisms. (This is a general fact: to define a functor, one often just gives the action on the objects and leaves it to the reader to figure out what the action on the morphisms is.) The \underline{homotopy functor} is a functor π: PHomoTop ⇝ Group^{ℕ} which takes a pointed space (X, x) to the sequence of its homotopy groups (π_{n}(X, x)). The \underline{singular complex functor} is a functor S: HomoTop ⇝ Homo∂AbGroup which takes a topological space to its singular complex (the most useful functor is of course the \underline{singular homology functor} HS: HomoTop ⇝ GradAbGroup, often written H instead of HS).

If 0 ≤ s ≤ r ≤ ω, then there is a “weakening of structure” (sometimes called forgetful) functor C^{r}Man ⇝ C^{s}Man. If s = 0 and r > 0 then it is known (though by no means obvious) that this functor is neither essentially injective nor essentially surjective. When s > 0, on the other hand, the functor is essentially injective and essentially surjective, as is stated by an approximation theorem. (The functor is always faithful, and is full iff s = r of course, but that is more or less trivial.)

If two groups G, G′ are made into categories, then a functor 𝔉: G ⇝ G′ is just the same as a group homomorphism G → G′. If two preordered sets are made into categories, then a functor from one to the other is just the same as a preorder-preserving map between them.

5. Natural transformations. Functors alone are not a very fascinating subject. Where things become truly fascinating is that functors between two categories can themselves be considered as the objects of a category, whose morphisms are called morphisms of functors or “natural transformations” (or “natural maps”, or “functorial transformations” but this last terminology seems a little confusing).

Suppose that C and D are two categories, and 𝔉, 𝔊: C ⇝ D are functors between them. Then a \underline{natural transformation} α from 𝔉 to 𝔊, in symbols α: 𝔉 → 𝔊, is a map from the class of objects of C to the class of morphisms of D, such that for every A ∈ ob C we have α(A): 𝔉A → 𝔊A, and which is natural in the sense that for every morphism f: A → B in C, the following diagram commutes:

𝔉A ⟶^{𝔉f} 𝔉B
α(A)↓  ↓α(B)
𝔊A ⟶^{𝔊f} 𝔊B

In other words, for every objects A, B of C and every morphism f: A → B, we have α(B) (𝔉f) = (𝔊f) α(A). Thus, α should be viewed as a collection of maps from the 𝔉A to the 𝔊A, which are compatible with one another. We will sometimes write α_{A} instead of α(A), as typography and clarity of notation require.

If 𝔉: C ⇝ D is any functor, then we have an obvious natural “identity” transformation 1_{𝔉}: 𝔉 → 𝔉, which takes any object A of C to the identity map 1_{𝔉A}: 𝔉A → 𝔉A. If 𝔉, 𝔊, ℌ: C ⇝ D are three functors, and α: 𝔉 → 𝔊 and β: 𝔊 → ℌ are natural transformations, then we have a natural transformation βα: 𝔉 → ℌ (the “composition” of β and α) given by (βα)(A) = (β(A))(α(A)) for every object A (or to write things differently, (βα)_{A} = β_{A}α_{A}). Associativity holds whenever it makes sense, and the identity natural transformations are two-sided unit elements for the composition. Thus, if C and D are categories (and say, D is small), then we have a category C^{D} of functors from D to C, whose objects are the functors D ⇝ C and whose morphisms are natural transformations between these. One immediately verifies that if the category D is discrete, then the category C^{D} just defined can be identified with the category C^{ob D} (a functor from D to C is just an ob D-indexed family of objects of C, and a natural map between functors is a ob D-indexed family of maps between the corresponding objects).

We also note that functors and natural transformations can be composed with one another in the following way: if 𝔉: C ⇝ D is a functor and α: 𝔊 → ℌ is a natural transformation, where 𝔊, ℌ: D ⇝ E, then we have a natural map α𝔉: 𝔊𝔉 → ℌ𝔉, given by (α𝔉)(A) = α(𝔉(A)). On the other hand, if α: 𝔉 → 𝔊 is a natural transformation, where 𝔉, 𝔊: C ⇝ D, and ℌ: D ⇝ E is a functor, then we have a natural map ℌα: ℌ𝔉 → ℌ𝔊, given by (ℌα)(A) = ℌ(α(A)). The identity functors act as unit elements for this composition law; as for the identity natural transformations, they are turned one into another by composition by a functor. Unfortunately, not all associativity rules hold: essentially, they hold when the composition of natural maps does not come into the game, and that one is distributive. In other words, with the evident notations, (𝔉𝔊)ℌ = 𝔉(𝔊ℌ), (𝔉𝔊)α = 𝔉(𝔊α), (𝔉α)ℌ = 𝔉(αℌ), (α𝔊)ℌ = α(𝔊ℌ), (𝔉𝔊)ℌ = 𝔉(𝔊ℌ), 𝔉(αβ) = (𝔉α)(𝔉β), (αβ)𝔉 = (α𝔉)(β𝔉) and (αβ)γ = α(βγ).

If α: 𝔉 → 𝔊, where 𝔉, 𝔊: C ⇝ D, is a natural transformation such that α(A) is an isomorphism for every A ∈ ob C, then α is an isomorphism as a morphism of functors, and conversely; the inverse is given by α^{−1}(A) = α(A)−1. Such a natural tranformation is called a \underline{natural isomorphism}. Of course, we write 𝔉 ≅ 𝔊 and we say that the functors 𝔉 and 𝔊 are isomorphic. Because of the previous paragraph, isomorphism of functors is compatible with composition, and the class of (say, small) categories with isomorphism classes of functors as morphisms forms a category, EqCategory. When two categories C and D are isomorphic in EqCategory, in other words when there exists functors 𝔉: C ⇝ D and 𝔊: D ⇝ C such that 𝔊𝔉 ≅ 1_{C} and 𝔉𝔊 ≅ 1_{D}, we say that C and D are \underline{equivalent} and we write C ≊ D. We also say that 𝔉 and 𝔊 are \underline{quasi-inverse} to one another.

We now prove the important fact that a necessary and sufficient condition for a functor 𝔉: C ⇝ D to admit a quasi-inverse is for it to be full, faithful and essentially surjective. Indeed, suppose 𝔊𝔉 ≅ 1_{C} and 𝔉𝔊 ≅ 1_{D} for some functor 𝔊: D ⇝ C. Then 𝔉 is essentially surjective since any A ∈ ob D is isomorphic (indeed, naturally isomorphic) to 𝔉(𝔊A). If f, f′: A → B are arrows in D such that 𝔉f = 𝔉f′ then then 𝔊𝔉f = 𝔊𝔉f′. But by composing the arrow 𝔊𝔉f: 𝔊𝔉A → 𝔊𝔉B with the natural arrows A → 𝔊𝔉A and 𝔊𝔉B → B, we obtain the arrow f again (that is the naturality statement), and similarily for f′. So 𝔊𝔉f = 𝔊𝔉f′ implies f = f′, which shows the faithfulness of 𝔉. The fullness assertion is similar: if f: 𝔉A → 𝔉B is an arrow in D, then 𝔊f: 𝔊𝔉A → 𝔊𝔉B composed with the natural maps A → 𝔊𝔉A and 𝔊𝔉B → B gives an arrow A → B whose image by 𝔉 is f. Conversely, suppose 𝔉: C ⇝ D is full, faithful and essentially surjective. For every object A ∈ ob D, choose an object 𝔊A ∈ ob C such that 𝔉𝔊A ≅ A, and choose such an isomorphism α(A): 𝔉𝔊A →^{∼} A. For f: A → B a morphism in D, define 𝔊f as the inverse image by 𝔉 of the composite arrow α(B)^{−1} f α(A) (this inverse image is well defined since 𝔉 is full and faithful). One checks easily that 𝔊 is a functor, that the α(A) define a natural isomorphism α: 𝔉𝔊 →^{∼} 1_{D}. As for the natural isomorphism in the other direction, it is obtained thus: we have α(𝔉A): 𝔉𝔊𝔉A →^{∼} 𝔉A, and since 𝔉 is full and faithful, this comes from an isomorphism 𝔊𝔉A →^{∼} A, which is again natural in A. Hence the result.

A natural transformation between contravariant functors, say, from C to D is just a natural transformations between these functors when viewed as (covariant) functors from C^{op} to D (or, what amounts to the same, from C to D^{op}). Similarily, a natural transformation between functors of several variables is defined by considering these as functors from an appropriate product category. For example, suppose 𝔉 and 𝔊 are functors of two variables, contravariant in the first and covariant in the second, both ranging in a category C, and taking values in a category D (that is, 𝔉 and 𝔊 can be identified with functors C^{op} × C ⇝ D). Then a natural transformation α: 𝔉 → 𝔊 is the giving, for two objects A, A′ of C, of a morphism α(A, A′): 𝔉(A, A′) → 𝔊(A, A′), such that if f: B → A and f′: A′ → B′ are two arrows in C, then the following square is commutative:

𝔉(A, A′) ⟶^{𝔉(f,f′)} 𝔉(B, B′)
α(A,A′)↓  ↓α(B,B′)
𝔊(A, A′) ⟶^{𝔊(f,f′)} 𝔊(B, B′)

(the only very moderate subtelty is the direction of the arrow f, which is B → A and not the other way around, since the functor is contravariant in the first variable).

We now proceed to give examples of natural maps, which should make it clear why they correspond to “canonical” morphisms.

To start with a very classical example (though I do not believe it is really the most illuminating possible) let R be a ring which we assume is commutative for simplicity. Then we have a contravariant functor 𝔇 from RMod to RMod, which takes an R-module M to its dual M^{∗} = L(M, R) (which is just the set Hom(M, R) with the obvious R-module structure on it), and a linear map f: M → N to the (transpose) map f^{∗}: N^{∗} → M^{∗} which takes φ to φf. Then the functor 𝔇^{2} (the composite of 𝔇 with itself) is a covariant functor RMod ⇝ RMod. If M is an R-module, then we have a “canonical” morphism ι(M): M → M^{∗∗} = 𝔇^{2}M which takes an element x of M to the linear form φ ↦ φ(x) on M^{∗}. It is painful but completely trivial to verify that ι defines a natural map 1_{RMod} → 𝔇^{2}: if f: M → N is a linear map of R-modules, then f^{∗∗}: M^{∗∗} → N^{∗∗} is given by ξ ↦ (φ ↦ ξ(φf)), and so if ξ is the form φ ↦ φ(x), its image by f^{∗∗} is φ ↦ φf(x), which is also the image by 𝔇^{2} of the element f(x), and that is exactly what naturality means.

Similarily, consider the two functors —^{—×—} and ((—)^{—})^{—} of three variables in Set, one covariant and two contravariant, and with values in Set. In other words, the functors in question are 𝔉 which takes (A, B, C) to A^{B×C} and (f, g, h) (where f: A → A′, g: B′ → B and h: C′ → C) to the map A^{B×C} → A^{′B′×C′} which takes γ to (x, y) ↦ f(γ(g(x), h(y))), and 𝔊 which takes (A, B, C) to (A^{B})^{C} and (f, g, h) (ditto) to the map (A^{B})^{C} → (A^{′B′})^{C′} which takes γ to y ↦ f(γ(h(y))(g(x))). Then there is a natural isomorphism between 𝔉 and 𝔊, given by α(A, B, C): A^{B×C} → (A^{B})^{C}, which takes γ: B × C → A to y ↦ (γ(·, y)). This is what is meant by saying that A^{B×C} and (A^{B})^{C} are “canonically” (or “naturally”) isomorphic. Similarily, we leave it to the reader to formulate the fact that (A × B)^{C} and A^{C} × B^{C} are naturally isomorphic (see the next paragraph for a generalization).

To generalize the last example of the previous paragraph, note that the functor —^{—} (of two variables, covariant in one and contravariant in the other) on Set is a particular case of the functor Hom(—, —) (of two variables, contravariant in the first and covariant in the second, and with values in Set) on any category. So if C is a category which admits products, then we can consider the two following functors of three variables (one contravariant and two covariant, in C) with values in Set: the functor 𝔉 = Hom(—, — × —) takes (A, B, C) to Hom(A, B × C) and does the obvious thing on morphisms (it is the composite of the functors — × — and Hom(—, —) which we have described previously), and the functor 𝔊 = Hom(—_{1}, —_{2}) × Hom(—_{1}, —_{3}) which takes (A, B, C) to Hom(A, B) × Hom(A, C) and does the obvious thing on morphisms. Then there is an isomorphism between 𝔉 and 𝔊, which is given by α(A, B, C): Hom(A, B ×C) → Hom(A, B) × Hom(A, C) taking γ to (p_{1}γ, p_{2}γ) where p_{1}: B × C → B and p_{2}: B × C → C are the projections. Note that the second functor, 𝔊, exists in any category, even one which does not have products (we only need Set to have products, and it certainly does): this allows us to consider morphisms A → B × C, even if B × C does not actually exist, simply as pairs made up by a morphism A → B and a morphism A → C.

While we’re at it, why are the canonical maps p_{1}: A × B → A and p_{2}: A × B → B called canonical? Because they correspond to natural maps — × — → —...

Also, the Hurewicsz homomorphism should really be regarded as a natural transformations between functors PHomoTop ⇝ Group^{ℕ}, namely the homotopy (sequence) and the homology (sequence) functors.

For a stranger example, let us consider the functor 1_{Set}: Set ⇝ Set, and let us ask what are the natural maps 1_{Set} → 1_{Set}. If α is such a natural map, then for any set A we are given a map α_{A}: A → A. Now if x ∈ A, then by considering the injection arrow f: {x} → A and using naturality, we see that we must have α_{A}f = fα_{{x}}, in other words α_{A}(x) = x; thus α_{A} is the identity for every set A, and α: 1_{Set} → 1_{Set} is the identity. In more intuitive terms, there is no way to map a set to itself canonically except with the identity. On the other hand, if we replace Set by PSet, then the functor 1_{PSet} admits a non identity endomorphism, namely the natural map b which is such that b(A) maps the pointed set A to its base point (exercice: show that this is the only one). Also note that in the full subcategory C of Set consisting of sets with exactly two elements, the identity functor 1_{C}: C ⇝ C has a non identity automorphism, namely the natural map which permutes the two elements of any pair.

Suppose P and P′ are two partially ordered sets, and we make them into categories P and P′ in the usual way. Then the objects of the category P^{′P} (namely functors from P to P′) can be identified with order preserving maps from P to P′. Interestingly, the category P^{′P} corresponds itself to a partially ordered set, the order being induced by the product order on P^{′P}.

If G and G′ are groups, and we make them into categories G and G′ in the usual way, then the objects of the category G^{′G} can be identified with group homomorphisms G → G′. If φ and ψ are such homomorphisms, and we identify them with the corresponding functors, then a natural map α: φ → ψ is an element g = α(•) of G′ such that for any element f ∈ G (i.e. arrow f: • → • in G) the diagram

\begin{matrix}• & ⟶^{φ(f)} & • \\ g↓ & & ↓g \\ • & ⟶^{ψ(f)} & • \end{matrix}

commutes, in other words ψ(f) = g φ(f) g^{−1} for every f ∈ G. Thus, the category G^{′G} is a groupoid, whose objects are the morphisms G → G′, and with two morphisms deemed isomorphic iff they are conjucate by an element of G′. This and a little bit of thought (or perhaps even without both) shows that two groups are equivalent as categories iff they are isomorphic.

Now for a few examples of equivalent categories. Recall that for any category C we had defined the reduced category of C to be the full subcategory C̄ of C whose objects are a system of representatives for the isomorphism classes of objects of C. Up to isomorphism, C̄ does not depend on the choice of these representatives (note, however, that the isomorphism in question is not canonical, since it depends on choosing a lot of isomorphisms between the two systems of representatives). The categories C and C̄ are equivalent, as the inclusion functor ℑ: C̄ → C is full, faithful and essentially surjective. However, they are not isomorphic in general. In the case of Set, for example, we can take the full subcategory of cardinals as the reduced category. Informally, that is what all equivalences of categories are: they do “essentially nothing” on the objects and really nothing on the morphisms.

The reduced category is important for the following reason: if C and D are categories, then we have C ≊ D iff C̄ ≅ D̄. We leave the simple proof as an exercice for the reader (hint: C ≊ D iff C̄ ≊ D̄).

Notice that if C is a groupoid (recall that this is a category in which all arrows are isomorphisms) then C̄ is the disjoint sum of groups. In other words, a groupoid is (equivalent to) a set in which certain elements have non trivial automorphisms. The group of automorphisms of an object of a groupoid is sometimes called its stabilizer. This is due to the following important example: suppose G is a group and X a G-set (i.e. a set on which G acts), and make X into a category by declaring that for each element g ∈ G gives rise to exactly one arrow x → y where y = g · x for each x ∈ X, composition being defined in the obvious way. Then X is a groupoid. The corresponding reduced category has X/G (the set of orbits) as set of objects, the group of automorphisms of an orbit being the stabilizer of any of its elements.

6. Points, representable functors and the Yoneda embedding. If C is a category, and A an object of C, then for any object T of C, we call \underline{T -point} of A a morphism T → A, that is, an element of Hom(T, A). For this reason, we shall also write A(T) instead of Hom(T, A). If T is the terminal object of C (provided it exists), then we speak of a \underline{global point}. This is in accordance with the fact that a global point of a set A is just an element of it.

Now we can view y(A): T ↦ A(T) as a contravariant functor from C to the category Set of sets (its action of morphisms is the following: if f: T′ → T is a morphism in C, then A(f): Hom(T, A) → Hom(T′, A) takes g to gf). We now let Ĉ = Set^{C^{op}} be the category of contravariant functors from C to Set, also called \underline{presheafs} (of sets) on C. Of course, morphisms of presheafs are just natural transformations. Then we make y into a (covariant) functor y: C ⇝ Ĉ by letting y(f) = f_{∗}: y(A) → y(B) be defined on every T as g ↦ fg for g ∈ y(A)(T) = Hom(T, A). This functor y is called the \underline{Yoneda embedding}, and the second word in the name is justified by the following extremely important fact: y is full and faithful. We now prove this assertion. Suppose that f: A → B. Then we can recover f from y(f) by noting that f is the image by y(f)(A): Hom(A, A) → Hom(A, B) of 1_{A} ∈ Hom(A, A). In other words, f = y(f)(A)(1_{A}). This is obvious from the definitions, and this shows that y is faithful. To show that y is full, we take α: y(A) → y(B), and we must show that α is of the form y(f) for some f: A → B. Now we have an obvious candidate for f, namely α(A)(1_{A}). To check that α is indeed equal to f_{∗} = y(f), we use the naturality of α, which implies that for any g: T → A the following square commutes:

1_{A} ∈ Hom(A, A) ⟶^{y(A)(g)} Hom(T, A) ∋ g
α(A)↓  ↓α(T)
f ∈ Hom(A, B) ⟶^{y(B)(g)} Hom(T, B) ∋ fg

which implies that fg = α(T)(g). But that is also f_{∗}(T)(g), so that α = f_{∗} and y is full.

The Yoneda lemma (namely the fullness and faithfulness assertion for y) implies that the category C is equivalent to a full subcategory of Ĉ, the category of presheafs which are isomorphic to a presheaf of the form y(A) for some A ∈ ob C. Or in other words, contravariant functors from C to Set which are isomorphic to a functor Hom(—, A) for some A. Such functors have been called \underline{representable} by Grothendieck, and they are sometimes very useful for constructing objects of C; they are also the fundamental tool in algebraic geometry for constructing “classifying spaces”. The category Ĉ can be viewed as some kind of very broad completion of C. For example, products exist in C̄, and the product A × B of two objects in C exists iff the presheaf y(A) × y(B) is representable, in which case it is (isomorphic to) y(A × B). (Note that this does not work with coproducts: although coproducts exist in Ĉ, they do not necessarily coincide with coproducts in C.) Now let us prove this assertion. First of all, to see that products exist in Ĉ and are computed termwise, let A and B be two presheafs on C, and write C for the presheaf defined by C(T) = A(T) × B(T) and if f: T′ → T then C(f) is the map C(T) → C(T′) whose components are the maps A(f): A(T) → A(T′) and B(f): B(T) → B(T′). Then C is obviously a presheaf, and also obviously satisfies the universal property of a product. So products exist in Ĉ (we just did it for products of two objects for simplicity, but there is no difficulty in generalizing), and are computed termwise Now if A and B are two objects of C, then to say that they admit a product C means that there exist arrows p_{1}: C → A and p_{2}: C → B such that for any object T we have Hom(T, C) ≅ Hom(T, A) × Hom(T, B) by means of u ↦ (p_{1}u, p_{2}u). But letting A = y(A), B = y(B) and C = y(C), and using the Yoneda lemma, that is again the same as saying that there exist arrows p_{1}: C → A and p_{2}: C → B such that for any object T we have C(T) ≅ A(T) × B(T) by means of u ↦ (p_{1}(T)(u), p_{2}(T)(u)). And that, as we have just seen, means exactly that C is a product of A and B.

A note on the terminology: those who know what a presheaf on a topological space is may wonder what that has to do with what we just defined. Well, let X be a topological space, and consider the category Open(X) whose objects are open sets of X and whose morphisms are just the canonical immersions (this is the same as considering the topology of X as a partially ordered set and making it into a category in the usual way). Then a presheaf of sets on X in the usual terminology is just what we called a presheaf of sets on Open(X). Of course, this can be read backwards as a definition of a presheaf on a topological space. Later on, we will define sheaves in all generality: to do this, we will need to know when an object of a category is “covered” (by arrows of that category), and this will lead to the definition of a Grothendieck topology on a category.

Representable functors can go the other way also: a covariant functor 𝔉: C ⇝ Set is said to be representable iff there exists an object A ∈ ob C such that 𝔉 ≅ Hom(A, —), and we have a dual Yoneda embedding which is none other than the Yoneda embedding for C^{op}. However, for some obscure reason, representability of covariant functors is (slightly) less interesting than that of contravariant functors.

We now say a few words on classification problems. Let C be a category with pullbacks. We assume that Φ is a class of arrows of C that is preserved by base change, i.e. if p: X → S belongs to Φ and f: S′ → S is a (base change) arrow, then the arrow p_{S′}: X_{S′} → S′ obtained by pulling back p along f belongs to Φ. Then we can consider the functor 𝔉, contravariant from C to Set, that to an object S of C associates the set of isomorphism classes of arrows X → S belonging to Φ (two arrows X → S and X′ → S being considered isomorphic iff there exists an isomorphism X ≅ X′ which takes one arrow to the other) and to every morphism f: S′ → S the change of base map taking X → S to X_{S′} → S′ as described above (obviously this commutes with isomorphism). We say that an object M (a “modulus space”) of C \underline{classifies} Φ iff the functor 𝔉 is represented by M, that is iff 𝔉 ≅ y(M) = Hom(—, M).

The simplest example of a classification is probably the subobject classifier in the category Set: let Φ be the category of monomorphisms (i.e. injective maps) in the category Set. Then the functor 𝔉 associates to every set S its power set P(S) and to every map S′ → S the inverse image map P(S) → P(S′). So we are looking for an object Ω of Set such that the functors S ↦ Hom(S, Ω) and S ↦ P(S) are naturally isomorphic. This object is well known and is the set {0, 1}. This serves perhaps to motivate the following intuitive statement: classifying maps means classifying their fibers (and of course the only possible fibers of a monomorphism in Set are the empty set and the singleton); the modulus space is the space of possible fibers; an arrow f: X → S in Φ corresponds to the arrow S → M which takes each “point” of S to its fiber in M. This is only meant intuitively but it turns out to be a very good approximation.

7. Adjoint functors. The notion of adjoint functors is an extremely important one: in a sense, it is the universal universal construction, as it is a universal construction which permits to describe every other universal construction.

So here is the definition: if C and D are categories and 𝔉: C ⇝ D and 𝔊: D ⇝ C are (covariant) functors, we say that 𝔉 is \underline{left adjoint} to 𝔊 (or that 𝔊 is \underline{right adjoint} to 𝔉) and we write 𝔉 ⊣ 𝔊 iff the functors Hom(𝔉—, —) and Hom(—, 𝔊—) are naturally isomorphic. In other words, this means that for every objects A of C and B of D we are given a bijection θ_{A,B} between Hom(𝔉A, B) and Hom(A, 𝔊B), which is natural in the sense that if f: A′ → A and g: B → B′ are arrows in C and D respectively, then the square

Hom(𝔉A, B) ⟶^{θ_{A,B}} Hom(A, 𝔊B)
g—(𝔉f)↓  ↓(𝔊g)—f
Hom(𝔉A′, B′) ⟶^{θ_{A′,B′}} Hom(A′, 𝔊B′)

is commutative.

If 𝔉 ⊣ 𝔊, then we call η_{A} the image of 1_{𝔉A} by the bijection θ_{A,𝔉A}: Hom(𝔉A, 𝔉A) → Hom(A, 𝔊𝔉A). This gives a map η_{A}: A → 𝔊𝔉A. Naturality of η can be proved in several ways, here is one (possibly not completely rigorous): as A varies, selecting 1_{A} from Hom(A, A) is natural, and therefore so is selecting 1_{𝔉A} from Hom(𝔉A, 𝔉A), and we apply the natural map θ_{A,𝔉A} to this, so the resulting map can only be natural. We leave it to the reader to formulate this rigorously; anyway, another proof follows from the identity we are about to formulate.

If h ∈ Hom(𝔉A, B) then the (right) naturality of θ gives the following commutative diagram:

1_{𝔉A} ∈ Hom(𝔉A, 𝔉A) ⟶^{θ_{A,𝔉A}} Hom(A, 𝔊𝔉A) ∋ η_{A}
h—↓  ↓(𝔊h)—
h ∈ Hom(𝔉A, B)  ⟶^{θ_{A,B}} Hom(A, 𝔊B) ∋ (𝔊h)η_{A}

from which one deduces the very important identity

θ_{A,B}(h) = (𝔊h)η_{A}

Similarily, if we let ε_{A}: 𝔉𝔊A → A be the inverse image of 1_{𝔊A} by θ_{𝔊A,A}, we get a natural map which satisfies the identity

θ_{A,B}^{−1}(h) = ε_{B}(𝔉h)

Moreover, applying this last identity to η_{A}, we see that 1_{𝔉A} = ε_{𝔉A}(𝔉η_{A}). In other words, we have found natural transformations η: 1_{C} → 𝔊𝔉 and ε: 𝔉𝔊 → 1_{D}, respectively called the \underline{unit} and the \underline{counit} of the adjunction, such that the composite 𝔉 →^{𝔉η} 𝔉𝔊𝔉 →^{ε𝔉} 𝔉 is the identity 1_{𝔉}, and similarily for the composite 𝔊 →^{η𝔊} 𝔊𝔉𝔊 →^{𝔊ε} 𝔊.

Now conversely assume that 𝔉: C ⇝ D and 𝔊: D ⇝ C are functors and η: 1_{C} → 𝔊𝔉 and ε: 𝔉𝔊 → 1_{D} are natural transformations such that the composites 𝔉 →^{𝔉η} 𝔉𝔊𝔉 →^{ε𝔉} 𝔉 and 𝔊 →^{η𝔊} 𝔊𝔉𝔊 →^{𝔊ε} 𝔊 are the identity, then define θ_{A,B}: Hom(𝔉A, B) → Hom(A, 𝔊B) by θ_{A,B}(h) = (𝔊h)η_{A}. This is trivially natural on the right and it is natural on the left because of the naturality of η (we invite the reader to write down the corresponding diagrams). Moreover, it is a bijection, because h ↦ ε_{B}(𝔉h) is its inverse (we omit a simple calculation here). Thus, θ is a natural isomorphism between Hom(𝔉—, —) and Hom(—, 𝔊—) and so 𝔉 ⊣ 𝔊, η and ε being the unit and counit of the adjunction.

Now suppose that 𝔉 ⊣ 𝔊, where 𝔉: C ⇝ D and 𝔊: D ⇝ C. Let C_{0} be the full subcategory of C whose objects are those A ∈ ob C such that η_{A} is an isomorphism, and D_{0} be the full subcategory of D whose objects are those B ∈ ob D such that ε_{B} is an isomorphism. Then 𝔉 and 𝔊 restrict to functors C_{0} ⇝ D_{0} and D_{0} ⇝ C_{0} respectively (indeed, if η_{A} is an isomorphism, then ε_{𝔉A} = 𝔉η_{A}^{−1} is also, and if ε_{B} is an isomorphism then η_{𝔊B} is also), which we call 𝔉_{0} and 𝔊_{0} respectively, and thus η: 1_{C_{0}} → 𝔊_{0}𝔉_{0} and ε𝔉_{0}𝔊_{0} → 1_{D_{0}} are natural isomorphisms, thus showing that 𝔉_{0} and 𝔊_{0} are category equivalences. In this way, any adjointness of functors determines equivalent categories; this principle is called the “equivalence of opposites”. Conversely, any pair of quasi-inverse functors are left and right adjoint to each other. However, if a functor is both left and right adjoint to another, it does not follow that they are quasi-inverse to one another.

Clearly, if 𝔉 is left adjoint to 𝔊, then 𝔉𝔊 and 𝔉𝔊𝔉𝔊 are isomorphic. :-(Both composite arrows 𝔉𝔊 →^{𝔉η𝔊} 𝔉𝔊𝔉𝔊 →^{ε𝔉𝔊} 𝔉𝔊 and 𝔉𝔊 →^{𝔉η𝔊} 𝔉𝔊𝔉𝔊 →^{𝔉𝔊ε} 𝔉𝔊 are the identity, whence it follows that 𝔉η𝔊 is an isomorphism with inverse 𝔉𝔊ε = ε𝔉𝔊 (this last identity is a consequence of what precedes, not an explanation).:-) Similarily, of course, the functors 𝔊𝔉 and 𝔊𝔉𝔊𝔉 are isomorphic.

Note that if a functor 𝔉 has a right adjoint 𝔊, then it is unique up to isomorphism. :-(Indeed, if 𝔊 and 𝔊′ are two, then 1_{𝔊A} ∈ Hom(𝔊A, 𝔊A) determines an element of Hom(𝔉𝔊A, A) (which is none other than ε_{A}, and then in turn an element of Hom(𝔊A, 𝔊′A) (which is none other than (𝔊′ε_{A})η′_{𝔊A} with the obvious notations), which is easily checked to be an isomorphism, and which is clearly natural in A.:-) The corresponding statement for left adjoints also holds, of course. Thus we commit the usual abuse of notation and speak of the right (or left) adjoint.

For another important statement, note that if 𝔉: C ⇝ D, 𝔊: D ⇝ C, 𝔉′: D ⇝ E and 𝔊′: E ⇝ D, that 𝔉 ⊣ 𝔊 and 𝔉′ ⊣ 𝔊′ then 𝔉′𝔉 ⊣ 𝔊𝔊′, and indeed the unit of the adjunction η′′: 1_{C} → 𝔊𝔊′𝔉′𝔉 is the composite of the unit η: 1_{C} → 𝔊𝔉 by the unit image 𝔊η𝔉: 𝔊𝔉 → 𝔊𝔊′𝔉′𝔉, and similarily for the counit. The proof goes without surprise.

Here is another way of defining adjoint functors which occasionally turns out to be useful: if 𝔉 ⊣ 𝔊 with 𝔉: C ⇝ D and 𝔊: D ⇝ C, then we see that for every object A of C the object 𝔉A and the arrow η_{A}: A → 𝔊𝔉A have the universal property that for each object B of D and each arrow f: A → 𝔊B there is a unique arrow g: 𝔉A → B such that (𝔊g)η_{A} = f; we say that η_{A} is universal among arrows from A to an object of the form 𝔊B. Conversely, if we have a functor 𝔊: D ⇝ C and for each object A of C an object 𝔉A and an arrow η_{A}: A → 𝔊𝔉A that is universal among arrows from A to an object of the form 𝔊B, then we can make 𝔉 into a functor by letting 𝔉f = g for f: A → A′, where g: 𝔉A → 𝔉A′ is the arrow corresponding to the composite η_{A′}f: A → 𝔊𝔉A′ by the universal property; it is then easily checked that 𝔉 is the left adjoint functor to 𝔊.

Examples of adjoint functors abound in mathematics. To start with the most classical example, let R be a ring, and 𝔊: RMod ⇝ Set be the forgetful functor (which takes an Rmodule to its underlying set), and let 𝔉: Set ⇝ RMod be the free R-module construction: it takes a set B to R^{(B)} (the left R-module of functions from B to R with finite support) and a map B → B′ to the unique morphism R^{(B)} → R^{(B′)} which restricts to the given map B → B′ (with B and B′ identified with the canonical bases of R^{(B)} and R^{(B′)}). Then I claim that 𝔉 is left adjoint to 𝔊. The unit η_{B} takes the set B to the subset of R^{(B)} which we have identified with B, and the counit ε_{M} shows M as a quotient of the free module with basis every element of M. It is a trivial exercice to verify that the adjunction identities are indeed satisfied. This is a general phenomenon: the left adjoint to a forgetful functor, when it exists, is a “free object” construction functor. Similarily, the left adjoint to the forgetful functor Group ⇝ Set is the free group functor Set ⇝ Group, the left adjoint to the forgetful functor Ring ⇝ Set is the polynomial ring functor (over ℤ), the left adjoint to the addition-forgetful functor Ring ⇝ Semigroup (where Semigroup is the category of semigroups, that is, associative magmas with a unit element, morphisms being magma homomorphisms which preserve the unit element) is the semigroup ring functor Semigroup ⇝ Ring. The multiplication forgetful functor Ring ⇝ AbGroup also has a left adjoint, but I do not believe it has a classical name; it is easily described, however: it takes an abelian group A to the ring of polynomials on elements of A quotiented out by all the (additive) relations that elements of A satisfy. If G is a group, the forgetful functor GSet ⇝ Set has a left adjoint, namely the functor taking a set X to the free (also called “induced”) G-set with basis X, that is the set G × X with G acting on the first coordinate (G then acts freely, hence the name).

Not only forgetful functors, but also inclusion functors tend to have left adjoints. When the inclusion functor 𝔊: C ⇝ D of a subcategory C of a category D has a left adjoint, we say that C is a \underline{reflective} subcategory of D, that the left adjoint in question is the \underline{reflector}, and that the unit of the adjunction is the \underline{reflection}. This terminology is mainly in use for full subcategories. For example, the inclusion functor AbGroup ⇝ Group has a left adjoint, namely the “abelianization” functor Group ⇝ AbGroup which takes a group G to G/G′ (where G′ is the derived group of G, viz. the subgroup generated by the commutators), and a morphism f: G → H to the induced morphism G/G′ → H/H′, which is meaningful because f(G′) ⊆ H′. The unit of the adjunction is the canonical morphism η_{G}: G → G/G′, and the counit is an isomorphism. Thus, AbGroup is a full reflective subcategory of Group. The inclusion functor Ring ⇝ PsRing also has a left adjoint, namely the functor PsRing ⇝ Ring which takes a pseudo-ring R to the ring ℤ ⊕ R with the obvious multiplication (so that the unit of ℤ becomes the unit of ℤ ⊕ R). The unit η_{R} identifies the pseudo-ring R with the obvious sub-pseudo-ring of the ring ℤ ⊕ R, and the counit ε_{R} identifies in ℤ ⊕ R the unit of ℤ and the unit of the ring R.

Examples from topology can also be given: for example, let ComTop be the category of compact (Hausdorff) topological spaces. Then the inclusion functor ComTop ⇝ Top has a left adjoint, which is none other than the Stone-Čech compactification functor. Thus, ComTop is a full reflective subcategory of Top. Another example: for n = 0, 1, 2, 3, let T_{n}Top be the category of T_{n} topological spaces (a T_{0} space is called a “Kolmogoroff” space by Bourbaki, a T_{1} space an “accessible” space, a T_{2} space is a Hausdorff space and a T_{3} space is a regular space — we take a definition for regularity which implies T_{1} and hence T_{2}). Then each of the inclusion functors T_{n}Top ⇝ T_{n−1}Top (for n = 1, 2, 3) has a left adjoint. This is (essentially) proved in Bourbaki, Topologie Générale, chapter I, exercice 27 to section 8.

Consider the diagonal functor Set ⇝ Set^{2}, which takes a set A to (A, A) and a map f to (f, f). It has a left adjoint and a right adjoint. The right adjoint is the product functor Set^{2} ⇝ Set, which takes (A, B) to A × B, and the left adjoint is the coproduct (disjoint union) functor Set^{2} ⇝ Set, which takes (A, B) to A ⨿ B. (This applies to any category with finite products and coproducts, of course, not just to Set.) More interestingly, for any set A, the functor A × —: Set ⇝ Set itself has a right adjoint, namely —^{A} (the reader will have no difficulty in figuring out what that means). This is also a contravariant functor in A, actually (the reader may wish to formulate a definition of adjointness for one variable of functors of several variables; but at this stage, it is perhaps better to do things by hand).

If the reader will recall our example from logical systems, if A is a proposition, the functor which to B associates A ∧ B has a right adjoint, which is the functor which to C associates A ⟹ C. The adjointness states that proofs of C starting from A ∧ B are “the same thing” as proofs of A ⟹ C starting from B, and that what is classically called the deduction theorem.

If P and P′ are partially ordered sets which are made into categories P and P′, so that a functor f: P ⇝ P′ is the same as an order preserving map f: P → P′, then two order preserving maps f: P → P′ and g: P′ → P are adjoint f ⊣ g as functors iff f(x) ≤ y is equivalent to x ≤ g(y). This is classically expressed by saying that f, g is a Galois correspondance.

8. Limits and colimits.

Let C be a category, and I a (small) category, which we call the “indexing” category. We consider the category C^{I}, and call it the category of \underline{projective systems} (or \underline{inductive systems} according to what we want to do with it). In other words, a projective system (or inductive system) indexed by I and with values in C is nothing else than a functor I ⇝ C. The images of the objects of I by the functor are sometimes called the “members” of the projective system, and the images of the arrows of I its “arrows”.

We note that there is an evident functor Δ: C ⇝ C^{I}, the so-called \underline{diagonal functor} which takes any object A of C to the projective system whose members are all equal to A and whose arrows are all 1_{A}. Suppose for a moment that I is not empty. Then the functor Δ is evidently faithful (it is not full in general — it is so if the category I is (weakly) connected, though) and injective, and so it identifies C with a (non necessarily full) subcategory of C^{I}. In particular, if 𝔓 ∈ ob C^{I} is a projective system, then we can consider the “slice” category C ↓ 𝔓, whose objects are morphisms Δ(A) → 𝔓 in C^{I} and whose arrows between Δ(A) → 𝔓 and Δ(B) → 𝔓 are arros A → B in C such that the corresponding arrow Δ(A) → Δ(B) makes the obvious triangle commute. For the construction to work even if I is empty, we shall say that C ↓ 𝔓 has for objects the pairs (A, α) where A is an object of C and α a morphism Δ(A) → 𝔓 in C^{ℑ}, and the morphisms between (A, α) and (B, β) are the morphisms f: A → B of C such that α = βΔ(f). The category C ↓ 𝔓 is also called the category of (projective) \underline{cones} on 𝔓. The object A in a cone Δ(A) → 𝔓 is called the \underline{apex} of the cone. If the category C ↓ 𝔓 has a universal (that is, terminal) object, then it is called the \underline{projective limit} of the projective system 𝔓 (or its apex is).

The previous definition was perhaps a little hard to swallow. Here it is in a predigested form. If 𝔓: I ⇝ C is a functor (i.e. projective system), then the projective limit of 𝔓 is an object L of C together with a natural transformation λ: Δ(L) → 𝔓 such that for any natural transformation (i.e. cone) α: Δ(A) → 𝔓 there exists a unique arrow f: A → L satisfying α = λΔ(f).

Now let us digest this even further: a projective system consists of an object X_{i} = 𝔓(i) for every object i of I, and an arrow p_{i→j}: X_{i} → X_{j} for every arrow i → j of I which compose like they should (of course the notation is abusive because there may be several arrows i → j in I but we assume the reader can keep track of them). A cone on this projective system consists of an object A and for each i an arrow α_{i}: A → X_{i} such that for each arrow i → j of I we have α_{j} = p_{i→j}α_{i}. The projective limit (if it exists) is an object L with arrows λ_{i}: L → X_{i} forming a cone and such that for each cone as above there exists a unique f: A → L such that α_{i} = λ_{i}f for each i.

Now this is beginning to seem clearer. In particular, it should be clear that if I is just a set I (i.e. a discrete category) then a projective system is just an I-indexed family of objects and the limit is the same thing as the product of the family (exists in the same cases and has the same value in case of existence). Similarily, the limit of a projective system A ⇉ B (which means two arrows f: A → B and g: A → B, identified with the obvious functor from • ⇉ • (the category with two objects and exactly two arrows from one to the other) to C) is the equalizer of the two arrows. And the limit of the projective system X_{1} →^{s_{1}} Y ←^{s_{2}} X_{2} is the fibered product X_{1} ×_{Y} X_{2}.

If I is empty, then there is only one projective system indexed by I, and its limit is the terminal object of C (if either exists). If I is weakly connected but not empty, then projective limit of a constant projective system (that is, the image by Δ of an object A) is the value of the constant, A. Note however that even if all the members of a projective system (over a non empty weakly connected indexing category) are equal to A it does not follow that the limit is A: what we said above applies if the arrows are all identities.

Some particular cases of projective limits are particularily important. We have mentioned the case where I is just a set, in which case projective limits over I are just products. The case where I is a category with two objects, A and Ω, the only arrows being the identities and some arrows from A to Ω, is the general case of equalizers. When I is a group G, a projective system on I is also called a G-object (it is the same thing as an object A of C and a morphism from G to the group of automorphisms of A), and the projective limit is called the object of fixed points, sometimes written A^{G}. When I is a preordered set, we speak of preordered projective limits. Notice, by the way, that replacing I by an equivalent category “does not change anything” to the projective limits (we leave the formulation of a precise statement and its proof to the reader; note that it is sufficient to prove the result when replacing I by Ī, the reduced category of I). There are also some more interesting results about replacing the category I by a coinitial subcategory with various conditions. We note however that if I has an initial object, then limits of projective systems indexed by I with values in any category always exist and are the value of the projective system on the initial object.

Another thing to note is that any projective limit can be constructed from products and equalizers. Indeed, if 𝔓: I ⇝ C is a projective system indexed by a category I and with values in a category C, let L_{0} be the product of the X_{i} = 𝔓(i) for all i ∈ ob I, and p_{i}: L_{0} → X_{i} be the projection maps. Now for every arrow i → j in I, we have a corresponding arrow p_{i→j} = 𝔓(i → j): X_{i} → X_{j} in C, and the arrows p_{k} for k ≠ j and p_{i→j}p_{i} determine an arrow z_{i→j}: L_{0} → L_{0} (which corresponds intuitively to replacing the i-th component in L_{0} by its image by p_{i→j}). Now the equalizer of all those arrows is the sought for limit L. This is really quite obvious. The interesting corollary is that 1) if a category admits arbitrary (small) products and arbitrary (small) equalizers then it admits arbitrary (small) limits and that 2) if a category admits a terminal object, binary products and binary equalizers, then it admits finite limits^{∗}. A category which admits finite products is called \underline{cartesian}.

If C, D and I are three categories (with I small and perhaps D also), then computing limits in C^{D} is easy when one know how to compute them in C. Namely: if 𝔓: I ⇝ C^{D} is a projective system, and L ∈ ob C^{D} its limit, then for every object D of D, L(D) is the projective limit of the system 𝔓_{D}: I ⇝ C obtained by composing 𝔓 by the evaluation-at-D functor C^{D} ⇝ C. And conversely, if every 𝔓_{D} has a projective limit L(D) there is an obvious way of making L into a functor (namely, by saying that if f: D → D′ then L(f) is the arrow L(D) → L(D′) obtained by applying the universal property of L(D′) to the arrow L(D) → 𝔓_{D′} obtained by composing the canonical L(D) → 𝔓_{D} with the arrow

∗ Very smart people may notice that if a category admits a terminal object and finite equalizers, then it admits finite limits; indeed, it admits binary products as the equalizer of no arrow.

𝔓_{D} → 𝔓_{D′} obtained by functoriality of 𝔓) so that L is the limit of 𝔓. One expresses all this by saying that limits in functor categories are computed pointwise.

There are many connections between universal constructions and adjoint functors. Here is one: if C and I are such that every projective system 𝔓: I ⇝ C has a limit then these limits constitute a functor 𝔏: C^{I} ⇝ C, and we have Δ ⊣ 𝔏. Conversely, if Δ admits a right adjoint 𝔏, then every projective system 𝔓 has a limit and this limit is 𝔏(𝔓). This follows almost immediately from the definitions, and we leave the details to the reader.

Suppose 𝔊: D ⇝ C is a functor. Then it induces a functor 𝔊^{I}: D^{I} ⇝ C^{I} in the obvious manner: thus we have 𝔊^{I}Δ_{D} = Δ_{C}𝔊. Now suppose 𝔊 has a left adjoint 𝔉; then it is relatively obvious that 𝔉^{I} ⊣ 𝔊^{I}. If the limit of every projective system indexed by the category I and with values in C or D exists then we call 𝔏_{C} and 𝔏_{D} the corresponding functors. Thus we have Δ_{C} ⊣ 𝔏_{C}, and Δ_{D} ⊣ 𝔏_{D}, and thus Δ_{D}𝔉 ⊣ 𝔊𝔏_{D} and also 𝔉^{I}Δ_{C} ⊣ 𝔏_{C}𝔊^{I}. But since Δ_{D}𝔉 = 𝔉^{I}Δ_{C}, we conclude that 𝔊𝔏_{D} ≅ 𝔏_{C}𝔊^{I}. In other words, any functor which has a left adjoint commutes with the formation of projective limits; or, for short, right adjoints preserve limits. Naturally, this still works even if not every limit is defined (there are several ways to prove this, one of them is to use the Yoneda embedding, see below).

Another way to define limits is by use of representable functors. First of all, notice that everyone know what a projective limit in the category Set is: if 𝔓 ∈ ob Set^{I} is a projective system, then its projective limit is the subset of ∏_{i∈ob I} 𝔓(i) consisting of families for which for every arrow i → j in I the j-th component is the image of the i-th component by the map 𝔓(i → j). Second, notice that it follows that we can calculate limits in every presheaf category Ĉ = Set^{C^{op}}, pointwise as we have seen (actually, it does not really matter that we know this; just define the limit in Ĉ to be the pointwise limit in what follows and whether it is the actual categorical limit is of little importance). And then one can define the projective limit L of any projective system 𝔓: I ⇝ C by letting y(L) be the projective limit of y𝔓, where y: C ⇝ Ĉ is the Yoneda embedding. In other words, “the projective limit of the 𝔓i is the object such that Hom(—, L) is the limit of the Hom(—, 𝔓i)”. This is essentially a restatement of the definition: an arrow from T to L is the same as a system of arrows from T to the 𝔓i which satisfies the compatibility conditions, viz. a cone with vertex T.

The definition of the colimit, or inductive limit, of an inductive system, is dual to that of the projective limit: if I: I ⇝ C is an inductive system, then its inductive limit is the same thing as the projective limit of the corresponding functor I^{op} ⇝ C^{op}. In other words, this time, we are looking for an initial object in the category ℑ ↑ C, or for a left adjoint to Δ. Colimits in functor categories are also computed pointwise. One word of warning, however: inductive limits in any category cannot be defined using inductive limits of sets; inductive limits in C do not coincide with inductive limits in Ĉ. Rather, inductive limits in C are defined as projective limits in C^{op}, or, what amounts to the same, Set^{C}.

An important particular case of inductive limits is that of (preordered) filtered colimits: that means that I is not only a preordered set but one where for each i, j there exists a k which satisfies i ⪯ k and j ⪯ k.

It is probably not useful to give many examples of limits and colimits. Probably everyone knows that ℤ_{p} is the projective limit of the ℤ/p^{k}ℤ, that is, of the functor from the category N^{op} (the ordered set of the natural numbers made into a category in the opposite of the usual way) to the category ComRing which takes k to ℤ/p^{k}ℤ and the arrow k → ℓ when k ≥ ℓ to the canonical map ℤ/p^{k}ℤ → ℤ/p^{ℓ}ℤ. Similarily, if G is a group then we define its profinite completion by letting I be the partially ordered set of normal subgroups of finite index of G made into a category in the usual way, and taking the limit of the projective system I ⇝ Group which takes a subgroup H ∈ ob I to the quotient G/H and the arrow H ≤ H′ to the canonical map G/H → G/H′. (One can also define the profinite completion by taking the left adjoint to the functor of the category of profinite, i.e. compact totally discontinuous groups, to the category of groups.) The inductive limit is used, for example, to define the stalk of a sheaf at a point.

We also point out that since many inclusion or forgetful functors have left adjoints (free object constructions), they preserve limits. This “explains” that the underlying set to the product of two groups is the product of the underlying sets, that the product of two abelian groups as abelian groups is their product as groups, and so on. Forgetful functors tend not to commute with inductive limits on the other hand (the free product of two groups is a rather violent counter-example); however, many forgetful functors commute with filtered inductive limits; it is certainly possible to issue a general statement to that effect but we shall not do so.

9. More about kinds of arrows and families of arrows. We recall that we defined a morphism f: A → B in a category C to be an \underline{monomorphism} iff for every g, g′: T → A such that fg = fg′ we have g = g′. In other words, that means that the morphism Hom(T, f): Hom(T, A) → Hom(T, B) (composition by f on the left) is a monomorphism for every object T of C. That is also the same as saying that the natural transformation y(f) = Hom(—, f): Hom(—, A) → Hom(—, B) is a monomorphism (as a morphism of functors). (There are several ways to see this: either “by hand” or by using what is already known about the Yoneda embedding and the characterization of monomorphisms using kernel pairs, which are limits and therefore are preserved by the Yoneda embedding.)

We now assume that the category C in which we work has (binary) amalgamated sums. We say that a morphism f: A → B is an \underline{effective monomorphism} iff the diagram

A → B ⇉ B ⨿_{A} B

is an equalizer, meaning that f is the equalizer of the two canonical arrows from B to B ⨿_{A} B (it is obvious from the definition that it equalizes them — the important statement is that it is the universal such arrow). In particular, f is a monomorphism. Now if f is the equalizer of any pair of arrows, say g_{1}, g_{2}: B → Z, then f is actually the equalizer of the canonical j_{1}, j_{2}: B → B ⨿_{A} B. :-(Indeed, there exists g: B ⨿_{A} B → Z such that g_{1} = gj_{1} and g_{2} = gj_{2}. Now if h: T → B coequalizes j_{1} and j_{2}, that is satisfies j_{1}h = j_{2}h, then it obviously coequalizes g_{1} = gj_{1} and g_{2} = gj_{2}, and so it factors through f, QED.:-) In other words, effective monomorphisms are just equalizers of pairs of arrows. Clearly, to test whether f: A → B is an effective monomorphism, it is necessary and sufficient that the diagram y(A) → y(B) ⇉ y(B ⨿_{A} B) be an equalizer (since the Yoneda embedding preserves limits), and that is again the same as testing that the diagram Hom(T, A) → Hom(T, B) ⇉ Hom(T, B ⨿_{A} B) be an equalizer for every T. Note however that this is not the same in general as asking for y(f): y(A) → y(B) to be an effective monomorphism; indeed, y(B ⨿_{A} B) is not necessarily the same as y(B) ⨿_{y(A)} y(B); and in fact, y(f) is an effective monomorphism iff it is a monomorphism since in Set every monomorphism is effective.

Now we dualize, which will give us the occasion to recapitulate before we go further (the point is that epimorphisms and effective epimorphisms are what we will need later but they are a little more annoying to define because of the dual Yoneda embedding which dualizes everything; besides, we will talk about base change which is more pleasant than cobase change — but of course there is no break in the symmetry). So here it goes:

We assume C is a category which admits fibered products. A morphism f: U → V in a category C is called an \underline{epimorphism} iff the natural map Hom(f, —): Hom(V, —) → Hom(U, —) is mono, or, what amounts to the same, is injective on every object T. The morphism f: U → V is called an \underline{effective epimorphism} iff it is the coequalizer of a pair of arrows, or, what amounts to the same, the diagram

U ×_{V} U ⇉ U → V

is a coequalizer, or, what amounts to the same, the diagram Hom(V, —) → Hom(U, —) ⇉ Hom(U ×_{V} U, —) is a coequalizer, or, what amounts to the same, the diagram Hom(V, T) → Hom(U, T) ⇉ Hom(U ×_{V} U, T) is a coequalizer (also sometimes called an “exact sequence”) of sets for every T. An effective epimorphism is an epimorphism, of course, but the converse does not hold (for a counterexample, take the epimorphism ℤ → ℚ in Ring).

The definition of an effective epimorphism suggests that we look (for an arbitrary morphism f: U → V in C) at the subset Hom_{(f)}(U, T) of Hom(U, T) consisting of those h: U → T such that hp_{1} = hp_{2} where p_{1}, p_{2}: U ×_{V} U → U are the projections. In other words, Hom_{(f)}(U, T) is the kernel (equalizer) of the double arrow Hom(U, T) ⇉ Hom(U × V U, T). Of course, the image of Hom(V, T) → Hom(U, T) is included in Hom_{(f)}(U, T), and saying that f is an effective epimorphism means that the map Hom(V, T) → Hom_{(f)}(U, T) is bijective for every T. Saying that it is injective means exactly that f is an epimorphism. When it is surjective, we say that f is \underline{conjunctive} (the dual notion is “disjunctive” — I do not believe these notions have any interest whatsoever). Now it is interesting to have another description of Hom_{(f)}(U, T) (in particular one which remains valid in a category that does not necessarily have pullbacks); here it is: Hom_{(f)}(U, T) is the set of arrows h: U → T such that if k_{1}, k_{2}: Z → U satisfy fk_{1} = fk_{2} then they also satisfy hk_{1} = hk_{2}. :-(If h satisfies this last condition, then, since fp_{1} = fp_{2}, it also satisfies hp_{1} = hp_{2} and thus is in Hom_{(f)}(U, T). Conversely, if h ∈ Hom_{(f)}(U, T) and fk_{1} = fk_{2}, then there is a k: Z → U ×_{V} U such that k_{1} = p_{1}k and k_{2} = p_{2}k; now since hp_{1} = hp_{2}, we also have hk_{1} = hp_{1}k = hp_{2}k = hk_{2}, QED.:-) So to reformulate the definition: an arrow f: U → V in an arbitrary category C is an epimorphism (resp. a conjunctive arrow, resp. an effective epimorphism) iff for every morphism h: U → T which coequalizes the same arrows as f there is at most (resp. at least, resp. exactly one) arrow g: V → T with h = gf. And of course, Hom_{(f)}(U, T) is the set of h: U → T which coequalize the same arrows as f. I do not believe that (in a category that does not necessarily have pullbacks) an effective epimorphism is the same as a coequalizer; however, I am certainly not going to look for a counterexample. Anyhow, even if we are not interested in categories without pullbacks, this reformulation of the definition is interesting because with it we can prove that a sectionable morphism is an effective epimorphism. :-(Suppose f: U → V has a section, s: V → U, so that fs = 1_{V}. We already know that f is an epimorphism (so we only have to show that it is conjunctive). Now let h ∈ Hom_{(f)}(U, T). We have an obvious candidate for g such that h = gf, namely hs. Now what we have to show is that h = hsf. But since h ∈ Hom_{(f)}(U, T), do do that we only have to show that f = fsf, and that is trivial.:-) Note also that if f is mono then Hom_{(f)}(U, T) = Hom(U, T), and so a monomorphism is an effective epimorphism iff it is an isomorphism.

We have seen that monomorphisms remain monomorphisms after an arbitrary base change. The same does not hold for epimorphisms (they are stable under cobase change, i.e. pushout, but not pullback in general). (For a counterexample, it is probably easier to refute the dual statement, and to do that, use the category of rings, take the monomorphism ℤ → ℚ and perform the cobase change ℤ → ℤ/2ℤ.) We say that a morphism f: U → V is a \underline{universal epimorphism} iff for every arrow h: V′ → V the arrow f_{V′}: U_{V′} → V′ obtained by pulling f back along h is an epimorphism (and in particular, f itself is an epimorphism). And then of course we have the notion of a universal effective epimorphism: a morphism f: U → V is said to be a \underline{universal effective epimorphism} iff for every arrow h: V′ → V the arrow f_{V′}: U_{V′} → V′ obtained by pulling f back along h is an effective epimorphism. We will give corresponding definitions in arbitrary categories later on.

Now suppose (f_{i}: U_{i} → V)_{i∈I} is a family of arrows with a common target. We say that the family is epimorphic iff the product arrow ∐_{i∈I} U_{i} → V is an epimorphism. Of course, to say that, we do not really need the coproduct to exist: rather, we shall say that the family (f_{i}) is epimorphic iff for every object T of C the arrow Hom(V, T) → ∏_{i∈I} Hom(U_{i}, T) (which sends an arrow V → T to its composites with every f_{i}) is injective. To define what it means for a family to be effective(ly) epimorphic, it would be tempting to ask for the arrow ∐_{i∈I} U_{i} → V to be an effective epimorphism, but unfortunately that is not quite what we need. Rather, we define Hom_{(f_{i})}(U_{i}, T) to be the set of all families (h_{i}: U_{i} → T) such that if k_{1}: Z → U_{i_{1}} and k_{2}: Z → U_{i_{2}} are such that f_{i_{1}}k_{1} = f_{i_{2}}k_{2} then also h_{i_{1}}k_{1} = h_{i_{2}}k_{2}. Now clearly the composition-by-f_{i} map Hom(V, T) → ∏_{i∈I} Hom(U_{i}, T) has image in Hom_{(f_{i})}(U_{i}, T). So we say that the family (f_{i}) is epimorphic (resp. conjunctive, resp. effective(ly) epimorphic) iff the map Hom(V, T) → Hom_{(f_{i})}(U_{i}, T) that it induces is injective (resp. surjective, resp. bijective) for every object T. Now if the category C has fibered products, this can be restated by saying that for every object T the sequence

Hom(V, T) → ∏_{i∈I} Hom(U_{i}, T) ⇉ ∏_{(i,j)∈I^{2}} Hom(U_{i} ×_{V} U_{j}, T)

is exact (that is, is an equalizer of sets). :-(We write p_{1ij}: U_{i} ×_{V} U_{j} → U_{i} and p_{2ij}: U_{i} ×_{V} U_{j} → U_{j} for the two projections. We have to show that a family (h_{i}: U_{i} → T) satisfies h_{i}p_{1ij} = h_{j}p_{2ij} for every i, j iff for every k_{1}: Z → U_{i_{1}} and k_{2}: Z → U_{i_{2}} such that f_{i_{1}}k_{1} = f_{i_{2}}k_{2} we have also h_{i_{1}}k_{1} = h_{i_{2}}k_{2}. Now if (h_{i}) satisfies the latter condition, then letting k_{1} = p_{1ij} and k_{2} = p_{2ij} we see that h_{i}p_{1ij} = h_{j}p_{2ij}. Conversely, if this is true for every i, j, and if k_{1}: Z → U_{i_{1}} and k_{2}: Z → U_{i_{2}} are such that f_{i_{1}}k_{1} = f_{i_{2}}k_{2}, then k_{1} and k_{2} factor through U_{i_{1}} ×_{V} U_{i_{2}}, and so we have the desired result (see the case of a single arrow, above, for details).:-)

We now make two easy comments: first, we can just as well talk of epimorphic (resp. etc.) sets of arrows as families of arrows; that is trivial. Second, a set S of arrows with codomain V is epimorphic (resp. etc.) iff so is the set S̃ of arrows of the form fr with f: U → V in S and r: U′ → U an arbitrary arrow. In other words, we can always assume that S is closed under composition by the right (we say that S is a sieve — clearly the set S̃ above is just the sieve generated by S). This is because in Hom_{(S)}(…, T), the component corresponding to fr (if fr is part of S) is determined by that corresponding to f (indeed, putting k_{1} = 1 and k_{2} = r, since f_{fr} = fr = f_{f}r, we must also have h_{fr} = h_{f}r), so adding or removing fr to S will not change anything.

To recapitulate, if S is a sieve of arrows, that is, a set of arrows with a common codomain V which is closed under composition on the right, we let Hom_{(S)}(…, T) be the set of families (h_{f})_{f∈S} of arrows such that h_{fr} = h_{f}r for every arrow r and f ∈ S. An arrow g: V → T determines such a family by putting h_{f} = gf. Thus for every T we get a map of sets Hom(V, T) → Hom_{(S)}(…, T). We say that the sieve S is epimorphic (resp. conjunctive, resp. effective(ly) epimorphic) iff this map is injective (resp. surjective, resp. bijective) for every T. Saying that a family of arrows is epimorphic (resp. etc.) is the same as saying that the sieve it generates is so.

Now we return to the word “universal” and discuss it in greater detail. If S is a sieve with codomain V (meaning that every arrow in S has codomain V) and h: V′ → V is an arrow, then we define a sieve h^{∗}(S) with codomain V′ in the following way: an arrow f: U → V′ is in h^{∗}(S) iff hf is in S. Now obviously if S is generated by a family (f_{i}: U_{i} → V) of arrows and fiber products exist then h^{∗}(S) is generated by the arrows (f_{iV′}: U_{iV′} → V′) obtained by pulling back the f_{i} along h. Thus it is compatible with our previous definitions to say that S is universally epimorphic (resp. universally conjunctive, resp. universally effective(ly) epimorphic) iff h^{∗}(S) is epimorphic (resp. conjunctive, resp. effective(ly) epimorphic) for every arrow h: V′ → V. Of course, we say that a family of arrows with a common codomain is universally epimorphic (resp. etc.) iff the sieve they generate is so. In a category with pullbacks, a family (f_{i}: U_{i} → V)_{i∈I} is universally effective(ly) epimorphic iff for every T and V′ → V the diagram

Hom(V′, T) → ∏_{i∈I} Hom(U_{i} ×_{V} V′, T) ⇉ ∏_{(i,j)∈I^{2}} Hom((U_{i} ×_{V} V′) ×_{V′} (U_{j} ×_{V} V′), T)

is exact (recall that (U_{i} ×_{V} V′) ×_{V′} (U_{j} ×_{V} V′) = (U_{i} ×_{V} U_{j}) ×_{V} V′).

We note that if S is an epimorphic sieve, say with codomain W, and R a sieve with codomain W such that for every h: V → W in S the sieve h^{∗}(R) is epimorphic, then the sieve R itself is epimorphic. :-(Suppose k_{1}, k_{2}: W → T are such that k_{1}g = k_{2}g for every g ∈ R. Now fix h ∈ S. If f ∈ h^{∗}(R) then hf ∈ R, and so k_{1}hf = k_{2}hf. Since this holds for every f in h^{∗}(R) which is epimorphic, we have k_{1}h = k_{2}h. Now this is true for every h ∈ S, which is epimorphic, so k_{1} = k_{2}, QED.:-) We also have the same statement obtained by replacing “epimorphic” everywhere by “effectively epimorphic”. :-(We already know R is epimorphic, so we only have to show that it is conjunctive. Suppose (k_{g})_{g∈R} ∈ Hom_{(R)}(…, T). Fix h ∈ S, say h: V → W. Then clearly (k_{hf})_{f∈h^{∗}(R)} ∈ Hom_{(h^{∗}(R))}(…, T), and so there exists k_{h} ∈ Hom(V, T) such that k_{hf} = k_{h}f for all f ∈ h^{∗}(R). Because h^{∗}(R) is epimorphic, and so k_{h} is uniquely determined, we have k_{hr} = k_{h}r for all r with codomain V. Thus, (k_{h})_{h∈S} ∈ Hom_{S}(…, T), and so there exists k ∈ Hom(W, T) such that k_{h} = kh for every h ∈ R. QED.:-) Notice in passing that even to show that R is conjunctive, we needed the fact that the h^{∗}(R) are epimorphic; the statement with “conjunctive” everywhere does not hold. Now we obviously have the corresponding statements with “universally epimorphic” and “universally effectively epimorphic”.

We have just proved that universally effectively epimorphic sieves constitute a topology, and we will soon be saying what a topology is. But before, we give a few examples of the concepts we have seen.

Let us start with Set. If f: U → V is a map of sets, then U ×_{V} U is the set in which every fiber of f is “squared”. An map U → T has the same image U ×_{V} U → T iff it is constant on every fiber. Such a map always comes from a map V → T except when T, and hence U also, is empty, but not V. And the map V → T in question is unique iff all fibers are non empty or T has at most one element. Hence, an epimorphism is the same as a surjective map, a conjunctive map is one whose domain is not empty except if the range is also, and an effective epimorphism is the same as an epimorphism. A universal (effective) epimorphism is again the same thing as a surjective map, and so is a universal conjunctive map (because a fiber of f can be written as a fiber product with a singleton). A family (f_{i}: U_{i} → V) is epimorphic (resp. effectively epimorphic, resp. universally epimorphic, resp. universally effectively epimorphic) iff V is the union of the f_{i}(U_{i}).

We now turn to the category Top. We have seen that epimorphisms are surjective continuous maps. Effective epimorphisms on the other hand are quotients (this follows from a description of coequalizers for example); not every surjective map is a quotient: for example, the identity from ℝ with the discrete topology to ℝ with the ordinary topology is mono and epi but is not iso, so it is not effective epi (nor is it effective mono). This also characterizes effective epimorphisms in HausTop.

In the category Ring, we have seen that epimorphisms are a little difficult to grasp. Effective epimorphisms are easier: f: A → B is an effective epimorphism iff it is surjective (this follows from the description of coequalizers). And it follows that effective epimorphisms are universally so. We may also look at the dual notions (or, what amounts to the same, look at the category Ring^{op}, which is equivalent to the category of affine schemes). A monomorphism f: A → B of rings is just an injective morphism. An effective monomorphism f: A → B is a morphism such that shows A as the set of elements x of B ⊗_{A} B such that x ⊗ 1 = 1 ⊗ x (this is merely restating the definition); so for example the monomorphism ℤ → ℚ is not effective (indeed, we know that it is epi, and it is not iso). A universal monomorphism f: A → B is one that shows A as a pure submodule of B; so the monomorphism ℤ → ℚ is not only not effective but also not universal.

Well, this should rather persuade the reader, if not that the notions in question are interesting, at least that they are not trivial, and lead to difficult problems when one tries to characterize them in the classical categories.

10. Grothendieck topologies and sheaves.

Let C be a category. We recall from the previous section that if V is an object of C, a \underline{sieve} on V is a set (class) of arrows with codomain V which is closed under composition on the right. Any family of arrows with codomain V generate a sieve in the evident way. We also recall that if S is a sieve on V and h: V′ → V, then we let h^{∗}(S) = {f: (ran f = V′) ∧ (hf ∈ S)}, which is a sieve on V′, and if pullbacks exist, then h^{∗}(S) is generated by the pullbacks of an arbitrary generating family of S.

By a \underline{Grothendieck topology} on C we mean a map which associates to every object V of C a set J(V) (class, collection, hyperclass, whatever) of sieves on V such that:

(i) For every V ∈ ob C the maximal sieve {f: ran f = V } is in J(V). (ii) (Stability) For any arrow h: V → W in C, and any S ∈ J(W), we have h^{∗}(S) ∈ J(V). (iii) (Transitivity) For every W ∈ ob C, if S ∈ J(W) and R is a sieve on W such that

h^{∗}(R) ∈ J(V) for every h: V → W in S then R ∈ J(W).

If S ∈ J(V) for an object V ∈ ob C, we say that S \underline{covers} V. More generally, we say that a family of arrows of C with a common codomain V cover V iff the sieve they generate does. So the axiom (i) means that the identity of V covers V, axiom (ii) means that if a family of arrows cover W then their pullback by an arbitrary arrow h: V → W covers V (or the best we can do in the absence of pullbacks), and axiom (iii) means that if W is covered by arrows which are themselves covered by other arrows, then W is covered by the other arrows in question (this is a bit approximative but it can be made rigorous).

We note for future reference that (iv) If V ∈ ob C, that S ∈ J(V) and R is a sieve on V that contains S (one says that S is a

\underline{refinement} of R, or that it is \underline{finer} than R) then R ∈ J(V). :-(Apply the transitivity axiom and note that h^{∗}(R) is the maximal sieve for every h ∈ R so in particular for every h ∈ S.:-)

(v) If V ∈ ob C and S, S′ ∈ J(V) then S∩S′ ∈ J(V). :-(Apply the transitivity axiom: for h ∈ S we have h^{∗}(S ∩S′) = h^{∗}(S′) and by the stability axiom this sieve is covering.:-) We say that a sieve S (or a family of arrows that generate it) on W covers an arrow

h: V → W iff h^{∗}(S) covers V, that is, h^{∗}(S) ∈ J(V). The axioms for a Grothendieck category can then be reformulated in the following “arrow” form: (ia) If S is a sieve on V and f ∈ S, then S covers f. (iia) (Stability) If S covers an arrow f: V → W, then it covers fg for every g: U → V. (iiia) (Transitivity) If S covers an arrow f: V → W and a sieve R on W covers every arrow

of S then it covers f.

The proofs of (i), (ii) and (iii) from (ia), (iia) and (iiia) respectively are obtained by considering the identitiy arrow. Conversely, let us prove (ia), (iia) and (iiia) from (i), (ii) and (iii) respectively. :-(To show (ia), note that f^{∗}(S) contains the identity, so it is the maximal sieve. To show (iia), note that (fg)^{∗}(S) = g^{∗}(f^{∗}(S)), and by hypothesis f^{∗}(S) covers V, so the result follows by (ii). To show (iiia), note that f^{∗}(S) covers W, and for every arrow h: U → V of f^{∗}(S), the sieve h^{∗}(f^{∗}(R)) covers U because R covers fh ∈ S; so (iii) tells us that f^{∗}(R) covers W.:-)

In a category with fiber products, the axioms for a Grothendieck topology can be restated as: (ib) If U → V is an isomorphism, then it covers V.

(iib) (Stability) If U_{i} → V cover V and V′ → V is any arrow, then U_{i} ×_{V} V′ → V′ cover V′. (iiib) (Transitivity) If V_{i} → W cover W and U_{ij} → V_{i} cover V_{i} for each i, then the

composites U_{ij} → W cover W.

The equivalence of this new form of the axioms is left as an easy exercice for the reader.

A category with a Grothendieck topology on it is called a \underline{site}. We now proceed to give some examples of sites.

As we have seen in the previous section, if C is any category, and we let J(V) be the set of all universally effectively epimorphic sieves on V, then this is a topology on C. It is called the \underline{canonical} topology on C. A topology such that all the sieves in J(V) are universally effectively epimorphic for every V is said to be \underline{subcanonical}. In many ways, subcanonical topologies are the only interesting ones.

The simplest example is probably that of Set. We define a topology on Set by saying that f_{i}: U_{i} → V cover V iff V is the union of the f_{i}(U_{i}). It is evident that this is a topology. In fact, it is precisely the canonical topology on Set. The same holds for GSet. We leave this as an exercice.

If P is a poset made into a category in the usual way, the canonical topology on P is quite simple to describe: V is covered by the U_{i} (there is no need to specify the morphisms because there is a unique morphism between any two elements of P) iff it is the greatest lower bound of the U_{i}. This applies in particular to the poset of open sets of a topological space X, that is, to the category Open(X): the objects of Open(X) are the open subsets of X and the morphisms are the inclusions, and the \underline{usual} topology of Open(X) is the one we have just described: V is covered by the U_{i} has the usual meaning.

We can also put all the sites Open(X) together in one big site in the following way: take the category Top (or a carefully chosen subcategory such as HausTop) and for V a topological space let S ∈ J(V) iff S is a sieve consisting of arrows f_{i}: U_{i} → V that are open embeddings and satisfy V = ⋃ f_{i}(U_{i}). For obvious reasons, this topology is called the \underline{open cover} or “usual” topology on Top.

Another interesting topology on Top is the étale topology, which we now describe. Recall that a continuous map f: X → Y of topological spaces is said to be \underline{étale} (or a local homeomorphism) iff for every x ∈ X there exists a neighborhood U of x in X (which we can assume to be open) such that the restriction of f to U is a homeomorphism onto its image. The étale topology on Top is defined exactly as the open cover topology above but replacing the words “open embeddings” by “étale”. This uses the rather simple fact that the pullback of an étale map by an arbitrary map is still étale (treat the case of a product and a subspace separately, and both are easy). We also note that if g: U → V is a continuous map such that f: V → X and gf: U → X are étale, then g itself is étale. In particular, if we consider the category Étale(X) of étale morphisms U → X (a full subcategory of the slice category Top ↓ X), all its morphisms are themselves étale. We have an obvious topology on Étale(X), and we call this site the \underline{étale site} of X. It plays for the étale topology on Top a similar role to that of Open(X) for the open cover topology.

We now describe sheafs on a site.

Let C be a category and J a Grothendieck topology on C. Let F ∈ ob Ĉ be a presheaf on C (recall that this is just a contravariant functor from C to Set). If V ∈ ob C and S ∈ J(V), by a \underline{matching family} (on the sieve S for the presheaf F) we mean a family (x_{f})_{f∈S} of sets with x_{f} ∈ F(dom f) that satisfies x_{fr} = x_{f}|_{r} for each f ∈ S and r an arrow with domain ran f, where x_{f}|_{r} stands for F(r)(x_{f}) (the restriction of x_{f} following r). If (x_{f}) is such a matching family, by an \underline{amalgamation} of (x_{f}) we mean an element x ∈ F(V) such that x_{f} = x|_{f} for each f ∈ S (here again, x|_{f} stands for F(f)(x). We say that F is a \underline{monopresheaf} or \underline{separated presheaf} (resp. \underline{conjunctive sheaf}, resp. \underline{sheaf}) iff every matching family (on any sieve) has at most (resp. at least, resp. exactly) one amalgamation.

There are several alternative ways to describe this. For one thing, if one wants to do things less “by hand”, one may describe matching families thus. Notice first that S is a category; indeed, it is a full subcategory of the slice category C ↓ V. The presheaf F defines a functor S^{op} ⇝ Set (by composing the “arrow source” functor S ⇝ C with F: C^{op} ⇝ Set); this is also called a projective system of sets indexed by S^{op}. A matching family is exactly an element of the projective limit of this projective system of sets. An amalgamation is just a matching family for the full sieve, and the inclusion of S in the full sieve determines a map from matching families on the full sieve to matching families on S. According as this map is injective, surjective or bijective (for all sieves S in the topology in question) we say that F is a monopresheaf, conjunctive sheaf or sheaf.

Yet another way of doing things is to look at S itself as a presheaf, which to any U associates the set of arrows U → V that are in S. Thus, S is a subobject of the representable presheaf y(V) (which corresponds to the maximal sieve). A matching family is then simply a natural transformation S → F, and an element of F(V) can be viewed as a natural transformation y(V) → F. Thus we consider the map Hom(y(V), F) → Hom(S, F) obtained by composing with the inclusion S → y(V); according as this map (etc, like in the previous paragraph).

In a category with pullbacks there is yet another way of doing things: suppose U_{i} → V are arrows in C. Then the we have the diagram

F(V) → ∏_{i∈I} F(U_{i}) ⇉ ∏_{(i,j)∈I^{2}} F(U_{i} ×_{V} U_{j})

Matching families for the sieve generated by the U_{i} → V are “the same thing” as elements of the kernel of the pair of maps on the right of this diagram (the argument is similar to the one given in the previous section only less understandable), and thus F is a sheaf iff the diagram above is an equalizer for every covering family of arrows. :-(We sketch the proof. Matching families for the sieve generated by the (f_{i}: U_{i} → V)_{i∈I} can be identified with families (x_{i})_{i∈I} such that if k_{1}: Z → U_{i_{1}} and k_{2}: Z → U_{i_{2}} are such that f_{i_{1}}k_{1} = f_{i_{2}}k_{2} then also x_{i_{1}}|_{k_{1}} = x_{i_{2}}|_{k_{2}}. We have to show that this condition is equivalent to saying that h_{i}p_{1ij} = h_{j}p_{2ij} for every i, j, where we write p_{1ij}: U_{i}×_{V} U_{j} → U_{i} and p_{2ij}: U_{i}×_{V} U_{j} → U_{j} for the two projections. Now if (x_{i}) is a matching family, then letting k_{1} = p_{1ij} and k_{2} = p_{2ij} we see that h_{i}p_{1ij} = h_{j}p_{2ij}. Conversely, if this is true for every i, j, and if k_{1}: Z → U_{i_{1}} and k_{2}: Z → U_{i_{2}} are such that f_{i_{1}}k_{1} = f_{i_{2}}k_{2}, then k_{1} and k_{2} factor through U_{i_{1}} ×_{V} U_{i_{2}}, and so we have the desired result (see the previous section for details).:-)

If J and J′ are two Grothendieck topologies on the same category C, we say that J is \underline{bigger} than J′, or that J′ is \underline{smaller} than J, iff J(V) ⊇ J′(V) for every V ∈ ob C (the terms “finer” and “coarser” are sometimes used, but they are better avoided because there is some doubt about which is which). The smallest topology on C is the one for which J(V) consists of the single maximal sieve for every V; the biggest topology is the one for which every sieve covers its codomain. These two topologies are respectively called the \underline{discrete} and \underline{coarse} topology, but that is probably a bad idea (the discrete topology on a topological space is does not lead to the discrete topology on its category of open sets, and same thing for the coarse topology; moreover, some authors say that a topology is “finer” than another one when it is bigger, so the coarse topology is the finest topology, not a very good idea). A topology which is slightly smaller than the biggest (coarse) topology is the one for which a sieve covers its codomain iff it is nonempty; we need a condition for this to be a topology, namely that every pair of arrows with common codomain can be completed to a commutative (not necessarily cartesian) square; the topology thus defined is called the \underline{atomic} topology. Note also that the intersection of a family (J_{i}) of topologies on a common category C (by this we mean the topology J defined by J(V) = ⋂_{i} J_{i}(V)) is also a topolog (we make the convention that the intersection of an empty family gives the biggest topology). The union of a family of topologies does not have to be a topology; however, every family of topologies has a least upper bound, namely the intersection of all topologies which are bigger than all of the members of the family.

We say of a sieve S (or of a family of arrows that generate it) that it is \underline{dominant} (resp. \underline{conjunctive}, resp. \underline{covering}) for a presheaf F iff every matching family on S for F has at most (resp. at least, resp. exactly) one amalgamation. Thus, a presheaf is a monopresheaf (resp. conjunctive, resp. a sheaf) iff every sieve of the topology is dominant (resp. conjunctive, resp. covering) for it. Clearly, the bigger the topology the harder it is for a presheaf to be a monopresheaf, conjunctive or a sheaf. We say that a sieve S with codomain W (or a family of arrows that generate it) is universally dominant (resp. universally conjunctive, resp. universally covering) for a presheaf F iff its inverse image h^{∗}(S) by any arrow h: V → W is dominant (resp. conjunctive, resp. covering) for F. Clearly, it is equivalent to require that a topology makes F into a monopresheaf (resp. a conjunctive presheaf, resp. a sheaf)) or to require that all its sieves are dominant (resp. conjunctive, resp. covering) for F, or the same condition with “universally” added everywhere. So we have an obvious candidate for a (potential) biggest topology for which F is a monopresheaf (resp. conjunctive, resp. a sheaf), namely the map taking each V to the set of universally dominant (resp. universally conjunctive, resp. universally covering) sieves for F with codomain V. Now it turns out that for “universally dominant” and “universally covering” this works, in other words, for any presheaf F on C there is a biggest topology making F into a monopresheaf (resp. a sheaf), namely the topology which consists of all universally dominant (resp. universally covering) sieves. (We omit the proof — only transitivity has to be proven, of course, and that works just like in the previous section.) However, this does not work for “conjunctive”, and that is probably the reason why everything with “conjunctive” in it is mainly folklore, and need not really concern us. Of course, taking intersections of topologies, we get the same result for families of presheaves. Thus the canonical topology is the biggest topology for which all representable presheaves are sheaves. And a subcanonical topology is one for which all representable presheaves are sheaves, i.e. one smaller than the canonical topology.

It is time we made sheaves into a category. No sooner said then done: a morphism of sheaves is by definition a morphism of presheaves between sheaves (and we recall that a morphism of presheaves is just a natural transformation between functors). Thus the category Sheave(C, J) of sheaves on a site (C, J) is a full subcategory of Ĉ. If J is subcanonical, it contains C (identified with its image in Ĉ — somewhat abusively). When the topology J is understood, one sometimes writes C̃ for the category of sheaves on C. A category which is equivalent to a category Sheave(C, J) is called a \underline{Grothendieck topos} (more general topoi, namely elementary topoi, which are actually far easier to define, correspond to more general topologies, namely Lawvere-Tierney topologies). We note that a projective limit in the category of presheaves on C of presheaves which actually turn out to be sheaves, is itself a sheaf. :-(This is because the condition for being a sheaf is expressed with limits and that limits commute with limits.:-) In other words, limits exist in sheaf categories, and are computed pointwise (the inclusion functor from the category of sheaves to the category of presheaves commutes with limits — we shall see below that it has a left adjoint).

Let F be a presheaf on a category C, and J a Grothendieck topology on C. We define a new presheaf F^{+} on C in the following way: if V ∈ ob C, we let F^{+}(V) consist of equivalence classes of matching families for F on sieves in J(V). In other words, an element of F^{+}(V) is a matching family (x_{f})_{f∈S} for some S ∈ J(V). We must describe when two such families are deemed equal. First note that if S and S′ are two sieves in J(V) such that S′ ⊆ S (we say that S′ is a \underline{refinement} of S, or that it is \underline{finer} than S) then a matching family for F on S determines by restriction to S′ a matching family on S. Also note that if S and S′ are two sieves in J(V) then there is a sieve in J(V) that is a refinement of both; in fact, S ∩ S′ is in J(V) (we have seen this above, number (v)). So we have an obvious equivalence relation: a matching family on S and a matching family on S′ will be considered equal iff they induce the same matching family on some common refinement of S and S′ (obviously, in virtue of what we have said, this is an equivalence relation). Then we have to make F^{+} into a presheaf. That is quite easy: if h: V → W is an arrow, we let F^{+}(h) be the map which takes (the equivalence class of) a matching family (x_{f})_{f∈S} on a sieve S ∈ J(W) to the (equivalence class of the) matching family (x_{hf})_{f∈h^{∗}(S)}. It is obvious that this is well defined and makes F^{+} into a presheaf. Now we have to make the construction F ↦ F^{+} into a functor (an endofunctor of Ĉ). So if γ: F → G is a morphism of presheaves (that is, a natural transformation), we define γ^{+}: F^{+} → G^{+} as follows: if V ∈ ob C, and (x_{f})_{f∈S} represents an element of F^{+}(V), where S ∈ J(V), then we let its image by γ_{V}^{+} be the class of the matching family (y_{f})_{f∈S}, where y_{f} = γ_{U}(x_{f}) if f: U → V. By naturality of γ, this defines a matching family, and it is obvious that this definition makes sense (i.e. is compatible with the equivalence relations); the naturality of γ^{+} is easier to see than to state, and the functoriality of the —^{+} functor is then perfectly clear. Also, we have a canonical morphism F → F^{+}, which takes an x ∈ F(V) to the family (x_{f}) ∈ F^{+}(V) defined over the maximal sieve on V and such that x_{1_{V}} = x. This morphism is a monomorphism (resp. an isomorphism) (i.e. F(V) → F^{+}(V) is injective (resp. bijective) for every V) precisely when F is a monopresheaf (resp. a sheaf) (this is perfectly clear from the definition).

Now we prove two important results about F^{+}. First, for any presheaf F, the presheaf F^{+} is separated (i.e. is a monopresheaf). :-(Indeed, let (\underline{x}_{f})_{f∈S} be a matching family for F^{+} on some sieve S ∈ J(V), and suppose that it has amalgamations \underline{x} and \underline{x}′, so we must show that \underline{x} = \underline{x}′. We can represent \underline{x} by a matching family (x_{g})_{g∈T} for F, on some sieve T in J(V), and similarily for \underline{x}′, which we can represent by a matching family (x′_{g})_{g∈T′} on some sieve T′ in J(V). That \underline{x} is an amalgamation for (\underline{x}_{f}) means that \underline{x}_{f} is represented by the matching family (x_{fg})_{g∈f^{∗}(T)}. Similarily, it is represented by the matching family (x′_{fg})_{g∈f^{∗}(T′)}. Thus, writing U for the domain of f, there is a sieve Q_{f} in J(U) such that Q_{f} ⊆ f^{∗}(T) and Q_{f} ⊆ f^{∗}(T′) and such that x_{fg} = x′_{fg} if g ∈ Q_{f}. We now call Q the sieve on V which consists of all fg for f ∈ S and g ∈ Q_{f}. For h ∈ Q we have x_{h} = x′_{h}, so we are done if we can prove that Q covers V. But if f ∈ S then f^{∗}(Q) certainly contains Q_{f}, so it is covering. By transitivity, we are done.:-) Second, if the presheaf F is separated (i.e. is a monopresheaf), then F^{+} is a sheaf. :-(Let (\underline{x}_{f})_{f∈S} (for some S ∈ J(V)) be a matching family for F^{+}. Each \underline{x}_{f} can be represented by a matching family (x_{f;g})_{g∈Q_{f}} for some Q_{f} ∈ J(U) (where U is the domain of f). Moreover, the fact that (\underline{x}_{f}) is matching shows that for any f ∈ S and r with codomain the domain of f we have \underline{x}_{fg} = \underline{x}_{f}|_{g}. By the definition of the restriction in F^{+}, this means that the two matching families (x_{fg;h})_{h∈Q_{fg}} and (x_{f;gh})_{h∈g^{∗}(Q_{f})} represent the same section of F^{+}, in other words that there is a sieve R_{f;g} that covers the domain of g, refines Q_{fg} and g^{∗}(Q_{f}), and such that for h ∈ R_{f,g} we have x_{fg;h} = x_{f;gh}. Now if f, f′ ∈ S and g ∈ Q_{f} and g′ ∈ Q_{f′} are such that fg = f′g′, then for all h ∈ R_{f,g} ∩R_{f′,g′} we have x_{f;g}|_{h} = x_{f;gh} = x_{fg;h} = x_{f′g′;h} = x_{f′;g′h} = x_{f′;g′}|_{h′}. Since R_{f,g} ∩ R_{f′,g′} covers the domain of g (which is also the domain of g′) we have x_{f;g} = x_{f′;g′}. Thus it makes sense to define x_{fg} = x_{f;g} for f ∈ S and g ∈ Q_{f}. Now we have defined a matching family (x_{k})_{k∈Q}, where Q is the sieve of all fg for f ∈ S and g ∈ Q_{f}. As in the previous proof, Q covers V. So (x_{k}) defines an element \underline{x} ∈ F(V). And it is then clear that \underline{x} is an amalgation of the (\underline{x}_{f}). Since by the previous result we know that this amalgamation is unique, we have shown that F^{+} is a sheaf.:-) In particular, we have the following surprise: if F is an arbitrary presheaf, then a(F) = F^{++} is a sheaf. Of course, since —^{+} is a functor, so is a: Ĉ ⇝ Sheave(C, J). To show that a is left adjoint to the inclusion functor Sheave(C, J) ⇝ Ĉ, we have to show that any morphism F → G, where F is a presheaf and G is a sheaf, factors uniquely as an arrow a(F) → G composed with the canonical arrow F → a(F) (which is itself obtained by composing the two canonical arrows F → F^{+} and F^{+} → F^{++}). To do this, we have only to show that for F → G factors uniquely as a F^{+} → G composed with the canonical arrow F → F^{+}. And this is indeed the case. :-(Let γ: F → G be the morphism in question. If \underline{x} ∈ F(V) is represented by a matching family (x_{f})_{f∈S} for some sieve S ∈ J(V), then (γ_{dom f}(x_{f}))_{f∈S} is a matching family of G, so it has a unique amalgamation, which we call γ̃(\underline{x}). This certainly defines a morphism γ̃: F^{+} → G like we wanted, and it is not hard to see that the definition was necessary, hence the uniqueness.:-)

11. 2-categories. We have already mentioned the category Category of categories, whose morphisms are functors. Now this category has a remarkable additional structure: for every objects C and D of Category, the set Hom(C, D) (which we previously have written D^{C}) of morphisms from C to D (that is, functors) has itself the structure of a category. We shall write Hom(C, D) to emphasize this fact (though not always consistently). Thus, there are not only morphisms (or 1-morphisms) between categories, but also morphisms between these morphisms, sometimes called 2-morphisms (and which in our case are nothing else but natural transformations). If C, D, E are objects of Category then the composition of functors is a map Hom(D, E) × Hom(C, D) → Hom(C, E). But actually, it is more than that: if we have natural transformations α: 𝔉 → 𝔉′ (where 𝔉, 𝔉′: C ⇝ D are functors) and β: 𝔊 → 𝔊′ (where 𝔊, 𝔊′: D ⇝ E are some more functors) then we get a natural transformation β ∗ α: 𝔊𝔉 → 𝔊′𝔉′ by declaring that

(β ∗ α)_{X} = β_{𝔉′X}(𝔊α_{X}) = (𝔊′α_{X})β_{𝔉X}

(the second equality follows by naturality of β). In other words, β ∗ α = (β𝔉′)(𝔊α) = (𝔊′α)(β𝔉) with the composition we have defined of functors with natural transformations. Moreover the composition is a functor

Hom(D, E) × Hom(C, D) ⇝ Hom(C, E)

of categories, and the unit-element and associativity rules when composing functors hold not only with the above viewed as a map of sets, but also when viewed as a functor. :-(The “hardest” statement is proving that if 𝔉, 𝔉′: C ⇝ D, 𝔊, 𝔊′: D ⇝ E and ℌ, ℌ′: E ⇝ F are functors and α: 𝔉 → 𝔉′, β: 𝔊 → 𝔊′ and γ: ℌ → ℌ′ are natural transformations then γ ∗ (β ∗ α) = (γ ∗ β) ∗ α. But it is easily checked that both (γ ∗ (β ∗ α))_{A} and ((γ ∗ β) ∗ α)_{A} are equal to

(γ_{𝔊′𝔉′A})(ℌβ_{𝔉′A})(ℌ𝔊α_{A})

hence the result.:-)

This leads us to introduce a more general definition: we shall call \underline{2-category} C a class ob(C), together with a category Hom(A, B) for each A, B ∈ ob(C) (all these categories being disjoint), and for all A, B, C ∈ ob(C) a “composition” functor

Hom(B, C) × Hom(A, B) ⇝ Hom(A, C)

which is associative whenever that makes sense and has a two-sided identity element 1_{A} ∈ ob Hom(A, A) for each A ∈ ob(C). In other words, in a 2-category C, we have not only objects (the elements of ob C) and morphisms (or 1-morphisms) (the objects of Hom(A, B)) but also 2-morphisms (the morphisms of Hom(A, B)). Of course, we write f: A → B when f is a 1-morphism between objects A and Y, and x: f → g when x is a 2-morphism between 1-morphisms f and g (which means in particular that f and g have the same domain and codomain — with the obvious meaning of these words). There is a composition law for 1-morphisms, which is associative and has the 1_{A} as two-sided unit elements. The 2-morphisms on the other hand come with two composition laws that should not be confused: when x: f → g and y: g → h are 2-morphisms, where f, g, h: A → B are 1-morphisms all with the same domain and codomain, then we have x ∈ Hom_{Hom(A,B)}(f, g) and y ∈ Hom_{Hom(A,B)}(g, h) and so x and y can be composed in the category Hom(A, B), giving yx: f → h. On the other hand, if f, f′: A → B and g, g′: B → C are 1-morphisms (where A, B, C are three objects), then the composition functor Hom(B, C) × Hom(A, B) ⇝ Hom(A, C) gives, for 2-morphisms x: f → f′ and y: g → g′, another 2-morphism gf → g′f′, which we write y ∗ x. We have for example, with obvious notations, z(yx) = (zy)x (this just because Hom(A, B) forms a category — and of course we simply write zyx), x1_{f} = x and 1_{g}x = x when x: f → g. We also have z ∗ (y ∗ x) = (z ∗ y) ∗ x (this is axiomatic: it is part of the associativity statement for the composition functor). The statement that 1_{A} is a two-sided unit element means that the composition-by-1_{A} functor from Hom(A, B) to Hom(A, B), obtained by fixing one variable in the composition functor, is the identity functor. This means that f1_{A} = f for any 1-morphism f: A → B, but also that x ∗ 1_{1_{A}} = x for any 2-morphism x: f → f′ (with f, f′: A → B). We encourage the reader to read again through the section on functors of several variables especially if he is wondering where the funny 1_{1_{A}} came from. We have similar statements on the right, of course. If f, f′: A → B are 1-morphisms, that x: f → f′ is a 2-morphism between them, and that g: B → C is a 1-morphism, then we can define gx = 1_{g} ∗ x (perhaps this is not the best notation but if so too bad). Similarily, of course, we put xh = x ∗ 1_{h} when h: C → A. There are many remarkable identities between all these composition laws, and we could not possibly enumerate them all. We still mention that the functoriality of the composition functor gives 1_{g} ∗ 1_{f} = 1_{gf} and also the very important rule that if x_{1}: f → f′, x_{2}: f′ → f′′ and y_{1}: g → g′ and y_{2}: g′ → g′′ then (y_{2} ∗ x_{2})(y_{1} ∗ x_{1}) = (y_{2}y_{1}) ∗ (x_{2}x_{1}), both being 2-morphisms from gf to g′′f′′ (we let the reader guess what the domains and codomains of the 1-morphisms in question are).

If C is a category (also called a 1-category to insist upon the difference), then we can form a 2-category also written C by letting the objects of the 2-category be those of the 1-category, the 1-morphisms of the 2-category be the morphisms of the 1-category and the 2-morphisms of the 2-category be only the identities, with the obvious composition rules (namely 1_{f}1_{f} = 1_{f}, and 1_{g} ∗ 1_{f} = 1_{gf} since these are to hold in any case). Conversely, if C is a 2-category, then we can form a category C by simply forgetting the 2-morphisms. This is not a very interesting construction, but still, when we write without comment the name of a 2-category in boldface instead of typerwriter face it means that we are forgetting its 2-morphisms to make it into a 1-category. As for the first construction explained, we will just identify a 1-category with the corresponding 2-category. We write Category for the 2-category of categories (with functors as 1-morphisms and natural transformations as 2-morphisms). Similarily, we have, for example, the 2-category Groupoid of groupoids (recall that a groupoid is a category all of whose arrows are isomorphisms) with functors as 1-morphisms and natural transformations as 2-morphisms.

If C is a 2-category, then a \underline{sub2category} (sometimes just “subcategory”) D of C is a 2-category whose objects are a subset (subclass, subcollection) of those of C and such that Hom_{D}(A, B) is a subcategory of Hom_{C}(A, B) whenever A, B ∈ ob D. When Hom_{D}(A, B) is actually a full subcategory of Hom_{C}(A, B) for every A, B ∈ ob D, we say that D is a \underline{strict} sub2category of C. When the underlying category C of C is a full subcategory of the underlying category D of D, in other words when every 1-morphism in C between objects of D is actually in D, then we say that D is a \underline{full} sub2category of C. When it is only true that every 1-morphism in C between objects of D is isomorphic (in the obvious sense, that is, in the corresponding category of morphisms) in C to a 1-morphism in D then we say that D is an \underline{essentially full} sub2category of C. A sub2category that is both strict and full is said to be \underline{strictly full} — while we could continue this little game for long, this is by far the most important notion. A strictly full sub2category is uniquely determined by its objects, and, as in the case of sub1categories we will sometimes (abusively) identify a strictly full sub2category with its class of objects. For example, Groupoid is (by definition) a strictly full sub2category of Category.

If C and D are 2-categories, a \underline{(2-)functor} 𝔉: C ⇝ D is a datum consisting of a map (also written 𝔉) ob C → ob D, and for each objects A, B ∈ ob C a functor (also written 𝔉) Hom_{C}(A, B) → Hom_{D}(𝔉A, 𝔉B) such that 𝔉 takes 1_{A} to 1_{𝔉A} and that 𝔉 is compatible with composition in the obvious sense. In other words, 𝔉 consists of a map of objects, a map of 1-morphisms and a map of 2-morphisms all of which satisfy all the nice properties you can imagine, essentially 𝔉1_{A} = 1_{𝔉A}, 𝔉1_{f} = 1_{𝔉f}, 𝔉(fg) = (𝔉f)(𝔉g), 𝔉(xy) = (𝔉x)(𝔉y) and 𝔉(x ∗ y) = (𝔉x) ∗ (𝔉y) with the obvious notations. Of course, 2-functors can be composed, and this composition law is associative whenever defined, and the (obviously defined) identity functor on a 2-category is a two-sided unit element. This makes the (super-duper-extra)class of all 2-categories into a category, which we will even make into a 3-category.

If 𝔉, 𝔉′: C ⇝ D are 2-functors, then a natural transformation (or 1-morphism of 2functors, or 2-morphism of 2-categories) α: 𝔉 → 𝔉′ is a datum consisting of a 1-morphism α_{A}: 𝔉A → 𝔉′A (also written α(A)) for every object A of C such that for any 1-morphism f: A → B of C the diagram

𝔉A ⟶^{𝔉f} 𝔉B
α(A)↓  ↓α(B)
𝔊A ⟶^{𝔊f} 𝔊B

commutes, in other words α_{B}(𝔉f) = (𝔉′f)α_{A}, but we also impose α_{B}(𝔉x) = (𝔉′x)α_{A} for any 2-morphism x: f → f′ where f, f′: A → B are 1-morphisms (recall that it is possible to compose a 1-morphism and a 2-morphism). It is possible to represent this last condition by the commutativity of a 2-diagram, obtained by taking the diagram above, doubling the arrow on top and the arrow at the bottom and inserting a 2-arrow between each of the two arrows on top and each of the two arrows at the bottom (I don’t have the patience of doing this with TEX). If α, α′: 𝔉 → 𝔉′ are natural transformations, then a natural 2transformation (or 2-morphism of 2-functors, or 3-morphism of 2-categories) ξ: α → α′ is a datum consisting of a 2-morphism ξ_{A}: α_{A} → α′_{A} (also written ξ(A)) for every object A of C such that for any 1-morphism f: A → B of C we have ξ_{B}(𝔉f) = (𝔉′f)ξ_{A} (as 2-morphisms from α_{B}(𝔉f) = (𝔉′f)α_{A} to α′_{B}(𝔉f) = (𝔉′f)α′_{A}); this is the statement of the commutativity of the following 2-diagram

𝔉A ⟶^{𝔉f} 𝔉B
α_{A}↓→^{ξA}↓α′_{A}  α_{B} ↓→^{ξB}↓α′_{B}
𝔊A ⟶^{𝔊f} 𝔊B

Now 2-diagrams are ugly enough so I WON’T BE WRITING ANY MORE OF THEM. The enterprising reader can define the notion of 3-category, and more generally of n-category, and show that 2-categories agregate in a 3-category, and more generally that n-categories agregate in an (n + 1)-category.

There is another notion which will come to be useful, but I do not know whether it has a classical name; I shall call it an “elevator” because it is related to descent arguments (!). If C and D are 2-categories, an \underline{elevator} 𝔉 from C to D is a datum consisting of a map (also written 𝔉) ob C → ob D, and for each objects A, B of C a functor (also written 𝔉) Hom_{C}(A, B) ⇝ Hom_{D}(𝔉A, 𝔉B) such that 𝔉1_{A} = 1_{𝔉A} and that for any three objects A, B, C of C the following diagram

Hom_{C}(B, C) × Hom_{C}(A, B)  ⟶ Hom_{C}(A, C)
𝔉↓  ↓𝔉
Hom_{D}(𝔉B, 𝔉C) × Hom_{D}(𝔉A, 𝔉B) ⟶ Hom_{D}(𝔉A, 𝔉C)

is commutative up to natural isomorphism, these natural isomorphisms satisfying the (obvious) cocycle condition. This means that we are given a natural isomorphism θ such that θ_{g,f}: (𝔉g)(𝔉f) ≅ 𝔉(gf); the cocycle condition states that (θ_{hg,f})(θ_{h,g}(𝔉f)) = (θ_{h,gf})((𝔉h)θ_{g,f}). In other words, 𝔉 consists of a map of objects, a map of 1-morphisms and a map of 2-morphisms; the map of 2-morphisms preserves composition of 2-morphisms: 𝔉(yx) = (𝔉y)(𝔉x); however, the map of 1-morphisms does not necessarily (contrarily to functors) preserve composition, but only up to 2-isomorphism, that is, θ_{g,f} is a 2-isomorphism between (𝔉g)(𝔉f) and 𝔉(gf); these 2-isomorphisms are natural in the sense that if x: f → f′ and y: g → g′ are 2-morphisms (where f, f′: A → B and g, g′: B → C are 1-morphisms) then (𝔉(y ∗ x))θ_{g,f} = θ_{g′,f′}((𝔉y) ∗ (𝔉x)); and they satisfy the cocycle condition written above. To recapitulate, the relations satisfied by 𝔉 (and θ) are: 𝔉1_{A} = 1_{𝔉A} (preservation of 1-identities), 𝔉1_{f} = 1_{𝔉f} (preservation of 2-identities), θ_{g,f}: (𝔉g)(𝔉f) ≅ 𝔉(gf) (almost-preservation of 1-composition), 𝔉(yx) = (𝔉y)(𝔉x) (preservation of 2-composition), (θ_{hg,f})(θ_{h,g}(𝔉f)) = (θ_{h,gf})((𝔉h)θ_{g,f}) (cocycle condition), and (𝔉(y ∗ x))θ_{g,f} = θ_{g′,f′}((𝔉y) ∗ (𝔉x)) (preservation of secondary 2-composition), with the obvious notations. In practice, elevators are most often used when the source is actually a 1-category (and the target is the 2-category of categories) so that some of these conditions drop out.

Now there is a little detail concerning elevators which we have to settle: namely, θ_{1,f} is a 2-isomorphism of 𝔉f; does it have to be the identity? Not necessarily, but we can always suppose it is, by replacing θ_{g,f} by ϑ_{g,f} = θ_{g,f}((𝔉g)θ_{1,f}^{−1}). Since θ_{h,1}(𝔉f) = (𝔉h)θ_{1,f} by the cocycle condition (put g = 1 — we omit the index on the 1), we also have ϑ_{g,f} = θ_{g,f}(θ_{g,1}^{−1}(𝔉f)). We now proceed to verify the cocycle condition on the ϑ (the naturality is evident since everything in the construction is natural). We proceed through the full verification because I had a hard time figuring it out and I don’t see why I should be alone to suffer; but I advise the reader who trusts me to skip the end of this paragraph: the others will pay for their insolence. :-(So, here we go. First notice that

θ_{hg,1}θ_{h,g} = θ_{h,g}((𝔉h)θ_{g,1})  (∗)

(set f = 1 in the cocycle condition). Now we have

ϑ_{hg,f}(ϑ_{h,g}(𝔉f)) = θ_{hg,f}(θ_{hg,1}^{−1}(𝔉f))((θ_{h,g}((𝔉h)θ_{1,g}^{−1}))(𝔉f))
= θ_{hg,f}(θ_{hg,1}^{−1}θ_{h,g}((𝔉h)θ_{1,g}^{−1})(𝔉f))
= θ_{hg,f}(θ_{h,g}((𝔉h)θ_{g,1}^{−1})((𝔉h)θ_{1,g}^{−1})(𝔉f)) by (∗)
= θ_{hg,f}(θ_{h,g}(𝔉f))((𝔉h)(θ_{g,1}^{−1}θ_{1,g}^{−1})(𝔉f))

On the other hand, we have, following exactly the same steps,

ϑ_{h,gf}((𝔉h)ϑ_{g,f}) = θ_{h,gf}((𝔉h)θ_{1,gf}^{−1})((𝔉h)(θ_{g,f}(θ_{g,1}^{−1}(𝔉f))))
= θ_{h,gf}((𝔉h)(θ_{1,gf}^{−1}θ_{g,f}(θ_{g,1}^{−1}(𝔉f))))
= θ_{h,gf}((𝔉h)(θ_{g,f}(θ_{1,g}^{−1}(𝔉f))(θ_{g,1}^{−1}(𝔉f))))
= θ_{h,gf}((𝔉h)θ_{g,f})((𝔉h)(θ_{1,g}^{−1}θ_{g,1}^{−1})(𝔉f))

Comparing the two equations above and using the cocycle condition on θ, we see that to show the cocycle condition on ϑ all we have to do is show that θ_{1,g} and θ_{g,1} commute. But this follows immediately from equation (∗) by putting h = 1. Hence the result. Since ϑ_{1,f} = 1 and ϑ_{g,1} = 1, ϑ satisfies with respect to 𝔉 exactly the same conditions as θ.:-) So from now on we shall always suppose that θ_{1,f} = 1 and θ_{g,1} = 1 when we speak of elevators.

12. Fibered and split categories. When 𝔭: E ⇝ C is a functor, we say also that 𝔭 or (abusively) E is a category \underline{above C}. Categories above C form a 2-category, where a 1-morphism between 𝔭: E ⇝ C and 𝔭′: E′ ⇝ C is a functor 𝔉: E ⇝ E′ such that 𝔭 = 𝔭′𝔉, and a 2-morphism between two such 1-morphism 𝔉_{1}, 𝔉_{2} is a natural transformation α: 𝔉_{1} → 𝔉_{2} such that α𝔭 = 1_{𝔭′}. If U is an object of C, we call \underline{fiber} of 𝔭 (or of E) above U the subcategory of E whose objects are those objects or E which go to U under 𝔭 and whose morphisms are those which go to 1_{U} under 𝔭. It is usually written E_{U} when no confusion can occur.

If φ: U → V is an arrow of C and f: x → y is an arrow of E such that 𝔭(f) = φ, then we say that f is “above” φ. When furthermore f is universal among such arrows, in the sense that if g: z → y is an arrow above φ then there exists a unique arrow h: z → x of E_{U} (that is, above 1_{U}) such that g = fh, then we say that f, or (abusively) x is an \underline{inverse image} of y by φ. We also say that f is \underline{cartesian}. Clearly, two inverse images of y by φ are isomorphic in the obvious sense. Moreover, if each object y of E_{V} has an inverse image by φ and we choose one such inverse image for each y and call it φ^{∗}y, then φ^{∗} becomes a functor from E_{V} to E_{U}, the action on morphisms being defined as follows: if k: y → y′ is an arrow of E_{V} and f: φ^{∗}y → y the chosen inverse image of y, then by the universal property of the chose inverse image f′: φ^{∗}y′ → y′ of y′, the map kf: φ^{∗}y → y′ factors uniquely through f′ so we write kf = fφ^{∗}k, thus defining the arrow φ^{∗}k and it is clear that φ^{∗} is then a functor.

A \underline{fibered category} (above C) is a category above C, say 𝔭: E ⇝ C, such that for every object y of E and arrow φ: U → V of C with 𝔭y = V there exists an inverse image of y by φ, and such that the composite of two cartesian morphisms is again cartesian (which means that an inverse image by ψ of an inverse image by φ of z is an inverse image by ψφ of z). We can, as above, choose an inverse image φ^{∗}y of each y for each arrow φ: U → V (with V the image of y under 𝔭), and then each φ^{∗} becomes a functor from E_{V} to E_{U}. One would hope to have (ψφ)^{∗} = φ^{∗}ψ^{∗} when φ: U → V and ψ: V → W ; unfortunately, that is not always the case (because some choices have been made), and the choices cannot always be made so that this be the case. However, we have something almost as good: since for z ∈ ob E_{W} the object φ^{∗}ψ^{∗}z of E_{U} is an inverse image of z by ψφ, it is canonically isomorphic to (ψφ)^{∗}z, the “canonical” statement being made precise by saying that there is a natural isomorphism θ: φ^{∗}ψ^{∗} ≅ (ψφ)^{∗} (we leave the naturality of θ as an easy exercice). Moreover, writing θ_{ψ,φ}: φ^{∗}ψ^{∗} ≅ (ψφ)^{∗} for the natural isomorphism in question, and if φ: U → V, ψ: V → W and χ: W → X, then these isomorphisms satisfy the following “cocycle” condition:

θ_{χψ,φ}(φ^{∗}θ_{χ,ψ}) = θ_{χ,ψφ}(θ_{ψ,φ}χ^{∗})

which just means that the following square commutes

φ^{∗}ψ^{∗}χ^{∗} ⟶ φ^{∗}(χψ)^{∗}
↓ ↓
(ψφ)^{∗}χ^{∗} ⟶ (χψφ)^{∗}

:-(The proof is a just a very complicated triviality. Of course, we can take an object t of E above W and we just have to prove equality on t. The proof uses backward and forward the fact that θ_{ψφ}(z) is the unique arrow in E_{U} making the following diagram commute

(ψφ)^{∗}z ⟶ z
↓ ∥
φ^{∗}ψ^{∗}z ⟶ ψ^{∗}z ⟶ z

(and similarily for the other ones, of course). This show that about anything you can think of, commutes.:-) This should ring a bell: we have just constructed a contravariant elevator from C to Category. We refer to the previous section for details on elevators.