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.
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.
|
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
|
LEMMA 4.8.6 The two composition operations are related by the middle four interchange law,
|
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:
|
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
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.
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.
|
PROOF:
u:G = X ® D, we have fD (u) = u;f.
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),
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
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:
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.
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.''