# Practical Foundations of Mathematics

## 4.8  Natural Transformations

The first task of category theory is an organisational one: after various kinds of objects (types, sets, posets, complete semilattices and dcpos) and maps (terms, relations; partial, total, monotone, continuous and structure- preserving functions; and adjunctions) have been introduced, we were able to put them in a common framework as categories. For categories as objects we provided functors as morphisms, so why have we not yet discussed the category of categories and functors?

One reason is the problem of ``size'' mentioned in Remark  4.1.8, but there is also an algebraic one. As we have said, mathematical constructions generally define objects only up to isomorphism, because frequently there is a different but equally useful representation which can be substituted. For example there are two versions of the three-fold cartesian product. But once the representation is chosen, (the elements and more generally) the morphisms have a unique construction.

Such constructions of objects are, with a few rare exceptions, always functors, albeit frequently contravariant or even of ``mixed'' variance (Example  4.4.6(c)). In particular, an algebra (the interpretation of a theory L) is a functor Cn×LÛ Set (Theorem  4.6.7). Thus functors are often parametric objects and so, like objects, are intrinsically defined only up to isomorphism. Whereas morphisms of a category are in some sense isolated from one another, functors (like the objects which are their values) have a kind of fluidity between them, given by the morphisms of the target category, which we haven't taken into account.

DEFINITION 4.8.1 Let F,G:C\twoheadrightarrow D be two parallel functors. Then a natural transformation f:FÛ G consists of, for each object X ö obC, a morphism fX:F XÛ G X in D such that, for each map f:XÛ Y of C, the following square commutes:

omitted diagram environment

Often the object X is put as a subscript (fX), but here we have written fX as an application to an object of C yielding a morphism of D. This is the counterpart of using the same notation for the result of a functor applied to a morphism as to an object (Definition  4.4.1). Indeed the naturality square is the application of f:FÛ G to f:XÛ Y. The square is not symmetrical, and occasionally we shall indicate whether the vertical is natural with respect to the horizontal (as above) or vice versa by an `` N'' or `` Z'' in the middle.

EXAMPLES 4.8.2

(a)
If C and D are preorders then a natural transformation FÛ G is (an instance of) the pointwise order F È G (Proposition 3.5.5).

(b)
Proposition 4.5.13 defined the effect of the product functor (-)x U by making p0:(-x U)Û id natural between functors CÛ C.

(c)
Application \evX:(-)XxXÛ (-) is natural for each X ö obC, by Definition  4.7.2(c).

(d)
Theorem 4.4.5 showed that functors A:\CloneLÛ Set correspond to algebras for a unary theory L. Similarly natural transformations f:AÛ B correspond to their homomorphisms. It suffices to test naturality with respect to the operation-symbols (generating maps) since by composition of squares it follows automatically for general maps of \CloneL, as they are composites of operation- symbols.

(e)
Natural transformations between the (product-preserving) functors A,B:Cn×L\twoheadrightarrow Set which interpret algebraic theories correspond to homomorphisms f:AÛ B. In this case the definition of f must be extended from base types to contexts in the same way as in the remarks after Definition 4.6.2.

(f)
Consider \HX = C(-,X):CopÛ Set as a functor (instead of the union àG \CloneL(G,X) in Proposition 4.2.9). Then postcomposition with u:XÛ Y gives a natural transformation \HXÛ \HY.

(g)
The pairing operation   ,  :C(-,X)xC(-,Y) Û C(-,Xx Y) is also a natural transformation between functors CopÛ Set.

(h)
The abstraction operation l-,X,Y: C(-x X,Y)Û C(-,[XÛ Y]) of a (raw) cartesian closed structure (Definition 4.7.2(c)) is another natural transformation between functors CopÛ Set.

Natural transformations show up even when we only set out to consider categories and functors.

PROPOSITION 4.8.3 Let C and G be categories.

(a)
Their product GxC in the category Cat of categories and functors has object class (obG)x( obC) and hom-sets
 (GxC) ÌÒ EÂ,XÂ,E,X —½ = G(EÂ,E)xC(X Â,X)
with componentwise composition, cf Proposition  3.5.1. The pairing operation and projection functions are as expected.

