Category Theory

Prof. Dr. B. Pareigis

Summer Semester 2004

June 14, 2004

Contents

Introduction 3 1. Foundations 6 1.1. Graphs 6 1.2. Monoids 8 1.3. Categories 12 1.4. Constructions on categories 18 1.4.1. Slice categories 18 1.4.2. Subcategories 20 1.4.3. The product of categories 20 1.4.4. The dual of a category 21 1.4.5. The free category generated by a graph 21 1.5. Functors 22 1.6. Special types of functors 24 1.6.1. Underlying functors 24 1.6.2. Free functors 25 1.6.3. Powerset functors 26 1.6.4. Hom functors or Mor functors 26 1.7. Natural transformations 27 1.7.1. Natural transformations between functors I 27 1.7.2. Diagrams 30 1.7.3. Commutative diagrams 31 1.7.4. Graph homomorphisms by commutative diagrams 33 1.7.5. Associativity by commutative diagrams 33 1.7.6. Natural transformations 35 1.7.7. Natural isomorphisms 38 1.7.8. Natural transformations between functors II 39 1.7.9. Natural transformations of graphs 42 1.7.10. Combining natural transformations and functors 43 2. Representable functors and the Yoneda Lemma 45 2.1. Representable functors 45 2.2. Terminal and initial objects 46 2.3. The extension principle 47 2.4. Isomorphisms 48 2.5. Monomorphisms and epimorphisms 50 2.6. Subobjects 54 2.7. Products 55 2.8. Equalizers 61 2.9. Universal elements 66 2.10. The Yoneda Lemma 71 2.11. Algebraic Structures 74 2.12. Limits 79 3. Adjoint functors and monads 84 3.1. Adjoint functors 84 3.2. Monads or Triples 86 3.3. Factorizations of a monad 87 3.4. Algebraic Categories 89 3.5. More facts about adjoint functors 89 References 90

Introduction

0.0.1. Remark (History.). – 1945 Categories first appear “officially” in S. Eilenberg and S. Mac Lane’s paper “General theory of natural equivalences”, (Trans. AMS 58, 1945, 231-294).

– 1950’s The main applications were originally in the fields of algebraic topology, particularly homology theory, and abstract algebra.

– 1960’s Grothendieck et al. began using category theory with great success in algebraic geometry.

– 1970’s Lawvere and others began applying categories to logic, revealing some deep and surprising connections.

– 1980’s Applications began appearing in computer science, linguistics, cognitive science, philosophy, …

– 1990’s Applications to theoretical physics – quantum groups, algebraic quantum field theories, higher category theory.

0.0.2. Remark (Why do we study categories?). (1) Abundance: Categories abound in mathematics and in related fields such as computer science. Categories are formed e.g. by

(a) Vector spaces,

(b) Abelian groups,

(c) groups,

(d) sets,

(e) monoids,

(f) semigroups,

(g) topological spaces,

(h) Banach spaces,

(i) manifolds,

(j) ordered sets,

(k) graphs,

(l) (computer-)languages,

(m) automata.

(2) Insight into similar constructions:

(a) products,

(b) free objects,

(c) direct sums,

(d) kernel and cokernels,

(e) limits,

(f) associated groups and algebras, such as homology groups, Grothendieck rings, fundamental groups, associative envelopes, compactifications, completions.

(3) Category theory proves that all information about a mathematical object can also be drawn from the knowledge of all structure preserving maps into this object. The knowledge of the maps is equivalent to the knowledge of the interior structure of an object. “Functions are everywhere!”

(4) Category theory is a language that allows to express similar properties and phenomena that occur in different mathematical areas. It helps to recognize certain properties and notions to have a general description and to be “categorical”. E.g:

(a) each finite dimensional vector space is isomorphic to its dual and hence also to its double dual. The second correspondence is considered “natural” and the first is not. Category theory can explain what the notion of “natural” really means. This was in fact the starting point of category theory.

(b) Topological spaces can be defined in many different ways, e.g. via open sets, via closed sets, via neighborhoods, via convergent filters, and via closure operations. Why do these definitions describe “essentially the same” objects? Category theory provides an answer via the notion of concrete isomorphism.

(c) Initial structures, final structures, and factorization structures occur in many different situations. Category theory allows one to formulate and investigate such concepts with an appropriate degree of generality.

(5) Category theory offers many convenient symbols that allow one to quickly perform the necessary calculations:

(a) commutative diagrams,

(b) braid diagrams,

(c) computations with symbolic elements.

(6) Transportation of problems from one area of mathematics (via suitable functors) to another area, where solutions are sometimes easier and then a transport back to the original area (sometimes via adjoint functors). For example, algebraic topology can be described as an investigation of topological problems (via suitable functors) by algebraic methods, such as associated homotopy groups.

(7) Duality: The concept of category is well-balanced, which allows an economical and useful duality.Thus is category theory the “two for the price of one” principle holds: every concept is two concepts, and every result is two results.

(8) Category theory provides the means to distinguish between general problems (“categorical” problems that may occur in many different areas in similar form) and specific problems (that a closely linked to the very special area and object one is studying).

0.0.3. Remark (Quotes). (1) (Steenrod) “Category theory is generalized abstract non-

sense.”

(2) (Hoare) “Category theory is quite the most general and abstract branch of pure mathematics. The corollary of a high degree of generality and abstraction is that the theory gives almost no assistance in solving the more specific problems within any of the subdisciplines to which it applies. It is a tool for the generalist, of little benefit for the practitioner.”

(3) (Barr-Wells) ”‘Categories originally arose in mathematics out of the need of a formalism to describe the passage from one type of mathematical structure to another. A category in this way represents a kind of mathematics, and may be described as category as mathematical workspace.

A category is also a mathematical structure. As such, it is a common generalization of both ordered sets and monoids (the latter are a simple type of algebraic structure that include transition systems as examples), and questions motivated by those topics often have interesting answers for categories. This is category as mathematical structure.

Finally, a category can be seen as a structure that formalizes a mathematician’s description of a type of structure. This is the role of category as theory. Formal descriptions in mathematical logic are traditionally given as formal languages with rules for forming terms, axioms and equations. Algebraists long ago invented a formalism based on tuples, the method of signatures and equations, to describe algebraic structures. Category theory provides another approach: the category is a theory and functors with that category as domain are models of the theory.”’

(4) (Stanford Encyclopedia of Philosophy) “Categories, functors, natural transformations, limits and colimits appeared almost out of nowhere in 1945 in Eilenberg & Mac Lane’s paper entitled ”General Theory of Natural Equivalences”. We said ”almost”, because when one looks at their 1942 paper ”Group Extensions and Homology”, one discovers specific functors and natural transformations at work, limited to groups. In fact, it was basically the need to clarify and abstract from their 1942 results that Eilenberg & Mac Lane came up with the notions of category theory. The central notion for them, as the title indicates, was the notion of natural transformation. In order to give a general definition of the latter, they defined the notion of functor, borrowing the terminology from Carnap, and in order to give a general definition of functor, they defined the notion of category, borrowing this time from Kant and Aristotle.”

1. Foundations

1.1. Graphs.

1.1.1. Definition. A (directed) graph (digraph) is a monad

G := (V, E, π)

consisting of the set V of vertices, the set E of edges or arrows and the map to the endpoints π : E ⟶ V × V. For each edge f ∈ E the vertices A and B with π(f) = (A, B) are called source and target or domain and codomain of f. We write the edge f also as f : A ⟶ B. Later on we will prefer the notation G_{0} for the set V of vertices and G_{1} for the set E of edges. There may be one or more arrows – or none at all – with given nodes as source and target. Moreover, the source and target of a given arrow need not be distinct. An arrow with the same source and target node will be called an endoarrow or endomorphism of that node. The set of arrows with source A and target B will be denoted by G(A, B) or Mor_{G}(A, B). A graph G is called simple, if π is injektive. (In the literature one also requires that there are no endoarrows.)

1.1.2. Definition. Let G = (V, E, π) and H = (V′, E′, π′) be directed graphs. A homomorphism F : G ⟶ H consists of two maps

F_{V} : V ⟶ V′, F_{E} : E ⟶ E′

(or

F_{0} : G_{0} ⟶ H_{0}, F_{1} : G_{1} ⟶ H_{1})

with

∀f ∈ E[π(f) = (A, B) ⟹ π′F_{E}(f) = (F_{V} (A), F_{V} (B))].

Thus homomorphisms send vertices to vertices and arrows to arrows in such a way that incidence and the direction of arrows are preserved. In particular we get for every pair (A, B) ∈ V × V a map

F_{E} : G(A, B) ⟶ H(F_{V} (A), F_{V} (B)).

An isomorphism F : G ⟶ H is a homomorphism, for which there is a second homomorphism \overline{F} : H ⟶ G such that \overline{F}F = id_{G} and F\overline{F} = id_{H}. Two graphs are called isomorphic, if there exists an isomorphism between them.

1.1.3. Examples. (1) Let V_{G} := {1, 2} and E_{G} := {a, b, c},

source(a) = target(a) = source(b) = target(c) = 1,

and

target(b) = source(c) = 2.

Then we can represent G as

[figure: b; 1; 2; c; a]

(2) The graph of sets and functions has all sets as nodes and all functions between sets as arrows. The source of a function is its domain, and its target is its codomain. This is a large graph: because of Russell’s paradox, its nodes and its arrows do not form sets.

(3) It is often convenient to picture a relation on a set as a graph. For example, let A = {1, 2, 3, 4} and α = {(1, 2), (2, 2), (2, 3), (1, 4)}. Then α can be pictured as

[figure: 1; 2; 3; 4]

22.04.04

(4) A data structure can sometimes be represented by a graph. The following graph represents the set ℕ of natural numbers in terms of zero and the successor function (adding 1):

[figure: 1; n; 0; succ]

The name ‘1’ for the left node is the conventional notation to require that the node denote a singleton set, that is, a set with exactly one element. One can give a formal mathematical meaning to the idea that this graph generates the natural numbers.

1.1.4. Remark. What are the natural numbers?

(1) Traditional, set-theoretic answer (Peano, one century ago):

The natural numbers form a set ℕ such that:

(a) ∃ zero ∈ ℕ,

(b) ∀n ∈ ℕ, ∃ succ(n) ∈ ℕ,

(c) ∀n ∈ ℕ : succ(n) ≠ zero ∈ ℕ

(d) ∀m, n ∈ ℕ : succ(m) = succ(n) ⟹ m = n (injectivity),

(e) ∀A ⊆ ℕ : ( zero ∈ A ∧ (∀a ∈ A : succ(a) ∈ A)) ⟹ A = ℕ. These axioms determine ℕ uniquely up to isomorphism.

(2) Categorical answer (Lawvere, 60’s): A natural number object

0 ∈ ℕ →^{s} ℕ

(in Set) consists of • a set ℕ

• with a distinguished element 0 ∈ ℕ

• and an endofunction s : ℕ ⟶ ℕ which is universal in the sense that for every structure

e ∈ X →^{g} X

there exists a unique function f : ℕ ⟶ X such that • f(0) = e

• f(s(n)) = g(f(n)) for all n ∈ ℕ.

The two characterizations are equivalent. This is a consequence of the theorem on simple recursion [Pareigis, 2000] Theorem 2.2.1 and the uniqueness given by the universal property [Pareigis, 2000] Theorem 2.2.3.

1.1.5. Remark. Notation of the form f : A ⟶ B is overloaded in several ways. It can denote a set-theoretic function, a graph homomorphism or an arrow in a graph. In fact, all three are instances of the third since there is a large graph whose nodes are sets and arrows are functions and another whose nodes are (small) graphs and arrows are graph homomorphisms. Another form of overloading is that if F : G ⟶ H is a graph homomorphism, ϕ actually stands for a pair of functions which we call F_{V} : V_{G} ⟶ V_{H} and F_{E} : E_{G} ⟶ E_{H}. In fact, it is customary to omit the subscripts and use F for all three (the graph homomorphism as well as its components F_{V} and F_{E}). This does not lead to ambiguity in practice; in reading about graphs you are nearly always aware of whether the author is talking about nodes or arrows.

1.1.6. Example. (1) If G is any graph, the identity homomorphism id_{G} : G ⟶ G is defined by (id_{G})_{V} = id_{V_{G}} (the identity function on the set of nodes of G ) and (id_{G})_{E} = id_{E_{G}}.

(2) If G is the graph

[figure: 1; 2; 3; 4]

and H is the graph

[figure: S; F; Q]

then there is a homomorphism F : G ⟶ H for which F_{V} (1) = S, F_{V} (2) = F_{V} (3) = F and F_{V} (4) = Q, and F_{E} takes the loop on 2 and the arrow from 2 to 3 both to the upper loop on F; what F_{E} does to the other two arrows is forced by the definition of homomorphism. Because there are two loops on F there are actually four possibilities for F_{E} on arrows (while keeping F_{V} fixed).

(3) If H is any graph with a node n and a loop u : n ⟶ n, then there is a homomorphism from any graph G to H that takes every node of G to n and every arrow to u. This construction gives two other homomorphisms from G to H in Example 1.5 (2) besides the four mentioned there. (There are still others.)

1.2. Monoids.

1.2.1. Definition. A monoid is a monad M = (M, μ, e) consisting of (1) a set M,

(2) a multiplication map μ : M × M ⟶ M, and

(3) a unit or neutral element e ∈ M satisfying the following axioms

- ∀a, b, c ∈ M :

a ∘ (b ∘ c) = (a ∘ b) ∘ c, (associativity)
- ∀a, b ∈ M :

e ∘ a = a and b ∘ e = b. (left and right unit element)

Here we use the notation a ∘ b := μ(a, b).

1.2.2. Definition. Let M = (M, μ, e) and M′ = (M′, μ′, e′) be monoids. A homomorphism of monoids F : M ⟶ M′ is a map F : M ⟶ M′ satisfying the following axioms

- ∀a, b ∈ M : F(a ∘ b) = F(a) ∘ F(b),

- F(e) = e′.

An isomorphism F : M ⟶ M′ is a homomorphism such that there exists another homomorphism \overline{F} : M′ ⟶ M with \overline{F}F = id_{M} and F\overline{F} = id_{M′}. Two monoids are called isomorphic if there exists an isomorphism from one monoid to the other.

23.04.04

1.2.3. Definition. Let M be a monoid. An M-graded monoid is a monad U = ((U_{i}), (μ_{i,j}), 1) consisting of

(1) a family of mutually disjoint sets (U_{i}|i ∈ M),

(2) a family of (multiplication) maps (μ_{i,j} : U_{i} × U_{j} ⟶ U_{i·j}|i, j ∈ M), and

(3) an element 1 ∈ U_{e} satisfying the following axioms (using the notation g ∘ f := μ_{i,j}(f, g)):

- ∀i, j, k ∈ M ∀f ∈ U_{i}, g ∈ U_{j}, h ∈ U_{k} :

h ∘ (g ∘ f) = (h ∘ g) ∘ f ∈ U_{(i·j)·k} = U_{i·(j·k)},

- ∀i, j ∈ M ∀f ∈ U_{i}, g ∈ U_{j} :

1 ∘ f = f and g ∘ 1 = g.

1.2.4. Definition. Let M and M′ be monoids, U be an M-graded monoid, and U′ be an M′-graded monoid. A homomorphism of graded monoids F : (M, U) ⟶ (M′, U′) consists of

(1) a homomorphism of monoids F_{M} : M ⟶ M′ and

(2) maps F_{i} : U_{i} ⟶ U′_{F_{M} (i)} for all i ∈ M such that the following conditions are satisfied

- ∀i, j ∈ M, f ∈ U_{i}, g ∈ U_{j}:

F_{i·j}(g ∘ f) = F_{j}(g) ∘ F_{i}(f)
- F_{e}(1) = 1 ∈ U′_{e′}.

It follows from the definition that a monoid is not allowed to be empty: it must contain an identity element. It also follows that we can extend the notation of powers to 0 by defining x^{0} to be the identity element of the monoid. The laws s^{k}s^{n} = s^{k+n} and (s^{k})^{n} = s^{kn} then hold for all nonnegative k and n.

1.2.5. Examples. One example of a monoid is the set of non-negative integers with addition as the operation. This includes 0 as a neutral element. The Kleene closure A^{∗} of a set A is the set of strings (or lists) of finite length of elements of A. We write the lists in parentheses; for example (a, b, d, a) is an element of {a, b, c, d}^{∗}. Some parts of the computer science literature call these strings instead of lists and write them this way: ‘abda’. A^{∗} includes the empty list () and for each element a ∈ A the list (a) of length one. The operation of concatenation makes the Kleene closure a monoid F (A), called the free monoid determined by A. The empty list is the identity element. We write concatenation as juxtaposition; thus

(a, b, d, a)(c, a, b) = (a, b, d, a, c, a, b).

Note that the underlying set of the free monoid is A^{∗}, not A. In the literature, A is usually assumed finite, but the Kleene closure is defined for any set A. The elements of A^{∗} are lists of finite length in any case. When A is nonempty, A^{∗} is an infinite set.

The concept of freeness is a general concept applied to many kinds of structures. It is treated systematically later on.

1.2.6. Definition. A submonoid of a monoid M is a subset S of M with the properties: SM-1 The identity element of M is in S. SM-2 If m, n ∈ S then mn ∈ S. (One says that S is closed under the operation.)

1.2.7. Example. The natural numbers with addition form a submonoid of the integers with addition. For another example, consider the integers with multiplication as the operation, so that 1 is the identity element. Again the natural numbers form a submonoid, and so does the set of positive natural numbers, since the product of two positive numbers is another one. Finally, the singleton set {0} is a subset of the integers that is closed under multiplication, and it is a monoid, but it is not a submonoid of the integers on multiplication because it does not contain the identity element 1.

In this section, we discuss categories whose objects are semigroups or monoids. These are typical of categories of algebraic structures; we have concentrated on semigroups and monoids because transition systems naturally form monoids.

1.2.8. Definition. A semigroup is a set S together with an associative binary operation m : S × S ⟶ S. The set S is called the underlying set of the semigroup.

1.2.9. Remark. Normally for s and t in S, m(s, t) is written ‘st’ and called ‘multiplication’, but note that it does not have to satisfy the commutative law; that is, we may have st ≠ ts. A commutative semigroup is a semigroup whose multiplication is commutative. It is standard practice to talk about ‘the semigroup S’, naming the semigroup by naming its underlying set. This will be done for other mathematical structures such as posets as well. Mathematicians call this practice ‘abuse of notation’. It is occasionally necessary to be more precise. We set s^{1} = s and, for any positive integer k, s^{k} = ss^{k−1}. Such powers of an element obey the laws s^{k}s^{n} = s^{k+n} and (s^{k})^{n} = s^{kn} (for positive k and n). On the other hand, the law (st)^{k} = s^{k}t^{k} requires commutativity. We specifically allow the empty semigroup, which consists of the empty set and the empty function from the empty set to itself. (Note that the cartesian product of the empty set with itself is the empty set.) This is not done in most of the non-category theory literature; it will become evident later why we should include the empty semigroup. An identity element e for a semigroup S is an element of S that satisfies the equation se = es = s for all s ∈ S. There can be at most one identity element in a semigroup.

1.2.10. Definition (Homomorphisms of semigroups). If S and T are semigroups, a function h : S ⟶ T is a homomorphism if for all s, s′ ∈ S, h(ss′) = h(s)h(s′).

1.2.11. Examples. The identity function on any monoid is a monoid homomorphism. If M is a monoid and S is a submonoid, the inclusion function from S to M is a monoid homomorphism. Another example is the function that takes an even integer to 0 and an odd integer to 1. This is a monoid homomorphism from the monoid of integers on multiplication to the set {0, 1} on multiplication. It is easy to see that identity functions are homomorphisms and homomorphisms compose to give homomorphisms. Thus we have two categories: Sem is the category of semigroups and semigroup homomorphisms, and Mon is the category of monoids and monoid homomorphisms.

1.2.12. Example. Let S be a semigroup with element s. Let ℕ^{+} denote the semigroup of positive integers with addition as operation. There is a semigroup homomorphism p : ℕ^{+} ⟶ S for which p(k) = s^{k}. That this is a homomorphism is just the statement s^{k+n} = s^{k}s^{n}.

1.2.13. Remark. A semigroup homomorphism between monoids need not preserve the identities. An example of this involves the trivial monoid E with only one element e (which is perforce the identity element) and the monoid of all integers with multiplication as the operation, which is a monoid with identity 1. The function that takes the one element of E to 0 is a semigroup homomorphism that is not a monoid homomorphism. And, by the way, even though {0} is a subsemigroup of the integers with multiplication and even though it is actually a monoid, it is not a submonoid.

1.2.14. Remark (Inverses of homomorphisms). As an example of how to use the definition of homomorphism, we show that the inverse of a bijective semigroup homomorphism is also a semigroup homomorphism. Let f : S ⟶ T be a bijective semigroup homomorphism with inverse g. Let t, t′ ∈ T. We have to show that g(t)g(t′) = g(tt′). Since f is injective, it is sufficient to show that f(g(t)g(t′)) = f(g(tt′)). The right hand side is tt′ because g is the inverse of f, and the left hand side is f(g(t)g(t′)) = f(g(t))f(g(t′)) because f is a homomorphism, but that is also tt′ since g is the inverse of f. This sort of theorem is true of other algebraic structures, such as monoids. It is not true for posets.

1.2.15. Remark (Isomorphisms of semigroups). If a homomorphism of semigroups has an inverse that is a homomorphism (equivalently, as we just saw, if it is bijective), we say that the homomorphism is an isomorphism. In this case, the two semigroups in question have the same abstract structure and are said to be isomorphic. As we will see later, the property of possessing an inverse is taken to define the categorical notion of isomorphism. It is important to understand that there may in general be many different isomorphisms between isomorphic semigroups. For example, there are two distinct isomorphisms between the monoid with underlying set {0, 1, 2, 3} and addition (mod 4) as operation and the monoid with underlying set {1, 2, 3, 4} and multiplication (mod 5) as operation.

We now discuss two important types of examples of monoid homomorphisms that will reappear later in the notes. The first example is a basic property of free monoids.

1.2.16. Remark (Kleene closure induces homomorphisms). Let A and B denote sets, thought of as alphabets. Let f : A ⟶ B be any set function. We define f^{∗} : A^{∗} ⟶ B^{∗} by f^{∗}((a_{1}, a_{2}, …, a_{k})) = (f(a_{1}), f(a_{2}), …, f(a_{k})). In particular, f^{∗}() = () and for any a ∈ A, f^{∗}(a) = f(a). Then f^{∗} is a homomorphism of monoids, a requirement that, in this case, means it preserves identity elements (by definition) and concatenation, which can be seen from the following calculation: Let a = (a_{1}, a_{2}, …, a_{m}) and a′ = (a′_{1}, a′_{2}, …, a′_{n}) be lists in A^{∗}. Concatenating them gives the list

aa′ = (a_{1}, a_{2}, …, a_{m}, a′_{1}, a′_{2}, …, a′_{n}).

Then

f^{∗}(a)f^{∗}(a′) = f^{∗}(a_{1}, a_{2}, …, a_{m})f^{∗}(a′_{1}, a′_{2}, …, a′_{n})
= (f(a_{1}), f(a_{2}), …, f(a_{m}))(f(a′_{1}), f(a′_{2}), …, f(a′_{n}))
= (f(a_{1}), f(a_{2}), …, f(a_{m}), f(a′_{1}), f(a′_{2}), …, f(a′_{n}))
= f^{∗}(a_{1}, a_{2}, …, a_{m}, a′_{1}, a′_{2}, …, a′_{n})
= f^{∗}(aa′)

Thus any set function between sets induces a monoid homomorphism between the corresponding free monoids. The reader may wish to verify that if f is an isomorphism then so is f^{∗}. The function f^{∗} is called αf in [Backus, 1981a] and in modern functional languages is usually called map f or map list f.

The other important example is a basic construction of number theory.

1.2.17. Remark (The remainder function). The set ℤ of all integers forms a monoid with respect to either addition or multiplication. If k is any positive integer, the set Z_{k} = {0, 1, …, k−1} of remainders of k is also a monoid with respect to addition or multiplication (mod k). Here are more precise definitions.

1.2.18. Definition. Let k be a positive integer and n any integer. Then n mod k is the unique integer r ∈ Z_{k} for which there is an integer q such that n = qk + r and 0 ≤ r < k.

It is not difficult to see that there is indeed a unique integer r with these properties. Define an operation ‘+_{k}’ of addition (mod k) by requiring that r +_{k} s = (r + s) mod k. The operation of addition of the contents of two registers in a microprocessor may be addition (mod k) for k some power of 2 (often complicated by the presence of sign bits).

1.2.19. Proposition. (ℤ_{k}, +_{k}) is a monoid with identity 0.

We also have the following.

1.2.20. Proposition. The function n ↦ (n mod k) is a monoid homomorphism from (ℤ, +) to (Z_{k}, +_{k}): A similar definition and proposition can be given for multiplication.

29.04.04

1.3. Categories.

1.3.1. Definition. A category is a quadruple C = (Ob(C), Mor(C), (μ), (1)) consisting of

(1) a class of objects

A, B, C ∈ Ob(C),

(2) a family of mutually disjoint sets

(Mor_{C}(A, B)|A, B ∈ Ob(C))

whose elements f, g, h … ∈ Mor_{C}(A, B) are called morphisms,

(3) a family of (composition) maps

(μ_{A,B,C} : Mor_{C}(A, B) × Mor_{C}(B, C) ∋ (f, g) ↦ gf ∈ Mor_{C}(A, C)|A, B, C ∈ Ob(C)),

and

(4) a family of elements called identities:

(1_{A} ∈ Mor_{C}(A, A)|A ∈ Ob(C))

satisfying the following axioms - ∀A, B, C, D ∈ Ob(C) ∀f ∈ Mor_{C}(A, B), g ∈ Mor_{C}(B, C), and h ∈ Mor_{C}(C, D) :

h(gf) = (hg)f ∈ Mor_{C}(A, D),
- ∀A, B, C ∈ Ob(C)∀f ∈ Mor_{C}(A, B), g ∈ Mor_{C}(B, C) :
1_{B}f = f and g1_{B} = g.

1.3.2. Remark. Alternative definition (Barr-Wells): Let k > 0. In a graph G, a path from a node A to a node B of length k is a sequence (f_{1}, f_{2}, …, f_{k}; A, B) of (not necessarily distinct) arrows for which

(1) source(f_{k}) = A,

(2) target(f_{i}) = source(f_{i−1}) for i = 2, …, k, and

(3) target(f_{1}) = B. By convention, for each node A there is a unique path of length 0 from A to A that is denoted ( ; A, A). It is called the empty path at A. Observe that if you draw a path as follows:

· →^{f_{k}} · →^{f_{k−1}} ⋯ →^{f_{2}} · →^{f_{1}} ·

with the arrows going from left to right, f_{k} will be on the left and the subscripts will go down from left to right. We do it this way for consistency with composition. For any arrow f : A ⟶ B, (f; A, B) is a path of length 1. Definition: The set of paths of length k in a graph G is denoted G_{k}. In particular, G_{2}, which will be used in the definition of category, is the set of pairs of arrows (f, g; source(g), target(f)) for which the target of g is the source of f. These are called composable pairs of arrows: · →^{g} · →^{f} · . We have now assigned two meanings to G_{0} and G_{1}. This will cause no conflict as G_{1} refers indifferently either to the collection of arrows of G or to the collection of paths of length 1, which is essentially the same thing. Similarly, we use G_{0} to represent either the collection of nodes of G or the collection of empty paths, of which there is one for each node. In each case we are using the same name for two collections that are not the same but are in a natural one to one correspondence. Compare the use of ‘2’ to denote either the integer or the real number. As this last remark suggests, one might want to keep the two meanings of G_{1} separate for purposes of implementing a graph as a data structure. The one to one correspondences mentioned in the preceding paragraph were called ‘natural’. The word is used informally here, but in fact these correspondences are natural in the technical sense. Definition: A category is a graph C together with two functions c : C_{2} ⟶ C_{1} and u : C_{0} ⟶ C_{1} with properties C-1 through C-4 below. (Recall that C_{2} is the set of paths of length 2.) The elements of C_{0} are called objects and those of C_{1} are called arrows. The function c is called composition, and if (f, g; A, C) is a composable pair, c(f, g; A, C) is written gf = g ∘ f and is called the composite of f and g. If A is an object of C , u(A) is denoted 1_{A}, which is called the identity of the object A.

C-1 The source of gf is the source of f and the target of gf is the target of g.

C-2 (hg)f = h(gf) whenever either side is defined.

C-3 The source and target of 1_{A} are both A.

C-4 If f : A ⟶ B, then f1_{A} = 1_{B}f = f. The significance of the fact that the composite c is defined on G_{2} is that gf is defined if and only if the source of g is the target of f. This means that composition is a function whose domain is an equationally defined subset of G_{1} × G_{1}: the equation requires that the source of g equal the target of f. It follows from this and C-1 that in C-2, one side of the equation is defined if and only if the other side is defined. In the category theory literature, 1_{A} is often written just A.

1.3.3. Remark (Terminology). In much of the categorical literature, ‘morphism’ is more common than ‘arrow’. We will normally denote objects of categories by capital letters but nodes of graphs (except when we think of a category as a graph) by lower case letters. Arrows are always lower case. In the computing science literature, the composite g ∘f is sometimes written f; g , a notation suggested by the perception of a typed functional programming language as a category. We have presented the concept of category as a two-sorted data structure; the sorts are the objects and the arrows. Categories are sometimes presented as one-sorted – arrows only. The objects can be recovered from the fact that C-3 and C-4 together characterize 1_{A} (not hard to prove), so that there is a one to one correspondence between the objects and the identity arrows 1_{A}.

1.3.4. Definition. A category is small if its objects and arrows constitute sets; otherwise it is large. A category with the property that Mor_{C}(A, B) is a set for all objects A and B is called locally small. All categories in these notes are locally small.

1.3.5. Remark. The category of sets and functions is an example of a large category. Although one must in principle be wary in dealing with large classes, it is not in practice a problem; category theorists have rarely, if ever, run into set theoretic difficulties.

1.3.6. Definition. For any path (f_{1}, f_{2}, …, f_{n}) in a category C , define f_{1} ∘ f_{2} ∘ … ∘ f_{n} recursively by

f_{1} ∘ f_{2} ∘ … ∘ f_{n} := (f_{1} ∘ f_{2} ∘ … ∘ f_{n−1}) ∘ f_{n}, n > 2.

1.3.7. Proposition (The general associative law.). For any path (f_{1}, f_{2}, …, f_{n}) in a category C and any integer k with 1 < k < n,

(f_{1} ∘ … ∘ f_{k}) ∘ (f_{k+1} ∘ … ∘ f_{n}) = f_{1} ∘ … ∘ f_{n}.

In other words, you can unambiguously drop the parentheses.

In this proposition, the notation f_{k+1} ∘ … ∘ f_{n} when k = n − 1 means simply f_{n}. This is a standard fact for associative binary operations (see [Jacobson, 1974], Section 1.4) and can be proved in exactly the same way for categories.

1.3.8. Examples. (1) Degenerate categories such as:

• Sets X – i.e. X is the class of objects and all arrows are identities.

• Monoids M – any monoid M determines a category C(M).

CM-1 C(M) has one object, which we will denote ∗, ∗ can be chosen arbitrarily.

A simple uniform choice is to take ∗ = M. CM-2 The arrows of C(M) are the elements of M with ∗ as source and target. CM-3 Composition is the binary operation of M. Thus a category can be regarded as a generalized monoid, or a ‘monoid with many objects’. This point of view has not been as fruitful in mathematics as the perception of a category as a generalized poset. It does have some applications in computing science.

• Preorders – any preorder (P, ≤) determines a category C(P). The class of objects of C(P) is the set P. There is exactly one arrow between x ∈ P and y ∈ P if and only if x ≤ y (otherwise there is no arrow). So there is at most one arrow between any two objects (see 1.3.8(11)).

Many categorists define a monoid to be a category with one object and a preordered set to be a category in which every hom set is either empty or a singleton.

(2) Categories determined by graphs:

• 0 – the category with empty class of objects (and no morphisms).

• 1 – the category with exactly one object and exactly one morphism (the identity of the object).

• 2 = (· ⟶ ·) – the category with two objects and one arrow between them. Together with the identity arrows there are 3 arrows. This can be represented by the category C(S, α) for S = {C, D} and α = {⟨C, C⟩, ⟨C, D⟩, ⟨D, D⟩}.

• ω – the category with a countably infinite number of objects and ascending arrows (succ) between them.

• Categories freely generated by directed graphs G.

(3) The opposite category C^{op} obtained by reversing the arrows of a given category C, while keeping the same objects.

(4) Set – the category of (small) sets and functions; composition is the usual function composition (as well as in the remaining examples). Note that type matters: the identity on the natural numbers is a different function from the inclusion of the natural numbers into the integers.

(5) Set_{∗} – pointed sets (i.e. sets with a selected base-point) and functions preserving the base point.

(6) A partial function from a set S to a set T is a function with domain S_{0} and codomain T, where S_{0} is some subset of S. The category Pfn of sets and partial functions has all sets as objects and all partial functions as arrows. If f : S ⟶ T and g : T ⟶ V are partial functions with f defined on S_{0} ⊆ S and g defined on T_{0} ⊆ T, the composite g ∘ f : S ⟶ V is the partial function from S to V defined on the subset S_{0} ∩ f^{−1}(T_{0}) of S by the requirement (g ∘ f)(x) = g(f(x)).

(7) Δ – finite ordinals (the ordinal n is the totally ordered set of all the preceding ordinals {0, 1, …, n − 1} and 0 is the empty set) and monotone or order preserving functions. This category is called the simplicial category.

(8) Fin – finite sets and functions. 30.4.04 (9) Let α be a relation from a set S to a set T and β a relation from T to U. The

composite β ∘ α is the relation from S to U defined as follows: If x ∈ S and z ∈ U then (x, z) ∈ β ∘ α if and only if there is an element y ∈ T for which (x, y) ∈ α and (y, z) ∈ β. With this definition of composition, the category Rel of sets and relations has sets as objects and relations as arrows. The identity for a set S is the diagonal relation Δ_{S} = {(x, x)|x ∈ A}.

In order to make the morphism sets disjoint, one has to take monads (α, S, T) for the morphisms, where α ⊆ S × T.

(10) Other examples of categories whose objects are sets are the category of sets and injective functions and the category of sets and surjective functions.

(11) Preordered sets: If S is a set, a subset α ⊂ S ×S is called a binary relation on S. It is often convenient to write xαy as shorthand for (x, y) ∈ α. We say that α is reflexive if xαx for all x ∈ S and transitive if xαy and yαz implies xαz for all x, y, z ∈ S.

A set S with a reflexive, transitive relation α on it is a structure (S; α), i.e. a preordered set determines a category C(S; α) defined as follows.

CO-1 The objects of C(S, α) are the elements of S. CO-2 If x, y ∈ S and xαy, then C(S, α) has exactly one arrow from x to y, denoted

(y, x). (The reader might have expected (x, y) here. This choice of notation fits better with the right-to-left composition that we use. Note that the domain of (y, x) is x and the codomain is y.)

CO-3 If x is not related by α to y there is no arrow from x to y. The identity arrows of C(S, α) are those of the form (x, x); they belong to α because it is reflexive. The transitive property of α is needed to ensure the existence of the composite described in 2.1.3, so that (z, y) ∘ (y, x) = (z, x).

(12) Preord – preorders and monotone functions: The objects of this category are preordered sets. If (S, α) and (T, β) are preordered sets, a function f : S ⟶ T is monotone if whenever xαy in S, f(x)βf(y) in T. If we write, as usual, x ≤ y for (x, y) ∈ α and use the same for β: u ≤ v if (u, v) ∈ β, then the condition for a monotone function is

∀x, y ∈ S : x ≤ y ⟹ f(x) ≤ f(y).

The identity function on a preordered set is clearly monotone, and the composite of two monotone functions is easily seen to be monotone, so that preordered sets with monotone functions form a category.

A variation on this is to consider only strictly monotone functions, which are functions f with the property that if

xαy and x ≠ y then f(x)βf(y) and f(x) ≠ f(y).

We saw how a single preordered set is a category. Now we are considering the category of preordered sets.

We must give a few words of warning on terminology. The usual word in mathematical texts for what we have called ‘monotone’ is ‘increasing’ or ‘monotonically increasing’. The word ‘monotone’ is used for a function that either preserves or reverses the order relation. That is, in mathematical texts a function f : (X, α) ⟶ (T, β) is also called monotone if whenever xαy in S, f(y)βf(x) in T.

(13) Poset – partial orders and monotone functions: A preordered set (S, α) for which α is antisymmetric (that is xαy and yαx imply x = y) is called a partially ordered set or poset. Two examples of posets are (R, ≤), the real numbers with the usual ordering, and for any set S, the poset (P(S), ⊆), the set of subsets of S with inclusion as ordering. The posets and the monotone functions form the category Poset.

(14) Mon – monoids and monoid homomorphisms.

(15) Grp – groups and group homomorphisms.

(16) SL – semi-lattices and join-preserving functions.

(17) Top – topological spaces and continuous functions.

(18) Met – metric spaces and non-expansive (contracting) functions.

(19) CMet: complete metric spaces and non-expansive functions.

(20) Vec – vector spaces,

(21) Ab – Abelian groups,

(22) SGrp – semigroups:

(23) Ban – Banach spaces and linear functions,

(24) Ban_{1} – Banach spaces and linear functions of norm ≤ 1,

(25) Mf – manifolds (topological or differential), (26) Grf – graphs: The category of graphs has graphs as objects and homomorphisms of

graphs as arrows. It is denoted Grf.

The identity homomorphism id_{G} is the identity function for both nodes and arrows. Let us check that the composite of graph homomorphisms is a graph homomorphism (identities are easy). Suppose ϕ : G ⟶ H and ψ : H ⟶ K are graph homomorphisms, and suppose that u : m ⟶ n in G . Then by definition ϕ_{E}(u) : ϕ_{V} (m) ⟶ ϕ_{V} (n) in H , and so by definition

ψ_{E}(ϕ_{E}(u)) : ψ_{V} (ϕ_{V} (m)) ⟶ ψ_{V} (ϕ_{V} (n)) in K.

Hence ψ ∘ ϕ is a graph homomorphism.

(27) An example from computer science:

A functional programming language has: FPL-1 Primitive data types, given in the language. FPL-2 Constants of each type. FPL-3 Operations, which are functions between the types. FPL-4 Constructors, which can be applied to data types and operations to produce

derived data types and operations of the language. The language consists of the set of all operations and types derivable from the

primitive data types and primitive operations. The word ‘primitive’ means given in the definition of the language rather than constructed by a constructor. Some authors use the word ‘constructor’ for the primitive operations.

Given a functional programming language L, there’s an associated category, where the objects are the data types of L, and the arrows are the computable functions of L (“processes”, “procedures”, “programs”). The composition of two such programs X →^{f} Y ⟶^{g!} Z is given by applying g to the output of f, sometimes also written g ∘ f = f; g. The identity is the “do nothing” program. This example is closely related to the notion of “cartesian closed category” to be considered later.

As a concrete example, we will suppose we have a simple such language with three data types, NAT (natural numbers), BOOLEAN (true or false) and CHAR (characters). We give a description of its operations in categorical style.

(i) NAT should have a constant 0 : 1 ⟶ NAT and an operation succ : NAT ⟶ NAT.

(ii) There should be two constants true; false : 1 ⟶ BOOLEAN and an opera-

tion ¬ subject to the equations ¬ ∘ true = false and ¬ ∘ false = true. (iii) CHAR should have one constant c : 1 ⟶ CHAR for each desired character c. (iv) There should be two type conversion operations ord : CHAR ⟶ NAT and

chr : NAT ⟶ CHAR. These are subject to the equation chr ∘ ord = idCHAR. (You can think of chr as operating modulo the number of characters, so that it is defined on all natural numbers.)

An example program is the arrow ‘next’ defined to be the composite chr ∘ succ ∘ ord : CHAR ⟶ CHAR.

It calculates the next character in order. This arrow ‘next’ is an arrow in the category representing the language, and so is any other composite of a sequence of operations. The objects of the category C(L) of this language are the types NAT, BOOLEAN, CHAR and 1. Observe that typing is a natural part of the syntax in this approach.

The arrows of C(L) consist of all programs, with two programs being identified if they must be the same because of the equations. For example, the arrow

chr ∘ succ ∘ ord : CHAR ⟶ CHAR

just mentioned and the arrow

chr ∘ succ ∘ ord ∘ chr ∘ ord : CHAR ⟶ CHAR

must be the same because of the equation in (iv).

Observe that NAT has constants succ ∘ succ ∘ … ∘ succ ∘ 0 where succ occurs zero or more times.

Composition in the category is composition of programs. Note that for composition to be well defined, if two composites of primitive operations are equal, then their composites with any other program must be equal. For example, we must have

ord ∘ (chr ∘ succ ∘ ord) = ord ∘ (chr ∘ succ ∘ ord ∘ chr ∘ ord)

as arrows from CHAR to NAT.

1.4. Constructions on categories. If you are familiar with some branch of abstract algebra (for example the theory of semigroups, groups or rings) then you know that given two structures of a given type (e.g., two semigroups), you can construct a ‘direct product’ structure, defining the operations coordinatewise. Also, a structure may have substructures, which are subsets closed under the operations, and quotient structures, formed from equivalence classes modulo a congruence relation. Another construction that is possible in many cases is the formation of a ‘free’ structure of the given type for a given set. All these constructions can be performed for categories. We will outline the constructions here, except for quotients. We will also describe the construction of the slice category, which does not quite correspond to anything in abstract algebra (although it is akin to the adjunction of a constant to a logical theory). You do not need to be familiar with the constructions in other branches of abstract algebra, since they are all defined from scratch here.

1.4.1. Slice categories.

1.4.1. Definition. If C is a category and A any object of C , the slice category C/A is described this way: SC-1 An object of C/A is an arrow f : C ⟶ A of C for some object C. SC-2 An arrow of C/A from f : C ⟶ A to f′ : C′ ⟶ A is an arrow h : C ⟶ C′ with the

property that f = f′ ∘ h. SC-3 The composite of h : f ⟶ f′ and h′ : f′ ⟶ f′′ is h′ ∘ h.

It is necessary to show that h′ ∘ h, as defined in SC-2, satisfies the requirements of being an arrow from f to f′′. Let h : f ⟶ f′ and h′ : f′ ⟶ f′′. This means f′ ∘h = f and f′′ ∘h′ = f′. To show that h′ ∘ h : f ⟶ f′′ is an arrow of C/A, we must show that f′′ ∘ (h′ ∘ h) = f. That follows from this calculation:

f′′ ∘ (h′ ∘ h) = (f′′ ∘ h′) ∘ h = f′ ∘ h = f.

The usual notation for arrows in C/A is deficient: the same arrow h can satisfy f = f′ ∘ h and g = g′ ∘ h with f′ ≠ g′ or f ≠ g (and then f′ ≠ g′). Then h : f ⟶ f′ and h : g ⟶ g′ are different arrows of C/A

[figure: B; C; h; A; f; f′; and; B; C; h; A.; g; g′]

Indeed h : (B, f) ⟶ (C, f′) and h : (B, g) ⟶ (C, g′), or h ∈ Mor_{C/A}((B, f), (C, f′)) and h ∈ Mor_{C/A}((B, g), (C, g′)). But Mor_{C/A}((B, f), (C, f′)) ∩ Mor_{C/A}((B, g), (C, g′)) = ∅ so that the two morphisms, both denoted h, are different. Thus one often says, that an “arrow” in the slice category is a “commutative diagram” as above.

1.4.2. Example. Let (P, α) be a poset and let C(P) be the corresponding category as in 1.3.8(11). For an element x ∈ P, the slice category C(P)/x is the category corresponding to the set of elements greater than or equal to x. The dual notion of coslice, i.e. the category A\C of arrows f : A ⟶ C for some C in C, gives the set of elements less than or equal to a given element.

1.4.3. Remark. The importance of slice categories comes in part with their connection with indexing. An S-indexed set or graded set is a set X together with a function τ : X ⟶ S. If x ∈ X and τ(x) = s then we say x is of type s, and we also refer to X as a typed set. The terminology ‘S-indexed set’ is that used by category theorists. Many mathematicians would cast the discussion in terms of the collection (τ^{−1}(s)|s ∈ S) of subsets of X, which would be called a family of sets indexed by S.

1.4.4. Example. The set G = G_{0} ∪ G_{1} of objects and arrows of a graph G is an example of a typed set, typed by the function τ : G ⟶ {0, 1} that takes a node to 0 and an arrow to 1. Note that this depends on the fact that a node is not an arrow: G_{0} and G_{1} are disjoint.

1.4.5. Remark (Indexed functions). A function from a set X typed by S to a set X′ typed by the same set S that preserves the typing (takes an element of type s to an element of type s) is exactly an arrow of the slice category Set /S. Such a function is called an indexed function, typed function, or graded function. It has been fruitful for category theorists to pursue this analogy by thinking of objects of any slice category C/A as objects of C indexed by A.

1.4.6. Example. A graph homomorphism f : G ⟶ H corresponds to a typed function according to the construction in Example 1.4.4. However, there are typed functions between graphs that are not graph homomorphisms, for example the function from the graph in 1.1.3(1)

[figure: b; 1; 2; c; a]

to the graph in 1.1.3(4)

[figure: 1; n; 0; succ]

defined by

1 ↦ 1, 2 ↦ n, a ↦ 0, b ↦ 0, c ↦ succ.

This is not a graph homomorphism because it does not preserve source and target.

1.4.2. Subcategories.

1.4.7. Definition. A subcategory D of a category C is a category for which:

S-1 All the objects of D are objects of C and all the arrows of D are arrows of C (in other

words, D_{0} ⊆ C_{0} and D_{1} ⊆ C_{1}). S-2 The source and target of an arrow of D are the same as its source and target in C (in

other words, the source and target maps for D are the restrictions of those for C). It follows that for any objects A and B of D, Mor_{D}(A, B) ⊆ Mor_{C}(A, B).

S-3 If A is an object of D then its identity arrow 1_{A} in C is in D.

S-4 If f : A ⟶ B and g : B ⟶ C in D, then the composite g ∘ f (in C) is in D and is the composite in D.

1.4.8. Examples. As an example, the category Fin of finite sets and all functions between them is a subcategory of Set, and in turn Set is a subcategory of the category of sets and partial functions between sets (see 2.1.12 and 2.1.13). These examples illustrate two phenomena:

(i) If A and B are finite sets, then Mor_{Fin}(A, B) = Mor_{Set}(A, B). In other words, every arrow of Set between objects of Fin is an arrow of Fin.

(ii) The category of sets and the category of sets and partial functions, on the other hand,

have exactly the same objects.

The phenomenon of (i) does not occur here: there are generally many more partial functions between two sets than there are full functions.

Example (i) motivates the following definition.

1.4.9. Definition. If D is a subcategory of C and for every pair of objects A, B of D, Mor_{D}(A, B) = Mor_{C}(A, B), then D is a full subcategory of C .

Thus Fin is a full subcategory of Set but Set is not a full subcategory of the category of sets and partial functions. Example 1.4.8(ii) also motivates a (less useful) definition, as follows.

1.4.10. Definition. If D is a subcategory of C with the same objects, then D is a wide subcategory of C.

Thus in the case of a wide subcategory, only the arrows are different from those of the larger category. In 2.4.9 we provide an improvement on this concept. As an example, Set is a wide subcategory of the category Pfn of sets and partial functions.

1.4.11. Example. Among all the objects of the category of semigroups are the monoids, and among all the semigroup homomorphisms between two monoids are those that preserve the identity. Thus the category of monoids is a subcategory of the category of semigroups that is neither wide nor full (see ??). As it stands, being a subcategory requires the objects and arrows of the subcategory to be identical with some of the objects and arrows of the category containing it. This requires an uncategorical emphasis on what something is instead of on the specification it satisfies.

06.05.04

1.4.3. The product of categories.

1.4.12. Definition. If C and D are categories, the product C×D is the category whose objects are all ordered pairs (C, D) with C an object of C and D an object of D, and in which an arrow (f, g) : (C, D) ⟶ (C′, D′) is a pair of arrows f : C ⟶ C′ in C and g : D ⟶ D′ in D. The identity of (C, D) is (1_{C}, 1_{D}). If (f′, g′) : (C′, D′) ⟶ (C′′, D′′) is another arrow, then the composite is defined by

(f′, g′) ∘ (f, g) = (f′ ∘ f, g′ ∘ g) : (C, D) ⟶ (C′′, D′).

1.4.4. The dual of a category. 1.4.13. Definition. The dual or opposite C^{op} of a category C is defined by:

D-1 The objects and arrows of C^{op} are the objects and arrows of C .

D-2 If f : A ⟶ B in C, then f : B ⟶ A in C^{op}, i.e. Mor_{C^{op}}(B, A) := Mor_{C}(A, B).

D-3 If h = g ∘ f in C , then h = f ∘ g in C^{op}. The meaning of D-2 is that source and target have been reversed. It is easy to see that the identity arrows have to be the same in the two categories C and C^{op} and that C-1 through C-4 of definition 1.3.1 hold, so that C^{op} is a category. 1.4.14. Example. If M is a monoid, then the opposite of the category C(M) is the category determined by a monoid M^{op}, if xy = z in M, then yx = z in M^{op}. (Hence if M is commutative then C(M) is its own dual. Similar remarks may be made about the opposite of the category C(P) determined by a poset P. The opposite of the poset (ℤ, ≤), for example, is (ℤ, ≥). Both the construction of the product of two categories and the construction of the dual of a category are purely formal constructions. Even though the original categories may have, for example, structure-preserving functions of some kind as arrows, the arrows in the product category are simply pairs of arrows of the original categories. Consider Set, for example. Let A be the set of letters of the English alphabet. The function v : A ⟶ {0, 1} that takes consonants to 0 and vowels to 1 is an arrow of Set. Then the arrow (1_{A}, v) : (A, A) ⟶ (A, {0, 1}) of Set × Set is not a function, not even a function of two variables, since there are no reasonable elements in (A, A). It is merely the arrow of a product category and as such is an ordered pair of functions. A similar remark applies to duals. In Set^{op}, v is an arrow from {0, 1} to A. And that is all it is. It is in particular not a function from {0, 1} to A. Nevertheless, it is possible in some cases to prove that the dual of a familiar category is essentially the same as some other familiar category. One such category is Fin, which is equivalent to the opposite of the category of finite Boolean algebras. The product of categories is a formal way to make constructions dependent on more than one variable. The major use we make of the concept of dual is that many of the definitions we make have another meaning when applied to the dual of a category that is often of independent interest. The phrase dual concept or dual notion is often used to refer to a concept or notion applied in the dual category.

1.4.5. The free category generated by a graph. 1.4.15. Definition. For any given graph G there is a category F(G) whose objects are the nodes of G and whose arrows are the paths in G. Composition is defined by the formula

(f_{1}, f_{2}, …, f_{k}) ∘ (f_{k+1}, …, f_{n}) = (f_{1}, f_{2}, …, f_{n}).

This composition is associative, and for each object A, 1_{A} is the empty path from A to A. The category F(G) is called the free category generated by the graph G. It is also called the path category of G.

1.4.16. Examples. – The free category generated by the graph with one node and no arrows is the category with one object and only the identity arrow, which is the empty path.

– The free category generated by the graph with one node and one loop on the node is the free monoid with one generator (Kleene closure of a one-letter alphabet); this is isomorphic with the nonnegative integers with + as operation.

– The free category generated by the graph in Example 1.1.3(4) has the following arrows (a) An arrow 1_{1} : 1 ⟶ 1.

(b) For each nonnegative integer k, the arrow succ^{k} : n ⟶ n. This is the path (succ, succ, …, sucsucc) (k occurrences of succ). This includes k = 0 which gives 1_{n}.

(c) For each nonnegative integer k, the arrow succ^{k} ∘ 0 : 1 ⟶ n. Here k = 0 gives 0 : 1 ⟶ n. Composition obeys the rule succ^{k} ∘ succ^{m} = succ^{k+m}.

It is useful to regard the free category generated by any graph as analogous to the Kleene closure (free monoid) generated by a set (as in 1.2.5). The paths in the free category correspond to the strings in the Kleene closure. The difference is that you can concatenate any symbols together to get a string, but arrows can be strung together only head to tail, thus taking into account the typing. In ?? we give a precise technical meaning to the word ‘free’.

1.5. Functors. A functor F from a category C to a category D is a graph homomorphism which preserves identities and composition. It plays the same role as monoid homomorphisms for monoids and monotone maps for posets: it preserves the structure that a category has. Functors have another significance, however: since one sort of thing a category can be is a mathematical workspace (see Introduction), many of the most useful functors used by mathematicians are transformations from one type of mathematics to another. Less obvious, but perhaps more important is the fact that many categories that are mathematically interesting appear as categories whose objects are a natural class of functors into the category of sets. A functor is a structure-preserving map between categories, in the same way that a homomorphism is a structure-preserving map between graphs or monoids. Here is the formal definition.

1.5.1. Definition. Let C = (Ob(C), Mor(C), (μ), (1)) and D = (Ob(D), Mor(D), (μ), (1)) be categories. Let F consist of

(1) a map F : Ob(C) ⟶ Ob(D) and a

(2) a family of maps

(Mor_{C}(A, B) ∋ f ↦ F(f) ∈ Mor_{D}(F(A), F(B)) | A, B ∈ Ob(C)).

F is called a covariant functor if

• ∀A ∈ Ob(C) :

F(1_{A}) = 1_{F(A)};

• ∀A, B, C ∈ Ob(C), ∀f ∈ Mor_{C}(A, B), g ∈ Mor_{C}(B, C) :

F(gf) = F(g)F(f).

An equivalent definition is:

1.5.2. Definition. A functor F : C ⟶ D is a pair of functions F_{0} : C_{0} ⟶ D_{0} and F_{1} : C_{1} ⟶ D_{1} for which F-1 If f : A ⟶ B in C , then F_{1}(f) : F_{0}(A) ⟶ F_{0}(B) in D. F-2 For any object A of C , F_{1}(1_{A}) = 1_{F_{0}(A)}. F-3 If g∘f is defined in C , then F_{1}(g)∘F_{1}(f) is defined in D and F_{1}(g∘f) = F_{1}(g)∘F_{1}(f).

By F-1, a functor is in particular a homomorphism of graphs. Following the practice for graph homomorphisms, the notation is customarily overloaded: if A is an object, F(A) = F_{0}(A) is an object, and if f is an arrow, F(f) = F_{1}(f) is an arrow. The notation for the constituents F_{0} : C_{0} ⟶ D_{0} and F_{1} : C_{1} ⟶ D_{1} is not standard, and we will use it only for emphasis.

1.5.3. Example. It is easy to see that a monoid homomorphism f : M ⟶ N determines a functor from C(M) to C(N) as defined in 1.3.8(1). On objects, a homomorphism f must take the single object of C(M) to the single object of C(N), and F-1 is trivially verified since all arrows in C(M) have the same domain and codomain and similarly for C(N). Then F-2 and F-3 say precisely that f is a monoid homomorphism. Conversely, every functor is determined in this way by a monoid homomorphism.

1.5.4. Example. Let us see what a functor from C(S, α) to C(T, β) must be when (S, α) and (T, β) are posets as in 1.3.8(1). It is suggestive to write both relations α and β as ‘≤’ and the posets simply as S and T. Then there is exactly one arrow from x to y in S (or in T) if and only if x ≤ y; otherwise there are no arrows from x to y. Let f : S ⟶ T be the functor. F-1 says if there is an arrow from x to y, then there is an arrow from f(x) to f(y); in other words, if x ≤ y then f(x) ≤ f(y). Thus f is a monotone map. F-2 and F-3 impose no additional conditions on f because they each assert the equality of two specified arrows between two specified objects and in a poset as category all arrows between two objects are equal.

1.5.5. Remark (The category of categories). The category Cat has all small categories as objects and all functors between such categories as arrows. The composite of functors is their composite as graph homomorphisms: if F : C ⟶ D and G : D ⟶ E, then G ∘ F : C ⟶ E satisfies G ∘ F(C) = G(F(C)) for any object C of C , and G ∘ F(f) = G(F(f)) for any arrow f of C. Thus (G ∘ F)_{i} = G_{i} ∘ F_{i} for i = 0, 1. We note that the composition circle is usually omitted when composing functors so that we write GF(C) = G(F(C)). It is sometimes convenient to refer to a category CAT which has all small categories and ordinary large categories as objects, and functors between them. Since trying to have CAT be an object of itself would raise delicate foundational questions, we do not attempt here a formal definition of CAT.

1.5.6. Example. If C is a category, the functor P_{1} : C × C ⟶ C which takes an object (C, D) to C and an arrow (f, g) : (C, D) ⟶ (C′, D′) to f is called the first projection. There is an analogous second projection functor P_{2} taking an object or arrow to its second coordinate.

1.5.7. Example. Let 2 + 2 be the category that can be pictured as

0 ⟶ 1 1′ ⟶ 2

with no other nonidentity arrows, and the category 3 the one that looks like

[figure: 0; 1; 2]

Define the functor F : 2 + 2 ⟶ 3 to take 0 to 0, 1 and 1’ to 1, and 2 to 2. Then what it does on arrows is forced.

Note that the image of F includes all of 3 except the composite arrow from 0 ⟶ 2. This example shows that the image of a functor need not be a subcategory of the codomain category.

1.5.8. Example. The inclusion map of a subcategory is a functor. The categorical point of view does not require that the object and arrows of a subcategory actually be objects and arrows of the bigger category, only that there be an injective identification of objects or morphisms of one category with the objects or morphisms of the other. For example, Set is a subcategory of Rel: the functor takes every set to itself and each function f : S ⟶ T to its graph {(s, t)|t = f(s)}, which is indeed a relation from S to T. This approach has the strange result that two different categories can each be regarded as subcategories of the other one. Observe that the category Ri of rings is not a subcategory of the category Ab of abelian group, although each ring is also an abelian group (under the addition) and every homomorphism of rings is also a homomorphism of abelian groups. There can be two nonisomorphic rings, that have the same additive abelian group.

1.6. Special types of functors.

1.6.1. Underlying functors.

1.6.1. Example. Forgetting some of the structure in a category of structures and structurepreserving functions gives a functor called an underlying functor or forgetful functor. The functor U : Mon ⟶ Sem which embeds the category of monoids into the category of semigroups by forgetting that a monoid has an identity is an example of an underlying functor. Another example is the functor which forgets all the structure of a semigroup. This is a functor U : Sem ⟶ Set. There are lots of semigroups with the same set of elements; for example, the set {0, 1, 2} is a semigroup on addition (mod 3) and also a different semigroup on multiplication (mod 3). The functor U applied to these two different semigroups gives the same set, so U is not injective on objects, in contrast to the forgetful functor from monoids to semigroups. We will not give a formal definition of underlying functor. It is reasonable to expect any underlying functor U to be faithful, i.e. injective on the morphism sets, and that if f is an isomorphism and U(f) is an identity arrow then f is an identity arrow.

1.6.2. Example. A small graph has two underlying sets: its set of nodes and its set of arrows. Thus there is an underlying functor U : Grf ⟶ Set × Set for which for a graph G , U(G) = (G_{0}, G_{1}), an arrowset functor A : Grf ⟶ Set which takes a graph to its set of arrows and a graph homomorphism to the corresponding function from arrows to arrows, and a similarly defined nodeset functor N : Grf ⟶ Set which takes a graph to its set of nodes.

1.6.3. Example. If you forget you can compose arrows in a category and you forget which arrows are the identities, then you have remembered only that the category is a graph. This gives an underlying functor U : Cat ⟶ Grf, since every functor is a graph homomorphism although not vice versa. As for graphs, there are also set-of-objects and set-of-arrows functors O : Cat ⟶ Set and A : Cat ⟶ Set which take a category to its set of objects and set of arrows respectively, and a functor to the appropriate set map.

7.5.04 1.6.4. Example. In 1.4.1, we described the notion of a slice category C/A based on a category C and an object A. An object is an arrow B ⟶ A and an arrow from f : B ⟶ A to g : C ⟶ A is an arrow h : B ⟶ C for which g ∘ h = f. There is a functor U : C/A ⟶ C that takes the object f : B ⟶ A to B and the arrow h from B ⟶ A to C ⟶ A to h : B ⟶ C. This is called the underlying functor of the slice. In the case that C = Set, an object T ⟶ S of Set /S for some set S is an S-indexed object, and the effect of the underlying functor is to forget the indexing.

1.6.2. Free functors.

1.6.5. Example. The free monoid functor from Set to the category of monoids takes a set A to the free monoid F (A), which is the Kleene closure A^{∗} with concatenation as operation (see 1.2.5), and a function f : A ⟶ B to the function F (f) = f^{∗} : F (A) ⟶ F (B) defined in 1.2.16. To see that the free monoid functor is indeed a functor it is necessary to show that if f : A ⟶ B and g : B ⟶ C, then F (g ∘ f) : F (A) ⟶ F (C) is the same as F (g) ∘ F (f), which is immediate from the definition, and that it preserves identity arrows, which is also immediate. The Kleene closure is itself a functor from Set to Set, taking A to A^{∗} and f to f^{∗}. It is the composite U ∘ F of the underlying functor U : Mon ⟶ Set and the free functor F : Set ⟶ Mon, but of course it can be defined independently of U and F.

1.6.6. Example. The free category on a graph is also the object part of a functor F : Grf ⟶ Cat. What it does to a graph is described in 1.4.15. Suppose φ : G ⟶ H is a graph homomorphism. The objects of the free category on a graph are the nodes of the graph, so it is reasonable to define F (φ)_{0} = φ_{0}. Now suppose (f_{n}, f_{n−1}, …, f_{1}) is a path, that is, an arrow, in F (G). Since functors preserve domain and codomain, we can define F (φ)_{1}(f_{n}, f_{n−1}, …, f_{1}) to be (φ_{1}(f_{n}), φ_{1}(f_{n−1}), …, φ_{1}(f_{1})) and know we get a path in F (H). That F preserves composition of paths is also clear.

1.6.7. Remark (The map-lifting property). The free category functor F : Grf ⟶ Cat and also other free functors, such as the free monoid functor 1.6.5, have a map lifting property called its universal mapping property which will be seen as the defining property of freeness. We will describe the property for free categories since we use it later. Let G be a graph and F (G) be the free category generated by G . There is a graph homomorphism with the special name ηG : G ⟶ U(F (G)) which includes a graph G into U(F (G)), the underlying graph of the free category F (G). The map (ηG)_{0} is the identity, since the objects of F (G) are the nodes of G. For an arrow f of G, (ηG)_{1}(f) is the path (f) of length one. This is an inclusion arrow in the generalized categorical sense, since f and (f) are really two distinct entities.

1.6.8. Proposition. Let G be a graph and C a category. Then for every graph homomorphism h : G ⟶ U(C), there is a unique functor ĥ : F (G) ⟶ C with the property that U(ĥ) ∘ ηG = h.

Proof. If () is the empty path at an object a, we set ĥ() = 1_{a}. For an object a of F (G) (that is, node of G), define ĥ(a) = h(a). And for a path (a_{n}, a_{n−1}, …, a_{1}), ĥ is ‘map h’:

ĥ(a_{n}, a_{n−1}, …, a_{1}) = (h(a_{n}), h(a_{n−1}), …, h(a_{1})).

As noted in 1.1.1, there is a unique empty path for each node a of G. Composing the empty path at a with any path p from a to b gives p again, and similarly on the other side. □

1.6.3. Powerset functors. Any set S has a powerset PS, the set of all subsets of S. There are three different functors F for which F_{0} takes a set to its powerset; they differ on what they do to arrows. One of them is fundamental in topos theory; that one we single out to be called the powerset functor. If f : A ⟶ B is any set function and C is a subset of B, then the inverse image of C, denoted f^{−1}(C), is the set of elements of A which f takes into C: f^{−1}(C) = {a ∈ A|f(a) ∈ C}. Thus f^{−1} is a function from PB to PA. Note that for a bijection f, the symbol f^{−1} is also used to denote the inverse function. Context makes it clear which is meant, since the input to the inverse image function must be a subset of the codomain of f, whereas the input to the actual inverse of a bijection must be an element of the codomain.

1.6.9. Definition. The powerset functor P : Set^{op} ⟶ Set takes a set S to the powerset PS, and a set function f : A ⟶ B (that is, an arrow from B to A in Set^{op}) to the inverse image function f^{−1} : PB ⟶ PA. Although we will continue to use the notation f^{−1}, it is denoted f^{∗} in much of the categorical literature. To check that P is a functor requires showing that 1_{A}^{−1} = 1_{PA} and that if g : B ⟶ C, then (g ∘ f)^{−1} = f^{−1} ∘ g^{−1}, where both compositions take place in Set.

1.6.10. Definition. A functor F : C^{op} ⟶ D is also called a contravariant functor from C to D.

As illustrated in the preceding definition, the functor is often defined in terms of arrows of C rather than of arrows of C^{op}. Opposite categories are most commonly used to provide a way of talking about contravariant functors as ordinary (covariant) functors: the opposite

13.05.04 category in this situation is a purely formal construction of no independent interest.

1.6.11. Remark. The other two functors which take a set to its powerset are both covariant. The direct or existential image functor takes f : A ⟶ B to the function f_{∗} : PA ⟶ PB, where f_{∗}(A_{0}) = {f(x)|x ∈ A_{0}}, the set of values of f on A_{0}. The universal image functor takes A_{0} to those values of f which come only from A_{0}: formally, it takes f : A ⟶ B to f_{!} : PA ⟶ PB, with

f_{!}(A_{0}) = {y ∈ B|f(x) = y implies x ∈ A_{0}} = {y ∈ B|f^{−1}({y}) ⊆ A_{0}}.

1.6.4. Hom functors or Mor functors. Let C be a category with an object C and an arrow f : A ⟶ B. f induces a set function Mor(A, f) : Mor(A, B) ⟶ Mor(A, C) defined by composing by f on the left: for any g ∈ Mor(A, B), that is, for any g : A ⟶ B, Mor(A, f)(g) = f ∘ g, which does indeed go from A to C. Similarly, for any object D, f : B ⟶ C induces a set function Mor(f, D) : Mor(C, D) ⟶ Mor(B, D) (note the reversal) by requiring that Mor(f, D)(h) = h ∘ f for h ∈ Mor(C, D).

1.6.12. Definition. For a given object C the covariant Mor functor Mor(C, -) : C ⟶ Set is defined as follows:

HF-1 Mor(C, -)(A) := Mor(C, A) for each object A of C; HF-2 Mor(C, -)(f) := Mor(C, f) : Mor(C, A) ⟶ Mor(C, B) for f : A ⟶ B.

The following calculations show that Mor(C, -) is a functor. For an object A, Mor(C, 1_{A}) : Mor(C, A) ⟶ Mor(C, A) takes an arrow f : C ⟶ A to 1_{A} ∘ f = f; hence Mor(C, 1_{A}) = 1_{Mor(C,A)}. Now suppose f : A ⟶ B and g : B ⟶ D. Then for any arrow k : C ⟶ A,

( Mor(C, g) ∘ Mor(C, f))(k) = Mor(C, g)( Mor(C, f)(k))
= Mor(C, g)(f ∘ k)
= g ∘ (f ∘ k)
= (g ∘ f) ∘ k
= Mor(C, g ∘ f)(k).

There is a distinct covariant Mor functor Mor(C, -) for each object C. In this expression, C is a parameter for a family of functors. The argument of each of these functors is indicated by the dash. An analogous definition in calculus would be to define the function which raises a real number to the nth power as f(-) = (-)^{n} (here n is the parameter). One difference in the Mor functor case is that the Mor functor is overloaded and so has to be defined on two different kinds of things: objects and arrows.

1.6.13. Definition. For a given object D, the contravariant mor functor Mor(-, D) : C^{op} ⟶ Set is defined for each object A by Mor(-, D)(A) := Mor(A, D) and for each arrow f : A ⟶ B, Mor(-, D)(f) := Mor(f, D) : Mor(B, D) ⟶ Mor(A, D). Thus if g : B ⟶ D, Mor(f, D)(g) = g ∘ f.

1.6.14. Definition. The two-variable Mor functor

Mor(-, -) : C^{op} × C ⟶ Set

takes a pair (C, D) of objects of C to Mor(C, D), and a pair (f, g) of arrows with f : C ⟶ A and g : B ⟶ D to

Mor(f, g) : Mor(A, B) ⟶ Mor(C, D)

where for h : A ⟶ B,

Mor(f, g)(h) = g ∘ h ∘ f

which is indeed an arrow from C to D.

In this case we also use the product of categories as a formal construction to express functors of more than one argument. From the categorical point of view, a functor always has one argument, which as in the present case might well be an object in a product category (an ordered pair).

1.7. Natural transformations. In order to see one of the aims of this section we first introduce natural transformation of functors and study their most elementary properties.

1.7.1. Natural transformations between functors I.

1.7.1. Definition. Let D, E : C ⟶ D be two covariant functors. A natural transformation α : D ⟶ E is given by a family of morphisms α_{A} of D indexed by the objects of C such that: NTF-1 α_{A} : D(A) ⟶ E(A) for each node A of C. NTF-2 For any morphism f : A ⟶ B in C, the diagram

(1)  [figure: D(A); E(A); α_{A}; D(B); E(B); α_{B}; D(f); E(f)]

commutes.

1.7.2. Definition. Let D, E and F be functors from C to D , and α : D ⟶ E and β : E ⟶ F natural transformations. The composite β ∘ α : D ⟶ F is defined componentwise: (β ∘ α)_{A} = β_{A} ∘ α_{A}.

1.7.3. Proposition. The composite of two natural transformations is also a natural transformation.

Proof. The diagram that has to be shown commutative is the outer rectangle of

(2)  [figure: D(A); E(A); α_{A}; F (A); β_{A}; D(B); E(B); α_{B}; F (B); β_{B}; D(f); E(f); F (f)]

for each arrow f : A ⟶ B in C. The rectangle commutes because the two squares do; the squares commute as a consequence of the naturality of α and β. □

1.7.4. Example. Examples for natural transformations – like for functors – are built into the definition of categories. Let f : A ⟶ B be a morphism in a category C. In 1.6.12 we have already studied covariant functors Mor_{C}(A, -), Mor_{C}(B, -) : C ⟶ Set. The morphism f induces a family of maps

Mor_{C}(f, C) : Mor_{C}(B, C) ∋ g ↦ g ∘ f ∈ Mor_{C}(A, C)

which is a natural transformation by Exercise ??.

1.7.5. Definition. A natural transformation α : F ⟶ G : C ⟶ D is called a natural isomorphism if there is a natural transformation β : G ⟶ F which is an inverse to α.

1.7.6. Definition. A functor F : C ⟶ D is an equivalence of categories if there are: E-1 A functor G : D ⟶ C. E-2 A family (u_{C} : C ⟶ G(F (C))|C ∈ Ob(C)) of isomorphisms of C indexed by the

objects of C with the property that for every arrow f : C ⟶ C′ of C, G(F (f)) = u_{C′} ∘ f ∘ u_{C}^{−1}.

E-3 A family v_{D} : D ⟶ F (G(D)) of isomorphisms of D indexed by the objects of D,

with the property that for every arrow g : D ⟶ D′ of D, F (G(g)) = v_{D′} ∘ g ∘ v_{D}^{−1}. If F is an equivalence of categories, the functor G of E-1 is called a pseudo-inverse of F. The idea behind the definition is that not only is every object of D isomorphic to an object in the image of F, but the isomorphisms are compatible with the arrows of D; and similarly

for C. 14.05.04

1.7.7. Example. An isomorphism of categories is an equivalence of categories, and its inverse is its pseudo-inverse.

1.7.8. Example (Monoids and one-object categories.). For each monoid M we constructed a small category C(M) in 1.3.8. We make the choice mentioned there that the one object of C(M) is M. Note that although an element of C(M) is now an arrow from M to M, it is not a set function. For each monoid homomorphism h : M ⟶ N, construct a functor C(h) : C(M) ⟶ C(N) as follows: CF-1 On objects, C(h)(M) = N. CF-2 C(h) must be exactly the same as h on arrows (elements of M).

It is straightforward to see that C(h) is a functor and that this construction makes C a functor from Mon to the full subcategory of Cat of categories with exactly one object. We will denote this full subcategory as Ooc. There is also a functor U : Ooc ⟶ Mon going the other way. UO-1 For a category C with one object, U(C) is the monoid whose elements are the arrows

of C and whose binary operation is the composition of C. UO-2 If F : C ⟶ D is a functor between one- object categories, U(F) = F_{1}, that is, the

functor F on arrows. The functors U and C are not inverse to each other, and it is worthwhile to see in detail why. The construction of C is in part arbitrary. We needed to regard each monoid as a category with one object. The choice of the elements of M to be the arrows of the category is obvious, but what should be the one object? We chose M itself, but we could have chosen some other thing, such as the set {e}, where e is the identity of M. The only real requirement is that it not be an element of M (such as its identity) in order to avoid set-theoretic problems caused by the category being an element of itself. The consequence is that we have given a functor C : Mon ⟶ Ooc in a way which required arbitrary choices. The arbitrary choice of one object for C(M) means that if we begin with a one-object category C , construct M = U(C), and then construct C(M), the result will not be the same as C unless it happens that the one object of C is M. Thus C ∘ U ≠ id_{Ooc}, so that U is not the inverse of C. (In this case U ∘ C is indeed id_{Mon}.) C is not surjective on objects, since not every small category with one object is in the image of C; in fact a category D is C(M) for some monoid M only if the single object of D is actually a monoid and the arrows of D are actually the arrows of that monoid. This is entirely contrary to the spirit of category theory: we are talking about specific elements rather than specifying behavior. Indeed, in terms of specifying behavior, the category of monoids and the category of small categories with one object ought to be essentially the same thing. The fact that C is not an isomorphism of categories is a signal that isomorphism is the wrong idea for capturing the concept that two categories are essentially the same. However, every small category with one object is isomorphic to one of those constructed as C(M) for some monoid M. This is the starting point for the definition of equivalence.

1.7.9. Proposition. A functor F : C ⟶ D is an equivalence of categories with pseudoinverse G : D ⟶ C if and only if G ∘ F is naturally isomorphic to id_{C} and F ∘ G is naturally isomorphic to id_{D}.

Proof. Conditions E-2 and E-3 of 1.7.6 can be recast as the statement that G(F (f)) ∘ u_{C} = u_{C′} ∘f and that F (G(g))∘v_{D} = v_{D′} ∘g, in other words that the following diagrams commute:

(3)  [figure: C; G(F (C)); u_{C}; C′; G(F (C′)); u_{C′}; f; G(F (f)); D; F (G(D)); v_{D}; D′; F (G(D′)); v_{D′}; g; F (G(g))]

In this form, they are the statements that u is a natural transformation from id_{C} to G ∘ F and that v is a natural transformation from id_{D} to F ∘ G. Since each component of u and each component of v is an isomorphism, u and v are natural isomorphisms. □

1.7.2. Diagrams. Commutative diagrams are the categorist’s way of expressing equations. Natural transformations are maps between functors; one way to think of them is as a deformation of one construction (construed as a functor) into another. We begin with diagrams in a graph and discuss commutativity later.

1.7.10. Definition. Let I and G be graphs. A diagram in G of shape I is a homomorphism D : I ⟶ G of graphs. I is called the shape graph of the diagram D. We have thus given a new name to a concept which was already defined (not uncommon in mathematics). A diagram is a graph homomorphism from a different point of view.

1.7.11. Example. At first glance, Definition 1.7.10 may seem to have little to do with what are informally called diagrams, for example

[figure: A; B; f; C; h; g]

The connection is this: a diagram in the sense of Definition 1.7.10 is pictured on the page with a drawing of nodes and arrows as for example in the previous diagram, which could be the picture of a diagram D with shape graph

[figure: i; j; u; k; w; v]

defined by D(i) = A, D(j) = B, D(k) = C, D(u) = f, D(v) = g and D(w) = h.

1.7.12. Example. Here is an example illustrating some subtleties involving the concept of diagram. Let G be a graph with objects A, B and C (and maybe others) and arrows f : A ⟶ B, g : B ⟶ C and h : B ⟶ B. Consider these two diagrams, where here we use the word ‘diagram’ informally:

[figure: A; B; f; C; g; A; B; f; h]

These are clearly of different shapes (again using the word ‘shape’ informally). But the diagram

[figure: A; B; f; B; h]

is the same shape as I even though as a graph it is the same as J. To capture the difference thus illustrated between a graph and a diagram, we introduce two shape graphs

[figure: I : 1; 2; u; 3; v; J : 1; 2; u; w]

(where, as will be customary, we use numbers for the nodes of shape graphs). Now the first diagram is seen to be the diagram D : I ⟶ G with D(1) = A, D(2) = B, D(3) = C, D(u) = f, and D(v) = g; whereas the second diagram is E : J ⟶ G with E(1) = A, E(2) = B, E(u) = f, and E(w) = h. Moreover, the third diagram is just like D (has the same shape), except that v goes to h and 3 goes to B.

1.7.13. Remark. Our definition in 1.7.10 of a diagram as a graph homomorphism, with the domain graph being the shape, captures both the following ideas:

(1) A diagram can have repeated labels on its nodes and (although the examples did not show it) on its arrows, and

(2) Two diagrams can have the same labels on their nodes and arrows but be of different shapes: the second diagram and the third diagram are different diagrams because they have different shapes.

1.7.3. Commutative diagrams. When the target graph of a diagram is the underlying graph of a category some new possibilities arise, in particular the concept of commutative diagram, which is the categorist’s way of expressing equations. In this situation, we will not distinguish in notation between the category and its underlying graph: if I is a graph and C is a category we will refer to a diagram D : I ⟶ C. We say that D is commutative (or commutes) provided for any nodes i and j of I and any two paths

[figure: i; s_{1}; k_{1}; k_{2}; s_{2}; …; k_{n−2}; k_{n−1}; s_{n−1}; j; s_{n}; t_{1}; l_{1}; l_{2}; t_{2}; …; l_{m−2}; l_{m−1}; t_{m−1}; t_{m}]

from i to j in I, the two paths

[figure: Di; Ds_{1}; Dk_{1}; Dk_{2}; Ds_{2}; …; Dk_{n−2}; Dk_{n−1}; Ds_{n−1}; Dj; Ds_{n}; Dt_{1}; Dl_{1}; Dl_{2}; Dt_{2}; …; Dl_{m−2}; Dl_{m−1}; Dt_{m−1}; Dt_{m}]

compose to the same arrow in C. This means that

Ds_{n} ∘ Ds_{n−1} ∘ … ∘ Ds_{1} = Dt_{m} ∘ Dt_{m−1} ∘ … ∘ Dt_{1}.

1.7.14. Remark (Much ado about nothing). There is one subtlety to the definition of commutative diagram: what happens if one of the numbers m or n in the last diagram should happen to be 0? If, say, m = 0, then we interpret the above equation to be meaningful only if the nodes i and j are the same (you go nowhere on an empty path) and the meaning in this case is that

Ds_{n} ∘ Ds_{n−1} ∘ … ∘ Ds_{1} = id_{Di}

(you do nothing on an empty path). In particular, a diagram D based on the graph

[figure: i; e]

commutes if and only if D(e) is the identity arrow from D(i) to D(i). Note, and note well, that both shape graphs

[figure: i; e; and; i; j; d]

have models that one might think to represent the diagram

[figure: A; f]

but the diagram based on the first graph commutes if and only if f = id_{A}, while the diagram based on the second graph commutes automatically (no two nodes have more than one path between them so the commutativity condition is vacuous). We will always picture diagrams so that distinct nodes of the shape graph are represented by distinct (but possibly identically labeled) nodes in the picture. Thus a diagram based on the second graph in which d goes to f and i and j both go to A will be pictured as

A f \overline{}A.

In consequence, one can always deduce the shape graph of a diagram from the way it is pictured, except of course for the actual names of the nodes and arrows of the shape graph. 1.7.15. Example (Examples of commutative diagrams – and others). The prototypical commutative diagram is the triangle

[figure: A; B; f; C; h; g]

that commutes if and only if h is the composite g ∘ f. The reason this is prototypical is that any commutative diagram – unless it involves an empty path – can be replaced by a set of commutative triangles. This fact is easy to show and not particularly enlightening, so we are content to give an example. The diagram

[figure: A; B; h; C; D; k; f; g]

commutes if and only if the two diagrams

[figure: C; D; k; A; g ∘ h; f; A; B; h; D; k ∘ f; g]

commute (in fact if and only if either one does). 1.7.16. Definition. Let C be a category. A morphism f : X ⟶ Y is called an isomorphism, if there exists a morphism g : Y ⟶ X with g ∘ f = 1_{X} and f ∘ g = 1_{Y}. g is uniquely determined by f and is itself an isomorphism. We use the notation f^{−1} := g. Thus we have (f^{−1})^{−1} = g^{−1} = f. 1.7.17. Example. An arrow f : A ⟶ B is an isomorphism with inverse g : B ⟶ A if and only if

[figure: f; A; B; g]

commutes. The reason for this is that for this diagram to commute, the two paths () and (g, f) from A to A must compose to the same value in the diagram, which means that g ∘ f = 1_{A}. A similar observation shows that f ∘ g must be 1_{B}.

20.05.04 1.7.4. Graph homomorphisms by commutative diagrams.

1.7.18. Remark. The definition of graph homomorphism in 1.1.2 can be expressed by a commutative diagram. Let φ = (φ_{0}; φ_{1}) be a graph homomorphism from G to H . For any arrow u : m ⟶ n in G , 1.1.2 requires that φ_{1}(u) : φ_{0}(m) ⟶ φ_{0}(n) in H. This says that φ_{0}(source(u)) = source(φ_{1}(u)), and a similar statement about targets. In other words, these diagrams must commute:

(4)  [figure: G_{1}; H_{1}; φ_{1}; G_{0}; H_{0}; φ_{0}; source; source; G_{1}; H_{1}; φ_{1}; G_{0}; H_{0}; φ_{0}; target; target]

In these two diagrams the two arrows labeled ‘source’ are of course different functions; one is the source function for G and the other for H. A similar remark is true of ‘target’. This point of view provides a pictorial proof that the composite of two graph homomorphisms is a graph homomorphism (see 1.3.8(26)). If φ : G ⟶ H and ψ : H ⟶ K are graph homomorphisms, then to see that ψ ∘ φ is a graph homomorphism requires checking that the outside rectangle below commutes, and similarly with target in place of source:

(5)  [figure: G_{1}; H_{1}; φ_{1}; G_{0}; H_{0}; φ_{0}; source; source; H_{1}; K_{1}; ψ_{1}; H_{0}; K_{0}; ψ_{0}; source]

The outside rectangle commutes because the two squares commute. This can be checked by tracing (mentally or with a finger or pointer) the paths from G_{1} to K_{0} to verify that source ∘ψ_{1}∘φ_{1} = ψ_{0}∘source ∘φ_{1} because the right square commutes, and that ψ_{0}∘source ∘φ_{1} = ψ_{0} ∘ φ_{0} ∘ source because the left square commutes. The verification process just described is called ‘chasing the diagram’. Of course, one can verify the required fact by writing the equations down, but those equations hide the source and target information given in diagram and thus provide a possibility of writing an impossible composite down. For many people, the diagram is much easier to remember than the equations. However, diagrams are more than informal aids; they are formally-defined mathematical objects just like automata and categories. The proof in 1.4.1 that the composition of arrows in a slice gives another arrow in the category can be represented by a similar diagram:

[figure: C; C′; h; C′′; h′; A; f; f′; f′′]

These examples are instances of pasting commutative diagrams together to get bigger ones.

1.7.5. Associativity by commutative diagrams. The fact that the multiplication in a monoid or semigroup is associative can be expressed as the assertion that a certain diagram in Set commutes. Let S be a semigroup. Define the following functions:

(1) mult : S × S ⟶ S satisfies mult(x, y) = xy.

(2) S × mult : S × S × S ⟶ S × S satisfies (S × mult)(x, y, z) = (x, yz).

(3) mult ×S : S × S × S ⟶ S × S satisfies (mult ×S)(x, y, z) = (xy, z). That the following diagram commutes is exactly the associative law.

[figure: S × S × S; S × S; S × mult; S × S; S; mult; mult ×S; mult]

Normally, associativity is expressed by the equation x(yz) = (xy)z for all x, y, z in the semigroup. The commutative diagram expresses this same fact without the use of variables. Of course, we did use variables in defining the functions involved, but we remedy that deficiency in Chapter 6 when we give a categorical definition of products. Another advantage of using diagrams to express equations is that diagrams show the source and target of the functions involved. This is not particularly compelling here but in other situations the two-dimensional picture of the compositions involved makes it much easier to follow the discussion.

1.7.19. Remark (Functors by commutative diagrams). We express the definition of functor using commutative diagrams. Let C and D be categories with sets of objects C_{0} and D_{0}, sets of arrows C_{1} and D_{1}, sets of composable pairs of arrows C_{2} and D_{2}, and identity morphisms given by id : C_{0} ⟶ C_{1} and id : D_{0} ⟶ D_{1}, respectively. A functor F : C ⟶ D consists of functions F_{0} : C_{0} ⟶ D_{0}, F_{1} : C_{1} ⟶ D_{1} along with the uniquely determined function F_{2} : C_{2} ⟶ D_{2} (think of F_{2}((f, g)) = (F_{1}(f), F_{1}(g))) such that

[figure: C_{2}; C_{1}; proj_{1}; D_{1}; F_{1}; D_{2}; F_{2}; D_{1}; F_{1}; C_{1}; proj_{2}; D_{2}; proj_{1}; proj_{2}]

commutes. In addition, the following diagrams must commute:

[figure: C_{1}; C_{0}; dom; D_{1}; D_{0}; dom; F_{1}; F_{0}; C_{1}; cod; D_{1}; cod; F_{1}; C_{2}; C_{1}; comp; D_{2}; D_{1}; comp; F_{2}; F_{1}; C_{0}; C_{1}; id; D_{0}; D_{1}; id; F_{0}; F_{1}]

where the second diagram represents F_{1}(f ∘ g) = F_{1}(f) ∘ F_{1}(g) and the third diagram represents F_{1}(1_{A}) = 1_{F_{0}(A)}.

1.7.20. Remark (Diagrams as functors). In much of the categorical literature, a diagram in a category C is a functor D : E ⟶ C where E is a category. Because of Proposition 1.6.8, a graph homomorphism into a category extends uniquely to a functor based on the free category generated by the graph, so that diagrams in our sense generate diagrams in the functorial sense. On the other hand, any functor is a graph homomorphism on the underlying graph of its domain (although not conversely!), so that every diagram in the sense of functor is a diagram in the sense of graph homomorphism.

21.05.04

1.7.6. Natural transformations. We saw that diagrams in a category are graph homomorphisms to the category from a different point of view. Now we introduce a third way to look at graph homomorphisms to a category, namely as models. To give an example, we need a definition.

1.7.21. Definition. A unary operation on a set S is a function u : S ⟶ S.

This definition is by analogy with the concept of binary operation on a set. A set with a unary operation is a (very simple) algebraic structure, which we call a u-structure. If the set is S and the operation is f : S ⟶ S, we say that (S, f) is a u-structure, meaning (S, f) denotes a u-structure whose underlying set is S, and whose unary operation is f. This uses positional notation in much the same way as procedures in many computer languages: the first entry in the expression ‘(S, f)’ is the name of the underlying set of the u-structure and the second entry is the name of its operation. A homomorphism of u-structures should be a function which preserves the structure. There is really only one definition that is reasonable for this idea: if (S, u) and (T, v) are u-structures, f : S ⟶ T is a homomorphism of u-structures if f(u(s)) = v(f(s)) for all s ∈ S. Thus this diagram must commute:

[figure: S; T; f; S; T; f; u; v]

It is not difficult to show that the composite of two homomorphisms of u-structures is another one, and that the identity map is a homomorphism, so that u-structures and homomorphisms form a category. We now use the concept of u-structure to motivate the third way of looking at graph homomorphisms to a category. Let U be the graph with one node u_{0} and one arrow e:

[figure: u_{0}; e]

Let us define a graph homomorphism D : U ⟶ Set as follows: D(u_{0}) = ℝ and D(e) = x ↦ x^{2}. Now (ℝ, x ↦ x^{2}) is a u-structure, and the notation we have introduced in 1.7.21 tells us that we have chosen ℝ to be its underlying set and x ↦ x^{2} to be its unary operation. Except for the arbitrary names ‘u_{0}’ and ‘e’, the graph homomorphism D communicates the same information: ‘ℝ is the particular set chosen to be the value of u_{0}, and x ↦ x^{2} is the particular function chosen to be the value of e.’ In this sense, a u-structure is essentially the same thing as a diagram in Set of shape U : a u-structure ‘models’ the graph U. This suggests the following definition.

1.7.22. Definition. A model M of a graph G is a graph homomorphism M : G ⟶ Set.

A monoid can be defined as a model involving a graph homomorphism (and other ingredients) using the concept of finite product. We had to introduce u-structures here to have an example for which we had the requisite techniques.

1.7.23. Example. As another example, consider this graph:

[figure: source; a; n; target]

A model M of this graph consists of sets G_{0} = M(n) and G_{1} = M(a) together with functions source = M(source) : G_{1} ⟶ G_{0} and target = M(target) : G_{1} ⟶ G_{0}. To understand what this structure is, imagine a picture in which there is a dot corresponding to each element of G_{0} and an arrow corresponding to each element a ∈ G_{1} which goes from the dot corresponding to source(a) to the one corresponding to target(a). It should be clear that the picture so described is a graph and thus the given graph is a graph whose models are graphs!

1.7.24. Remark (Models in arbitrary categories). The concept of model can be generalized to arbitrary categories: if C is any category, a model of G in C is a graph homomorphism from G to C . For example, a model of the graph for u-structures in the category of posets and monotone maps is a poset and a monotone map from the poset to itself. In these notes, the bare word ‘model’ always means a model in Set.

1.7.25. Remark (Natural transformations between models of a graph). In a category, there is a natural notion of an arrow from one model of a graph to another. This usually turns out to coincide with the standard definition of homomorphism for that kind of structure.

1.7.26. Definition. Let D, E : G ⟶ C be two models of the same graph in a category. A natural transformation α : D ⟶ E is given by a family of arrows αa of C indexed by the nodes of G such that: NT-1 αa : Da ⟶ Ea for each node a of G. NT-2 For any arrow s : a ⟶ b in G, the diagram

(6)  [figure: Da; Ea; αa; Db; Eb; αb; Ds; Es]

commutes.

The commutativity of the diagram in NT-2 is referred to as the em naturality condition on α. The arrow αa for an object a is the component of the natural transformation α at a. Note that you talk about a natural transformation from D to E only if D and E have the same domain (here G) as well as the same codomain (here C) and if, moreover, the codomain is a category. In this situation, it is often convenient to write α : D ⟶ E : G ⟶ C.

1.7.27. Definition. Let D, E and F be models of G in C , and α : D ⟶ E and β : E ⟶ F natural transformations. The composite β ∘ α : D ⟶ F is defined componentwise: (β ∘ α)a = βa ∘ αa.

1.7.28. Proposition. The composite of two natural transformations is also a natural transformation.

Proof. The diagram that has to be shown commutative is the outer rectangle of

(7)  [figure: Da; Ea; αa; F a; βa; Db; Eb; αb; F b; βb; Ds; Es; F s]

for each arrow s : a ⟶ b in G. The rectangle commutes because the two squares do; the squares commute as a consequence of the naturality of α and β. □

It is interesting that categorists began using modes of reasoning like that in the preceding proof because objects of categories generally lacked elements; now one appreciates them for their own sake because they allow element-free (and thus variable-free) arguments.

It is even easier to show that there is an identity natural transformation between any model D and itself, defined by 1_{D}a = 1_{Da}. We then have the following proposition, whose proof is straightforward.

1.7.29. Proposition. The models of a given graph G in a given category C, and the natural transformations between them, form a category. We denote this category by Mod(G, C).

1.7.30. Example. The natural transformations between models in Set of the u-structure graph U (one vertex and one non-trivial arrow) are exactly the homomorphisms of ustructures defined in 1.7.21. The graph U has one object u_{0} and one arrow e, so that a natural transformation from a model D to a model E has only one component which is a function from D(u_{0}) to E(u_{0}). If we set S = D(u_{0}), u = D(e), T = E(u_{0}), v = E(e), and we define αu_{0} = f, this is the single component of a natural transformation from D to E. Condition NT-2 in 1.7.26 coincides in this case with the diagram in 1.7.21: the naturality condition is the same as the definition of homomorphism of u-structures. It follows that the category of u-structures and homomorphisms is essentially Mod(U, Set).

1.7.31. Example. A homomorphism of graphs is a natural transformation between models of the graph

[figure: source; a; n; target]

The two graphs in diagram (4) are the two necessary instances (one for the source and the other for the target) of the diagram (6). In a similar way, the diagram (7), used to show that the composite of two natural transformations is a natural transformation, reduces in this case to the commutativity of diagram (5): specifically, the only possibilities (other than those in which s is an identity arrow) for a and b in diagram (7) are a = a and b = n, giving two diagrams shaped like diagram (7), one for s = source (that is diagram (5)) and the other for s = target.

1.7.32. Example. A model of the graph

(8)  0 ⟶^{u} 1

in an arbitrary category C is essentially the same as an arrow in C (see 5.2.23 below). A natural transformation from the model represented by the arrow f : A ⟶ B to the one represented by g : C ⟶ D is a pair of arrows h : A ⟶ C and k : B ⟶ D making a commutative diagram:

(9)  [figure: Da; Ea; αa; Db; Eb; αb; Ds; Es]

The component at 0 is h and the component at 1 is k. The category of models in C is called the arrow category of C; it is often denoted C⟶.

1.7.33. Example. Let G be the graph with two nodes and no arrows, and C any category. Then Mod(G, C) is isomorphic to C × C.

1.7.7. Natural isomorphisms.

1.7.34. Definition. A natural transformation α : F ⟶ G : G ⟶ D is called a natural isomorphism if there is a natural transformation β : G ⟶ F which is an inverse to α in the category Mod(G, D). Natural isomorphisms are often called natural equivalences.

1.7.35. Example. The arrow (h, k) : f ⟶ g in the arrow category of a category C , as shown in (9), is a natural isomorphism if and only if h and k are both isomorphisms in C. This is a special case of an important fact about natural isomorphisms, which we now state.

1.7.36. Theorem. Suppose F : G ⟶ D and G : G ⟶ D are models of G in D and α : F ⟶ G is a natural transformation of models. Then α is a natural isomorphism if and only if for each node a of G, αa : F (a) ⟶ G(a) is an isomorphism of D.

Proof. Suppose α has an inverse β : G ⟶ F in Mod(G, D). Then for any node a, by definition 1.7.27 the definition of the identity natural transformation, and the definition of inverse,

αa ∘ βa = (α ∘ β)a = id_{G} a = id_{G(a)}

and

βa ∘ αa = (β ∘ α)a = id_{F} a = id_{F (a)}

which means that the arrow βa is the inverse of the arrow αa, so that αa is an isomorphism in D as required. Conversely, suppose that for each node a of G , αa : F (a) ⟶ G(a) is an isomorphism of D. The component of the inverse β at a node a is defined by letting βa = (αa)^{−1}. This is the only possible definition, but it must be shown to be natural. Let f : a ⟶ b be an arrow of the domain of F and G. Then we have

F f ∘ (αa)^{−1} = (αb)^{−1} ∘ (αb) ∘ F f ∘ (αa)^{−1}
= (αb)^{−1} ∘ Gf ∘ (αa) ∘ (αa)^{−1}
= (αb)^{−1} ∘ Gf.

which says that β is natural. The second equality uses the naturality of α. □

27.05.04 1.7.37. Remark. In 1.7.32, we said that a model in an arbitrary category C of the graph (8) is ‘essentially the same’ as an arrow in C . This is common terminology and usually refers implicitly to an equivalence of categories. We spell it out in this case. Let us say that for a category C , C′ is the category whose objects are the arrows of C and for which an arrow from f to g is a pair (h, k) making diagram (9) commute.

A model M of the graph (8) in a category C specifies the objects M(0) and M(1) and the arrow M(u). M(u) has domain M(0) and codomain M(1). But the domain and codomain of an arrow in a category are uniquely determined by the arrow. So that the only necessary information is which arrow M(u) is. Now we can define a functor F : C⟶ ⟶ C′. On objects it takes M to M(u). The remarks in the preceding paragraph show that this map on objects is bijective. If M(u) = f and N(u) = g, an arrow from M to N in C⟶ and an arrow from f to g in C′ are the same thing – a pair (h, k) making diagram (9) commute. So we say F is the identity on arrows. It is straightforward to see that F is actually an isomorphism of categories.

1.7.8. Natural transformations between functors II.

1.7.38. Definition. A functor is among other things a graph homomorphism, so a natural transformation between two functors is a natural transformation of the corresponding graph homomorphisms. The following proposition is an immediate consequence of 1.7.28.

1.7.39. Proposition. If C and D are categories, the functors from C to D form a category with natural transformations as arrows.

We denote this category by Func(C, D). Other common notations for it are D^{C} and [C, D]. Tennent [1986] provides an exposition of the use of functor categories for programming language semantics. Of course, the graph homomorphisms from C to D, which do not necessarily preserve the composition of arrows in C , also form a category Mod(C, D) (see 1.7.29), of which Func(C, D) is a full subcategory. A natural transformation from one functor to another is a special case of a natural transformation from one graph homomorphism to another, so the ideas we have presented concerning natural transformations between graph homomorphisms apply to natural transformations between functors as well. In particular, Theorems 1.7.28 and 1.7.36 are true of natural transformations of functors. If C is not a small category (see 1.3.4), then Func(C, D) may not be locally small (see 1.3.4). In fact functors will be large, too, so they cannot be elements (objects) of a class of objects. This is a rather esoteric question that will not concern us in these notes since we will have no occasion to form functor categories of that sort. We motivated the concept of natural transformation by considering models of graphs, and most of the discussion in the rest of this section concerns that point of view. Historically, the concept first arose for functors and not from the point of view of models.

1.7.40. Examples. We have already described some examples of natural transformations, as summed up in the following propositions. In 1.6.7, we defined the graph homomorphism ηG : G ⟶ U(F (G)) which includes a graph G into U(F (G)), the underlying graph of the free category F (G).

1.7.41. Proposition. The family of arrows ηG form a natural transformation from the identity functor on Grf to U ∘ F, where U is the underlying graph functor from Cat to Grf.

The proof is left as an exercise. Further examples of natural transformations are given by actions on sets. We begin with a definition.

1.7.42. Definition. Let M be a monoid with identity 1 and let S be a set. An action of M on S is a function α : M × S ⟶ S for which

A-1 α(1, s) = s for all s ∈ S.

A-2 α(mn, s) = α(m, α(n, s)) for all m, n ∈ M and s ∈ S. It is customary in mathematics to write ms for α(m, s); then the preceding requirements become

A’-1 1s = s for all s ∈ S.

A’-2 (mn)s = m(ns) for all m, n ∈ M and s ∈ S. When actions are written this way, S is also called an M-set. The same syntax ms for m ∈ M and s ∈ S is used even when different actions are involved. This notation is analogous to (and presumably suggested by) the notation cv for scalar multiplication, where c is a scalar and v is a vector. It is useful to think of the set S as a state space and the elements of M as acting to induce transitions from one state to another.

1.7.43. Example. One major type of action by a monoid is the case when the state space is a vector space and M is a collection of linear transformations closed under multiplication. However, in that case the linear structure (the fact that states can be added and multiplied by scalars) is extra structure which the definition above does not require. Our definition also does not require that there be any concept of continuity of transitions. Thus, the definition is very general and can be regarded as a nonlinear, discrete approach to state transition systems. Less structure means, as always, that fewer theorems are true and fewer useful tools are available. On the other hand, less structure means that more situations fit the axioms, so that the theorems that are true and the tools that do exist work for more applications.

1.7.44. Definition. Let M be a monoid with actions on sets S and T. An equivariant map from S to T is a function φ : S ⟶ T with the property that mφ(s) = φ(ms) for all m ∈ M and s ∈ S. The identity function is an equivariant map and the composite of two equivariant maps is equivariant. This means that for each monoid M, monoid actions and equivariant maps form a category M- Act.

1.7.45. Remark. Let α be an action of a monoid M on a set S. Let C(M) denote the category determined by M with one object and morphisms the elements of M. The action α determines a functor F_{α} : C(M) ⟶ Set defined by: AF-1 F_{α}(∗) = S. AF-2 F_{α}(m) = s ↦ α(m, s) for m ∈ M and s ∈ S.

1.7.46. Example. Let α : M × S ⟶ S and β : M × T ⟶ T be two actions by a monoid M. Let φ : S ⟶ T be an equivariant map. If F and G are the functors corresponding to α and β, as in 1.7.45, then φ is the (only) component of a natural transformation from F to G. Conversely, the only component of any natural transformation from F to G is an equivariant map between the corresponding actions. If φ : S ⟶ T is an isomorphism of actions by M then φ determines a natural isomorphism.

1.7.47. Example. Let U : Mon ⟶ Set be the underlying functor from the category of monoids. Define U × U : Mon ⟶ Set as follows:

(1) For a monoid M, (U × U)(M) = U(M) × U(M).

(2) For a monoid homomorphism h : M ⟶ N,

(U × U)(h)(m, n) = (h(m), h(n)).

Then monoid multiplication is a natural transformation from U × UtoU. Formally: Let μ : U × U ⟶ U be the family of maps whose value at a monoid M is the function μM : U(M) × U(M) ⟶ U(M) defined by μM(m, m′) = mm′, the product of m and m′ in M. Then μ is a natural transformation. (The function μM is not in general a monoid homomorphism, unless M is commutative.) It is instructive to see why μ is a natural transformation. Let h : M ⟶ N be a monoid homomorphism. We must show that the following diagram commutes:

(10)  [figure: (U × U)(M); U(M); μM; (U × U)(N); U(N); μN; (U × U)(h); h]

The top route takes an element (m, m′) ∈ (U × U)(M) to h(mm′). The lower route takes it to h(m)h(m′). The commutativity of the diagram then follows from the fact that h is a homomorphism.

1.7.48. Definition. Let C be a category. A subfunctor of a functor F : C ⟶ Set is a functor G : C ⟶ Set with the property that for each object C of C, G(C) ⊆ F (C) and such that for each arrow f : C ⟶ C′ and each element x ∈ G(C), we have that Gf(x) = F f(x). It is straightforward to check that the inclusion function i_{C} : G(C) ⟶ F (C) is a natural transformation.

1.7.49. Example. Let B be a fixed set. We define a functor R : Set^{op} ⟶ Set such that for a set A, R(A) = Rel(A, B), the set of relations from A to B. (A relation from A to B is essentially set of ordered pairs in A × B.) For a set function f : A′ ⟶ A and relation α ∈ Rel(A, B), define R(f)(α) to be the relation α′ ∈ Rel(A′, B) defined by a′α′b if and only if f(a′)αb. It is easy to see that this makes R : Set^{op} ⟶ Set a functor. (Note that R(A) = Rel(A, B), but R is not Mor_{Rel}(-, B).) For each A, let φ_{A} : Rel(A, B) ⟶ Mor(A, PB) be the bijection that takes a relation α from A to B to the function that takes an element a ∈ A to the set {b ∈ B|aαb}. (You should check that this is a bijection.) If we check that the functions φ_{A} are the components of a natural transformation from R to Mor(A, PB), the transformation will automatically be a natural isomorphism by Theorem 1.7.36. To show that it is natural, let α ∈ Rel(A, B) and a′ ∈ A′. Then

Mor(f, PB)(φ_{A}(α)(a′)) = φ_{A}(α)(f(a′)) = {b|f(a′)αb} = {b|a′α′b} = φ_{A′}(R(f)(a′))

as required. This natural isomorphism can be taken to be the defining property of a topos. A topos is a cartesian closed category with some extra structure which produces an object of subobjects for each object. This structure makes toposes very much like the category of sets.

1.7.50. Example. For each set S, let {}S : S ⟶ PS be the function which takes an element x of S to the singleton subset {x}. Then fg is a natural transformation from the identity functor on Set to the direct image powerset functor P. (See 1.6.3.) However, fg is not a natural transformation from the identity functor on Set to the universal image powerset functor (see 1.6.11), and it does not even make sense to ask whether it is a natural transformation to the inverse image powerset functor.

1.7.9. Natural transformations of graphs. We now consider some natural transformations involving the category Grf of graphs and homomorphisms of graphs.

1.7.51. Example. The map which takes an arrow of a graph to its source is a natural transformation from A to N. (See 1.6.2.) The same is true for targets. Actually, every operation in any multisorted algebraic structure gives a natural transformation. Example 1.7.47 was another example of this.

1.7.52. Example. In 1.6.2, we defined the functor N : Grf ⟶ Set. It takes a graph G to its set G_{0} of nodes and a homomorphism φ to φ_{0}. Now pick a graph with one node ∗ and no arrows and call it E. Let V = Mor_{Grf}(E, -). A graph homomorphism from the graph E to an arbitrary graph G is evidently determined by the image of E and that can be any node of G. In other words, nodes of G are ‘essentially the same thing’ as graph homomorphisms from E to G, that is, as the elements of the set V (G). We can define a natural transformation α : V ⟶ N by defining αG(f) = f_{0}(∗) where G is a graph and f : E ⟶ G is a graph homomorphism (arrow of Grf). There must be a naturality diagram (6) for each arrow of the source category, which in this case is Grf. Thus to see that α is natural, we require that for each graph homomorphism g : G_{1} ⟶ G_{2}, the diagram

(11)  [figure: V G_{1}; V G_{2}; V g; NG_{1}; NG_{2}; Ng; αG_{1}; αG_{2}]

commutes. Now Ng is g_{0} (the node map of g) by definition, and the value of V (which is a hom functor) at a homomorphism g composes g with a graph homomorphism from the graph E. Then we have, for a homomorphism f : E ⟶ G_{1} (i.e., an element of the upper left corner of the diagram),

(αG_{2} ∘ V g)(f) = αG_{2}(g ∘ f) = (g ∘ f)_{0}(∗)

while

(Ng ∘ αG_{1})(f) = Ng(f_{0}(∗)) = g_{0}(f_{0}(∗))

and these are equal from the definition of composition of graph homomorphisms. The natural transformation α is in fact a natural isomorphism. This shows that N is naturally isomorphic to a hom functor. Such functors are called representable, and are considered in greater detail in 2.1.1

1.7.53. Remark (Connected components). A node a can be connected to the node b of a graph G if it is possible to get from a to b following a sequence of arrows of G in either direction. In order to state this more precisely, let us say that an arrow a ‘has’ a node n if n is the domain or the codomain (or both) of a. Then a is connected to b means that there is a sequence (c_{0}, c_{1}, …, c_{n}) of arrows of G with the property that a is a node (either the source or the target) of c_{0}, b is a node of c_{n}, and for i = 1, …, n, c_{i−1} and c_{i} have a node in common. We call such a sequence an undirected path between a and b. It is a good exercise to see that ‘being connected to’ is an equivalence relation. (For reflexivity: a node is connected to itself by the empty sequence.) An equivalence class of nodes with respect to this relation is called a connected component of the graph G, and the set of connected components is called W G. Connected components can be defined for categories in the same way as for graphs. In that case, each connected component is a full subcategory. If f : G ⟶ H is a graph homomorphism and if two nodes a and b are in the same component of G , then f(a) and f(b) are in the same component of H , this is because f takes an undirected path between a and b to an undirected path between f(a) and f(b). Thus the arrow f induces a function W f : W G ⟶ W H, namely the one which takes the component of a to the component of f(a); and this makes W a functor from Grf to Set. For a graph G, let βG : NG ⟶ W G be the set function which takes a node of G to the component of G that contains that node. (The component is the value of βG at the node, not the codomain.) Then β : N ⟶ W is a natural transformation. It is instructive to check the commutativity of the requisite diagram.

1.7.10. Combining natural transformations and functors.

1.7.54. Remark (Composites of natural transformations). Let F : A ⟶ B and G : B ⟶ C be functors. There is a composite functor G ∘ F : A ⟶ C defined in the usual way by G ∘ F (A) = G(F (A)). Similarly, let H, K and L be functors from A to B and α : H ⟶ K and β : K ⟶ L be natural transformations. Recall that this means that for each object A of A , αA : HA ⟶ KA and βA : KA ⟶ LA. Then as in ??.2.11, we define β ∘ α : H ⟶ L by (β ∘ α)A = βA ∘ αA.

1.7.55. Remark (Functors and natural transformations). Things get more interesting when we mix functors and natural transformations. For example, suppose we have three categories A , B and C , four functors, two of them, F, G : A ⟶ B and the other two H, K : B ⟶ C , and two natural transformations α : F ⟶ G and β : H ⟶ K. We picture this situation as follows:

(12)  [figure: A; B; B; C; F; H; G; K; ⇓ α; ⇓ β]

1.7.56. Definition. The natural transformation βF : H∘F ⟶ K∘F is defined by the formula (βF)A = β(F A) for an object A of A. The notation β(F A) means the component of the natural transformation β at the object F A. This is indeed an arrow H(F (A)) ⟶ K(F (A)) as required. To show that βF is natural requires showing that for an arrow f : A ⟶ A′ of A, the diagram

(13)  [figure: H(F (A)); K(F (A)); βF A; H(F (A′)); K(F (A′)); βF A′; H(F (f)); K(F (f))]

commutes, but this is just the naturality diagram of β applied to the arrow F (f) : F (A) ⟶ F (A′).

1.7.57. Definition. The natural transformation Hα : H ∘ F ⟶ H ∘ G is defined by letting (Hα)A = H(αA) for an object A of A, that is the value of H applied to the arrow αA. To see that Hα thus defined is natural requires showing that

[figure: H(F (A)); H(G(A)); H(αA); H(F (A′)); H(G(A′)); H(αA′); H(F (f)); H(G(f))]

commutes. This diagram is obtained by applying the functor H to the naturality diagram of α. Since functors preserve commutative diagrams, the result follows. Note that the proofs of naturality for βF and for Hα are quite different. For example, the second requires that H be a functor, while the first works if F is merely an object function.

2. Representable functors and the Yoneda Lemma

2.1. Representable functors. For an arbitrary category C, the functors from C to Set are special because the hom functors Mor(C, -) for each object C of C are set-valued functors. In this section, we introduce the concept of representable functor and discuss how certain set theoretic concepts can be transferred to arbitrary categories by representable functors. The main tool for this is the Yoneda Lemma, and universal elements, all of which are based on these hom functors. These ideas have turned out to be fundamental tools for categorists. They are also closely connected with the concept of adjunction, to be discussed later. If you are familiar with group theory, it may be illuminating to realize that representable functors are a generalization of the regular representation, and the Yoneda embedding is a generalization of Cayley’s Theorem. We have already considered set-valued functors as actions in 1.7.42.

2.1.1. Definition. A functor F from a category C to the category of sets Set (a set-valued functor) is said to be representable if there exists an object C of C and a natural isomorphism α : F ⟶ Mor_{C}(C, -) to the hom functor Mor_{C}(C, -); in this case one says that C represents the functor. A contravariant functor is representable if there exists an object C of C and a natural isomorphism α : F ⟶ Mor_{C}(-, C) to the hom functor Mor_{C}(-, C); again one says that C represents the functor.

We have already looked at one example of representable functor in some detail in 1.7.52, where we showed that the set-of-nodes functor for graphs is represented by the graph with one node and no arrows. The set-of-arrows functor is represented by the graph with two nodes and one arrow between them.

2.1.2. Example. The arrow functor A : Grf ⟶ Set of 1.6.2 is a representable functor represented by the graph 2 which is pictured as

1 ⟶^{e} 2.

Representable functors are used to think of objects as if they were sets. The main aim is to write morphisms then as set maps.

2.1.3. Definition. In definition 2.5.2 and many like it, what replaces the concept of element of A is an arbitrary arrow into A. In this context, an arbitrary arrow a : T ⟶ A is called a variable element of A, parametrized by T. The set of variable elements of A parametrized by T is A(T) := Mor_{C}(T, A). When a is treated as a variable element of A and f has source A, one may write f(a) for f ∘ a. So we may consider f as a map of variable elements:

f = Mor_{C}(T, f) : Mor_{C}(T, A) ⟶ Mor_{C}(T, B).

So f takes the variable elements of A with parameter T to the variable elements of B with the same parameter T.

2.1.4. Proposition. If f, g : A ⟶ B are morphisms in C then the following are equivalent: (1) f = g,

(2) f(a) = g(a) for all parameters T and all variable elements a ∈ A(T).

Proof. Clearly (1) implies (2). Assume that (2) holds. Take T := A and a = 1_{A}. Then f(a) = g(a) implies f = f ∘ 1_{A} = f(1_{A}) = g(1_{A}) = g ∘ 1_{A} = g. □

2.2. Terminal and initial objects. One of the most fundamental objects in the category of sets is a singleton set T = {∗}, a set with exactly one element. It has the categorical property, that there is exactly one arrow A ⟶ T for each set A. The last property can be generalized to arbitrary categories as follows.

2.2.1. Definition. An object T of a category C is called a terminal object if there is exactly one arrow A ⟶ T for each object A of C. We usually denote the terminal object by 1 and the unique arrow A ⟶ 1 by ⟨⟩. The dual notion (see 1.4.13), an object of a category that has a unique arrow to each object (including itself), is called an initial object and is often denoted 0.

2.2.2. Examples. In the category of sets, the empty set is initial and any one-element set is terminal. Thus the category of sets has a unique initial object but many terminal objects. The one-element monoid is both initial and terminal in the category of monoids. In the category determined by a poset, an object is initial if and only if it is an absolute minimum for the poset, and it is terminal if and only if it is an absolute maximum. Since there is no largest or smallest whole number, the category determined by the set of integers with its natural order (there is an arrow from m to n if and only if m ≤ n) gives an example of a category without initial or terminal object. In the category of semigroups, the empty semigroup (see 1.2.9) is the initial object and any one- element semigroup is a terminal object. On the other hand, the category of nonempty semigroups does not have an initial object. Warning: To prove this, it is not enough to say that the initial object in the category of semigroups is the empty semigroup and that semigroup is missing here! You have to show that no other object can be the initial object in the smaller category. One way to do this is to let U be the semigroup with two elements 1 and e with 1 · e = e · 1 = e, 1 · 1 = 1 and e · e = e. Then any nonempty semigroup S has two homomorphisms to U: the constant function taking everything to 1 and the one taking everything to e. Thus no nonempty semigroup S can be the initial object. In the category of graphs and graph homomorphisms, the graph with one node and one arrow is the terminal object.

2.2.3. Proposition. Any two terminal (respectively initial) objects in a category C are isomorphic.

Proof. Suppose 1 and 1′ are terminal objects. Since 1 is terminal, there is an arrow f : 1′ ⟶ 1. Similarly, there is an arrow g : 1 ⟶ 1′. The arrow f ∘ g : 1 ⟶ 1 is an arrow with target 1. Since 1 is a terminal object of the category, there can be only one arrow from 1 to 1. Thus it must be that f ∘ g is the identity of 1. An analogous proof shows that g ∘ f is the identity of 1′. □

2.2.4. Remark. In Set, an element x of a set A is the image of a function from a singleton set to A that takes the unique element of the singleton to x. Thus if we pick a specific singleton {∗} and call it 1, the elements of the set A are in one to one correspondence with Mor(1, A), which is the set of functions from the terminal object to A. Moreover, if f : A ⟶ B is a set function and x is an element of A determining the function x : 1 ⟶ A, then the element f(x) of B is essentially the same thing as the composite f ∘ x : 1 ⟶ B. Because of this, the categorist typically thinks of an element x ∈ A as being the constant x : 1 ⟶ A.

2.2.5. Definition. An arrow 1 ⟶ A in a category, where 1 is the terminal object, is called a constant of type A.

Thus each element of a set is a constant in Set. On the other hand, each monoid M has just one constant 1 ⟶ M in the category of monoids, since monoid homomorphisms must preserve the identity. The more common name in the categorical literature for a constant is global element of A, a name that comes from sheaf theory.

2.2.6. Example. The identity functor on Set is a representable functor represented by a terminal object in Set; in other words, Mor_{Set}(1, -) is naturally isomorphic to the identity functor. This can be described by saying that ‘a set is its set of global elements.’

A terminal object is an object with exactly one arrow ⟨⟩ : A ⟶ 1 to it from each object A. So the arrows to 1 are not interesting. Global elements are arrows from the terminal object. There may be none or many, so they are interesting. If 1 and 1′ are two terminal objects in a category and x : 1 ⟶ A and x′ : 1′ ⟶ A are two constants with the property that x′ ∘ ⟨⟩ = x (where ⟨⟩ is the unique isomorphism from 1 to 1′), then we regard x and x′ as the same constant. Think about this comment as it applies to elements in the category of sets, with two different choices of terminal object, and you will see why. There is an interesting technique to generalize notions in the categories Set to arbitrary categories C by using representable functors. We apply this technique to terminal objects.

2.2.7. Proposition. An object 1 in an arbitrary category C is a terminal object if and only if the (contravariant) representable functor Mor_{C}(-, 1) : C^{op} ⟶ Set maps every object A in C to a terminal object Mor_{C}(A, 1) in Set.

Proof. Since Mor_{C}(A, 1) is a singleton for all A, this is nothing but the definition of the terminal object. □

2.2.8. Remark. The definition of an initial object I is dual to the definition of a terminal object, so it is a terminal object in C^{op}. It is characterized by the fact that all Mor_{C^{op}}(A, I) = Mor_{C}(I, A) are singleton sets.

28.05.04

2.3. The extension principle.

2.3.1. Remark (Covariant extension of set-theoretic properties). For the notion of terminal object we should proceed according to the following principle of covariant extension of set-theoretic properties or extension principle:

(1) We define a (set-theoretic) property P of a set A (or a map f or a diagram D : I ⟶ Set) in such a way that this property holds for all sets (resp. maps resp. diagrams) of the isomorphism class of A (resp. f resp. D), i.e. it holds for all sets (resp. maps resp. diagrams) isomorphic to A (resp. f resp. D).

(2) We say that the (categorical) property P holds for an object C (resp. morphism f resp. diagram D : I ⟶ C) of an arbitrary category C by requiring that the contravariant representable functor Mor_{C}(-, C) (resp. the natural transformation Mor_{C}(-, f) resp. the diagram functor Mor_{C}(-, D) : C × I ⟶ Set) has as images sets Mor_{C}(B, C) (resp. maps Mor_{C}(B, f) resp. diagrams Mor_{C}(B, D) : I ⟶ Set) with property P in Set for all objects B in C.

(3) We check that the objects (resp. morphisms resp. diagrams) with (categorical) property P in Set are exactly the sets (resp. maps resp. diagrams) with (settheoretic) property P.

The last condition means in our example of a terminal object, that a set 1 is a singleton iff all Mor_{Set}(B, 1) are singletons. Very often the property P is given by a definition referring to specific elements. The construction of products is an example. Such a property might not hold for all objects of an isomorphism class. Then we will have to extend the definition to the whole isomorphism class (see for example section 2.7).

2.3.2. Example. The set of objects of a small category is ‘essentially the same thing’ as the set of global elements of the category (as an object of Cat). In other words, the set of objects functor is represented by the terminal object of Cat, which is the category with one object and one arrow. The set of arrows of a small category is the object part of a functor that is represented by the category 2, which is the graph 2 with the addition of two identity arrows.

2.4. Isomorphisms. In 1.7.16 we have defined the notion of an isomorphism. This is another example of the principle of covariant extension of set-theoretic properties. In general, the word ‘isomorphic’ is used in a mathematical context to mean indistinguishable in form.

2.4.1. Definition. A map f : A ⟶ B in Set is called an isomorphism if it is bijective.

It is clear that f : A ⟶ B is an isomorphism iff there is an inverse map g : B ⟶ A such that g ∘ f = 1_{A} and f ∘ g = 1_{B}. In the category of arrows of Set two arrows f : A ⟶ B and f′ : A′ ⟶ B′ are isomorphic if and only if there are maps g : A ⟶ A′, h : B ⟶ B′, g′ : A′ ⟶ A, and h′ : B′ ⟶ B such that

h ∘ f = f′ ∘ g, h′ ∘ f′ = f ∘ g′,
g′ ∘ g = 1_{A}, g ∘ g′ = 1_{A′},
h′ ∘ h = 1_{B}, h ∘ h′ = 1_{B′}.

with

(14)  [figure: A; A′; g; B; B′; h; A; g′; B; h′; A; A′; g; B; B′; h; f; f′; f; f′]

It is clear that f′ is bijective if f is bijective, since f′ = f′ ∘ g ∘ g′ = h ∘ f ∘ g′ with bijective maps h, f, and g′. Hence f is bijective if and only if all f′ that are isomorphic to f are bijective maps. This is the extension principle 2.3.1 (1). The extension principle 2.3.1 (2) provides the following definition.

2.4.2. Definition. A morphism f : A ⟶ B in an arbitrary category C is called invertible or an isomorphism if Mor_{C}(C, f) : Mor_{C}(C, A) ⟶ Mor_{C}(C, B) is bijective for all objects C in C.

This definition coincides with the original definition 1.7.16 of an isomorphism by the following Lemma:

2.4.3. Lemma. Let f : A ⟶ B be a morphism in C. f is an isomorphism (as in definition 2.4.2) if and only if there exists a morphism g : B ⟶ A such that g ∘ f = 1_{A} and f ∘ g = 1_{B}.

Proof. Let f be an isomorphism. Choose C := B. Then Mor_{C}(B, f) : Mor_{C}(B, A) ⟶ Mor_{C}(B, B) is a bijective map. Thus there is g ∈ Mor_{C}(B, A) with f ∘ g = Mor_{C}(B, f)(g) = 1_{B}. Furthermore Mor_{C}(A, f) : Mor_{C}(A, A) ⟶ Mor_{C}(A, B) is bijective hence Mor_{C}(A, f)(g ∘ f) = f ∘ g ∘ f = 1_{B} ∘ f = f ∘ 1_{A} = Mor_{C}(A, f)(1_{A}) implies g ∘ f = 1_{A}. Conversely assume that there is a morphism g : B ⟶ A such that g ∘ f = 1_{A} and f ∘ g = 1_{B}. Let C be an object in C and h : C ⟶ A. Then Mor_{C}(C, g) ∘ Mor_{C}(C, f)(h) = g ∘ f ∘ h = h hence Mor_{C}(C, g) ∘ Mor_{C}(C, f) = 1_{Mor_{C}(C,A)}. Furthermore let k : C ⟶ B. Then Mor_{C}(C, f) ∘ Mor_{C}(C, g)(k) = f ∘ g ∘ k = k hence Mor_{C}(C, f) ∘ Mor_{C}(C, g) = 1_{Mor_{C}(C,B)}. Thus Mor_{C}(B, f) : Mor_{C}(C, A) ⟶ Mor_{C}(C, B) is a bijective map. □

We now have to show that this definition satisfies extension principle 2.3.1 (3). Let f : A ⟶ B be a (categorical) isomorphism in Set. By Lemma 2.4.3 f has an inverse map g : B ⟶ A, hence it is bijective.

2.4.4. Proposition. If f : A ⟶ B and g : B ⟶ C are isomorphisms in a category with inverses f^{−1} : B ⟶ A and g^{−1} : C ⟶ B, then g∘f is an isomorphism with inverse f^{−1}∘g^{−1}.

The proof is omitted. This proposition is sometimes called the ‘Shoe-Sock Theorem’: to undo the act of putting on your socks, then your shoes, you have to take off your shoes, then your socks.

2.4.5. Definition. Let C be a category and suppose that A and B are two objects of C. We say that A is isomorphic to B, written A ≅ B, if there is an isomorphism f : A ⟶ B.

2.4.6. Definition. An arrow f : A ⟶ A in a category (with the source and target the same) is called an endomorphism. If it is invertible, it is called an automorphism.

2.4.7. Examples. Identity arrows in a category are isomorphisms (hence an automorphisms). In the category determined by a partially ordered set, the only isomorphisms are the identity arrows. If, in the category determined by a monoid, every arrow is an isomorphism then the monoid is a group. Because of this, a category in which every arrow is an isomorphism is called a groupoid. In the category of semigroups and semigroup homomorphisms, and likewise in the category of monoids and monoid homomorphisms, the isomorphisms are exactly the bijective homomorphisms. On the other hand, in the category of posets and monotone maps, there are bijective homomorphisms that have no inverse.

2.4.8. Definition. A property that objects of a category may have is preserved by isomorphisms if for any object A with the property, any object isomorphic to A must also have the property.

From the categorist’s point of view there is no reason to distinguish between two isomorphic objects in a category, since the interesting fact about a mathematical object is the way it relates to other mathematical objects and two isomorphic objects relate to other objects in the same way. For this reason, the concept of wide subcategory (definition 1.4.10) is not in the spirit of category theory. What really should matter is whether the subcategory contains an isomorphic copy of every object in the big category. This motivates the following definition.

2.4.9. Definition. A subcategory D of a category C is said to be a representative subcategory if every object of C is isomorphic to some object of D.

2.4.10. Example. Let D be the category whose objects are the empty set and all sets of the form {1, 2, …, n} for some positive integer n and whose arrows are all the functions between them. Then D is a representative subcategory of Fin (Definition 2.1.12), since there is a bijection from any nonempty finite set to some set of the form {1, 2, …, n}. Note that D is also full in Fin and that D is a small category.

2.5. Monomorphisms and epimorphisms. Recall that a function f : A ⟶ B in Set is injective if for any x, y ∈ A, if x ≠ y, then f(x) ≠ f(y).

2.5.1. Definition. A map f : A ⟶ B in Set is called a (set-theoretic) monomorphism if it is injective.

Let the two arrows f : A ⟶ B and f′ : A′ ⟶ B′ be isomorphic with bijective g : A ⟶ A′, h : B ⟶ B′, g′ : A′ ⟶ A, and h′ : B′ ⟶ B as in diagram (14). Then f′ is injective if f is injective. In fact assume f′(x) = f′(y). Then fg′(x) = h′f′(x) = h′f′(y) = fg′(y) implies g′(x) = g′(y) and hence x = y since g′ is bijective and f is injective. So the notion of monomorphism satisfies the extension principle 2.3.1 (1). The extension principle 2.3.1 (2) provides the following definition.

2.5.2. Definition. (1) A morphism f : A ⟶ B in an arbitrary category C is called a (categorical) monomorphism if Mor_{C}(C, f) : Mor_{C}(C, A) ⟶ Mor_{C}(C, B) is injective for all objects C in C.

(2) A morphism f : A ⟶ B in an arbitrary category C is called an epimorphism if Mor_{C^{op}}(C, f) : Mor_{C^{op}}(C, A) ⟶ Mor_{C^{op}}(C, B) is injective for all objects C in C.

2.5.3. Proposition. (1) A morphism f : A ⟶ B is a monomorphism if and only if it

satisfies the left cancelation property:

• ∀C ∈ C, ∀g, h : C ⟶ A:

f ∘ g = f ∘ h ⟹ g = h.

(2) A morphism f : A ⟶ B is an epimorphism if and only if it satisfies the right

cancelation property:

• ∀C ∈ C, ∀g, h : B ⟶ C:

g ∘ f = h ∘ f ⟹ g = h.

Proof. The left cancelation property says that

Mor_{C}(C, f) : Mor_{C}(C, A) ⟶ Mor_{C}(C, B)

is injective for all C in C. The right cancelation properties follows by duality. □

03.06.04 We now have to show that the definition of a monomorphism satisfies the extension principle 2.3.1 (3).

2.5.4. Proposition. A map in Set is a (categorical) monomorphism if and only if it is injective.

Proof. Let f : A ⟶ B be a monomorphism in Set. Then Mor_{Set}(C, f) : Mor_{Set}(C, A) ⟶ Mor_{Set}(C, B) is injective for all sets C. Let x, y ∈ A with f(x) = f(y). Let C be a terminal object {∗} in Set. Then there are maps g, h : {∗} ⟶ A with g(∗) = x and h(∗) = y. The composites satisfy f ∘ g(∗) = f(x) = f(y) = f ∘ h(∗) hence f ∘ g = f ∘ h and g = h. So we get x = g(∗) = h(∗) = y which shows that f is injective. Conversely assume that f is injective. Let g, h : C ⟶ A maps with f ∘ g = f ∘ h. Then f(g(x)) = f(h(x)) for all x ∈ C, hence g(x) = h(x) and g = h. Thus f is left cancelable and hence a monomorphism. □

Using the notation of variable elements of 2.1.3, f is a monomorphism if for any variable elements x, y : T ⟶ A, if x ≠ y, then f(x) ≠ f(y), i.e. f : A(T) ⟶ B(T) is injective for all parameters T.

2.5.5. Remark. Now that we have completed all three steps of the extension principle we may abbreviate the term ‘categorical monomorphism’ just to ‘monomorphism’. An arrow, that is a monomorphism in a category, is a monomorphism in any subcategory it happens to be in. However, an arrow can be a monomorphism in a subcategory of a category C without being a monomorphism in C.

2.5.6. Examples. In most familiar categories of sets with structure and functions that preserve structure, the monomorphisms are exactly the injective functions. In particular, the monomorphisms in Mon are the injective homomorphisms (see 2.5.7). This is more evidence that definition 2.5.2 is the correct categorical definition generalizing the set-theoretic concept of injectivity. In the category determined by a poset, every arrow is a monomorphism. A monomorphism of the category determined by a monoid is generally called left cancelable. An isomorphism in any category is a monomorphism. For suppose f is an isomorphism and assume f ∘ x = f ∘ y. Then x = f^{−1} ∘ f ∘ x = f^{−1} ∘ f ∘ y = y.

2.5.7. Proposition. A monomorphism in the category of monoids is an injective homomorphism, and conversely.

Proof. Let f : M ⟶ M′ be a monoid homomorphism. Suppose it is injective. Let g, h : V ⟶ M be homomorphisms for which f ∘ g = f ∘ h. For any v ∈ V, f(g(v)) = f(h(v)), so g(v) = h(v) since f is injective. Hence g = h. It follows that f is a monomorphism. Essentially the same proof works in other categories of structures and structure-preserving maps – if the map is injective it is a monomorphism for the same reason as in Set (see Exercise ??). However, the converse definitely does not work that way. The proof for Set in Theorem 2.5.4 above uses distinct global elements x and y, but a monoid need not have distinct global elements. For example, let N denote the monoid of nonnegative integers with addition as operation. Then the only global element of N on addition is 0. So we have to work harder to get a proof. Suppose f is a monomorphism. Let x, y ∈ M be distinct elements. Let p_{x} : N ⟶ M take k to x^{k} and similarly define p_{y}; p_{x} and p_{y} are homomorphisms since for all x, x^{k+n} = x^{k}x^{n}. Since x ≠ y, p_{x} and p_{y} are distinct homomorphisms. If f(x) = f(y) then for all positive integers k, f(p_{x}(k)) = f(x^{k}) = f(x)^{k} = f(y)^{k} = f(y^{k}) = f(p_{y}(k)) so that f ∘ p_{x} = f ∘ p_{y} which would mean that f is not a monomorphism. Thus we must have f(x) ≠ f(y) so that f is injective. □

The trick in the preceding proof was to find an object (N here) that allows one to distinguish elements of the arbitrary monoid M. In Set, the corresponding object was the terminal object, but that does not work for Mon: each monoid has exactly one global element because a map from the one-element monoid must have the identity element as value. We now state two propositions that give some elementary properties of monomorphisms.

2.5.8. Proposition. Suppose f : A ⟶ B and g : B ⟶ C in a category C. Then (1) If f and g are monomorphisms, so is g ∘ f.

(2) If g ∘ f is a monomorphism, so is f.

Proof. (1) The extension principle and the definition 2.5.2 of monomorphisms give a short proof. Using Mor_{C}(T, g) ∘ Mor_{C}(T, f) = Mor_{C}(T, g ∘ f) we get:

f, g are monomorphisms ⟺

Mor_{C}(T, f), Mor_{C}(T, g) are injective for all objects T in C ⟹ Mor_{C}(T, g ∘ f) is injective for all objects T in C ⟺ g ∘ f is a monomorphism.

(2) With the same arguments we get:

g ∘ f is a monomorphism ⟺

Mor_{C}(T, g ∘ f) is injective for all objects T in C ⟹ Mor_{C}(T, f) is injective for all objects T in C ⟺ f is a monomorphism.

□

2.5.9. Proposition. Let m : C ⟶ 0 be a monomorphism into an initial object. Then m is an isomorphism.

Proof. Let i : 0 ⟶ C be the unique arrow given by definition of initial object. Then m∘i and 1_{0} are both arrows from 0 to 0 and so must be the same. It remains to show that i ∘ m = 1_{C}. This follows from the fact that m ∘ i ∘ m = m ∘ 1_{C} and that m is a monomorphism. □

2.5.10. Remark (Properties of Cat). We note some properties without proof. The initial category has no objects and, therefore, no arrows. The terminal category has just one object and the identity arrow of that object. To any category C there is just one functor that takes every object to that single object and every arrow to that one arrow. A functor is a monomorphism in Cat if and only if it is injective on both objects and arrows. The corresponding statement for epimorphisms is not true.

2.5.11. Example. Not all monomorphisms, however, coincide with injective maps between objects in C, even if there is an underlying (faithful) functor from C to Set. For an example consider the category of divisible abelian groups. An abelian group G is called divisible if nG = G for each natural number n ≥ 1, i.e. for each g ∈ G and n there is an element g′ ∈ G with ng′ = g. Consider the residue class homomorphism ν : ℚ ⟶ ℚ/ℤ from rational numbers to rational numbers modulo integers. This is a monomorphism in the category of divisible abelian groups (with group homomorphisms as morphisms). Let f, g : A ⟶ ℚ be homomorphisms with f ≠ g. Then there is a ∈ A with 0 ≠ f(a) − g(a) = r/s ∈ ℚ. Let b ∈ A with rb = a. Then r(f(b) − g(b)) = f(a) − g(a) = r/s, hence f(a) − g(a) = 1/s and νf(b) ≠ νg(b). This implies νf ≠ νg hence ν is a monomorphism.

For the dual notion of epimorphisms we have similar properties.

2.5.12. Proposition. A set function is an epimorphism in Set if and only if it is surjective.

Proof. Suppose f : S ⟶ T is surjective, and g, h : T ⟶ X are two functions. If g ≠ h, then there is some particular element t ∈ T for which g(t) ≠ h(t). Since f is surjective, there is an element s ∈ S for which f(s) = t. Then g(f(s)) ≠ h(f(s)), so that g ∘ f ≠ h ∘ f. Conversely, suppose f is not surjective. Then there is some t ∈ T for which there is no s ∈ S such that f(s) = t. Now define two functions g : T ⟶ {0, 1} and h : T ⟶ {0, 1} as follows:

(i) g(x) = h(x) = 0 for all x in T except t.

(ii) g(t) = 0.

(iii) h(t) = 1. Then g ≠ h but g ∘ f = h ∘ f, so f is not an epimorphism. □

04.06.04

2.5.13. Proposition. Let f : A ⟶ B and g : B ⟶ C. Then (1) If f and g are epimorphisms, so is g ∘ f.

(2) If g ∘ f is an epimorphism, so is g.

Proof. This is the dual of Proposition 2.5.8. □

2.5.14. Remark. In Set an arrow that is both monic and epic is bijective, and hence an isomorphism. In general, this need not happen. One example is the inclusion of ℤ in ℚ in Ri described in ?? (an inverse would also have to be an inverse in Set, but there isn’t one since the inclusion is not bijective). An easier example is the arrow in

[figure: C; D]

from C to D. It is both monic and epic (vacuously) but there is no arrow from D to C so it is not an isomorphism because there is no arrow in the category that could be its inverse.

If we try to generalize the notion of a surjective map according to the extension principle we obtain the notion of a split epimorphism. We first introduce this notion. An arrow f : A ⟶ B in a category is an isomorphism if it has an inverse g : B ⟶ A which must satisfy both the equations g ∘ f = 1_{A} and f ∘ g = 1_{B}. If it only satisfies the second equation, f ∘ g = 1_{B}, then f is a left inverse of g and (as you might expect) g is a right inverse of f.

2.5.15. Definition. Suppose f has a right inverse g. Then f is called a split epimorphism (f is split by g) and g is called a split monomorphism.

2.5.16. Lemma. Every surjection in Set is a split epimorphism.

Proof. If f : A ⟶ B, then choose, for each b ∈ B, some element a ∈ A such that f(a) = b. The existence of such an a is guaranteed by surjectivity. Define g(b) to be a. Then f(g(b)) = f(a) = b for any b ∈ B, so f ∘ g = 1_{B}. □

The so-called axiom of choice is exactly what is required to make all those generally infinitely many choices. And in fact, one possible formulation of the axiom of choice is that every epimorphism splits.

2.5.17. Proposition. A morphism f : A ⟶ B in C is a split epimorphism if and only if

Mor_{C}(C, f) : Mor_{C}(C, A) ⟶ Mor_{C}(C, B)

is surjective for all objects C in C.

Proof. Let f have the splitting g : B ⟶ A. Let h ∈ Mor_{C}(C, B). Then g ∘ h ∈ Mor_{C}(C, A) and f ∘ (g ∘ h) = (f ∘ g) ∘ h = h so that Mor_{C}(C, f) is surjective. Conversely assume that all Mor_{C}(C, f) are surjective. Choose C = B and let g ∈ Mor_{C}(B, A) with Mor_{C}(B, f)(g) = 1_{B} ∈ Mor_{C}(B, B). Then f ∘ g = 1_{B} so that f is a split epimorphism.

□

So we have checked all items for the extension principle and a split epimorphism is the covariant extension of the notion of surjective map in Set. Epimorphisms in other categories may not be split. The function that includes the monoid of non-negative integers (ℕ, +) on addition in the monoid of all the integers (ℤ, +) on addition certainly does not have a right inverse in the category of monoids, since it does not have a right inverse in the category of sets. There are plenty of examples of epimorphisms of monoids which are surjective which have no right inverse in the category of monoids, although of course they do in the category of sets. One such epimorphism of monoids is the function that takes the integers mod 4 on addition to the integers mod 2 on addition, with 0 and 2 going to 0 and 1 and 3 going to 1. Unlike epis, which always split in the category of sets, monics in Set do not always split. Every arrow out of the empty set is monic and, save for the identity of ∅ to itself, is not split. On the other hand, every monic with nonempty source does split. We leave the details to the reader.

2.6. Subobjects. The concept of subobject is intended to generalize the concept of subset of a set, submonoid of a monoid, subcategory of a category, and so on. This idea cannot be translated exactly into categorical terms, since the usual concept of subset violates the strict typing rules of category theory: to go from a subset to a set requires a change of type, so there is no feasible way to say that the same element x is in both a set and a subset of the set. Because of this, any categorical definition of subobject will not give exactly the concept of subset when applied to the category of sets. However, the usual definition of subobject produces, in Set, a concept that is naturally equivalent to the concept of subset. The definition, when applied to sets, defines subset in terms of the inclusion function. We need a preliminary idea. Let C/C be a comma category. We call an object f : A ⟶ C monic if f is a monomorphism in C.

2.6.1. Proposition. If f : A ⟶ C and f′ : A′ ⟶ C are monic, then there is at most one morphism g : (A, f) ⟶ (A′, f′) in C/C.

Proof. Given g, g′ : (A, f) ⟶ (A′, f′). Then f′ ∘ g = f = f′ ∘ g′ in C. Since f′ is a monomorphism in C we get g = g′. □

2.6.2. Corollary. If there are morphisms g : (A, f) ⟶ (A′, f′) and h : (A′, f′) ⟶ (A, f), then g is an isomorphism and h = g^{−1}.

Proof. By the proposition we have h ∘ g = 1_{A} : (A, f) ⟶ (A, f) and g ∘ h = 1_{A′} : (A′, f′) ⟶ (A′, f′) so that g and h are mutually inverse morphisms. □

2.6.3. Remark. Isomorphisms between objects (A, f) in C define an equivalence relation. The equivalence classes are partially ordered by \overline{(A, f)} ≤ \overline{(A′, f′)} iff there is a morphism g : (A, f) ⟶ (A′, f′).

2.6.4. Definition. In a category C, a subobject of an object C is an equivalence or isomorphism class of monics in C/C. The subobject is a proper subobject if it does not contain 1_{C} : C ⟶ C.

Observe that it follows immediately from Proposition 2.5.9 that an initial object in a category has no proper subobjects.

2.6.5. Remark. Let α : F ⟶ G be a natural transformation between models of G in D. Suppose each component of α is a monomorphism in D. Then it is easy to prove that α is a monomorphism in Mod(G, D). The converse is not true.

2.7. Products. Another application of the extension principle relates to products. We first define the product of two sets.

2.7.1. Definition. If A and B are sets, the Cartesian product A × B is the set of all ordered pairs with first coordinate in A and second coordinate in B; in other words,

A × B = {(a, b)|a ∈ A and b ∈ B}.

The coordinates define functions p_{A} = proj_{1} : A × B ⟶ A and proj_{2} = proj_{2} : A × B ⟶ B called the coordinate functions, or the projections.

Now this definition does not satisfy the first property for the extension principle, a set X isomorphic to A×B will in general not consist of pairs of elements. So the sets {0, 1, 2, 3, 4, 5} and {0, 1, } × {0, 1, 2} are clearly isomorphic, because both have 6 elements, but the first set does not consist of pairs. So here we have a set theoretic definition that refers to specific properties of the elements. All the more it is interesting to find out that there is an example for the extension principle hidden behind their concept.

2.7.2. Proposition. Let A, B be sets. The Cartesian product A × B together with the projections proj_{1} : A × B ⟶ A and proj_{2} : A × B ⟶ B satisfies the following universal property:

(*) for every set T and every pair of maps f : T ⟶ A, g : T ⟶ B there is a unique map (f, g) : T ⟶ A × B such that the diagram

[figure: A; A × B; proj_{1}; B; proj_{2}; (f, g); T; f; g]

commutes, i.e. proj_{1} ∘(f, g) = f and proj_{2} ∘(f, g) = g.

Proof. We first show the uniqueness of the map (f, g) : T ⟶ A × B: Given T, f, and g. If h, k : T ⟶ A × B are maps such that proj_{1} ∘h = f = proj_{1} ∘k and proj_{2} ∘h = g = proj_{2} ∘k then for any t ∈ T we have h(t) =: (a, b) ∈ A × B and k(t) =: (a′, b′) ∈ A × B. Then we get a = proj_{1}(a, b) = (proj_{1} ∘h)(t) = f(t) = (proj_{1} ∘k)(t) = proj_{1}(a′, b′) = a′ and b = proj_{2}(a, b) = (proj_{2} ∘h)(t) = g(t) = (proj_{2} ∘k)(t) = proj_{2}(a′, b′) = b′, hence h(t) = (a, b) = (a′, b′) = k(t) and h = k. This shows the uniqueness of the map h. Existence: From the uniqueness proof we obtain a reasonable definition of (f, g). For t ∈ T we define

(f, g)(t) := (f(t), g(t)).

This is a map from T to A×B. Since it satisfies (proj_{1} ∘(f, g))(t) = f(t) and (proj_{2} ∘(f, g))(t) = g(t) we get proj_{1} ∘(f, g) = f and proj_{2} ∘(f, g) = g. □

Obviously any triple (P, p′_{A} : P ⟶ A, p′_{B} : P ⟶ B) isomorphic to (A × B, proj_{1}, proj_{2}) satisfies the same universal property. In fact let h : P ⟶ A × B be an isomorphism such that

[figure: P; A; p′_{A}; B; p′_{B}; A × B; proj_{1}; proj_{2}; h]

commutes. Let T be a set and let f : T ⟶ A, g : T ⟶ B be maps. Then the map h^{−1} ∘ (f, g) : T ⟶ P satisfies p′_{A} ∘ (h^{−1} ∘ (f, g)) = f and p′_{B} ∘ (h^{−1} ∘ (f, g)) = g. It is an easy exercise to show that this map is unique with this property. So the universal property given in the theorem satisfies the first property of the extension principle. In arbitrary categories we cannot construct the Cartesian product of two objects since there are no elements and we thus cannot construct pairs of elements. So when we use the notation A × B in an arbitrary category this cannot mean a set of pairs of elements. It will stand for an arbitrary object with additional properties described by morphisms. The extension principle 2.3.1 (2) provides the following definition.

2.7.3. Definition. Given objects A and B in a category C. An object A × B together with morphisms p_{A} : A × B ⟶ A and p_{B} : A × B ⟶ B is called a (not the!) (categorical) product of A and B, and the morphisms p_{A}, p_{B} are called projections, if for all objects T in C there is an isomorphism of sets

Mor_{C}(T, A × B) ≅ Mor_{C}(T, A) × Mor_{C}(T, B)

(where Mor_{C}(T, A) × Mor_{C}(T, B)is the Cartesian product) such that the diagram

[figure: Mor_{C}(T, A × B); Mor_{C}(T, A); Mor_{C}(T, p_{A}); Mor_{C}(T, B); Mor_{C}(T, p_{B}); Mor_{C}(T, A) × Mor_{C}(T, B); p_{Mor_{C}(T,A)}; p_{Mor_{C}(T,B)}; h]

commutes.

11.06.04

2.7.4. Proposition (Characterization of products by the universal mapping property). Given objects A and B in a category C. An object A × B together with morphisms p_{A} : A × B ⟶ A and p_{B} : A × B ⟶ B is a (categorical) product, (**) if and only if for each object T ∈ C and each pair of morphisms f : T ⟶ A, g : T

⟶ B there is a unique morphism (f, g) : T ⟶ A × B such that the diagram

[figure: A; A × B; p_{A}; B; p_{B}; (f, g); T; f; g]

commutes, i.e. p_{A} ∘ (f, g) = f and p_{B} ∘ (f, g) = g.

Proof. ⟸: Let (A × B, p_{A}, p_{B}) be a product of A and B. Let T be an object in C and let u ∈ Mor_{C}(T, A × B). Define f := p_{A} ∘ u : T ⟶ A und g := p_{B} ∘ u : T ⟶ B. Then (f, g) ∈ Mor_{C}(T, A) × Mor_{C}(T, B). Now we define h(u) := (f, g) ∈ Mor_{C}(T, A) × Mor_{C}(T, B) and get Mor_{C}(T, p_{A})(u) = p_{A} ∘ u = f = p_{Mor_{C}(T,A)} ∘ h(u) and Mor_{C}(T, p_{B})(u) = p_{B} ∘ u = g = p_{Mor_{C}(T,B)} ∘ h(u). It remains to show that h is bijective. We construct the inverse map as

k : Mor_{C}(T, A) × Mor_{C}(T, B) ⟶ Mor_{C}(T, A × B) k((f, g)) := u

where (f, g) ∈ Mor_{C}(T, A) × Mor_{C}(T, B). By the universal property of the product there is a unique u : T ⟶ A × B such that p_{A} ∘ u = f and p_{B} ∘ u = g. We use this u for the definition of the map h. Let (f, g) ∈ Mor_{C}(T, A) × Mor_{C}(T, B). Then (h ∘ k)((f, g)) = h(u) = (p_{A} ∘ u, p_{B} ∘ u) = (f, g) hence (i ∘ u) = 1_{Mor_{C}(T,A)×Mor_{C}(T,B)}. Let u ∈ Mor_{C}(T, A × B). Then (k ∘ h)(u) = k((f, g)) = k((p_{A} ∘ u, p_{B} ∘ u)) = u′ where u′ : T ⟶ A × B is the unique morphism such that p_{A} ∘ u′ = p_{A} ∘ f and p_{B} ∘ u′ = p_{B} ∘ u hence u = u′ and (k ∘ h) = 1_{Mor_{C}(T,A×B)}. ⟹: Given morphisms f : T ⟶ A and g : T ⟶ B. Then (f, g) is an element of Mor_{C}(T, A)× Mor_{C}(T, B). So there is a unique morphism u := h^{−1}((f, g)) satisfying p_{Mor_{C}(T,A)}∘h(u) = f and p_{Mor_{C}(T,B)}∘ h(u) = g. Equivalently Mor_{C}(T, p_{A})(u) = f = p_{A} ∘ u and Mor_{C}(T, p_{B})(u) = g = p_{B} ∘ u with a unique u. Thus (A × B, p_{A}, p_{B}) is a product of A and B. □

2.7.5. Proposition. The family of isomorphisms

h_{T} : Mor_{C}(T, A × B) ⟶ Mor_{C}(T, A) × Mor_{C}(T, B)

such that

[figure: Mor_{C}(T, A × B); Mor_{C}(T, A); Mor_{C}(T, p_{A}); Mor_{C}(T, B); Mor_{C}(T, p_{B}); Mor_{C}(T, A) × Mor_{C}(T, B); p_{Mor_{C}(T,A)}; p_{Mor_{C}(T,B)}; h_{T}]

commute for all objects T in C, is a natural isomorphism in T, A, and B.

Proof. We show that the inverses

k_{T} : Mor_{C}(T, A) × Mor_{C}(T, B) ⟶ Mor_{C}(T, A × B)

as constructed in Proposition 2.7.4 form a natural transformation. So for t : T′ ⟶ T we have to show that the diagram

[figure: Mor_{C}(T, A) × Mor_{C}(T, B); Mor_{C}(T, A × B); k_{T}; Mor_{C}(T′, A) × Mor_{C}(T′, B); Mor_{C}(T′, A × B); k_{T′}; Mor_{C}(t, A) × Mor_{C}(t, B); Mor_{C}(t, A × B)]

commutes. Let (f, g) ∈ Mor_{C}(T, A) × Mor_{C}(T, B). Then [f, g] := k_{T} ((f, g)) is the unique morphism satisfying p_{A} ∘ [f, g] = f and p_{B} ∘ [f, g] = g. The two sides of the square give two morphisms [f ∘ t, g ∘ t] = (k_{T} ∘ Mor_{C}(t, A) × Mor_{C}(t, B))((f, g)) and [f, g] ∘ t = (Mor_{C}(f, A × B) ∘ k_{T′})((f, g)). We have to show that these are equal. Observe that a morphism u ∈ Mor_{C}(T′, A × B) is uniquely determined by the morphisms p_{A} ∘ u and p_{B} ∘ u. We get from p_{A} ∘ [f, g] ∘ t = f ∘ t = p_{A} ∘ [f ∘ t, g ∘ t] and p_{B} ∘ [f, g] ∘ t = g ∘ t = p_{B} ∘ [f ∘ t, g ∘ t] the result [f, g] ∘ t = [f ∘ t, g ∘ t]. Now let a : A ⟶ A′ and b : B ⟶ B′ be given. Then the diagram

[figure: Mor_{C}(T, A) × Mor_{C}(T, B); Mor_{C}(T, A × B); k; Mor_{C}(T, A′) × Mor_{C}(T, B′); Mor_{C}(T, A′ × B′); k; Mor_{C}(T, a) × Mor_{C}(T, b); Mor_{C}(T, a × b)]

commutes since p_{A′} ∘ (Mor_{C}(T, a × b) ∘ k)((f, g)) = p_{A′} ∘ (a × b) ∘ [f, g]) = a ∘ p_{A} ∘ [f, g] = a∘f = p′_{A}([a∘f, b∘f]) = p′_{A}∘(k∘(Mor_{C}(T, a)×Mor_{C}(T, b)))((f, g)) and p_{B′} ∘(Mor_{C}(T, a×b)∘ k)((f, g)) = p_{B′}∘(a×b)∘[f, g]) = b∘p_{B}∘[f, g] = b∘f = p′_{B}([a∘f, b∘f]) = p′_{B}∘(k∘(Mor_{C}(T, a)× Mor_{C}(T, b)))((f, g)) implies Mor_{C}(T, a × b) ∘ k = k ∘ (Mor_{C}(T, a) × Mor_{C}(T, b)). □

