Introduction to Category Theory/Products are Limits

Cone over 2 objects

edit
 
Cone category over (C1, C2).

Let   be any two objects in category  . We define the cone category,  , as follows

  • Objects are 3-tuples  , where X is an object in  , and   is a morphism  , and   is a morphism  .
  • Arrows are morphisms   such that both triangles commute, in other word   is a morphism in   such that
     

We must check that this is really a category:

  • Identity morphism of object   in   is the identity morphism   in  .
  • Composition of   and   in   is the composition   in  . Commutativity of bigger triangles follows trivially from commutativity of smaller triangles. (Write equations if you want.)
  • Composition is associative   since it's associative in  .

Terminal object in Cone

edit

What is the terminal object in the category  ?

By the definition of terminal object it must be an object   such that

  • for every object   in   there is exactly one morphism  .

In other words

  • for every 3-tuple   there is exactly one morphism   in   such that   and  .

But this is exactly the universal property of the product  . We conclude

  • The terminal object in category  , if it exists, is the object  .

By duality argument we also have

  • The initial object in category  , if it exists, is the object  .

Functors

edit

A category is, among other things, a kind of algebraic system, but so far we've left out one of the most important ingredients in algebra, homomorphisms, which are, essentially, mappings that 'preserve structure'. Functors are the structure-preserving mappings of category theory, although functors are more immediately complicated than homomorphisms. To begin with, they come in two flavors, covariant and contravariant, the former defined as follows:

Definition of Covariant Functors

edit

A (covariant) functor F from category   to category   satisfies

  • F sends objects of   to objects of  .
  • F sends arrows of   to arrows of  .
  • If m is an arrow from A to B in  , then   is an arrow from   to   in  .
  • F sends identity arrows to identity arrows:  .
  • F preserves compositions:  .

Contravariant functors are similar, but the direction of the arrows gets reversed, we'll discuss them later.

Examples

edit

Monoid Functors

edit

We've already seen that a monoid is a category with a single object. So suppose   is a functor from the monoid   to the monoid  . These monoids have a single object, which we can just call  , so   will have to map   in   onto   in  .

  will also take arrows of   onto arrows of  , and the third condition (on sources and targets of arrows) will hold automatically.

So what about the last two? Well the first says that the identity arrows are preserved, the second that composition is. But these are exactly the conditions characterizing a monoid homomorphism! So for monoids (viewed as categories), functors are homomorphisms (as conventionally defined in abstract algebra books). This applies automatically to groups as well, which are just monoids where every arrow has an inverse.

Hom Functors

edit

Let   be a locally small category, and pick some object   of  . Now, for any object   of  , we have the set   of arrows with domain   and codomain   (a set, because   is locally small). So the mapping

 

looks like it might be the object part of a functor from   to  .

To get a functor, we need to do something with the arrows, specifically, an arrow   needs to become a function from   to  . An evident way to produce such a function is to tack   onto the end of the arrows in  :

 

It is then a straightforward exercise to show that the result, standardly notated  , is a functor. A useful notation is that   is often written  .

The fact that any locally small category produces Hom-functors means that any such category has substantial manifestations in  , some of the important ones expressed by the famous Yoneda lemma.

The Free Monoid Functor

edit

A more complex example is the free monoid functor which takes any set onto the free monoid generated by that set. Suppose   is an object of  . Then   is the monoid whose elements are strings of members of  , with concatenation as the binary operation, and the empty string serving as the identity (if you want to get very tedious, a string can be defined as a function whose domain is an initial segment of the natural numbers (e.g.   for some  , the case where   constituting the empty string), and whose codomain in  ).