(b)
In particular for groups (one-object categories), the factors C and G are isomorphic to subgroups of the product GxC by fÛ id,f and hÛ h,id, and these commute.

(c)
Let P:GxCÛ D be a functor (``of two variables'') and h:EÂÛ E a morphism of G. Then P(h,-):P(EÂ,-)Û P(E,-) is a natural transformation between functors CÛ D. omitted diagram environment

(d)
Suppose that the value \funcPo(E,X) of the functor on objects is given, together with P(E,f) and P(h,X), functorially in each argument separately, such that the square above commutes. Then the (``joint'') functor P:GxC Û D can be defined, cf 3.5.1(c). []

It is often the case that ``naturally defined'' constructions are functorial or natural in the formal sense by completely routine calculation. However normality, like functoriality (Examples 4.4.6ff), does carry mathematical force, since it provides an equation, and may be the point at issue, as it is in Theorem 7.6.9.

1

1

Composition   We shall use the following scheme to discuss composition of natural transformations; it also explains the geometrical terminology.

omitted diagram environment

DEFINITION 4.8.4 The vertical composite f;y:FÛ H is defined by (f;y)X = (fX);(yX), as in the following diagram:

omitted diagram environment

The identity for this composition is defined by (\idF)X = \idFX = F\idX, but it is often called just F. We never use (;) to compose functors. For posets, vertical composition is the transitivity of the pointwise order.

On the other hand, functors themselves apply to morphisms and hence to natural transformations, giving K·f and L·f. These are natural because the functors K and L preserve commutativity of the naturality square for f. Natural transformations also apply to the results of the functors on the objects, to give q·F and q·G, which are natural by instantiation. These are related by the square,

omitted diagram environment

which commutes by naturality of q. Note that the object X is completely passive; in fact if we replace it by a morphism f:XÛ Y we obtain the commutative cube which shows naturality of q·f. For posets, we are simply applying a monotone function to the pointwise order.

DEFINITION 4.8.5 The common composite is a natural transformation

 q·f = (K·f);(q·G) = (q· F);(L·f):(K·F)Û (L·G)
which is called the horizontal composite. The notation is inherited from composition of functors, and is consistent with writing the name of a functor for its vertical identity natural transformation. The identity for this composition is the (componentwise) identity natural transformation on the identity functor, id = \id\idC:\idCÛ \idC.

LEMMA 4.8.6 The two composition operations are related by the middle four interchange law,

 (q;c)·(f;y) = (q·f);(c· y)
as suggested by the diagram opposite. []

LEMMA 4.8.7 A natural transformation f is vertically invertible iff every component fX is invertible, and is then called a natural isomorphism. It is horizontally invertible iff also the functors which it relates are themselves invertible. []

EXAMPLES 4.8.8 The following are natural isomorphisms:

(a)
Pairing and l-abstraction (Examples  4.8.2(g) and (h)) make
 C(-,X)xC(-,Y) ¤ \HXx Y     and     C(-x X,Y) ¤ \H[XÛ Y].

(b)
The double transpose (-)^^:VÛ V** for a finite-dimensional vector space; this was the original example considered by Saunders Mac Lane and Sammy Eilenberg (1945), in order to distinguish this from the ``unnatural'' (basis-dependent) isomorphism V ¤ V*.

(c)
Any natural transformation between functors F,G:C \twoheadrightarrow D for which either C or D is a group, groupoid or equivalence relation.

(d)
In particular between permutation or matrix representations of a group.

Equivalences   Functors are the means of exchange between categories, so since functors are only defined up to isomorphism, exchange between categories is a notion of isomorphism that is further weakened by putting isomorphism for equality. In Section 7.6 we exploit the difference between strong and weak equivalences to resolve the issue of whether products, exponentials, etc in a category are structure or properties.

DEFINITION 4.8.9 A functor F:SÛ A is

(a)
an isomorphism of categories if there is a functor U:AÛ S such that \idS = U· F and F·U = \idA as functors, ie on both objects and morphisms;

(b)
a strong equivalence of categories if the following are given together with F:

• a functor U:AÛ S, called its pseudo-inverse,

• natural isomorphisms h:\idS ¤ U·F and e:F·U ¤ \idA, and