Before we show that the definition of a product satisfies the extension principle 2.3.1 (3) we show a general uniqueness theorem.

2.7.6. Theorem. Let A and B be objects of a category C. If (P, p_{A}, p_{B}) and (P′, p′_{A}, p′_{B}) are products of A and B in C, then there is a unique isomorphism k : P′ ⟶ P such that p_{A} ∘ k = p′_{A} and p_{B} ∘ k = p′_{B}.

Proof. Since (P, p_{A}, p_{B}) satisfies the universal property (**) there is a unique morphism k : P′ ⟶ P such that p_{A} ∘ k = p′_{A} and p_{B} ∘ k = p′_{B}. Symmetrically there is a unique morphism h : P′ ⟶ P such that p′_{A} ∘ h = p_{A} and p′_{B} ∘ h = p_{B}. Consider the following commutative diagram:

[figure: P; A; p_{A}; P′; p′_{A}; P; p_{A}; P′; p′_{A}; B; p_{B}; p′_{B}; p_{B}; p′_{B}; h; k; h; 1_{P}; 1_{P′}]

Since p_{A} ∘k ∘h = p_{A} = p_{A} ∘1_{P} and p_{B} ∘k ∘h = p_{B} = p_{B} ∘1_{P} we get by uniqueness k ∘h = 1_{P}. Symmetrically we get h∘k = 1_{P′}, thus h is an isomorphism with the required properties. □

We now have to show that the definition of a product satisfies the extension principle 2.3.1 (3).

2.7.7. Proposition. Given sets A and B. A set P together with two maps p′_{A} : P ⟶ A and p′_{B} : P ⟶ B satisfies the universal property (*) of proposition 2.7.2 if and only if there is an isomorphism h : P ⟶ A × B such that p_{A} ∘ h = p′_{A} and p_{B} ∘ h = p′_{B}.

Proof. By proposition 2.7.2 the Cartesian product A × B and the projections p_{A} : A × B ⟶ A and p_{B} : A × B ⟶ B satisfy the universal property of proposition 2.7.4. Following the proof of proposition 2.7.2 we have shown that (P, p′_{A}, p′_{B}) also satisfies the universal property (*). Conversely if a triple (P, p′_{A}, p′_{B}) satisfies the universal property (*) resp. (**) then by theorem 2.7.6 P and A × B are isomorphic by h with p_{A} ∘ h = p′_{A} and p_{B} ∘ h = p′_{B}. □

So in the future we will assume that products are given by and satisfy property (**). All propositions and theorems of this section of products are as well valid for products with more than two factors, for products of arbitrary families of objects (A_{i}|i ∈ I).

2.7.8. Definition. Let (A_{i}|i ∈ I) be a family of objects in a category C. An object ∏_{i∈I} A_{i} together with a family of morphisms (p_{j} : ∏_{i∈I} A_{i} ⟶ A_{j}|j ∈ I) is called a product, the morphisms p_{j} : ∏_{i∈I} A_{i} ⟶ A_{j} are called projections, if for each object T ∈ C and each family of morphisms (f_{i} : T ⟶ A_{i}|i ∈ I) there is a unique morphism [f_{i}|i ∈ I] : T ⟶ ∏_{i∈I} A_{i} such that for all j ∈ I the diagrams

[figure: ∏_{i∈I} A_{i}; A_{j}; p_{j}; T; [f_{i}]; f_{j}]

commute.

These products consist of an object and a family of projections and are denoted

(∏_{i∈I} A_{i}, (p_{j} : ∏_{i∈I} A_{i} ⟶ A_{j}|j ∈ I)).

We leave the details to the reader. If a category C has a product for any two objects in C then it is clear that it has products for any finite non-empty family of objects. If C has a product for any two objects in C and a terminal object then it has products for any finite family of objects.

2.7.9. Definition. (1) A category C is called a category with finite products, if there is

a product in C for any finite family of objects (empty families included).

(2) A category C is called a category with products, if there is a product in C for any

family of objects (empty families included).

17.06.04

The dual notion of a product the notion of a coproduct.

2.7.10. Definition. Let (A_{i}|i ∈ I) be a family of objects in a category C. An object ∐_{i∈I} A_{i} together with a family of morphisms (ι_{j} : A_{j} ⟶ ∐_{i∈I} A_{i}|j ∈ I) is called a coproduct, the morphisms ι_{j} : A_{j} ⟶ ∐_{i∈I} A_{i} are called injections, if for each object T ∈ C and each family of morphisms (f_{i} : A_{i} ⟶ T |i ∈ I) there is a unique morphism ⟨f_{i}|i ∈ I⟩ : ∐_{i∈I} A_{i} ⟶ T such that for all j ∈ I the diagrams

[figure: A_{j}; ∐_{i∈I} A_{i}; ι_{j}; T; ⟨f_{i}⟩; f_{j}]

commute.

2.7.11. Examples. (1) The Cartesian products of semigroups, monoids, groups, abelian groups, modules, vector spaces, rings, algebras, Lie algebras with componentwise operations are products.

(2) The Cartesian product of topological spaces with the product topology is a product. Here and in the first example the more precise statement is that there exist products and that the underlying functor to sets maps these products and their projections to Cartesian products. So there is a product structure on the Cartesian products of the underlying sets, but the product structure has to be determined in each case.

(3) In the category of fields there are in general no products.

(4) Let G and H be two graphs. The product G × H in the category of graphs and homomorphisms is defined as follows: (G × H)_{0} = G_{0} × H_{0}. An arrow from (g, h) to (g′; h′) is a pair (a, b) with a : g ⟶ g′ in G and b : h ⟶ h′ in H. The projections are the usual first and second projections.

(5) We have already seen in 1.3.8 that any poset (partially ordered set) has a corresponding category structure C(P). Let P be a poset and x and y two objects of C(P) (that is, elements of P). Let us see what, if anything, is their product. A product must be an element z together with a pair of arrows z ⟶ x and z ⟶ y, which is just another way of saying that z ≤ x and z ≤ y. The definition of product also requires that for any w ∈ P, given an arrow w ⟶ x and one w ⟶ y, there is an arrow w ⟶ z.

This translates to w ≤ x and w ≤ y implies w ≤ z which, together with the fact that z ≤ x and z ≤ y, characterizes z as the infimum of x and y, often denoted x ∧ y. Thus the existence of products in such a category is equivalent to the existence of infimums.

In particular, we see that products generalize a well- known construction in posets. Note that a poset that lacks infimums provides an easy example of a category without products.

(6) The product of categories as defined in 1.4.12 is the product of the categories in Cat.

(7) The coproduct of vector spaces is the direct sum.

(8) The coproduct of two abelian groups in the category of abelian groups is the direct sum or the product.

(9) The coproduct of two finite abelian groups (≠ 0) in the category of groups is an infinite nonabelian group.

2.7.12. Proposition. If A is an object in a category with a terminal object 1, then

[figure: 1; A; ⟨⟩; A; 1_{A}]

is a product diagram.

Proof. A cone over A and 1 has to have this form, where f : B ⟶ A is any arrow.

[figure: 1; A; ⟨⟩; A; 1_{A}; T; f; ⟨⟩; f]

Clearly the only possible arrow in the middle is f. □

2.7.13. Definition and Remark. Our notation A × B means that A × B is the vertex of a product cone with base the discrete diagram D with D(1) = A and D(2) = B. Then B × A denotes the product given by the diagram

[figure: B; B × A; p_{1}; A; p_{2}]

where we use p_{1} and p_{2} to avoid confusing them with the arrows proj_{1} and proj_{2} of the product diagram. (Of course, this is an ad hoc solution. If one had to deal with this situation a lot it would be necessary to introduce notation such as proj_{1}^{A,B} and proj_{1}^{B,A}.) Then this is a product diagram:

[figure: A; B × A; p_{2}; B; p_{1}]

It follows from Theorem 2.7.6 that there is an isomorphism [p_{2}, p_{1}] : B × A ⟶ A × B (called the switch morphism) that commutes with the projections. Its inverse is [proj_{2}, proj_{1}] : A×B ⟶ B × A.

2.8. Equalizers. If A and B are sets and f, g : A ⟶ B are functions, it is an important task to collect all solutions a ∈ A of the equation

f(a) = g(a).

This is more general that solving an equation f(a) = 0 since B does not necessarily contain some element 0. Again we want to apply the extension principle in this case.

2.8.1. Definition. If A and B are sets and f, g : A ⟶ B are functions, the equalizer Eq(f, g) is the subset Eq(f, g) ⊆ A consisting of all elements a ∈ A for which f(a) = g(a); in short,

Eq(f, g) = {a ∈ A|f(a) = g(a)}.

Together with the set Eq(f, g) there is the inclusion function j : Eq(f, g) ⟶ A.

To make this into a categorical concept and apply the extension principle, we first observe that Eq(f, g) is a subset of A. So it has a property that cannot directly be transfered to isomorphic sets. But there is a universal property connected with this notion that will give us the correct concept.

2.8.2. Proposition. Let A and B be sets and f, g : A ⟶ B be functions. The equalizer Eq(f, g) together with the inclusion map j : Eq(f, g) ⟶ A satisfies the following universal property:

• f ∘ j = g ∘ j; • for every set T and every map h : T ⟶ A, such that f ∘ h = g ∘ h, there is a unique

map k : B ⟶ Eq(f, g) such that the diagram

[figure: Eq(f, g); A; j; B; f; g; T; k; h]

commutes, i.e. j ∘ k = h.

Proof. We first show the uniqueness of the map k : T ⟶ Eq(f, g): Suppose that j : Eq(f, g) ⟶ A is the inclusion function: j(a) = a for a ∈ Eq(f, g). Given T and h. If k, k′ : T ⟶ Eq(f, g) are maps such that j ∘k = h = j ∘k′ then for any t ∈ T we have k(t) =: a ∈ Eq(f, g) and k′(t) =: a′ ∈ Eq(f, g). Then we get a = j(a) = (j ∘k)(t) = h(t) = (j ∘k′)(t) = j(a′) = a′, hence k(t) = a = h(t) = a′ = k′(t) and k = k′. This shows the uniqueness of the map k. Existence: From the uniqueness proof we obtain a reasonable definition of k. For t ∈ T we define k(t) := h(t). This is a map from T to Eq(f, g) since h(t) satisfies f(h(t)) = (f ∘h)(t) = (g ∘ h)(t) = g(h(t)). Then we get j ∘ k = h. □

Obviously any pair (E, ι) isomorphic to (Eq(f, g), j) satisfies the same universal property. In fact given an isomorphism i : E ⟶ Eq(f, g) such that

[figure: Eq(f, g); A; j; E; i; ι]

commutes. Let T be a set and h : T ⟶ A be a map such that f ∘ h = g ∘ h. Let k : T ⟶ Eq(f, g) be the unique map that satisfies j ∘ k = h. Then the map i^{−1} ∘ k : T ⟶ E satisfies ι ∘ (i^{−1} ∘ k) = j ∘ i ∘ i^{−1} ∘ k = j ∘ k = h. It is an easy exercise to show that this map is unique with this property. So the universal property given in the theorem satisfies the first property of the extension principle. To define the extension of the property for arbitrary categories we use again the special description of equalizers in sets as a subsets of A. In arbitrary categories we cannot construct an equalizer of two morphisms since there are no elements and we thus cannot construct the set of those elements on which the two maps coincide. But the extension principle 2.3.1 (2) provides the following definition.

2.8.3. Definition. Let A and B be objects in a category C and f, g : A ⟶ B be morphisms. An object Eq(f, g) together with a morphisms ι : Eq(f, g) ⟶ A is called a (categorical) equalizer of f and g, if for all objects T in C there is an isomorphism of sets

i : Mor_{C}(T, Eq(f, g)) ≅ Eq(Mor_{C}(T, f), Mor_{C}(T, g))

(where Eq(Mor_{C}(T, f), Mor_{C}(T, g)) is the set-theoretic equalizer from 2.8.1) such that the diagram

[figure: Eq(Mor_{C}(T, f), Mor_{C}(T, g)); Mor_{C}(T, A); j; Mor_{C}(T, Eq(f, g)); Mor_{C}(T, ι); i]

commutes.

Frequently, Eq(f, g) is referred to as an equalizer of f and g without referring to j. Nevertheless, j is a crucial part of the data. 18.06.04

2.8.4. Proposition (Characterization of equalizers by the universal mapping property). Given objects A and B and morphisms f, g : A ⟶ B in a category C. An object E together with a morphism ι : E ⟶ A is a (categorical) equalizer, if and only if for each object T ∈ C and each morphism h : T ⟶ A such that such that f ∘ h = g ∘ h, there is a unique map k : B ⟶ E such that the diagram

[figure: E; A; ι; B; f; g; T; k; h]

commutes, i.e. ι ∘ k = h.

Proof. ⟸: Let (E, ι) be an equalizer of f and g. Let T be an object in C and let k ∈ Mor_{C}(T, E). Define h := ι ∘ k : T ⟶ A. Then f ∘ h = f ∘ ι ∘ k = g ∘ ι ∘ k = g ∘ h and thus Mor_{C}(T, f)(h) = Mor_{C}(T, g)(h) so that h ∈ Eq(Mor_{C}(T, f), Mor_{C}(T, g)). Now we can define i(k) := h ∈ Eq(Mor_{C}(T, f), Mor_{C}(T, g)) and get Mor_{C}(T, ι)(k) = ι ∘ k = h ∈ Eq(Mor_{C}(T, f), Mor_{C}(T, g)). It remains to show that i is bijective. We construct the inverse map

u : Eq(Mor_{C}(T, f), Mor_{C}(T, g)) ⟶ Mor_{C}(T, E) u(h) := k

where h ∈ Eq(Mor_{C}(T, f), Mor_{C}(T, g)) implies Mor_{C}(T, f)(h) = Mor_{C}(T, f)(h). By the universal property of the equalizer there is a unique k : T ⟶ L such that ι ∘ k = h. We use this k for the definition of the map u. Let h ∈ Eq(Mor_{C}(T, f), Mor_{C}(T, g)). Then (i ∘ u)(h) = i(k) = ι ∘ k = h hence (i ∘ u) = 1_{Eq(Mor_{C}(T,f),Mor_{C}(T,g))}. Let k ∈ Mor_{C}(T, E). Then (u ∘ i)(k) = u(h) = u(ι ∘ k) = k′ where k′ : T ⟶ E is the unique morphism such that ι ∘ k′ = ι ∘ k hence k = k′ and (u ∘ i) = 1_{Mor_{C}(T,E)}. ⟹: If h : T ⟶ A is a morphism in C such that f ∘ h = g ∘ h. Then h is an element of Eq(Mor_{C}(T, f), Mor_{C}(T, g)), since Mor_{C}(T, f)(h) = Mor_{C}(T, g)(h). So there is a unique morphism k := i^{−1}(h) satisfying (j ∘ i)(k) = h or Mor_{C}(T, ι)(k) = h or ι ∘ k = h. Thus (E, ι) is an equalizer of f and g. □

2.8.5. Proposition. The family of isomorphisms

i_{T} : Mor_{C}(T, Eq(f, g)) ⟶ Eq(Mor_{C}(T, f), Mor_{C}(T, g))

such that

[figure: Eq(Mor_{C}(T, f), Mor_{C}(T, g)); Mor_{C}(T, A); j; Mor_{C}(T, Eq(f, g)); Mor_{C}(T, ι); i]

commute for all objects T in C, is a natural isomorphism in T and morphisms of (f, g).

Proof. is similar to the proof of Proposition 2.7.5. □

2.8.6. Examples. (1) In Set, an equalizer E of the functions (x, y) ↦ x^{2} +y^{2} and (x, y) ↦ 1 from ℝ × ℝ to ℝ is the circle x^{2} + y^{2} = 1. The arrow j : E ⟶ ℝ × ℝ is the inclusion.

(2) Given a graph G , the inclusion of the set of loops in the graph is an equalizer of the source and target functions. This equalizer will be empty if the graph has no loops.

A theorem like 2.7.6 is true of equalizers as well.

2.8.7. Proposition. If j : E ⟶ A and j′ : E′ ⟶ A are both equalizers of f, g : A ⟶ B, then there is a unique isomorphism i : E ⟶ E′ for which j′ ∘ i = j.

Proof. We give two proofs. The first uses the concept of universal element. Let C be the category containing the equalizers given. Let F : C^{op} ⟶ Set be the functor for which F(C) = {u : C ⟶ A|f ∘u = g ∘u}, the set of arrows from C which equalize f and g. If h : D ⟶ C let F(h)(u) = u ∘ h. This makes sense, because if u ∈ F (C), then f ∘ u ∘ h = g ∘ u ∘ h, so u ∘ h ∈ F (D). Note that this makes F a subfunctor of the contravariant hom functor Mor(-, A). The definition of an equalizer of f and g can be restated this way: an equalizer of f and g is an element j ∈ F(E) for some object E such that for any u ∈ F (C) there is a unique arrow k : C ⟶ E such that F(k)(j) = u. This means j is a universal element of F, so by Proposition 2.9.3, any two equalizers j ∈ F (E) and j′ ∈ F (E′) are isomorphic by a unique arrow i : E ⟶ E′ such that F (i)(j′) = j. That is, j = j′ ∘ i, as required. Here is a direct proof not using universal elements: the fact that f ∘ j′ = g ∘ j′ implies the existence of a unique arrow h : E′ ⟶ E such that j′ = j ∘h. The fact that f ∘j = g∘j implies the existence of a unique arrow h′ : E ⟶ E′ such that j = j′ ∘ h′. Then j ∘ h ∘ h′ = j′ ∘ h′ = j = j ∘ 1_{E} and the uniqueness part of the definition of equalizer implies that h ∘ h′ = 1_{E}. By symmetry, h′ ∘ h = 1_{E′}. □

We add some more properties of monomorphisms and equalizers.

2.8.8. Proposition. Let j : E ⟶ A be an equalizer of the pair of arrows f, g : A ⟶ B. Then j is a monomorphism. Moreover, any two equalizers of f and g belong to the same subobject of A.

Proof. To see that j is a monomorphism, suppose h, k : C ⟶ E with j ∘ h = j ∘ k = l. Then f ∘ l = f ∘ j ∘ k = g ∘ j ∘ k so there is a unique arrow m : C ⟶ E with j ∘ m = l. But both h and k are such arrows and so h = k. Now suppose j and j′ are equalizers of f and g. In the notation of Proposition 8.1.4, i and i^{−1} are the arrows required by the definition of subobject in 3.3.12, since j′ ∘ i = j and j ∘ i^{−1} = j′. □

8.1.6 More generally, if f_{1}, …, f_{n} are arrows from A to B, then an object E together with an arrow j : E ⟶ A is an equalizer of f_{1}, …, f_{n} if it has the property that an arbitrary arrow h : C ⟶ A factors uniquely through j if and only if f_{1} ∘ h = … = f_{n} ∘ h. Having equalizers of parallel pairs implies having equalizers of all finite lists.

2.8.9. Definition. A monomorphism e : S ⟶ T in a category is regular if e is an equalizer of a pair of arrows.

2.8.10. Proposition. An arrow in a category that is both an epimorphism and a regular monomorphism is an isomorphism.

Proof. Let f : A ⟶ B be both an epimorphism and an equalizer of g, h : B ⟶ C. Since g ∘ f = h ∘ f and f is epi, g = h. Then g ∘ 1_{B} = h ∘ 1_{B} so there is a k : B ⟶ A such that f ∘ k = 1_{B}. But then f ∘ k ∘ f = f = f ∘ 1_{A}. But f being a monomorphism can be canceled from the left to conclude that k ∘ f = 1_{A}. □

2.8.11. Proposition. Every monomorphism in Set is regular.

Proof. A monomorphism in Set is an injective function (see Theorem 3.3.3), so let f : A ⟶ B be an injective function. Let C be the set of all pairs {(b, i)|b ∈ B, i = 0, 1} and impose an equivalence relation on these pairs forcing (b, 0) = (b, 1) if and only if there is an a ∈ A with f(a) = b (and not forcing (b, i) = (c, j) if b and c are distinct). Since f is injective, if such an a exists, there is only one. Let g : B ⟶ C by g(b) = (b, 0) and h : B ⟶ C by h(b) = (b, 1). Then clearly g(b) = h(b) if and only if there is an a ∈ A with f(a) = b. Now let k : D ⟶ B with g ∘ k = h ∘ k. It must be that for all x ∈ D, there is an a ∈ A, and only one, such that k(x) = f(a). If we let l(x) = a, then l : D ⟶ A is the unique arrow with f ∘ l = k. □

2.8.12. Proposition. (1) Every split monomorphism in C is a regular monomorphism.

(2) Every regular monomorphism in C is a monomorphism.

Proof. (1) Let f : A ⟶ B be s split monomorphism with left inverse g : B ⟶ A, such that g ∘ f = 1_{A}. We claim that (A, f) is an equalizer of (f ∘ g, 1_{B}). We have (fg)f = f(gf) = f1_{A} = 1_{B}f. Now let h : T ⟶ B be a morphism with fgh = 1_{B}h = h. Then h = f(gh) so that we have a factorization gh of h through f. To show uniqueness let u : T ⟶ A satisfy h = fu. Then gh = gfu = 1_{A}u = u. (2) holds by Proposition 2.8.8. □

2.8.13. Remark. Functors preserve split monomorphisms. In general they do not preserve regular monomorphisms or monomorphisms. The next definition can again be viewed as a generalization of a set theoretic notion. We only give a direct definition.

2.8.14. Definition. Let f : A ⟶ B be a morphism in C. A triple (K, g : K ⟶ A, h : K ⟶ A) is a kernel pair of f if

(1) f ∘ g = f ∘ h,

(2) for each triple (T, u : T ⟶ A, v : T ⟶ A) satisfying f ∘ u = f ∘ v there is a unique k : T ⟶ K such that g ∘ k = u and h ∘ k = v, i.e. the following diagram commutes:

[figure: K; A; g; h; u; v; T; k; B; f]

2.8.15. Proposition. (1) Let f : B ⟶ C be a morphism in C that has a kernel pair

g, h : A ⟶ B. If f is a coequalizer then f is a coequalizer of g and h.

(2) Let g, h : A ⟶ B be a pair of morphisms that has a coequalizer f : B ⟶ C. If (A, g, h) is a kernel pair then it is a kernel pair of f.

Proof. (1) In the diagram

[figure: A; B; h; g; C; f; X; x; u; v; Y; k; C; y]

let (C, f) be the coequalizer of (u, v). Let (A, g, h) be a kernel pair of f. Then there is a unique morphism x such that gx = u and hx = v. Given k : B ⟶ Y with kg = kh. Then ku = kgx = khx = kv, so that there is a unique y : C ⟶ Y such that yf = k. Thus f is a coequalizer of g and h.

(2) Let (A, g, h) be a kernel pair of k and let (C, f) be a coequalizer of (g, h). Then there is a unique morphism y such that yf = k. Given u, v : X ⟶ B with fu = fv. Then ku = yfu = yfv = kv, so that there is a unique x : X ⟶ A such that gx = u and hx = v. Thus (A, g, h) is a kernel pair of f. □

24.06.04 2.8.16. Lemma. f : A ⟶ B is a monomorphism if and only if (A, 1_{A}, 1_{A}) is a kernel pair for f.

Proof. f monomorphism ⟺ ∀u, v : T ⟶ A : fu = fv ⟹ u = v ⟺ ∀u, v : T ⟶ A : fu = fv ⟹ ∃_{1}k : T ⟶ A : 1_{A}k = u, 1_{A}k = v ⟺ (A, 1_{A}, 1_{A}) kernel pair of f.

□

2.8.17. Corollary. If a functor preserves kernel pairs, the it preserves monomorphisms.

Proof. Let f : A ⟶ B be a monomorphism. Then (A,_{A} , 1_{A}) is a kernel pair for f. Thus (F (A), 1_{F (A)}, 1_{F (A)}) is a kernel pair of F (f), hence F (f) is a monomorphism. □

2.9. Universal elements. There is a second important way of defining a representable functor. We will show its impact with a number of examples.

2.9.1. Definition. Let F : C ⟶ Set be a covariant functor. A pair (A, x) with A ∈ C, x ∈ F(A) is called a universal (or generic) object for F, if for each B ∈ C and y ∈ F(B) there exists a unique f ∈ Mor_{C}(A, B) such that F(f)(x) = y:

[figure: A; B; f; F(A); F(B); F(f); ∋ x; ∋ y]

Let F : C ⟶ Set be a contravariant functor. A pair (A, x) with A ∈ C, x ∈ F(A) is called a (co-)universal (or (co-)generic) object for F, if for each B ∈ C and y ∈ F(B) there exists a unique f ∈ Mor_{C}(B, A) such that F(f)(x) = y:

[figure: A; B; f; F(A); F(B); F(f); ∋ x; ∋ y]

The following proposition is a version of the Yoneda Lemma and could also be derived from it.

2.9.2. Proposition. F has a universal element (A, a) if and only if F is representable, i.e. there is a natural isomorphism φ : F ≅ Mor_{C}(A, −) (with a = φ(A)^{−1}(1_{A})).

Proof. ⟹ : The map

φ(B) : F(B) ∋ y ↦ f ∈ Mor_{C}(A, B) with F(f)(a) = y

is bijective with the inverse map

ψ(B) : Mor_{C}(A, B) ∋ f ↦ F(f)(a) ∈ F(B).

In fact we have y ↦ f ↦ F(f)(a) = y and f ↦ y := F(f)(a) ↦ g such that F(g)(a) = y but then F(g)(a) = y = F(f)(a). By uniqueness we get f = g. Hence all φ(B) are bijective with inverse map ψ(B). It is sufficient to show that ψ is a natural transformation. Given g : B ⟶ C. Then the following diagram commutes

[figure: Mor_{C}(A, C); F(C); ψ(C); Mor_{C}(A, B); F(B); ψ(B); Mor_{C}(A,g); F(g)]

since ψ(C) Mor_{C}(A, g)(f) = ψ(C)(gf) = F(gf)(a) = F(g)F(f)(a) = F(g)ψ(B)(f). ⇐: Let A be given. Let a := φ(A)^{−1}(1_{A}). For y ∈ F(B) we get y = φ(B)^{−1}(f) = φ(B)^{−1}(f1_{A}) = φ(B)^{−1} Mor_{C}(A, f)(1_{A}) = F(f)φ(A)^{−1}(1_{A}) = F(f)(a) for a uniquely determined f ∈ Mor_{C}(A, B). □

2.9.3. Proposition. Let (A, x) and (B, y) be universal elements for F. Then there exists a unique isomorphism h : A ⟶ B such that F(h)(x) = y.

Proof. The proof follows from the following commutative diagram as in the proof of Theorem 2.7.6:

[figure: A; B; h; A; k; B; h; 1_{A}; 1_{A}; F(A); F(B); F(h); F(A); F(k); F(B); F(h); 1_{F(A)}; 1_{F(B)}; x; y; x; y]
□

2.9.4. Examples. (1) Let R be a ring. Let X ∈ Set be a set. F : R- Mod ⟶ Set, F(M) := Map(X, M) is a covariant functor. A representing object for F is given by the free R-module (RX, x : X ⟶ RX) with the property, that for all (M, y : X ⟶ M) there exists a unique f ∈ Mor_{R}(RX, M) such that F(f)(x) = Map(X, f)(x) = fx = y

[figure: X; RX; x; y; M.; f]

(2) Given modules M_{R} and _{R}N (or vector spaces M_{K} and _{K}N). Define F : Ab ⟶ Set by F(A) := Bil_{R}(M, N; A). Then F is a covariant functor. A representing object for F is given by the tensor product (M ⊗_{R} N, ⊗ : M × N ⟶ M ⊗_{R} N) with the property that for all (A, f : M × N ⟶ A) there exists a unique g ∈ Mor(M ⊗_{R} N, A) such that F(g)(⊗) = Bil_{R}(M, N; g)(⊗) = g⊗ = f

[figure: M × N; M ⊗_{R} N; ⊗; f; A.; g]

(3) Given a K-module V. Define F : K- Alg ⟶ Set by F(A) := Mor(V, A). Then F is a covariant functor. A representing object for F is given by the tensor algebra (T (V), ι : V ⟶ T (V)) with the property that for all (A, f : V ⟶ A) there exists a unique g ∈ Mor_{Alg}(T (V), A) such that F(g)(ι) = Mor(V, g)(ι) = gι = f

[figure: V; T (V); ι; f; A.; g]

(4) Given a K-module V. Define F : K- cAlg ⟶ Set by F(A) := Mor(V, A). Then F is a covariant functor. A representing object for F is given by the symmetric algebra (S(V), ι : V ⟶ S(V)) with the property that for all (A, f : V ⟶ A) there exists a unique g ∈ Mor_{cAlg}(S(V), A) such that F(g)(ι) = Mor(V, g)(ι) = gι = f

[figure: V; S(V); ι; f; A.; g]

(5) Given a K-module V. Define F : K- Alg ⟶ Set by

F(A) := {f ∈ Mor(V, A)|∀v, v′ ∈ V : f(v)f(v′) = f(v′)f(v)}.

Then F is a covariant functor. A representing object for F is given by the symmetric algebra (S(V), ι : V ⟶ S(V)) with the property that for all (A, f : V ⟶ A) such that f(v)f(v′) = f(v′)f(v) for all v, v′ ∈ V there exists a unique g ∈ Mor_{Alg}(S(V), A) such that F(g)(ι) = Mor(V, g)(ι) = gι = f

[figure: V; S(V); ι; f; A.; g]

(6) Given a K-module V. Define F : K- Alg ⟶ Set by

F(A) := {f ∈ Mor(V, A)|∀v ∈ V : f(v)^{2} = 0}.

Then F is a covariant functor. A representing object for F is given by the exterior algebra (E(V), ι : V ⟶ E(V)) with the property that for all (A, f : V ⟶ A) such that f(v)^{2} = 0 for all v ∈ V there exists a unique g ∈ Mor_{Alg}(E(V), A) such that F(g)(ι) = Mor(V, g)(ι) = gι = f

[figure: V; E(V); ι; f; A.; g]

(7) Let K be a commutative ring. Let X ∈ Set be a set. F : K- cAlg ⟶ Set, F(A) := Map(X, A) is a covariant functor. A representing object for F is given by the polynomial ring (K[X], ι : X ⟶ K[X]) with the property, that for all (A, f : X ⟶ A) there exists a unique g ∈ Mor_{cAlg}(K[X], A) such that F(g)(ι) = Map(X, g)(x) = gι = f

[figure: X; K[X]; ι; f; A.; g]

(8) Let K be a commutative ring. Let X ∈ Set be a set. F : K- Alg ⟶ Set, F(A) := Map(X, A) is a covariant functor. A representing object for F is given by the noncommutative polynomial ring (K⟨X⟩, ι : X ⟶ K⟨X⟩) with the property, that for all (A, f : X ⟶ A) there exists a unique g ∈ Mor_{Alg}(K⟨X⟩, A) such that F(g)(ι) = Map(X, g)(x) = gι = f

[figure: X; K⟨X⟩; ι; f; A.; g]

(9) Let S be a set. A function f : ℝ ⟶ S is called of period 2π if f(x + 2π) = f(x) for all x ∈ ℝ. Define F : Set ⟶ Set by F(S) = {f : ℝ ⟶ S|f is of period 2π}. Obviously F is a functor. We want a ”‘universal function of period 2π”’. Let S^{1} := ℝ/2πℤ be the unit circle and w : ℝ ⟶ S^{1} be the ”‘wrapping”’ of ℝ onto S^{1}. Each periodic function f : ℝ ⟶ S

can be written uniquely as ℝ ⟶^{w} S^{1} ⟶^{\overline{f}} S. This means w ∈ F(S^{1}) and for each f ∈ F(S) there is a unique map \overline{f} : S^{1} ⟶ S such that F(\overline{f})(w) = \overline{f} ∘ w = f. So (S^{1}, w) is a universal element for F:

[figure: ℝ; S^{1}; w; f; S.; \overline{f}]

(10) Let F be as in (9). Let J := {x ∈ ℝ|0 ≤ x < 2π} and t : ℝ ⟶ J be given by t(y) := x ⟺ y − x = 2πn for some n ∈ ℤ. Obviously t is a function of period 2π. For a function f : ℝ ⟶ S of period 2π there is a unique f̃: J ⟶ S such that F(f̃)(t) = f ∈ F(S). Thus (J, t) is a universal element for F:

[figure: ℝ; J; t; f; S.; f̃]

By Proposition 2.9.3 we get (S^{1}, w) ≅ (J, t).

25.06.04 2.9.5. Proposition. Let D be a category. Given a representable functor F_{X} : C ⟶ Set for each X ∈ D. Given a natural transformation F_{g} : F_{Y} ⟶ F_{X} for each g : X ⟶ Y (contravariant!) such that F depends functorially on X, i.e. F_{1_{X}} = 1_{F_{X}}, F_{hg} = F_{g}F_{h}. Then the representing objects (A_{X}, a_{X}) for F_{X} depend functorially on X, i.e. for each g : X ⟶ Y there is a unique morphism A_{g} : A_{X} ⟶ A_{Y} (with F_{X}(A_{g})(a_{X}) = F_{g}(A_{Y})(a_{Y})) and the following identities hold A_{1_{X}} = 1_{A_{X}}, A_{hg} = A_{h}A_{g}. So we get a covariant functor D ∋ X ⟶ A_{X} ∈ C.

Proof. Choose a representing object (A_{X}, a_{X}) for F_{X} for each X ∈ D (by the axiom of choice). Then there is a unique morphism A_{g} : A_{X} ⟶ A_{Y} with

F_{X}(A_{g})(a_{X}) = F_{g}(A_{Y})(a_{Y}) ∈ F_{X}(A_{Y}),

for each g : X ⟶ Y because F_{g}(A_{Y}) : F_{Y} (A_{Y}) ⟶ F_{X}(A_{Y}) is given. We have F_{X}(A_{1})(a_{X}) = F_{1}(A_{X})(a_{X}) = a_{X} = F_{X}(1)(a_{X}) hence A_{1} = 1, and F_{X}(A_{hg})(a_{X}) = F_{hg}(A_{Z})(a_{Z}) = F_{g}(A_{Z})F_{h}(A_{Z})(a_{Z}) = F_{g}(A_{Z})F_{Y} (A_{h})(a_{Y}) = F_{X}(A_{h})F_{g}(A_{Y})(a_{Y}) = F_{X}(A_{h})F_{X}(A_{g})(a_{X}) = F_{X}(A_{h}A_{g})(a_{X}) hence A_{h}A_{g} = A_{hg} for g : X ⟶ Y and h : Y ⟶ Z in D. □

2.9.6. Corollary. (1) Map(X, M) ≅ Mor_{R}(RX, M) is a natural transformation in M (and in X!). In particular Set ∋ X ↦ RX ∈ R- Mod is a functor.

(2) Bil_{R}(M, N; A) ≅ Mor(M ⊗_{R} N, A) is a natural transformation in A (and in (M, N) ∈ Mod -R × R- Mod). In particular Mod -R × R- Mod ∋ M, N ↦ M ⊗_{r} N ∈ Ab is a functor.

(3) R- Mod -S × S- Mod -T ∋ (M, N) ↦ M ⊗_{S} N ∈ R- Mod -T is a functor.

2.10. The Yoneda Lemma. If F : C ⟶ D and G : C ⟶ D are functors then we denote with Nat(F, G) the set of natural transformations from F to G. Actually this is an illegal set, it may be too large. In our applications, however, it will be isomorphic to a set so that we don’t run into problems. If C is a small category then there are no problems either, since each natural transformation is a family of morphisms indexed by a set.

2.10.1. Theorem. (Yoneda Lemma) Let C be a category. Given a covariant functor F : C ⟶ Set and an object A ∈ C. Then the map

π : Nat(Mor_{C}(A, -), F) ∋ ϕ ↦ ϕ(A)(1_{A}) ∈ F(A)

is bijective with the inverse map

π^{−1} : F(A) ∋ a ↦ h^{a} ∈ Nat(Mor_{C}(A, -), F),

where h^{a}(B)(f) = F(f)(a).

Proof. For ϕ ∈ Nat(Mor_{C}(A, -), F) we have a map ϕ(A) : Mor_{C}(A, A) ⟶ F(A), hence π with π(ϕ) := ϕ(A)(1_{A}) is a well defined map. For π^{−1} we have to check that h^{a} is a natural transformation. Given f : B ⟶ C in C. Then the diagram

[figure: F(B); F(C); F(f); Mor_{C}(A, B); Mor_{C}(A, C); Mor(A,f); h^{a}(B); h^{a}(C)]

is commutative. In fact if g ∈ Mor_{C}(A, B) then h^{a}(C) Mor_{C}(A, f)(g) = h^{a}(C)(fg) = F(fg)(a) = F(f)F(g)(a) = F(f)h^{a}(B)(g). Thus π^{−1} is well defined. Let π^{−1}(a) = h^{a}. Then ππ^{−1}(a) = h^{a}(A)(1_{A}) = F(1_{A})(a) = a. Let π(ϕ) = ϕ(A)(1_{A}) = a. Then π^{−1}π(ϕ) = h^{a} and h^{a}(B)(f) = F(f)(a) = F(f)(ϕ(A)(1_{A})) = ϕ(B) Mor_{C}(A, f)(1_{A}) = ϕ(B)(f), hence h^{a} = ϕ. □

2.10.2. Corollary. Given A, B ∈ C. Then the following hold

(1) Mor_{C}(A, B) ∋ f ↦ Mor_{C}(f, -) ∈ Nat(Mor_{C}(B, -), Mor_{C}(A, -)) is a bijective map.

(2) Under the bijective map from (1) the isomorphisms in Mor_{C}(A, B) correspond to natural isomorphisms in Nat(Mor_{C}(B, -), Mor_{C}(A, -)).

(3) For contravariant functors F : C ⟶ Set we have Nat(Mor_{C}(-, A), F) ≅ F(A).

(4) Mor_{C}(A, B) ∋ f ↦ Mor_{C}(-, f) ∈ Nat(Mor_{C}(-, A), Mor_{C}(-, B)) is a bijective map that defines a one-to-one correspondence between the isomorphisms in Mor_{C}(A, B) and the natural isomorphisms in Nat(Mor_{C}(-, A), Mor_{C}(-, B)).

Proof. (1) follows from the Yoneda Lemma with F = Mor_{C}(A, -).

(2) Observe that h^{f}(C)(g) = Mor_{C}(A, g)(f) = gf = Mor_{C}(f, C)(g) hence h^{f} = Mor_{C}(f, -). Since we have Mor_{C}(f, -) Mor_{C}(g, -) = Mor_{C}(gf, -) and Mor_{C}(f, -) = id_{Mor_{C}(A,-)} if and only if f = 1_{A} we get the one-to-one correspondence between the isomorphisms from (1).

(3) and (4) follow by dualizing. □

2.10.3. Remark. The map π is a natural transformation in the arguments A and F. More precisely: if f : A ⟶ B and ϕ : F ⟶ G are given then the following diagrams commute

[figure: Nat(Mor_{C}(A, -), G); G(A); π; Nat(Mor_{C}(A, -), F); F(A); π; Nat(Mor(A,-),ϕ); ϕ(A)]

[figure: Nat(Mor_{C}(B, -), F); F(B).; π; Nat(Mor_{C}(A, -), F); F(A); π; Nat(Mor(f,-),F); F(f)]

This can be easily checked. Indeed we have for ψ : Mor_{C}(A, -) ⟶ F

π Nat(Mor_{C}(A, -), ϕ)(ψ) = π(ϕψ) = (ϕψ)(A)(1_{A}) = ϕ(A)ψ(A)(1_{A}) = ϕ(A)π(ψ)

and

π Nat(Mor_{C}(f, -), F)(ψ) = π(ψ Mor_{C}(f, -)) = (ψ Mor_{C}(f, -))(B)(1_{B}) = ψ(B)(f) = ψ(B) Mor_{C}(A, f)(1_{A}) = F(f)ψ(A)(1_{A}) = F(f)π(ψ).

2.10.4. Remark. By the previous corollary the representing object A is uniquely determined up to isomorphism by the isomorphism class of the functor Mor_{C}(A, -).

2.10.5. Proposition. Let G : C × D ⟶ Set be a covariant bifunctor such that the functor G(C, -) : D ⟶ Set is representable for all C ∈ C. Then there exists a contravariant functor F : C ⟶ D such that G ≅ Mor_{D}(F-, -) holds. Furthermore F is uniquely determined by G up to isomorphism.

Proof. For each C ∈ C choose an object F(C) ∈ D and an isomorphism ξ_{C} : G(C, -) ≅ Mor_{D}(F(C), -). Given f : C ⟶ C′ in C then let F(f) : F(C′) ⟶ F(C) be the uniquely determined morphism (by the Yoneda Lemma) in D such that the diagram

[figure: G(C′, -); Mor_{D}(F(C′), -); ξ_{C′}; G(C, -); Mor_{D}(F(C), -); ξ_{C}; G(f,-); Mor(F(f),-)]

commutes. Because of the uniqueness of F(f) and because of the functoriality of G it is easy to see that F(fg) = F(g)F(f) and F(1_{C}) = 1_{F(C)} hold and that F is a contravariant functor. If F′ : C ⟶ D is given with G ≅ Mor_{D}(F′-, -) then ϕ : Mor_{D}(F-, -) ≅ Mor_{D}(F′-, -). Hence by the Yoneda Lemma ψ(C) : F(C) ≅ F′(C) is an isomorphism for all C ∈ C. With these isomorphisms induced by ϕ the diagram

[figure: Mor_{D}(F′(C′), -); Mor_{D}(F(C′), -); Mor(ψ(C′),-); Mor_{D}(F′(C), -); Mor_{D}(F(C), -); Mor(ψ(C),-); Mor(F′(f),-); Mor(F(f),-)]

commutes. Hence the diagram

[figure: F(C); F′(C); ψ(C); F(C′); F′(C′); ψ(C′); F′(f); F(f)]

commutes. Thus ψ : F ⟶ F′ is a natural isomorphism. □

2.10.6. Remark. The Yoneda Lemma says in principle that we can recover (all properties of) an object A from the contravariant functor Mor_{C}(-, A). Corollary 2.10.2 says that we can also recover a morphism f from the natural transformation Mor_{C}(-, f). More importantly any natural transformation φ : Mor_{C}(-, A) ⟶ Mor_{C}(-, B) is of the form φ = Mor_{C}(-, f) for some f : A ⟶ B. So we get the following Theorem.

2.10.7. Theorem (The Yoneda Embedding). Let C be a (small) category. Then the functor h : C ⟶ Func(C^{op}, Set) with h(A) = Mor_{C}(-, A) and h(f) = Mor_{C}(-, f) is full and faithful. In particular C is equivalent to a full subcategory of Func(C^{op}, Set).

2.10.8. Theorem (Cayley). Every group G is isomorphic to a group of permutations.

Sketch of Proof.

1. First, define the Cayley representation \overline{G} of G to be the following group of permutations: the underlying set of \overline{G} is just G, and for each g ∈ G, we have the permutation \overline{g}, defined for all h ∈ G by: \overline{g}(h) = g · h. Now check that \overline{g} = \overline{h} implies g = h.

2. Next define homomorphisms i : G ⟶ \overline{G} by i(g) = \overline{g}, and j : \overline{G} ⟶ G by j(\overline{g}) = g.

3. Finally show that i ∘ j = 1\overline{G} and j ∘ i = 1_{G}. □

2.10.9. Remark. Warning: Note the two different levels of isomorphisms that occur in the proof of Cayley’s theorem. There are permutations of the set of elements of G, which are isomorphisms in Set, and there is the isomorphism between G and \overline{G}, which is in the category Groups of groups and group homomorphisms. Cayley’s theorem says that any abstract group can be represented as a “concrete” one, i.e. a group of permutations of a set. The theorem can be generalized to show that any category can be represented as one that is “concrete”, i.e. a category of sets and functions.

2.10.10. Theorem. Every category C is isomorphic to one in which the objects are sets and the arrows are functions. (One should really require here that C is small.)

Sketch of Proof. Define the Cayley representation of C to be the following concrete category: • objects are sets of the form:

\overline{C} = \{f ∈ C| cod(f) = C\}

for all C ∈ C, • arrows are functions

\overline{g} : \overline{C} ⟶ \overline{D},

for g : C ⟶ D in C, defined by \overline{g}(f) = g ∘ f.

□

2.11. Algebraic Structures.

Algebraic structures are defined by operations, i.e. by composition maps from products of a set to the set itself, together with additional equations. These operations lead to natural transformations. Again monoids are the first interesting example. We consider the category Mon of monoids and the underlying functor U : Mon ⟶ Set. First we translate the definition of a monoid into a category theoretical version.

2.11.1. Definition. Let C be a category with finite products. A monoid in C is a triple (M, mult, e_{M}) where

(1) M is an object in C,

(2) mult : M × M ⟶ M is a morphism in C,

(3) e_{M} : 1 ⟶ M is a morphism in C with 1 a terminal object. such that the following diagrams commute:

[figure: M × M × M; M × M; M × mult; M × M; M; mult; mult ×M; mult]

and

[figure: ≅ M ≅ M × 1; M × M; 1_{M} × e_{M}; M × M; M; mult; 1 × M; e_{M} × 1_{M}; mult; 1_{M}]

We note that the unit element is replaced by a variable element e_{M} : 1 ⟶ A. In the category Set of sets a terminal object is a one-point set (or singleton). An element in m ∈ M defines a unique map m_{M} : 1 ⟶ M, in fact M and M(1) are isomorphic sets. In case of the unit element m = e this leads to e_{M} : {∗} ⟶ M with e_{M}(∗) = e ∈ M. So in the case of sets this

01.07.04 map makes the last diagram commutative. The conditions for a (homo-)morphism of monoids f : M ⟶ N translate to commutative diagrams

(15)  [figure: M × M; M; mult; N × N; N; mult; f × f; f; and; 1; M; e_{M}; 1; N; e_{N}; 1_{1} = f^{0}; f]

It is easy to see that the composition of morphisms of monoids is again a morphism of monoids. One also has that the identity morphism 1_{M} in C is a morphism of monoids for all monoids (M, mult, e_{M}) in C. So we can define the category of monoids Mon_{C} in an arbitrary category C.

All other algebraic structures as long as they are defined by operations and equations (equationally defined algebraic structures) can be treated in the same way. Examples abound: semigroups, groups, abelian groups, rings, vector spaces over a (set-theoretic) field 𝕂, 𝕂algebras, R-modules, Lie algebras, Jordan algebras, semirings, etc. An easy example of an algebraic structure is the case of unary operations u : S ⟶ S as discussed in 1.7.21. These operations play an important role in the study of endomorphisms of vector spaces, i.e. of square matrices.

2.11.2. Remark (Vector spaces). The case of 𝕂-vector spaces and R-modules contains an interesting variant. Since 𝕂 will not be an object in C in general the question arises how to define the action of 𝕂 on vector spaces. This is done by considering each element α ∈ 𝕂 as an endomorphism for the vector space object V in C, so each α ∈ 𝕂 induces α· : V ⟶ V in C. The relevant equations for a vector space are then written as equations of morphisms. For this purpose we first consider the structure of an abelian group on V.

2.11.3. Definition. Let C be a category with finite products. A group in a category C is a quadruple (V, +, 0, −) where

(1) V is an object in C,

(2) + : V × V ⟶ V is a morphism, the addition,

(3) 0 : 1 ⟶ V is a morphism, the neutral elements,

(4) − : V ⟶ V is a morphism, the inverse, such that

[figure: V × V × V; V × V; V × +; V × V; V; +; + × V; +]

[figure: ≅ V ≅ V × 1; V × V; 1_{V} × 0; V × V; V; +; 1 × V; 0 × 1_{V}; +; 1_{V}]

[figure: V; 1; ⟨⟩; 1; V; 0; V × V; V × V; 1_{V} × −; [1_{V} , 1_{V}]; +; and; V; 1; ⟨⟩; 1; V; 0; V × V; V × V; − × 1_{V}; [1_{V} , 1_{V}]; +]

A group is called abelian or commutative if in addition the following diagram commutes

[figure: V × V; V × V; [p_{2}, p_{1}]; V; +; +]

where [p_{2}, p_{1}] is the switch morphism of 2.7.13.

This definition allows us to define groups in many categories. Examples are groups in Top, called topological groups, groups in the category of analytical manifolds, called analytical groups, groups in the dual category of the category of commutative algebras, called commutative Hopf algebras. We denote the category of groups resp. abelian groups in C by Gr −C resp. Ab −C.

2.11.4. Lemma. Let V = (V, +, 0, −) be an Abelian group in C. Then Mor_{Ab −C}(V, V) is a ring with unit.

Proof. The addition is given by

f + g := (V ⟶^{[1_{V} ,1_{V} ]} V × V ⟶^{f×g} V × V ⟶^{+} V).

The morphism [1_{V} , 1_{V}] is usually abbreviated by Δ. It makes the following diagram commutative:

[figure: V; V × V; Δ; V × V; V × V × V; 1_{V} × Δ; Δ; Δ × 1_{V}]

i.e. it is coassociative. Then

(f + g) + h = + ∘ ((f + g) × h) ∘ Δ
= + ∘ ((+ ∘ (f × g) ∘ Δ) × h) ∘ Δ
= + ∘ (+ × 1_{V}) ∘ (f × g × h) ∘ (Δ × 1_{V}) ∘ Δ
= + ∘ (1_{V} × +) ∘ (f × g × h) ∘ (1_{V} × Δ) ∘ Δ
= f + (g + h).

Since we will prove a more general result in ??? we leave it to the reader to check that V ⟶^{⟨⟩} 1 ⟶^{0} V is the neutral element for the addition on Mor_{Ab −C}(V, V) and that V ⟶^{f} V ⟶^{−} V is the additive inverse of f. The multiplication on Mor_{Ab −C}(V, V) is defined to be the composition of morphisms, so it is associative with unit element. The multiplication is distributive since

f ∘ (g + h) = f ∘ + ∘ (g × h) ∘ Δ
= + ∘ (f × f) ∘ (g × h) ∘ Δ
= + ∘ ((f ∘ g) × (f ∘ h)) ∘ Δ
= (f ∘ g) + (f ∘ h),

by the fact that f is a morphism of abelian groups, and

(f + g) ∘ h) = + ∘ (f × g) ∘ Δ ∘ h
= + ∘ (f × g) ∘ (h × h) ∘ Δ
= + ∘ ((f ∘ h) × (g ∘ h)) ∘ Δ
= (f ∘ h) + (g ∘ h),

by an easy property of Δ. □

So a 𝕂-vector space in C can be defined as follows:

2.11.5. Definition. Let 𝕂 be a field. A vector space in a category C with finite products consists of an abelian group V ∈ C together with a ring homomorphism · : 𝕂 ⟶ Mor_{Ab −C}(V, V).

So we get a unary operation for each element α ∈ 𝕂. This example shows that there may be infinitely many different operations on an algebraic structure in C.

There is another point of view that produces many natural transformations. Again we use the example of monoids. Observe first that there is an underlying functor U : Mon_{C} ⟶ C like in the case of sets and ordinary monoids. Then the diagrams 15 can be rewritten as

[figure: U(M) × U(M); U(M); mult; U(N) × U(N); U(N); mult; U(f) × U(f); U(f); and; 1; U(M); e_{M}; 1; U(N); e_{N}; 1_{1} = f^{0}; U(f)]

These diagrams commute for any choice of monoid morphism f : M ⟶ N. They show that mult and e are natural transformations. mult is a natural transformation from the functor U ×U : Mon_{C} ⟶ C to the underlying functor U : Mon_{C} ⟶ C. It is easy the check that U ×U is a functor in one variable. The interpretation of the second diagram is a bit more subtle. As first functor we use the one point functor E : Mon_{C} ⟶ C with E((M, mult, e)) := 1 for any monoid in C and E(f) := 1_{1}, the identity. Then it is clear that e : 1 ⟶ M defines also a natural transformation e : E ⟶ U. Again any operation of any equationally defined algebraic structure can be considered as a natural transformation. We close this section with a theorem that leads us back to the extension principle.

2.11.6. Theorem. Let C be a category with finite products. An object G in C is a group if and only if the contravariant functor Mor_{C}(-, G) : C ⟶ Set can be factored through the category of groups, i.e. there is a contravariant functor G : C ⟶ Gr from C to the category Gr of groups such that Mor_{C}(-, G) = U ∘ G, where U : Gr ⟶ Set is the underlying functor.

The construction given in the following proof will show more, namely that there is a bijection between the group structures on G and the different possible factorizations G. The statement of the Theorem also holds for any other equationally defined algebraic structures. A given factorization G of Mor_{C}(-, G) can also be viewed as a group structure for G, so we see another example of the extension principle. This variant of a definition for a group structure can also be given without any finite products, so that it is in fact more general than the definition, we have given for a group in a category.

Proof. The Yoneda Lemma defines a bijection between the set of morphisms f : X ⟶ Y and the set of natural transformations f(-) : X(-) ⟶ Y (-) by f(Z) = Mor_{C}(Z, f). In particular we have m_{X} = Mor_{C}(X, m) = m(X). The diagram

[figure: G(-) × G(-) × G(-); G(-) × G(-); m-×1; G(-) × G(-); G(-); m-; 1×m-; m-]

commutes if and only if Mor_{C}(-, m(m × 1)) = Mor_{C}(-, m)(Mor_{C}(-, m) × 1) = m-(m- × 1) = m-(1 × m-) = Mor_{C}(-, m)(1 × Mor_{C}(-, m)) = Mor_{C}(-, m(1 × m)) if and only if m(m × 1) = m(1 × m) if and only if the diagram

[figure: G × G × G; G × G; m×1; G × G; G; m; 1×m; m]

commutes. In a similar way one shows the equivalence of the other diagram(s). □

02.07.04 2.11.7. Remark. Let C be a category with finite products. A morphism f : G ⟶ G′ in C is a homomorphism of groups if and only if

[figure: G × G; G; m; G′ × G′; G′; m′; f×f; f]

commutes.

2.11.8. Definition. A cogroup (comonoid) G in C is a group (monoid) in C^{op}, i.e. an object G ∈ Ob C = Ob C^{op} together with a natural transformation m(X) : G(X) × G(X) ⟶ G(X) where G(X) = Mor_{C^{op}}(X, G) = Mor_{C}(G, X), such that (G(X), m(X)) is a group (monoid) for each X ∈ C.

2.11.9. Remark. Let C be a category with finite (categorical) coproducts. An object G in C carries the structure m : G(-) × G(-) ⟶ G(-) of a cogroup in C if and only if there are morphisms Δ : G ⟶ G ⨿ G, ε : G ⟶ I, and S : G ⟶ G such that the diagrams

[figure: G ⨿ G; G ⨿ G ⨿ G; Δ⨿1; G; G ⨿ G; Δ; 1⨿Δ; Δ; G ⨿ G; I ⨿ G ≅ G ≅ G ⨿ I; ε⨿1; G; G ⨿ G; Δ; 1⨿ε; Δ; 1]

[figure: G; I; G; ε; G ⨿ G; G ⨿ G; 1⨿S; S⨿1; Δ; ∇]

commute where ∇ is dual to the morphism Δ defined in [?] ??. The multiplications are related by Δ_{X} = Mor_{C}(Δ, X) = Δ(X). Let C be a category with finite coproducts and let G and G′ be cogroups in C. Then a homomorphism of groups f : G′ ⟶ G is a morphism f : G ⟶ G′ in C such that the diagram

[figure: G; G × G; Δ; G′; G′ × G′; Δ′; f×f; f]

commutes. An analogous result holds for comonoids.

2.11.10. Remark. Obviously similar observations and statements can be made for other algebraic structures in a category C. So one can introduce vector spaces and covector spaces, monoids and comonoids, rings and corings in a category C. The structures can be described by morphisms in C if C is a category with finite (co-)products.

2.11.11. Proposition. Let G ∈ C be a group with multiplication a ∗ b, unit e, and inverse a^{−1} in G(X). Then the morphisms m : G × G ⟶ G, u : E ⟶ G, and S : G ⟶ G are given by

m = p_{1} ∗ p_{2},  u = e_{E},  S = id_{G}^{−1}.

