Lambda the Ultimate

• What is Category Theory?
• Why should we be interested in Category Theory?
• How much Category Theory is it useful to know?
• What kinds of things can you do with Category Theory in
Software Engineering?

Ought to be posted to front page. :-)

For someone who liked the style of intro material in this presentation and wants to learn more, I would recommend "Conceptual Mathematics" by Lawvere and Schanuel, or "Sets for Mathematics" by Lawvere and Rosebrugh.

Unlike some earlier books, they don't shy away from using intuitions about the category of Sets as a basis for developing intuitions about general category theory. (A good thing for beginners I think)

When reading it, I don't understand how he infered any of the equivalences he shows. An arrow from B to A is not necessarily the same as another arrow from B to A, right? Otherwise it would never make sense to draw multiple arrows from B to A.

And if f : A->B and h : B -> A are functions, f(h(x)) does not necessarily return x! It depends on what B and A are made up of internally, and on the definitions for f and h (if you think of the objects as sets and the arrows as functions between sets).

The only way I've made sense of the proof is to assume that, on slide 6, all of the categories shown have objects which are singleton sets, and thus both arrows from B to A are equivalent. But that seems like a silly proof in that case, and that also makes the picture in the lower left hand corner "not a category"

The thing to remember is that the diagram shows ALL of the arrows for the category.

By the axiom of composition, if A->B exists and B->C exists a specific A->C must exist that is equivalent to A->B->C.

So lets say you have a category that has two objects and only two non-identity arrows A->B and B->A. Then the composite A->B->A MUST be equivalent to the identity arrow, which is the only other arrow from A->A. Likewise with B->A->B must be the identity arrow for B.

This is actually a little tricky even if you have a backgroud in CT, since it is not invariably the case that the arrows shown are exhaustive; sometimes the composition is left to be inferred.

The associative part of the proof shows that there can't be two DIFFERENT arrows from B to A in this case, since application of the associative law shows that they have to be equivalent.

It depends on what B and A are made up of internally

One of the key concepts of CT is that you try to only describe the mappings externally. Having said that, it sure as hell helps if you have a good grasp of what the internals look like to make sense of it. ;-) So often you find yourself asking "What internal structure would give me that mapping in that category?"

that also makes the picture in the lower left hand corner "not a category"

The trick part here is that because there is a third object, the associative law doesn't kick in and force equality.

Imagine that the first object is the empty set, the middle one and the far one are arbitrary non-empty sets. There is a unique arrow from the empty set to any other set (the empty inclusion). That accounts for both maps from the first object. The composition of the empty inclusion with either of the other maps (doesn't matter what they are) is empty. So even if those mappings are entirely distinct their composite with the empty inclusion is the same.

This satisfies the category axioms, so this can be a category.

So what you're saying is that if the morphism exists, it must be drawn (or be an implicit identity morphism as descirbed in the note). In your hypothetical picture, if I don't see an explicit arrow from A to A, then the only possible morphism from A -> A is the identity morphism.

Okay, I was looking at slide 5 as if it were a collection of axioms and derivation rules (which I guess it is) and thinking of the pictures on slide 6 as base pictures that one can apply the rules to in order to derive new pictures that describe the exact same category as the original category. The idea of requiring one to draw the entire collection of morphisms, including derivable ones, didn't occur to me.

At first I was going to write that this requirement (of drawing the whole set "explicitly" was something I wasn't used to seeing, but then something clicked within me. This is sort of like the difference between describing the natural numbers as "{0, 1, 2, ... }" versus with the Peano axioms ('zero', 'succ', and various constraints relating them). The former doesn't explicitly denote every element of the set, but the reader is meant to imagine that the "..." expands into an infinite sequence. So these pictures are like writing "{ a, b, c, ... }" and then you're supposed to apply the definitions on slide 5 to verify that the informal description actually matches up with the class that's being decribed...

Does this make any sense?

I'm going to go back and re-read my print-out of the slides.

I think that was definitely part of my confusion when reading the slides; I thought that Slide 6 was making a point of having the lower right picture be the only non-category depicted.

Right, in this case. As I say though, this is a bit confusing because this in not always the case in the literature.

thinking of the pictures on slide 6 as base pictures that one can apply the rules to in order to derive new pictures

Not all pictures on 6 are valid categories at all. (The 6th being invalid of course)

you're supposed to apply the definitions on slide 5 to verify that the informal description actually matches up with the class that's being decribed...

Does this make any sense?

Precisely!

Yep. I actually missed that one too, because I automatically "supplied" the composition in my head. ;-)

An object lesson in inconsistent notation, I guess.

Also, the wording on the slides, `Which can be valid categories?', is IMO very misleading. There are many ways to specify a category, and sometimes two methods can use the same data to describe different categories. Slide 6 gives some data, a graph, and asks whether it is a category, but does not give the method. (We should remember that this point may have been clarified verbally during the talk.) To figure out what the author has in mind, one has to look at the proof on Slide 7.

For example, there is a method called free completion which can produce a category from every graph; it's called the path category because the morphisms are paths in the underlying graph. But clearly this is not what the author meant.

What does he mean, then? What is actually being asked here is better phrased, `Which of these diagrams can commute?' where `diagram' is used in the technical sense of a graph homomorphism. But even that is wrong because one needs to specify the ambient category. In this case, the ambient category is different for each graph, and knowing that there are no unmentioned morphisms is critical for deciding the question. The fact that there are no unmentioned morphisms can be expressed by saying that the diagrams are `full', another technical term.

So, a better way to phrase the question is, `Which of these full diagrams can commute?' But even this is not so well-defined because a diagram is labeled by definition, and one must know that whether there are other, non-trivial equalities between edges. (Usually there are.) This amounts to specifying the domain of each diagram, which is again different for each picture, so I won't get into it.

This illustrates the pitfalls of using an ill-defined syntax. In the categorical community, diagrams (in the non-technical sense) are a commonly used tool for describing semantics, and thus there is a convention for interpreting them, just as there is a convention for interpreting a more conventional syntax like terms (textual expressions). But the problem here is that members of the audience cannot be expected to know what the convention is. The importance of this issue can be gleaned from the fact that Barr and Wells' CTCS spends almost ten pages on the semantics of diagrams.

It's ironic that the confusion here, which stems from mixing up syntax and semantics, is exactly the sort of thing category theory is supposed to be good at avoiding!

The more I think about it, the more I think this has nothing to do with CT. It is really a combinatorics question, which uses CT as an example.

On the one hand, I'll cut Easterbrook some slack, since it was a presentation, and it was probably a good way to briefly introduce an audience to CT.

On the other hand, I think there is an appalling habit in Math of assuming too much in the notation and expression of problems. ("I figured this out so the reader can too." or "I'd better not spell out the detail, or it won't be elegant enough.")

The fatal flaw with these diagrams is that they are NOT full graphs since they omit the identity arrows. If he had simply added those, it would have been clearer what he meant. Without them it is too easy to confuse them with the more typical example of the category "generated by" the graph.

I have to assume he thought his audience had no idea about CT, so he was just trying to get across the basic definition.