• the laws F(hX);e(FX) = \idFX and h(U Y);U( eY) = \idU Y hold;

(c)
an equivalence functor if it is full, faithful and also essentially surjective (Definition  4.4.8(g)).

(d)
As in Remark 3.6.7(d) we also say that two categories S and \cat T are weakly equivalent if a third category A and equivalence functors F:SÛ A and G:\cat TÛ A are given.

We write S @ A to indicate that categories are equivalent, making it clear in each context whether we mean strongly or weakly. See Definition  3.6.7 for the preorder version and Exercise  3.26 for the need for Choice.

We shall show in Corollary 7.2.10(c) that, with Choice, strong and weak equivalence coincide, ie any equivalence functor F has a pseudo-inverse, but this is determined only up to unique isomorphism, not equality. For given Y ö obA there may be many objects X ö obS with F X ¤ Y, and any such object may itself have many automorphisms. (The reason for postponing the proof is simply to avoid repetition, since it is technically the same as the relationship between universal properties and categorical adjunctions.) Exercises 4.36ff explore equivalences for monoids.

Functor categories   As we observed in Proposition 4.1.5ff, categories may arise as structures as well as congregations. In particular, some of the more exotic ``domains'' in the literature [HP89, Tay89] are categories rather than posets.

THEOREM 4.8.10 The category Cat of small categories and functors (Remark  4.1.8) has a cartesian closed structure.

PROOF: We shall follow the four-point plan set out in Theorem  4.7.13, but Proposition  4.8.3 has already discussed the product. To compare with Proposition 3.5.5, think of a category as a ``preorder with proofs'' (Definition  4.1.6). The generalisation forces us to give notation explicitly for them: f:FÛ G and f:\typeX1Û \typeX2 are ``the reasons why f È g and x1 È x2'' and monotonicity becomes the idea of a functor.

(a)
We know that functors XÛ Y and natural transformations between them form a category with vertical composition.

(b)
Next we show that ev:[XÛ Y ]xXÛ Y is a functor. A map in its source category consists of a natural transformation f:FÛ G and a morphism f: \typeX1Û \typeX2. The naturality square (Definition  4.8.1) for f at f corresponds to that in Proposition 3.5.5. Its diagonal defines evaluation on maps, by ev(f,f) = f f. A similar diagram of nine objects in four squares shows that composites are preserved.

(c)
To show that l preserves functoriality, let P:Gx XÛ Y be a functor. Then so are \expx P(UÂ) = P(UÂ,-) and \expx P(U) = P(U,-); moreover h:UÂÛ U gives rise to a natural transformation between them, \expx P(h) = P(h,-) (Example 4.8.3(c)).

(d)
Finally, naturality and the b- and h-rules must be tested on maps as well as on objects. []

REMARK 4.8.11 As Set is not a small category, the size problems have to be handled differently in the next result. In practice, the easiest way is to continue to treat functors as schemes of constructions, but the objects of SetCop also have an alternative representation by the Grothendieck construction (Proposition  9.2.7), so long as at least C remains small. For the (large) category-domains mentioned above, it is still possible to control the size of the functor categories, because the functors in question are Scott-continuous and are therefore determined by their values on ``finite'' objects as in Proposition 3.4.12. We restrict attention to those locally finitely presentable categories (Definition  6.6.14(c)) which have a set of generators in the sense of Definition 4.5.4.

The Yoneda Lemma   The following theorem is the abstract result which underlies the regular (Cayley) representation studied in Section 4.2 (and, for posets, in Sections 3.1 and 3.2). Unfortunately, the abstract version is often all that is presented, leaving students unenlightened and, more seriously, depriving them of a powerful technique. Section 4.3 used it to construct the category of contexts and substitutions of a formal language, which we shall develop in Chapter VIII. Proposition  3.1.8 gave the poset analogues of parts (b) and (c).

THEOREM 4.8.12 Let C be a category and X,Y ö obC.

(a)
Let fG :C(G,X)Û C(G,Y) be any system of functions. Then f(-) is natural iff it arises by postcomposition with some map f:XÛ Y as in Example  4.8.2(f), and then f is unique.

