Personal tools

User:Michiexile/MATH198/Lecture 6

From HaskellWiki

< User:Michiexile | MATH198(Difference between revisions)
Jump to: navigation, search

Revision as of 20:24, 27 October 2009



1 Useful limits and colimits



One useful theorem to know about is:

Theorem The following are equivalent for a category C:

  • C has all finite limits.
  • C has all finite products and all equalizers.
  • C has all finite colimits.
  • C has all finite coproducts and all coequalizers.
  • C has all pushouts and an initial object.















1.1 Pullbacks

The preimage f − 1(T) of a subset T\subseteq S along a function f:U\to S is a maximal subset V\subseteq U such that for every v\in V: f(v)\in T.

We recall that subsets are given by (equivalence classes of) monics, and thus we end up being able to frame this in purely categorical terms. Given a diagram like this:


where i is a monomorphism representing the subobject, we need to find an object V with a monomorphism injecting it into U such that the map fi: U\to S factors through T. Thus we're looking for dotted maps making the diagram commute, in a universal manner.

The maximality of the subobject means that any other subobject of U that can be factored through T should factor through V.

Suppose U,V are subsets of some set W. Their intersection U\cap V is a subset of U, a subset of V and a subset of W, maximal with this property.

Translating into categorical language, we can pick representatives for all subobjects in the definition, we get a diagram with all monomorphisms:


where we need the inclusion of U\cap V into W over U is the same as the inclusion over V.

Definition A pullback of two maps A \rightarrow^f C \leftarrow^g B is the limit of these two maps, thus:


By the definition of a limit, this means that the pullback is an object D with maps \bar f: D\to B, \bar g: D\to A and f\bar g = g\bar f : D\to C, such that any other such object factors through this.

For the diagram U\rightarrow^f S \leftarrow^i T, with i:T\to S one representative monomorphism for the subobject, we get precisely the definition above for the inverse image.

For the diagram U\rightarrow W \leftarrow V with both map monomorphisms representing their subobjects, the pullback is the intersection.

1.2 Pushouts

Often, especially in geometry and algebra, we construct new structures by gluing together old structures along substructures. Possibly the most popularly known example is the Möbius band: we take a strip of paper, twist it once and glue the ends together.

Similarily, in algebraic contexts, we can form amalgamated products that do roughly the same.

All these are instances of the dual to the pullback:

Definition A pushout of two maps A\leftarrow^f C\rightarrow^g B is the co-limit of these two maps, thus:


Hence, the pushout is an object D such that C maps to the same place both ways, and so that, contingent on this, it behaves much like a coproduct.

2 Free and forgetful functors

Recall how we defined a free monoid as all strings of some alphabet, with concatenation of strings the monoidal operation. And recall how we defined the free category on a graph as the category of paths in the graph, with path concatenation as the operation.

The reason we chose the word free to denote both these cases is far from a coincidence: by this point nobody will be surprised to hear that we can unify the idea of generating the most general object of a particular algebraic structure into a single categorical idea.

The idea of the free constructions, classically, is to introduce as few additional relations as possible, while still generating a valid object of the appropriate type, given a set of generators we view as placeholders, as symbols. Having a minimal amount of relations allows us to introduce further relations later, by imposing new equalities by mapping with surjections to other structures.

One of the first observations in each of the cases we can do is that such a map ends up being completely determined by where the generators go - the symbols we use to generate. And since the free structure is made to fulfill the axioms of whatever structure we're working with, these generators combine, even after mapping to some other structure, in a way compatible with all structure.

To make solid categorical sense of this, however, we need to couple the construction of a free algebraic structure from a set (or a graph, or...) with another construction: we can define the forgetful functor from monoids to sets by just picking out the elements of the monoid as a set; and from categories to graph by just picking the underlying graph, and forgetting about the compositions of arrows.

Now we have what we need to pinpoint just what kind of a functor the free widget generated by-construction does. It's a functor F: C\to D, coupled with a forgetful functor U: D\to C such that any map S\to U(N) in C induces one unique mapping F(S)\to N in D.

For the case of monoids and sets, this means that if we take our generating set, and map it into the set of elements of another monoid, this generates a unique mapping of the corresponding monoids.

3 Adjunctions

Modeling on the way we construct free and forgetful functors, we can form a powerful categorical concept, which ends up generalizing much of what we've already seen - and also leads us on towards monads.

  • Free and forgetful
  • Curry and uncurry

4 Homework

  1. Prove that an equalizer is a monomorphism.
  2. Prove that a coequalizer is an epimorphism.
  4. Prove that if the right arrow in a pullback square is a mono, then so is the left arrow. Thus the intersection as a pullback really is a subobject.
  5. Prove that if both the arrows in the pullback 'corner' are mono, then the arrows of the pullback cone are all mono.
  6. What is the pullback in the category of posets?
  7. What is the pushout in the category of posets?