I’ll continue then with this brief subseries on category theory. Today I want to talk more about universal properties, and about the notion of natural transformation. Maybe not today, but soon at any rate, I want to tie all this in with the central concept of representability, which leads directly and naturally to the powerful and fundamental idea of adjoint functors. This goes straight to the very heart of category theory.

The term “natural”, often bandied about by mathematicians, is perhaps an overloaded term (see the comments here for a recent disagreement about certain senses of the word). I don’t know the exact history of the word as used by mathematicians, but by the 1930s and 40s the description of something as “natural” was part of the working parlance of many mathematicians (in particular, algebraic topologists), and it is to the great credit of Eilenberg and Mac Lane that they sought to give the word a precise mathematical sense. A motivating problem in their case was to prove a universal coefficient theorem for Cech cohomology, for which they needed certain comparison maps (transformations) which cohered by making certain diagrams commute (which was the naturality condition). In trying to precisely define this concept of naturality, they were led to the concept of a “functor” and then, to define the concept of functor, they were led back to the notion of category! And the rest, as they say, is history.

More on naturality in a moment. Let me first give a few more examples of universal constructions. Last time we discussed the general concept of a cartesian product — obviously in honor of Descartes, for his tremendous idea of the method of coordinates and analytic geometry.

But of course products are only part of the story: he was also interested in the representation of equations by geometric figures: for instance, representing an equation y = f(x) as a subset of the plane. In the language of category theory, the variable y denotes the second coordinate or second projection map \pi_2: \mathbb{R} \times \mathbb{R} \to \mathbb{R}, and f(x) denotes the composite of the first projection map followed by some given map f:

\displaystyle \mathbb{R} \times \mathbb{R} \stackrel{\pi_1}{\to} \mathbb{R} \stackrel{f}{\to} \mathbb{R}.

The locus of the equation y = f(x) is the subset of \mathbb{R} \times \mathbb{R} where the two morphisms \pi_2 and f \circ \pi_1 are equal, and we want to describe the locus L in a categorical way (i.e., in a way which will port over to other categories).

Definition: Given a pair of morphisms

\displaystyle f, g: X \stackrel{\to}{\to} Y

their equalizer consists of an object L and a map e: L \to X, such that f \circ e = g \circ e, and satisfying the following universal property: for any map h: A \to X such that f \circ h = g \circ h, there exists a unique map j: A \to L such that h = e \circ j (any map h: A \to X that equalizes f and g factors in a unique way through the equalizer e: L \to X). \Box

Another way of saying it is that there is a bijection between (f, g)-equalizing maps h: A \to X and maps j: A \to L,

\displaystyle \frac{h: A \to X \mbox{ such that } fh = gh}{j: A \to L \qquad },

effected by composing such maps j with the universal (f, g)-equalizing map e: L \to X.

Exercise: Apply a universality argument to show that any two equalizers of a given pair of maps (f, g) are isomorphic.

It is not immediately apparent from the definition that an equalizer e: L \to X describes a “subthing” (e.g., a subset) of X, but then we haven’t even discussed subobjects. The categorical idea of subobject probably takes some getting used to anyway, so I’ll be brief. First, there is the idea of a monomorphism (or a “mono” for short), which generalizes the idea of an injective or one-to-one function. A morphism f: S \to T is monic if for all g, h: A \to S, f \circ g = f \circ h implies g = h. Monos with codomain T are preordered by a relation \leq, where

(e: R \to T) \leq (f: S \to T)

if there exists g: R \to S such that e = f \circ g. (Such a g is unique since f is monic, so it doesn’t need to be specified particularly; also this g is easily seen to be monic [exercise].) Then we say that two monics e, f mapping into T name the same subobject of T if e \leq f and f \leq e; in that case the mediator g is an isomorphism. Writing e \sim f to denote this condition, it is standard that \sim is an equivalence relation.

Thus, a subobject of X is an equivalence class of monos into X. So when we say an equalizer e: L \to X of maps f, g: X \to Y defines a subobject of X, all we really mean is that e is monic. Proof: Suppose eh = ej for maps h, j: A \to X. Since fe = ge, we have f(ej) = g(ej) for instance. By definition of equalizer, this means there exists a unique map k: A \to X for which eh = ej = ek. Uniqueness then implies h, j are equal to this self-same k, so h = j and we are done.

Let me turn to another example of a universal construction, which has been used in one form or another for centuries: that of “function space”. For example, in the calculus of variations, one may be interested in the “space” of all (continuous) paths \alpha: I = \left[0, 1\right] \to X in a physical space X, and in paths which minimize “action” (principle of least action).

If X is a topological space, then one is faced with a variety of choices for topologizing the path space (denoted X^I). How to choose? As in our discussion last time of topologizing products, our view here is that the “right” topology will be the unique one which ensures that an appropriate universal property is satisfied.

To get started on this: the points of the path space X^I are of course paths \alpha: I \to X, and paths in the path space, I \to X^I, sending each s \in I to a path \alpha_s: I \to X, should correspond to homotopies between paths, that is continuous maps h: I \times I \to X; the idea is that h(s, t) := \alpha_s(t). Now, just knowing what paths in a space Y = X^I look like (homotopies between paths) may not be enough to pin down the topology on Y, but: suppose we now generalize. Suppose we decree that for any space Z, the continuous maps Z \to X^I should correspond exactly to continuous maps h: Z \times I \to X, also called homotopies. Then that is enough to pin down the topology on X^I. (We could put it this way: we use general spaces Z to probe the topology of X^I.)

This principle applies not just to topology, but is extremely general: it applies to any category! I’ll state it very informally for now, and more precisely later:

Yoneda principle: to determine any object Y up to isomorphism, it suffices to understand what general maps Z \to Y mapping into it look like.

For instance, a product X_1 \times X_2 is determined up to isomorphism by knowing what maps Z \to X_1 \times X_2 into it look like [they look like pairs of maps (Z \to X_1, Z \to X_2)]. In the first lecture in the Stone duality, we stated the Yoneda principle just for posets; now we are generalizing it to arbitrary categories.

In the case at hand, we would like to express the bijection between continuous maps

\displaystyle \frac{f: Z \to X^I}{h: Z \times I \to X}

as a working universal property for the function space X^I. There is a standard “Yoneda trick” for doing this: probe the thing we seek a universal characterization of with the identity map, here 1_{X^I}: X^I \to X^I. Passing to the other side of the bijection, the identity map corresponds to a map

ev: X^I \times I \to X

and this is the “universal map” we need. (I called it ev because in this case it is the evaluation map, which maps a pair (path \alpha: I \to X, point t \in I) to \alpha(t), i.e., evaluates \alpha at t.)

Here then is the universal characterization of the path space: a space X^I equipped with a continuous map ev: X^I \times I \to X, satisfying the following universal property: given any continuous map h: Z \times I \to X, there exists a unique continuous map f: Z \to X^I such that h is retrieved as the composite

\displaystyle Z \times I \stackrel{f \times 1_I}{\to} X^I \times I \stackrel{ev}{\to} X

(for the first arrow in the composite, cf. the exercise stated at the end of the last lecture).

Exercise: Formulate a universality argument that this universal property determines X^I up to isomorphism.

Remark: Incidentally, for any space X, such a path space exists; its topology turns out to be the topology of “uniform convergence”. We can pose a similar universal definition of any function space X^Y (replacing I by Y, mutatis mutandis); a somewhat non-trivial result is that such a function space exists for all X if and only if Y is locally compact; the topology on X^Y is then the so-called “compact-open” topology.

But why stop there? A general notion of “exponential” object is available for any category C with cartesian products: for objects c, d of C, an exponential d^c is an object equipped with a map ev: d^c \times c \to d, such that for any h: b \times c \to d, there exists a unique f: b \to d^c such that h is retrieved as the composite

\displaystyle b \times c \stackrel{f \times 1_c}{\to} d^c \times c \stackrel{ev}{\to} d.

Example: If the category is a meet-semilattice, then (assuming x^y exists) there is a bijection or equivalence which takes the form

\displaystyle \frac{a \leq x^y}{a \wedge y \leq x} iff

But wait, we’ve seen this before: x^y is what we earlier called the implication y \Rightarrow x. So implication is really a function space object! \Box

Okay, let me turn now to the notion of natural transformation. I described the original discovery (or invention) of categories as a kind of reverse engineering (functors were invented to talk about natural transformations, and categories were invented to talk about functors). Moving now in the forward direction, the rough idea can be stated as a progression:

  • The notion of functor is appropriately defined as a morphism between categories,
  • The notion of natural transformation is appropriately defined as a morphism between functors.

That seems pretty bare-bones: how do we decide what the appropriate notion of morphism between functors should be? One answer is by pursuing an analogy:

  • As a space Y^X of continuous functions X \to Y is to the category of topological spaces, so a category D^C of functors C \to D should be to the category of categories.

That is, we already “know” (or in a moment we’ll explain) that the objects of this alleged exponential category D^C are functors F: C \to D. Since D^C is defined by a universal property, it is uniquely determined up to isomorphism. This in turn will uniquely determine what the “right” notion of morphism between functors F, G: C \to D should be: morphisms F \to G in the exponential D^C! Then, to discover the nature of these morphisms, we employ an appropriate “probe”.

To carry this out, I’ll need two special categories. First, the category \mathbf{1} denotes a (chosen) category with exactly one object and exactly one morphism (necessarily the identity morphism). It satisfies the universal property that for any category C, there exists a unique functor C \to \mathbf{1}. It is called a terminal category (for that reason). It can also be considered as an empty product of categories.

Proposition: For any category C, there is an isomorphism \mathbf{1} \times C \cong C.

Proof: Left to the reader. It can be proven either directly, or by applying universal properties. \Box

The category \mathbf{1} can also be considered an “object probe”, in the sense that a functor \mathbf{1} \to C is essentially the same thing as an object of C (just look where the object of \mathbf{1} goes to in C).

For example, to probe the objects of the exponential category D^C, we investigate functors \mathbf{1} \to D^C. By the universal property of exponentials D^C, these are in bijection with functors \mathbf{1} \times C \to D. By the proposition above, these are in bijection with functors C \to D. So objects of D^C are necessarily tantamount to functors C \to D (and so we might as well define them as such).

Now we want to probe the morphisms of D^C. For this, we use the special category given by the poset \mathbf{2} = \{0 \leq 1\}. For if X is any category and f: x \to y is a morphism of X, we can define a corresponding functor F: \mathbf{2} \to X such that F(0) = x, F(1) = y, and F sends the morphism 0 \leq 1 to f. Thus, such functors F are in bijection with morphisms of X. Speaking loosely, we could call the category \mathbf{2} the “generic morphism”.

Thus, to probe the morphisms in the category D^C, we look at functors \mathbf{2} \to D^C. In particular, if F, G are functors C \to D, let us consider functors \phi: \mathbf{2} \to D^C such that \phi(0) = F and \phi(1) = G. By the universal property of D^C, these are in bijection with functors \eta: \mathbf{2} \times C \to D such that the composite

\displaystyle C \cong \mathbf{1} \times C \stackrel{0 \times 1_C}{\to} \mathbf{2} \times C \stackrel{\eta}{\to} D

equals F, and the composite

\displaystyle C \cong \mathbf{1} \times C \stackrel{1 \times 1_C}{\to} \mathbf{2} \times C \stackrel{\eta}{\to} D

equals G. Put more simply, this says \eta(0, c) = F(c) and \eta(1, c) = G(c) for objects c of C, and \eta(1_0, f) = F(f) and \eta(1_1, f) = G(f) for morphisms f of C.

The remaining morphisms of \mathbf{2} \times C have the form (0 \leq 1, f: c \to d). Introduce the following abbreviations:

  1. \phi_c := \eta(0 \leq 1, 1_c) for objects c of C;
  2. \phi_f := \eta(0 \leq 1, f) for morphisms f of C.

Since \eta is a functor, it preserves morphism composition. We find in particular that since

(1_1, f) \circ (0 \leq 1, 1_c) = (1_1 \circ (0 \leq 1), f \circ 1_c) = (0 \leq 1, f)

(0 \leq 1, 1_d) \circ (1_0, f) = ((0 \leq 1) \circ 1_0, 1_d \circ f) = (0 \leq 1, f)

we have

\eta(1_1, f) \circ \eta(0 \leq 1, 1_c) = \eta(0 \leq 1, f)

\eta(0 \leq 1, 1_d) \circ \eta(1_0, f) = \eta(0 \leq 1, f)

or, using the abbreviations,

G(f) \circ \phi_c = \phi_f = \phi_d \circ F(f).

In particular, the data \phi_f is redundant: it may be defined either as either side of the equation

G(f) \circ \phi_c = \phi_d \circ F(f).

Exercise: Just on the basis of this last equation (for arbitrary morphisms f and objects c of C), prove that functoriality of \eta follows.

This leads us at last to the definition of natural transformation:

Definition: Let C, D be categories and let F, G be functors from C to D. A natural transformation \phi: F \to G is an assignment of morphisms \phi_c: F(c) \to G(c) in D to objects c of C, such that for every morphism f: c \to d, the following equation holds: G(f) \circ \phi_c = \phi_d \circ F(f). \Box

Usually this equation is expressed in the form of a commutative diagram:

          F(f)
     F(c) ---> F(d)
      |         |
phi_c |         | phi_d
      V   G(f)  V
     G(c) ---> G(d)

which asserts the equality of the composites formed by following the paths from beginning (here F(c)) to end (here G(d)). (Despite the inconvenience in typesetting them, commutative diagrams as 2-dimensional arrays are usually easier to read and comprehend than line-by-line equations.) The commutative diagram says that the components \phi_c of the transformation are coherent or compatible with all morphisms f: c \to d of the domain category.

Remarks: Now that I’ve written this post, I’m a little worried that any first-timers to category theory reading this will find this approach to natural transformations a little hardcore or intimidating. In that case I should say that my intent was to make this notion seem as inevitable as possible: by taking seriously the analogy

function space: category of spaces :: functor category: category of categories

we are inexorably led to the “right” (the “natural”) notion of natural transformation as morphism between functors. But if this approach is for some a pedagogical flop, then I urge those readers just to forget it, or come back to it later. Just remember the definition of natural transformation we finally arrived at, and you should be fine. Grasping the inner meaning of fundamental concepts like this takes time anyway, and isn’t merely a matter of pure deduction.

I should also say that the approach involved a kind of leap of faith that these functor categories (the exponentials D^C) “exist”. To be sure, the analysis above shows clearly what they must look like if they do exist (objects are functors C \to D; morphisms are natural transformations as we’ve defined them), but actually there’s some more work to do: one must show they satisfy the universal property with respect to not just the two probing categories \mathbf{1} and \mathbf{2} that we used, but any category E.

A somewhat serious concern here is that our talk of exponential categories played pretty fast and loose at the level of mathematical foundations. There’s that worrying phrase “category of categories”, for starters. That particular phraseology can be avoided, but nevertheless, it must be said that in the case where C is a large category (i.e., involving a proper class of morphisms), the collection of all functors from C to D is not a well-formed construction within the confines of Gödel-Bernays-von Neumann set theory (it is not provably a class in general; in some approaches it could be called a “super-class”).

My own attitude toward these “problems” tends to be somewhat blasé, almost dismissive: these are mere technicalities, sez I. The main concepts are right and robust and very fruitful, and there are various solutions to the technical “problem of size” which have been developed over the decades (although how satisfactory they are is still a matter of debate) to address the apparent difficulties. Anyway, I try not to worry about it much. But, for those fine upstanding citizens who do worry about these things, I’ll just state one set-theoretically respectable theorem to convey that at least conceptually, all is right with the world.

Definition: A category with finite products is cartesian closed if for any two objects c, d, there exists an exponential object d^c.

Theorem: The category of small categories is cartesian closed. \Box