Mark Gritter (markgritter) wrote,
Mark Gritter
markgritter

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
Subscribe
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 12 comments