To make this a bit more concrete, if  , then the members of   are   (infinitely many), plus an empty string often symbolized as   or  . Intuitively, 'free' means that the only identities that hold in this monoid are the ones required by the associative and identity laws, so that for example   and   are distinct (but in the free commutative monoid, they'd be the same, but different from   and  ). So that's the object part of this functor: it takes sets of elements (which may be finite in number) onto the sets of all strings on those elements (which will always be infinite in size, unless the set is empty). A superscripted Kleene star   is often used to represent the applying   to a set, in fields such as mathematical linguistics, so that   will be the set of strings made out of members of  .

Exercise: what does   look like?

Now to be a functor,   also has to do something to arrows. An arrow   of   is just a function, say from   to  , so what we do to compute the value   on   is replace each element of each string in   with its  -value. So if:

  •  ,

then

  •  

For people who want to be very fussy,   can be defined by induction over the length of strings.

Exercise: proove that   as defined above is really a functor.

This example will prove useful in defining the notion of 'adjunction', to come.

[SHOULD THE NEXT SECTION BE STUCK IN HERE AS ONE OF THE EXAMPLES? I'd rather keep multiple top levels, unless you add other top level sections.]

Binary Product Functor

edit

This next example takes a fair amount of space to explain, but is perhaps easier than the free monoid functor. The basic point is that if a category   has designated products, we can then construct a functor from the pair-category   to  .

Product of Objects

edit

For an object   of  , define:

  •  

(recall that 'has designated products means that there's some specific method for picking a particular product object for each pair  ).

Well that wasn't too hard!

Product of Morphisms

edit

But to make a functor, we need to do something with the morphisms of  , which are pairs of morphisms of  . Specifically, if   and   are arrows of  , then   is an arrow from   to  . Just thinking notationally, we'd expect to write the output of   on this as  , but then we need to construct something in   from   and   in such a way that   so-defined is a functor. This takes a bit of work.

The first step is to observe that If   are objects in category   where   exists, and   and   are any morphisms, then we have  , the unique morphism   satisfying the universal property for products. If g is any morphism  , then

 

by the universal property. [LINK TO DEDUCTION EXAMPLE, ???]

 
Product of morphisms f and g.

So now we move on to the defition. If   are objects in category   with designated prooducts, and   and   are any morphisms, then the product of   and  , denoted  , is the morphism

 .

This can be hard to remember at first, but eventually you get to be able to see that it basically is just the obvious thing to do its job.

This morphism commutes with the projection morphisms

 
 

If we also have morphisms   and  , then

 
 

and we get

 
 .

(Lots of Exercises here!!)

Functoriality

edit

For all this to define a functor, domains, codomains, associativity and identity elements must be preserved. So recall the definition of composition in a pair category:

 

And identities:

 

So we have our Proposition. If category   has all products, then mapping

 

defined by

 
 

is a functor.

Proof.

  • If   are two morphisms, it is obvious that   is a morphism from   to  .
  • The identity morphism of   is   and it's image   is easily seen to be the identity morphism of  .
  •  

 

Unary Product Functor

edit

Given what we've just done, this example should be easy, perhaps even too easy to be worth bothering with, but it's important in the development of later topics such as Exponentials.

Unary Product on Object

edit

Let   be a category with products and let A be any object in  . We define a product functor

 

by setting

  for every object B in  
  for every morphism  .

Let's verify this really is a functor.

  • For every morphism  , the morphism   is a morphism from   to  .
  • Image of the identity arrow   is
     .
  • For every morphisms   and   we have
     .

Unary Product on Arrow

edit

Just like we define functor   for every object A, we can define similar mapping   for every morphism f. For reasons to be explained later we define this mapping as follows

 
 

In other words the domain of this mapping is the objects of   and the codomain is the arrows of  . The image of object C is a product of f and the identity morphism of C.

 
Functor Ax- is natural.

This mapping has the following commutativity property:

Proposition. Let   be a morphism in category  . The mapping   commutes with respect to functors   and  . To be more specific, for every morphisms   the following equation holds

 .

Proof.

 
   

We will later see that a mapping with this kind of commutativity property is a natural transformation from one functor to another.

Category of 2-Functors

edit

Category   is a category with 2 objects (1 and 2) and no arrows other that the two identity arrows. We wish to define a category  , whose objects are functors from the category   to category  . In order to make this a category, we must answer the question: What is an arrow from one functor to another? Before we can answer this, we must have better understanding of functors in this category.

Objects

edit

What is a functor F from the category   to arbitrary category  ?

  • Functor must map objects in   to objects in  . So   and  , for some objects   in  .
  • Functor must map arrows in   to arrows in  . The only arrows in   are the identity arrows. So we must have   and  .
  • Only compositions of arrows in   are compositions of the identity arrow with itself. We easily verify   and  .

Thus   is a functor   that maps

  • object 1 to object   and
  • object 2 to object  .

Arrows

edit

Arrows between functors are called natural transformations. What could natural transformations in this functor category look like?

Let   be objects in category  . What could a natural transformation from functor   to functor   possibly be? Since all the functors consist of a pair of objects from  , it seems reasonable to define natural transformations to be pairs of morphisms from  . So for every morphisms   and   in  , we define a natural transformation   from functor   to functor   to be a mapping

 
 .

We define composion of natural transformations pointwise, that is

 

Summary

edit

Category   consists of

  • Functor   for every pair of objects   in  .
  • Natural transformation  , for every pair of morphisms   in  .

It is obvious that this category is isomorphic to the pair category  .

Preview: Limit functor

edit

We now introduce the limit notation but defer the actual definition to a later lesson.

Let   be a category with all products. The limit of functor   in the category  , is the terminal object in the category  .

 .

Projection morphisms are usually clear from the context, so we can drop them and simple write

 .
 
Limit functor.

Proposition. If category   has all products, then mapping

 

defined by

 
 

is a functor.

Proof. Since   is isomorphic to  , this follows from earlier result.




OLD: Product is Limit

edit

Category   is a category with 2 objects (1 and 2) and no arrows other that the two identity arrows.

What is a functor F from the category   to arbitrary category  ?

  • Functor must map objects in   to objects in  . So   and  , for some objects   in  .
  • Functor must map arrows in   to arrows in  . The only arrows in   are the identity arrows. So we must have   and  .
  • Only compositions of arrows in   are compositions of the identity arrow with itself. We easily verify   and  .

Thus   is a functor   that maps

  • object 1 to object   and
  • object 2 to object  .

We now introduce the limit notation but defer the actual definition to a later lesson.

The limit of functor  , if it exists, is the terminal object in the category  .

 .

Projection morphisms are usually trivial from the context, so we can drop them and simple write

 .

The colimit of functor  , if it exists, is the initial object in the category  .

 .

OLD: Product of Morphisms

edit

If A, B, and X are objects in category   and   and   are any morphisms, we use notation   for the unique morphism   given by the universal property. If g is any morphism  , then

 

by the universal property.

 
Product of morphisms f and g.

If A, B, X and Y are objects in category   and   and   are any morphisms, then the product of f and g, denoted  , is the morphism

 .

This morphism commutes with the projection morphisms

 
 

If we also have morphisms   and  , then

 
 

and we get

 
 .

OLD: Product Functor

edit

Let   be a category with products and let A be any object in  . We define a product functor

 

by setting

  for every object B in  
  for every morphism  .

Let's verify this really is a functor.

  • For every morphism  , the morphism   is a morphism from   to  .
  • Image of the identity arrow   is
     .
  • For every morphisms   and   we have
     .
 
Functor Ax- is natural.

Proposition. Functor   is natural in A. This means that if   is any morphism, then there is natural transformation from functor   to functor  . This in turn simply means that the diagram on the right commutes for all morphisms  . Mapping   is a natural transformation from functor   to functor  .

Proof.

 
   

OLD: Natural Transformation

edit

If F and G are covariant functors between the categories   and  , then a natural transformation   from F to G associates to every object X in   a morphism   in   called the component of   at X, such that for every morphism   in   we have  . This equation can conveniently be expressed by the commutative diagram

 
diagram defining natural transformations

Natural transformations are usually far more natural than the definition above.

OLD: Category of Functors

edit

We wish to define a category  , whose objects are functors from the category   to category  . What could the arrows in this category be?

Let   be objects in category  . What is a natural transformation from functor   to functor  ? To every object in category   we must associate a morphism in category   in such a way that for every morphism in   the corresponding diagram in   commutes. But there are no morphisms other than the identity morphisms in category  , so the diagram commutes trivially. For every pair of morphisms   and   in  , there is a natural transformation   from functor   to functor  .

Category   consists of

  • Functor   for every pair of objects   in  .
  • Natural transformation  , for every pair of morphisms   in  .

It's trivial to verify that it really is a category. (What is the identity morphism of functor  ? Why is the composition of natural transformations a natural transformation? Why is composition associative?)

OLD: Limit is Functor

edit
 
Limit functor.

We still won't give the general definition of limit, sorry. Instead we will prove that in the special case of category  , the limit is a functor from category   to category  .

Proposition. If category   has all products, then mapping

 

defined by

 
 

is a functor.

Proof.

 

OLD: Hmmm

edit

We end this lesson with two cryptic formulas...

 
 
 
 
 

and

 
 
 
 
 

where

 

is defined by

 .

(This is an example of adjoints.)

edit