02 September 2006

A Categorical Definition

Categories, best described with commutative diagrams, allow for truly non-linear thinking, and yet they are usually defined linearly, similar to the way groups are usually introduced. This almost makes sense: morphisms, as one-dimensional objects, are about the most natural thing to compose linearly. And yet the power of category theory comes from the non-linear diagrams people draw, showing non-linear relationships between objects. The snake lemma, for instance, is poorly expressed and even more poorly understood if you are limited to writing words on a page.

I am, on this blog, constrained to poor, linear writing. Nevertheless, I would like to provide a definition of "category" using only visual, diagramatic ideas. Perhaps I will succeed in ASCIIing the diagrams. This definition, I hope, will ultimately be seen as providing a more basic understanding of these powerful creatures.


To begin with, a diagram is a (labeled) directed graph: it's composed of (labeled) vertices ("objects") connected by (labeled) directed edges ("arrows"). There is a natural notion of "subdiagram", formed by deleting any collection of edges, and any collection of vertices and all their edges. A category is a collection of diagrams, subject to certain rules, to be enunciated lower down. The diagrams in a category are said to commute. I will sometimes leave off labels, in which case I generally mean to refer to all (commutative) diagrams of that "shape".

Rule 0: A diagram commutes if and only if all its finite subdiagrams commute. (Thus any subdiagram of a commutative diagram commutes. In any category, the empty diagram commutes.)

One advantage of this construction is that I don't need any of that junk about "a collection of objects, and between each pair A and B of objects a set Hom(A,B) of arrows...". Instead, I can say simply that a morphism is a commutative diagram A ---> B, where I have left of the label on the arrow: I will write "f:A->B" for the very simple diagram of an arrow from A to B labeled by f, but only because I have to make it fit in this constrained formatting.

Rule 1: If two diagrams commute, then their disjoint union commutes. If diagram D contains an object label A, and E contains B, and if A ---> B commutes (morphism called f), then in the disjoint union we can connect A and B via f so that the diagram still commutes:
DDD      EEE
D f E
D A ---> B E


Often we will draw a dotted arrow in a diagram. In these notes, creating dotted arrows is too hard; I will use equal signs instead, as in ===>. A diagram with a dotted arrow means "If the diagram without the dotted arrow commutes, then there is exactly one diagram with an (labeled) arrow in place of the dotted one." Sometimes folks will write a label on the arrow, in which they mean the name (label) that the (unique) arrow which replaces it should have.

Rule 2: For any diagram E containing a finite chain (in the picture, I draw E "surrounding" the chain, to suggest that various objects in the chain might have other arrows to and from the rest of E), we have
EEEEEEEEEEEEEEEEEEEEEEEEE
E __ B -...-> C E
E /| \ E
E / _| E
E A =============> D E


So, in particular, some corollaries:
  • "composition"
    A -> B -> C
    ========>

  • "associativitiy"
    if  B -> C  and  B -> C  commute
    ^ > \ |
    | / > v
    A D

    then so do C and B
    > | ^ / v | >
    A -> D A -> D

    (of course, with all edges (consistently) labeled.)
  • "identity"
     A <==||    \\\    //
    \====/
    normally called "\mathbb{1}_A", I will just call this morphism "1_A". I will let you write out the "left and right identity laws" in this language; they follow from Rule 2.

However, one more rule concerning the various 1_A morphisms is necessary.

Rule 3If a commutative diagram contains 1_A:A->A for some A, then we can maintain commutativity by replacing this diagram with A: all arrows into and out of either A in the original diagram now go into and out of the single A in the new diagram. Conversely, any object A in a diagram may be replaced by 1_A:A->A, where all arrows on A are now duplicated, and placed once on each A. I will not try to draw this, but you should.

And that, folks, is it. Rules 0 through 3 suffice to define a category.


Of course, we should say some more, to convince you that pure diagrammatic thinking is useful. For instance, an isomorphism is a commutative diagram of the form
 --->
A B.
<---


With our "dotted arrow" (except I'm using equal signs) notation, we can go on to define "universal properties". It seems to me that there should really be "universal properties" and "co-universal properties", depending on which direction the arrows go. To define these, we introduce another new symbol [], which is kindof like ==>; whereas ==> defined an arrow uniquely, [] defines objects up to isomorphism. How? Well, say we have a diagram with a box. Then we're saying that (if the rest of the diagram commutes), then there's some object X which can fill the box (i.e. a labeling for that object that makes the diagram commute) s.t. if any other Y can also fill the box, then there's a dotted arrow from Y to X. I.e.:
  DD                  DD
DDDDDD DDDDDD
[] DD means that X DD
DDDDDD DDDDDD
DD DD

DD
DDDDDD
and if any other Y DD, then
DDDDDD
DD
DDDDDDDD
DD DD DD
Y => X DD
DD DD DD
DDDDDDDD

where the idea in the last picture is that Y and X each have all the arrows going from and to them and D that the original diagram says they should have. The dual notion to a universal property is a "co-universal property", in which Y => X is replaced by "Y <= X" in the definition. If needed, I will write that as {}.

Now, I don't actually know of any useful (co-)universal properties that are not (co-)limits — well, I think tensor products might be one, but I don't remember how to define that — so I really ought to just define limit. And maybe I should have just started with them, I dunno.

Anyhoo, given a (commutative) diagram D, the limit of the diagram lim D is the (universal property) diagram given by D with a box added, and arrows from the added box to each object in D. Co-limits are the dual notion. Limits, like anything defined via universal property, need not exist. Some examples:
A x B  =  lim  A  B

B
A x_C B = lim |
v
A -> C

terminal object = lim (empty diagram)

1_A
lim A = A ---> A, which we're considering to be equivalent to A.


I will stop here. Many category theory books from around here and onward start using diagrammatic reasoning and definitions more frequently, so I refer you to them for other definitions of other objects. My goal was to give diagrammatic definitions of the most basic elements of category theory, and to suggest that categories are best thought of not as collections of objects and morphisms, but simply as collections of diagrams.

No comments: