Building Structure in Category Theory: Definitions to Build On

Dec 29 2011 Published by under Category Theory

The thing that I think is most interesting about category theory is that what it's really fundamentally about is structure. The abstractions of category theory let you talk about structures in an elegant way; and category diagrams let you illustrate structures in a simple visual way. Morphisms express the structure of a category; functors are higher level morphisms that express the structure of relationships between categories.

In my last category theory post, I showed how you can use category theory to describe the basic idea of symmetry and group actions. Symmetry is, basically, an immunity to transformation - that is, a kind of structural property of an object or system where applying some kind of transformation to that object doesn't change the object in any detectable way. The beauty of category theory is that it makes that definition much simpler.

Symmetry transformations are just the tip of the iceberg of the kinds of structural things we can talk about using categories. Category theory lets you build up pretty much any mathematical construct that you'd like to study, and describe transformations on it in terms of functors. In fact, you can even look at the underlying conceptual structure of category theory using category theory itself, by creating a category in which categories are objects, and functors are the arrows between categories.

So what happens if we take the same kind of thing that we did to get group actions, and we pull out a level, so that instead of looking at the category of categories, focusing on arrows from the specific category of a group to the category of sets, we do it with arrows between members of the category of functors?

We get the general concept of a natural transformation. A natural transformation is a morphism from functor to functor, which preserves the full structure of morphism composition within the categories mapped by the functors. The original inventor of category theory said that natural transformations were the real point of category theory - they're what he wanted to study.

Suppose we have two categories, C and D. And suppose we also have two functors, F, G : C → D. A natural transformation from F to G, which we'll call η maps every object x in C to an arrow ηx : F(x) → G(x). ηx has the property that for every arrow a : x → y in C, ηy º F(a) = G(a) º ηx. If this is true, we call ηx the component of η for (or at) x.

That paragraph is a bit of a whopper to interpret. Fortunately, we can draw a diagram to help illustrate what that means. The following diagram commutes if η has the property described in that paragraph.

natural-transform.jpg

I think this is one of the places where the diagrams really help. We're talking about a relatively straightforward property here, but it's very confusing to write about in equational form. But given the commutative diagram, you can see that it's not so hard: the path ηy º F(a) and the path G(a) º η<sub compose to the same thing: that is, the transformation η hasn't changed the structure expressed by the morphisms.

And that's precisely the point of the natural transformation: it's a way of showing the relationships between different descriptions of structures - just the next step up the ladder. The basic morphisms of a category express the structure of the category; functors express the structure of relationships between categories; and natural transformations express the structure of relationships between relationships.

Of course, this being a discussion of category theory, we can't get any further without some definitions. To get to some of the interesting material that involves things like natural transformations, we need to know about a bunch of standard constructions: initial and final objects, products, exponentials... Then we'll use those basic constructs to build some really fascinating constructs. That's where things will get really fun.

So let's start with initial and finial objects.

An initial object is a pretty simple idea: it's an object with exactly one arrow to each of the other objects in the category. To be formal, given a category C, an object o \in Obj(C) is an initial object if and only if \forall b \in Obj(c): \exists_1 f: o \rightarrow b \in Mor(C). We generally write 0_c for the initial object in a category. Similarly, there's a dual concept of a terminal object 1_c, which is object for which there's exactly one arrow from every object in the category to 1_c.

Given two objects in a category, if they're both initial, they must be isomorphic. It's pretty easy to prove: here's the sketch. Remember the definition of isomorphism in category theory. An isomorphism is an arrow f : a \rightarrow b, where \exists g : b \rightarrow a) such that f \circ g = 1_b and g \circ f = 1_a. If an object is initial, then there's an arrow from it to every other object --- including the other initial object. And there's an arrow back, because the other one is initial. The iso-arrows between the two initials obviously compose to identities.

Now, let's move on to categorical products. Categorical products define the product of two objects in a category. The basic concept is simple - it's a generalization of cartesian product of two sets. It's important because products are one of the major ways of building complex structures using simple categories.

Given a category C, and two objects a,b \in Obj(C), the categorical product a \times b consists of:

  • An object p, often written a \times b;
  • two arrows p_a and p_b, where p \in Obj(C), p_a : p \rightarrow a, and p_b : p \rightarrow b.
  • a "pairing" operation, which for every object c \in C, maps the pair of arrows f : c \rightarrow a and
    g : c \rightarrow b to an arrow \langle f,g \rangle : c \rightarrow a\times b, where \langle f, g \rangle has the
    following properties:

    1. p_a \circ \langle f,g \rangle = f
    2. p_b \circ  \langle f,g \rangle = g
    3. \forall h : c \rightarrow a \times b: \langle p_a \circ h, p_b \circ h \rangle = h

The first two of those properties are the separation arrows, to get from the product to its components; and the third is the merging arrow, to get from the components to the product. We can say the same thing about the relationships in the product in an easier way using a commutative diagram:

One important thing to understand is that categorical products do not have to exist. This definition doen not say that given any two objects a and b, that a \times b is a member of the category. What it says is what the categorical product
looks like if it exists. If, for a given pair a and b of objects, there is an object that meets this definition, then the product of a and b exists in the category. If not, it doesn't. For many categories, the products don't exist for some or even all of the objects in the category. But as we'll see later, the categories for which the products do exist have some really interesting properties.

2 responses so far

  • delosgatos says:

    I really enjoyed Category Theory. I remember one graduate topology class where I used "it's an initial object in (some) category" as a one line proof of something that took several lines of rather fussy proof if you did it from

    Couple of questions on the product definition. (Have to use parens instead of angle braces to get past the HTML):

    - Shouldn't the second bullet read "where for all p \in Obj(P)", rather than "Obj(C)"?
    - Does one commutative diagram suffice for all three properties of the pairing operation? I think if you change the h in your commutative diagram to (f,g) you get the first two properties, and for the third you need another commutative diagram with h, (p_a \comp h, p_b \comp h) and the identity arrow.

    But it's been a looong time for me, maybe I'm mistaken. :)

    In any case, love the walkthrough of category theory, thanks!

Leave a Reply

Bad Behavior has blocked 1341 access attempts in the last 7 days.