(b)
Hence \H(-):C\hookrightarrow Set Cop (where \HX ¤ C(-,X):Cop Û Set) is a full and faithful functor, known as the Yoneda embedding.

(c)
For any functor F:CÛ Set and object X ö obC,
 SetCop(\HX,F) ¤ FX
naturally. (This part is called the Yoneda Lemma itself, 1954.) omitted diagram environment

PROOF:

(a)
[[a]] Put f = fX(\idX), so this is uniquely determined by f. Then by naturality with respect to

u:G = X Û D, we have fD (u) = u;f.

(b)
[[b]] Verify that post(f) is functorial in f; it is full and faithful by the previous part.

(c)
[[c]] Let f(-):\HXÛ F be natural. Put a = fX(\idX) ö FX. Then by naturality with respect to u:GÛ X, fG (u) = Fu(a). Conversely, verify that this defines a natural transformation for any a ö FX. []

By Exercises 4.40 and 4.41, the Yoneda embedding preserves products (indeed all limits) and exponentials. Section 7.7 is a powerful application of the Yoneda lemma to the equivalence between semantics and syntax.

DEFINITION 4.8.13 A representable functor is one which is naturally isomorphic to some \HX = C(-,X) ( cf Definition  3.1.7).

EXAMPLES 4.8.14 By Examples 4.8.8(a),

(a)
Xx Y represents C(-,X)xC(-,Y) ¤ C(-,XxY);

(b)
XY represents C(-x Y,X) as C(-,XY);

(c)
P(Y) represents Rel(-,Y) in Lemma  3.3.6 as Set(-,P(Y)); for Y = 1, W = P(1) represents Sub (Proposition  5.2.6);

(d)
LiftY represents Pfn(-,Y) in Definition 3.3.7 as Set(-, LiftY).

We shall relate representable functors to universal properties in general in Corollary 7.2.10(a).

2-Categories   Since it is equipped with natural transformations as well as functors, the class of categories is an example of a two-dimensional generalisation of categories themselves.

DEFINITION 4.8.15 A 2-category has

(a)
a class of 0-cells;

(b)
for each pair of 0-cells, a category, whose objects and morphisms we call 1-cells and 2-cells respectively; the given 0-cells are called the left and right hand ends of these 1- and 2-cells; the source and target of the 2-cells are called their top and bottom sides or edges and the composition is styled vertical;

(c)
for each pair of 1-cells or 2-cells of which the right side of the first is the left side of the second, a horizontal composite 1- or 2-cell;

such that the vertical and horizontal associativity and identity laws and the middle four interchange law hold. There is a corresponding notion of 2-functor. Beware that 2-cells are not square but lens-shaped, with two ends and two sides, cf the diagram before Definition  4.8.4.

EXAMPLES 4.8.16 The following each define the 0-, 1- and 2-cells of 2-categories:

(a)
C/at: categories, functors and natural transformations;

(b)
Pos: posets, monotone functions and (instances of) the pointwise order; horizontal composition is defined by the monotonicity of functional composition ( cf the proof of Proposition  3.5.5);

(c)
Rel: sets, binary relations and inclusion;

(d)
Sp: topological spaces, continuous functions and the specialisation order (Example 3.1.2(i)) pointwise;

(e)
the objects and morphisms of any category, with only identity 2-cells (the discrete 2-category on a category);

(f)
\Frak CnÛ : the types, raw terms and standard reduction paths of the l-calculus (Exercise 4.34) .

Sometimes composition is only defined up to isomorphism, satisfying certain coherence equations that were identified by Saunders Mac Lane and Max Kelly (1963); structure of this kind is called a bi-category.

(g)
The points, paths and homotopies in a topological space form a bi-category (Exercise 4.43); a 2-functor p1(X)Û C takes a homotopy, ie a continuous function IxIÛ X, to a commutative square in C, a fact which we use to prove van Kampen's Theorem 5.4.8.

(h)
Conversely, Exercise 4.49 about l-abstraction of natural transformations may be seen as homotopy of functors.

Since there are two directions of motion, there are two independent ways of forming opposite 2-categories, and a third by doing both of them. Hence there are three notions of contravariant 2-functor. We say that a functor is ``contravariant at the 1- and/or 2-level.''