Proof. By the Yoneda Lemma 2.10.1 these morphisms can be constructed from the natural transformation as follows. Under Mor_{C}(G×G, G×G) = G×G(G×G) ≅ G(G×G)×G(G× G) ⟶^{∗} G(G × G) = Mor_{C}(G × G, G) the identity id_{G×G} = (p_{1}, p_{2}) is mapped to m = p_{1} ∗ p_{2}. Under Mor_{C}(E, E) = E(E) ⟶ G(E) = Mor_{C}(E, G) the identity of E is mapped to the neutral element u = e_{E}. Under Mor_{C}(G, G) = G(G) ⟶ G(G) = Mor_{C}(G, G) the identity is mapped to its ∗-inverse S = id_{G}^{−1}. □

2.11.12. Corollary. Let G ∈ C be a cogroup with multiplication a ∗ b, unit e, and inverse a^{−1} in G(X). Then the morphisms Δ : G ⟶ G ⨿ G, ε : G ⟶ I, and S : G ⟶ G are given by

Δ = ι_{1} ∗ ι_{2},  ε = e_{I},  S = id_{G}^{−1}.

2.12. Limits. Equalizers and products are special cases of the general notion of a (categorical) limit. Limits can also be described as a generalization of a set theoretic construction with the extension principle. We will, however, use the short way and give a direct definition and cover the relation to limits on sets by an extra proposition.

2.12.1. Definition. (1) Let D be a (shape) graph and F : D ⟶ C be a diagram. A limit or projective limit of F consists of

• an object \underleftarrow{lim} F in C together with

• a family of morphisms (p_{A} : \underleftarrow{lim} F ⟶ F (A)| for all vertices A ∈ D) called projections, with commuting triangles

[figure: F (A); F (B); F (f); \underleftarrow{lim} F; p_{A}; p_{B}]

for all edges f : A ⟶ B in D, if the following universal property is satisfied:

(*) for each – object T in C and each

– family of morphisms (f_{A} : T ⟶ F (A)| for all vertices A ∈ D), with commuting triangles

[figure: F (A); F (B); F (f); T; f_{A}; f_{B}]

for all edges f : A ⟶ B in D, there is a unique morphism g : T ⟶ \underleftarrow{lim} F such that the triangles

[figure: T; \underleftarrow{lim} F; g; F (A); f_{A}; p_{A}]

commute for all vertices A ∈ D.

(2) If there is a limit for each diagram F : D ⟶ C of shape D then C is called D-complete. We also say that C has limits of shape D.

(3) If there is a limit for all diagrams F : D ⟶ C in C (for all D), then C is called complete.

2.12.2. Remark. Limits are unique up to isomorphism. This can be proved essentially the same way as the uniqueness of products up to isomorphism (Proposition 2.7.6) or the uniqueness of equalizers up to isomorphism (Proposition 2.8.7). It is indeed a special case of the uniqueness of a universal element (Proposition 2.9.3). The connection with a universal element will be given by the next theorem.

2.12.3. Examples. (1) Let D be an empty graph. Then a limit of a diagram consists of an object E, such that for each object T there is a unique morphism g : T ⟶ E. This is the definition of a terminal object E.

(2) Let D be a set of two vertices without any edges. Then a diagram consists of two objects A and B. A limit consists of an object A × B and two morphisms p_{A} : A × B ⟶ B and p_{B} : A×B ⟶ B. The universal property says that for each object T and any two morphisms f_{A} : T ⟶ A and f_{B} : T ⟶ A × B there is a unique morphism (f, g) : T ⟶ A × B such that p_{A} ∘ (f_{A}, f_{B}) = f_{A} and p_{B} ∘ (f_{A}, f_{B}) = f_{B}. So this gives the definition of a product of two objects. If D has an arbitray set I of vertices and an empty set of edges, then a limit of F : D ⟶ C

08.07.04 is the product ∏_{i∈I} A_{i} with A_{i} := F (i). (3) Let D consist of two vertices 1 and two and two edges

[figure: 1; 2.; i; j]

Then a limit of a diagram

[figure: A; B; f; g]

consists of an object K := \underleftarrow{lim} F and two morphisms ι : K ⟶ A and λ : KtoB such that f ∘ ι = λ = g ∘ ι which is universal. Obviously λ is uniquely determined by ι, so it is superfluous and we have the additional equation

f ∘ ι = g ∘ ι.

So in this case we obtain the notion of an equalizer.

(4) Let

D = [figure: 2; 3.; j; 1; i]

A limit of the diagram

[figure: B; C; g; A; f]

consists of an object A×_{C} B := \underleftarrow{lim} F and two morphisms 𝔭_{A} : A×_{C} B ⟶ A and p_{B} : A×_{C} B ⟶ B such that the diagram

[figure: B; C; g; f; A ×_{C} B; A; p_{A}; p_{B}]

The third morphism p_{C} : A ×_{C} B ⟶ C is given by the property p_{C} = f ∘ p_{A} = g ∘ p_{B}, so it is uniquely determined. The triple (A ×_{C} B, p_{A}, p_{B}) satisfies the fowwlowing universal property. Given an object T in C and two morphisms q_{A} : T ⟶ A and q_{B} : T ⟶ B such that f ∘ q_{A} = g ∘ q_{B} (again we need not give the third morphism q_{C} = f ∘ q_{A} = g ∘ q_{B}) then there is a unique morphism q : T ⟶ A ×_{C} B such that

[figure: B; C; g; f; A ×_{C} B; A; p_{A}; p_{B}; T; q; q_{A}; q_{B}]

commutes. This limit (A ×_{C} B, p_{A}, p_{B}) is called a fibre product or a pullback.

(5) The limit F : D ⟶ Set of a shape graph D with vertex set V = V (D) and edge set E = E(D) can be described as follows. The set \underleftarrow{lim} F is

\underleftarrow{lim} F = \{ (a_{i}) | for all i ∈ V : a_{i} ∈ F (i) and for all (u : i ⟶ j) ∈ E : F (u)(a_{i}) = a_{j}\}.

The projections p_{i} : \underleftarrow{lim} F ⟶ F (i) are defined by p_{i}((a_{j})) := a_{i}.

2.12.4. Proposition (Characterization of limits). Let F : D ⟶ C be a diagram. An object L together with a family of morphisms (p_{A} : L ⟶ F (A)) for all A ∈ D is a limit of F : D ⟶ C if and only if

• for all objects T in C there is an isomorphism of sets

i : Mor_{C}(T, L) ≅ \underleftarrow{lim}(Mor_{C}(T, F) : D ⟶ Set)

such that the tringles

[figure: \underleftarrow{lim}(Mor_{C}(T, F)); Mor_{C}(T, A); p̃_{A}; Mor_{C}(T, L); Mor_{C}(T, p_{A}); i]

commute for all A ∈ D.

Frequently, \underleftarrow{lim} F is referred to as a limit of F : D ⟶ C without referring to (p_{A}). Nevertheless, (p_{A}) is a crucial part of the data.

Proof. ⟹: Let (L, (p_{A})) be a limit of F : D ⟶ C. Let T be an object in C and let f ∈ Mor_{C}(T, L). Define f_{A} := p_{A} ∘ f : T ⟶ A. Then Mor_{C}(T, F)(u)(f_{A}) = Mor_{C}(T, F (u))(p_{A} ∘ f) = F (u) ∘ p_{A} ∘ f = p_{B} ∘ f = f_{B} for all (u : A ⟶ B) ∈ D so that (f_{A}) ∈ \underleftarrow{lim}(Mor_{C}(T, F). Now we can define i(f) := (f_{A}) ∈ \underleftarrow{lim}(Mor_{C}(T, F) and get Mor_{C}(T, p_{A})(f) = p_{A} ∘ f = f_{A} = p̃_{A} ∘ i(f).

It remains to show that i is bijective. We construct the inverse map as

u : \underleftarrow{lim}(Mor_{C}(T, F)) ⟶ Mor_{C}(T, L) u((f_{A})) := f

where (f_{A}) ∈ \underleftarrow{lim}(Mor_{C}(T, F)) implies Mor_{C}(T, F)(u)(f_{A}) = f_{B} = F (u) ∘ f_{A} for all (u : A ⟶ B) ∈ D. By the universal property of the limit there is a unique f : T ⟶ L such that p_{A} ∘ f = f_{A}. We use this f for the definition of the map u.

Let (f_{A}) ∈ \underleftarrow{lim}(Mor_{C}(T, F)). Then (i ∘ u)((f_{A})) = i(f) = (p_{A} ∘ f) = (f_{A}) hence (i ∘ u) =

1_{⟵^{lim}(Mor_{C}(T,F))}.

Let f ∈ Mor_{C}(T, L). Then (u ∘ i)(f) = u((f_{A})) = u((p_{A}) ∘ f) = f′ where f′ : T ⟶ L is the unique morphism such that p_{A}∘f′ = p_{A}∘f for all A ∈ D hence f = f′ and (u∘i) = 1_{Mor_{C}(T,L)}.

⟸: If (f_{A} : T ⟶ F (A) | A ∈ D) is a family of morphisms such that F (u) ∘ f_{A} = f_{B} for all (u : A ⟶ B) ∈ D. Then (f_{A}) is an element of \underleftarrow{lim}(Mor_{C}(T, F)), since Mor_{C}(T, F)(u)(f_{a}) = F (u) ∘ f_{A} = f_{B} for all (u : A ⟶ B) ∈ D. It is the unique element with p̃_{A}((f_{A})) = f_{A} for all A ∈ D. So there is a unique morphism f := i^{−1}((f_{A})) satisfying p̃_{A}∘i(f) = f_{A} or Mor_{C}(T, p_{A})(f) = f_{A} or p_{A} ∘ f = f_{A} for all A ∈ D. Thus (L, (p_{A})) is a limit of F. □

2.12.5. Proposition. The family of isomorphisms

i_{T} : Mor_{C}(T, \underleftarrow{lim} F) ⟶ \underleftarrow{lim}(Mor_{C}(T, F)

such that the tringles

[figure: \underleftarrow{lim}(Mor_{C}(T, F)); Mor_{C}(T, A); p̃_{A}; Mor_{C}(T, \underleftarrow{lim} F); Mor_{C}(T, p_{A}); i]

commute for all objects T in C, is a natural isomorphism in T and morphisms of diagrams F.

Proof. is similar to the proof of Proposition 2.7.5. □

2.12.6. Remark. Thus the most important properties of the extension principle are now verified. Observe that Proposition 2.12.4 implies

Mor_{C}(T, \underleftarrow{lim} F) ≅ \underleftarrow{lim} Mor_{C}(T, F).

The dual notion of a limit is a colimit or direct limit. You can define it as the limit in the dual category C^{op} of C. Then for colimits the following isomorphism holds:

Mor_{C}(\underrightarrow{lim} F, T) ≅ \underleftarrow{lim} Mor_{C}(F, T).

These isomorphisms can be interpreted as • a covariant representable functor preserves limits;

• a contravariant representable functor maps colimits to limits.

2.12.7. Example. Let (V_{i}|i ∈ I) be a family of vector spaces. Then

Hom_{𝕂}(W, ∏_{i∈I} V_{i}) ≅ ∏_{i∈I} Hom_{𝕂}(W, V_{i})

and

Hom_{𝕂}(⨁_{i∈I} V_{i}, W) ≅ ∏_{i∈I} Hom_{𝕂}(V_{i}, W)

2.12.8. Theorem. Let F : D ⟶ C be a diagram in a category C. If (L, (p_{A})) and (L′, (p′_{A})) are limits of F, then there is a unique isomorphism h : L ⟶ L′ such that p′_{A} ∘ h = p_{A} for all A ∈ D.

Proof. Since (L′, (p′_{A})) satisfies the universal property of a limit there is a unique morphism h : L ⟶ L′ such that p′_{A} ∘ h = p_{A} for all A ∈ D. Symmetrically there is a unique morphism k : L′ ⟶ L such that p_{A} ∘ k = p′_{A} for all A ∈ D. Consider the following commutative diagram:

[figure: L; A; p_{A}; L′; p′_{A}; L; p_{A}; L′; p′_{A}; h; k; h; 1_{L}; 1_{L′}]

Since p_{A} ∘ k ∘ h = p_{A} = p_{A} ∘ 1_{L} for all A ∈ D we get by uniqueness k ∘ h = 1_{L}. Symmetrically we get h ∘ k = 1_{L′}, thus h is an isomorphism with the required properties. □

09.07.04

3. Adjoint functors and monads

3.1. Adjoint functors.

3.1.1. Definition. Let C and D be categories. Let F : C ⟶ D and G : D ⟶ C be covariant functors. F is called left adjoint to G and G is called right adjoint to F if there is a natural isomorphism (natural in C ∈ C and D ∈ D)

φ(C, D) : Mor_{D}(F C, D) ≅ Mor_{C}(C, GD)

or simply

Mor_{D}(F -, -) ≅ Mor_{C}(-, G-) : C^{op} × D ⟶ Set .

3.1.2. Proposition. Let F : C ⟶ D be left adjoint to G : D ⟶ C. Then G determines F uniquely up to a natural isomorphism.

Proof. Assume that also F′ : C ⟶ D is left adjoint to G. Then we have natural isomorphisms

Mor_{D}(F -, -) ≅ Mor_{C}(-, G-) ≅ Mor_{D}(F′-, -).

By the Yoneda Lemma and Proposition 2.10.5 we get F ≅ F′. □

3.1.3. Corollary. Let F_{i} : C ⟶ D be left adjoint to G_{i} : D ⟶ C for i = 1, 2. Let α : G_{1} ⟶ G_{2} be a natural transformation. Then there is a unique natural transformation β : F_{2} ⟶ F_{1} such that the diagram

Proof. Given A, B ∈ D. Then there is a unique morphism β(A) : F_{2}A ⟶ F_{1}A such that the following diagram commutes We have to show that β : F_{2} ⟶ F_{1} is a natural transformation. Let f : A ⟶ B be a morphism in D. Then

[figure: Mor_{D}(F_{1}-, -); Mor_{C}(-, G_{1}-); φ_{1}(-, -); Mor_{D}(F_{2}-, -); Mor_{C}(-, G_{2}-); φ_{2}(-, -); Mor_{D}(β-, -); Mor_{C}(-, α-)] [figure: Mor_{D}(F_{1}A, -); Mor_{C}(A, G_{1}-); φ_{1}(A, -); Mor_{D}(F_{2}A, -); Mor_{C}(A, G_{2}-); φ_{2}(A, -); Mor_{D}(β(A), -); Mor_{C}(A, α-)]

[figure: Mor_{D}(F_{1}B, -); Mor_{C}(B, G_{1}-); φ_{1}(B, -); Mor_{D}(F_{2}B, -); Mor_{C}(B, G_{2}-); φ_{2}(B, -); Mor_{D}(β(B), -); Mor_{C}(B, α-); Mor_{D}(F_{1}A, -); Mor_{C}(A, G_{1}-); φ_{1}(A, -); Mor_{D}(F_{2}A, -); Mor_{C}(A, G_{2}-); φ_{2}(A, -); Mor_{D}(β(A), -); Mor_{C}(A, α-); Mor_{D}(F_{1}f, -); Mor_{C}(f, G_{1}-); Mor_{D}(F_{2}f, -); Mor_{C}(f, G_{2}-)]
□

There is an equivalent definition of adjoint functors that we want to give now. First we need some preparation.

3.1.4. Lemma. Let F : C ⟶ D and G : D ⟶ C be functors. Then the map

Nat(Id_{C}, GF) ∋ Φ ↦ G- ∘ Φ- ∈ Nat(Mor_{D}(F -, -), Mor_{C}(-, G-))

is bijective with inverse map

Nat(Mor_{D}(F -, -), Mor_{C}(-, G-)) ∋ φ ↦ φ(-, F -)(1_{F-}) ∈ Nat(Id_{C}, GF).

Given φ : Mor_{D}(F -, -) ⟶ Mor_{C}(-, G-) as a family φ(C, D) : Mor_{D}(F C, D) ⟶ Mor_{C}(C, GD). Take D := F C. Then we get Φ(C) := φ(C, F C)(1_{F C}) : C ⟶ GF C. We show that Φ : Id_{C} ⟶ GF is a natural transformation. For f : C ⟶ C′ the diagram commutes:

[figure: Mor_{D}(F C, F C); Mor_{D}(F C, F C′); Mor_{D}(F C, F f); Mor_{D}(F C′, F C′); Mor_{D}(F f, F C′); Mor_{C}(C, GF C); Mor_{C}(C, GF C′); Mor_{C}(C, GF f); Mor_{C}(C′, GF C′); Mor_{C}(f, GF C′); φ(C, F C); φ(C, F C′); φ(C′, F C′)]

Hence we get

Φ(C′) ∘ f = (Mor_{C}(f, GF C′) ∘ φ(C′, F C′))(1_{F C′})
= (φ(C, F C′) ∘ Mor_{D}(F f, F C′))(1_{F C′})
= φ(C, F C′)(F f)
= (φ(C, F C′) ∘ Mor_{D}(F C, F f))(1_{F C})
= (Mor_{C}(C, GF f) ∘ φ(C, F C))(1_{F C})
= GF f ∘ Φ(C).

Conversely let Φ : Id_{C} ⟶ GF be a natural transformation and let

φ(C, D)(f) := Gf ∘ Φ(C) = (Mor_{C}(Φ(C), GD) ∘ G)(f) : C ⟶^{Φ(C)} GF C ⟶^{Gf} GD

for f : F C ⟶ D. We show that φ : Mor_{D}(F --) ⟶ Mor_{C}(-, G-) is a natural transformation. Given g : C ⟶ C′ then

[figure: Mor_{D}(F C′, D); Mor_{D}(F C, D); Mor_{D}(F g, D); Mor_{C}(C′, GD); Mor_{C}(C, GD); Mor_{C}(g, GD); φ(C′, D); φ(C, D)]

commutes since

(φ(C, D) ∘ Mor_{D}(F g, D))(f) = φ(C, D)(f ∘ F g)
= G(f ∘ F g) ∘ Φ(C)
= Gf ∘ GF g ∘ Φ(C)
= Gf ∘ Φ(C′) ∘ g
= Mor_{C}(g, GD)(Gf ∘ Φ(C′)
= (Mor_{C}(g, GD) ∘ φ(C′, D))(f).

Now let g : D ⟶ D′ be given. The the diagram

[figure: Mor_{D}(F C, D); Mor_{D}(F C, D′); Mor_{D}(F C, g); Mor_{C}(C, GD); Mor_{C}(C, GD′); Mor_{C}(C, Gg); φ(C, D); φ(C, D′)]

commutes since

3.2. Monads or Triples. We now describe a structure based on an endofunctor which has turned out to be an important technical tool in studying toposes and related topics. It is an abstraction of the concept of adjoint and in a sense an abstraction of universal algebra (see the remarks in fine print at the end of 10.2.3 below).

3.2.1. Definition. Let A be a category and R : A ⟶ A be an endofunctor. An R-algebra is a pair (A, a) where a : RA ⟶ A is an arrow of A . A homomorphism between R-algebras (A, a) and (B, b) is an arrow f : A ⟶ B of A such that

[figure: RA; A; a; RB; B; b; Rf; f]

commutes. This construction gives a category (R : A) of R-algebras.

3.2.2. Definition. A monad 𝕋 = (T, η, μ) on a category A consists of a functor T : A ⟶ A, together with two natural transformations η : id ⟶ T and μ : T^{2} ⟶ T for which the following diagrams commute

[figure: T; T^{2}; ηT; T; T η; T; =; =; μ; T^{3}; T^{2}; T μ; T^{2}; T; μ; μT; μ]

Here, ηT and T η are defined as in 1.7.56and 1.7.57.The transformation η is the unit of the monad and μ is the multiplication. The left diagram constitutes the (left and right) unary identities and the right one the associative identity. The reason for these names comes from the analogy between monads and monoids. This will be made clear in 3.2.4.Another widely used name for monad is ‘triple’. An adjoint pair gives rise to a monad on the domain of the left adjoint.

3.2.3. Proposition. Let U : B ⟶ A and F : A ⟶ B be functors such that F is left adjoint to U with η : id ⟶ UF and ε : F U ⟶ id the unit and counit, respectively. Then (UF, η, UεF) is a monad on A.

Note that UεF : UF UF ⟶ UF, as required for the multiplication of a monad with functor UF. Conversely, every monad arises in that way out of some (generally many) adjoint pair. See Section 3.3 for two ways of constructing such adjoints.

3.2.4. Example. Let M be a monoid. The representation monad T = (T, η, μ) on the category of sets is given by letting T (S) = M × S for a set S. ηS : S ⟶ T (S) = M × S takes an element s ∈ S to the pair (1, s). We define μS by (μS)(m1, m2, s) = (m1m2, s) for s ∈ S, m1, m2 ∈ M. Thus the unit and multiplication of the monad arise directly from that of the monoid. The unitary and associativity equations can easily be shown to follow from the corresponding equations for the monoid. The standard way of getting this monad from an adjoint pair is by using the underlying and free functors on M-sets (see 4.2.1???). If S and T are M-sets, then a function f : S ⟶ T is said to be M-equivariant if f(ms) = mf(s) for m ∈ M, s ∈ S. For a fixed monoid M, the M-sets and the M-equivariant functions form a category, called the category of M-sets. The free M-set generated by the set S is the set M × S with action given by m′(m, s) = (m′m, s). Using Theorem 9.3.5???, one can show immediately that this determines a functor left adjoint to the underlying set functor on the category of M-sets. The monad associated to this adjoint pair is the one described above.

3.2.5. Example. Let T : Set ⟶ Set be the functor which takes a set A to the Kleene closure A^{∗} and a function f : A ⟶ B to the function f^{∗} : A^{∗} ⟶ B^{∗} defined in Section 2.5.7???. Let ηA : A ⟶ A take an element a to the one-element string (a), and let μA : A^{∗∗} ⟶ A^{∗} be the flattening operation taking a string (s_{1}, s_{2}, …, s_{n}) of strings to the concatenated string s_{1}s_{2} … s_{n} in A^{∗} obtained in effect by erasing inner brackets: thus ((a, b), (c, d, e), (), (a, a)) goes to (a, b)(c, d, e)()(a, a) = (a, b, c, d, e, a, a). In particular, μA((a, b)) = (a, b). Then η : id ⟶ T and μ : T ∘ T ⟶ T are natural transformations, and (T, η, μ) is a monad.

3.2.6. Definition. A comonad G = (G, ε, δ) in a category A is a monad in A^{op}. Thus G is an endofunctor of A and ε : G ⟶ id and δ : G ⟶ G2 are natural transformations such that

[figure: G; G^{2}; εG; G; Gε; G; =; =; δ; G; G^{2}; δ; G^{2}; G^{3}; Gδ; δ; δG]

3.3. Factorizations of a monad.

3.3.1. Remark. Let 𝕋 = (T, η, μ) be a monad on C . We describe here a construction which exhibits the monad as coming from an adjoint. This construction, which is due to Kleisli [1965], has proven to be quite useful in theoretical computer science. We define a category K = K(𝕋) which has the same objects as C. If A and B are objects of C, then an arrow in K from A to B is an arrow A ⟶ T B in C . The composition of arrows is as follows. If f : A ⟶ T B and g : B ⟶ T C are arrows in C, we let their composite in K be the following composite in C :

A ⟶^{f} T B ⟶^{T g} T^{2}C ⟶^{μC} T C.

The identity of the object A is the arrow ηA : A ⟶ T A. It can be shown that this defines a category. Moreover, there are functors U : K(𝕋) ⟶ C and F : C ⟶ K(𝕋) defined by UA = T A and Uf = μB ∘ μT f, where B is the codomain of f, and F A = A and for g : A ⟶ B, F g = T g ∘ ηA. Then F is left adjoint to U and T = U ∘ F.

Here is a second way, due to Eilenberg and Moore [1965] of factoring every monad as an adjoint pair of functors. In mathematics, this construction has been much more interesting than the Kleisli construction, but in computer science it has been quite the opposite.

3.3.2. Definition. Let 𝕋 = (T, η, μ) be a monad on A. A T -algebra (A, a) is called a 𝕋-algebra if the following two diagrams commute:

[figure: T^{2}A; T A; μA; T A; A; a; T a; a; A; T A; ηA; =; A; a]

An arrow (homomorphism) between 𝕋-algebras is the same as an arrow between the corresponding T -algebras. With these definitions, the 𝕋-algebras form a category traditionally denoted A^{𝕋} and called the category of 𝕋-algebras. There is an obvious underlying functor U : A^{𝕋} ⟶ A with U(A, a) = A and Uf = f. This latter makes sense because an arrow of A^{𝕋} is an arrow of A with special properties. There is also a functor F : A ⟶ A^{𝕋} given by F A = (T A, μA) and F f = T f. Some details have to be checked, these are included in the following.

3.3.3. Proposition. The function F above is a functor left adjoint to U. The monad associated to the adjoint pair F U is precisely T.

By a theorem of Linton’s, every equationally defined category of one-sorted algebraic structures is in fact equivalent to the category of Eilenberg-Moore algebras for some monad in Set ([Barr and Wells, 1985], Theorem 5 of Section 4.3). In fact, the converse is true if infinitary operations are allowed (but then a hypothesis has to be added on the direct part of the theorem that there is only a set of operations of any given arity).

3.3.4. Example. Let (T, η, u) be the monad in Set defined in 10.1.6. An algebra for this monad is a monoid: specifically, if ff : T (A) ⟶ A is an algebra, then the definition ab = ff(a, b) makes A a monoid, and up to isomorphisms every monoid arises this way. Moreover, algebra homomorphisms are monoid homomorphisms, and every monoid homomorphism arises this way. The proof requires lengthy but not difficult verifications.

The Kleisli category of a monad 𝕋 = (T, η, μ) is equivalent to the full subcategory of free 𝕋-algebras. Its definition makes it clear that the arrows are substitutions.

3.3.5. Example. As an example, consider the list monad of 10.1.6???. An arrow f : A ⟶ B (here A and B are sets) of the Kleisli category is a set function A ⟶ T B, so that it associates a string of elements of B to each element of A. Suppose A = {a, b} and B = {c, d, e}, and that f(a) = cddc and f(b) = ec. Then T f : T A ⟶ T T B takes, for example, the string abba to (cddc)(ec)(ec)(cddc), the result of substituting cddc for a and ec for b in abba. Then μ takes that string to cddcececcddc. It is instructive in this situation to think of μ as carrying out a computation. In this case the computation is carried out using the (only) monoid operation, since in fact the algebras for this monad are monoids. Thus one can think of the objects of the Kleisli category as computations. This is more compelling if one uses a monad arising from algebraic structures such as rings that abstract some of the properties of numerical addition and multiplication, then the objects of the free algebra are polynomial expressions and μ evaluates the polynomial.

3.4. Algebraic Categories.

3.5. More facts about adjoint functors.

3.5.1. Theorem. Let F : C ⟶ D be a covariant functor that has a left adjoint. Then F preserves limits.

Idea of proof. Let D : I ⟶ C be a diagram. Consider the isomorphisms

Mor_{D}(T, F \underleftarrow{lim} D) ≅ Mor_{C}(GT, \underleftarrow{lim} D) ≅ \underleftarrow{lim} Mor(GT, D) ≅

≅ \underleftarrow{lim} Mor(T, F D) ≅ Mor(T, \underleftarrow{lim} F D)

which implies F \underleftarrow{lim} D ≅ \underleftarrow{lim} F D. □

3.5.2. Definition. Let F : C ⟶ D be a functor. Let D ∈ D. A set 𝔏_{D} of objects in C is called a solution set of D with respect to F, if for each C ∈ C and for each morphism D ⟶ F (C) there is an object C′ ∈ 𝔏_{D} and morphisms f : C′ ⟶ C and D ⟶ F (C′) such that the triangle

[figure: D; F (C′); F (C); F (f)]

commutes.

3.5.3. Theorem. Let C be a complete, locally small category and let F : C ⟶ D be a (covariant) functor. Assume that C has a cogenerator. F has a left adjoint if and only if

• F preserves limits and • F has solutions sets.

3.5.4. Definition. An object C ∈ C is called a cogenerator, if for any two morphisms f, g : A ⟶ B with f ≠ g there is a morphism h : B ⟶ C such that h ∘ f ≠ h ∘ g.

3.5.5. Theorem. Let C be a complete, locally small category and let F : C ⟶ D be a (covariant) functor. Assume that C has a cogenerator. F has a left adjoint if and only if F preserves limits.

References

[Backus, 1981a] Backus, J.: The algebra of functional programs: Function level reasoning, linear equations, and extended definitions. In: Formalization of Programming Concepts, J. Diaz and I. Ramos, editors, volume 107 of Lecture Notes in Computer Science. Springer-Verlag 1981.

[Backus, 1981b] Backus, J.: Is computer science based on the wrong fundamental concept of program? In:

Algorithmic Languages, J. W. deBakker and J. C. van Vliet, editors. North-Holland 1981. [Barr and Wells, 1999] Barr, M. and Wells, C.: Category Theory for Computing Science, third edition. Les

publications Centre de recherches mathématiques 1999. [Cockett, 1989] Cockett, J. R. B.: On the decidability of objects in a locos. In: Categories in Computer

Science and Logic, J. W. Gray and A. Scedrov, editors, volume 92 of Contemporary Mathematics. American Mathematical Society 1989.

[Jacobson, 1974] Jacobson, N.: Basic Algebra. I. W. H. Freeman 1974. [Pareigis, 1969] Pareigis, B.: Kategorien und Funktoren. Teubner Verlag 1969. [Pareigis, 2000] Pareigis, B.: Lineare Algebra für Informatiker. Springer Verlag 2000. [Pitt, 1986] Pitt, D., Abramsky, S., Poigné, A., and Rydeheard, D., editors. Category Theory and Computer

Programming, volume 240 of Lecture Notes in Computer Science. Springer-Verlag 1986. [Wagner, 1986] Wagner, E. G.: Algebraic theories, data types and control constructs. Fundamenta Infor-

matica, volume 9, pages 343-370 1986. [Williams, 1982] Williams, J. H.: Notes on the fp style of functional programming. In: Functional Program-

ming and its Applications, P. H. Darlington, J. and D. Turner, editors. Cambridge University Press