Introduction to Category Theory/Products are Limits

From Wikiversity
Jump to navigation Jump to search

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.)

Related resources[edit]