Mark Gritter (markgritter) wrote,
Mark Gritter

Category Theory Geekery

Allergy shots == spending a half hour waiting in their office twice per week. (They recommend this so that I don't die.) I'm trying to work my way through Robert Goldblatt's "Topoi: The Categorial Analysis of Logic" in order to pass the time.

Nearly every category-theory proof works out to:

1. Remember what all the terms mean.
2. Draw a widget.
3. Chase the arrows.
4. Magic happens! This often leaves one with a vaguely unsatisfying feeling.

Here's the exercise from section 3.13 in the book. Given a pullback:

Show that if f is monic, g must be monic as well.

Step 1: A is a pullback, which means that the diagram commutes (any path from X to Y is equal to any other path). Further, if there is another object Q with arrows to B to C that makes the diagram commute (a "cone"), then there is a unique arrow !p: Q->A that makes the resulting diagram commute.

(In Set a pullback A can be interpreted as ordered tuples from BxC for which k and j agree, along with the projections from BxC to B and to C.)

"monic" is the category theory version of "1-1" for functions. It means f is "left-cancellable" so that if x.f = y.f then x = y. (I'll use a period for arrow composition because I'm too lazy to insert HTML dot operators.)

Step 2: We want to show that the monic property holds for g as well. So suppose g.s1 = g.s2 for some arbitrary s1,s2:S->A. (S could be one of the existing objects, or a new one--- it doesn't matter.)

Then k.g.s1 = k.g.s2.

Because the diagram commutes, k.g.s1 = f.j.s2.

Also f.j.s1 = f.j.s2, which because f is monic means j.s1 = j.s2.

Now we can draw our widget, which is a "cone" from S to B and C:

Step 3: Does the new diagram commute? Yes, as we showed above k.g.s1 = f.j.s2, so both 'arms' of the cone from S fit. That means we can apply the pullback property, and introduce the unique arrow p.

What is p? Well, suppose we put s1 there. Then g.s1 (via the dotted line) = g.s1 trivially. And j.s1 = j.s2 we showed above. So s1 makes the diagram commute.

Now what is we put s2 there instead? Then j.s2 (dotted line) = j.s2 (solid line) trivially again. And g.s1 = g.s2 is what we assumed. So s2 makes the diagram commute as well.

Step 4: We showed s1 satisfies the properties of p, and also s2. But p is unique, so s1 = s2.
Tags: category theory, exercise, geek, mathematics
  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded