Arrow Equality and Pullbacks

We're almost at the end of this run of category definitions. We need to get to the point of talking about something called a *pullback*. A pullback is a way of describing a kind of equivalence of arrows, which gets used a lot in things like interesting natural transformations. But, before we get to pullbacks, it helps to understand the equalizer of a pair of morphisms, which is a weaker notion of arrow equivalence.

We'll start with sets and functions again to get an intuition; and then we'll work our way back to categories and categorical equalizers.

Suppose we have two functions mapping from members of set A to members of set B.


f, g : A → B

Suppose that they have a non-empty intersection: that is, that there is some set of values x ∈ A for which f(x) = g(x). The set of values C from A on which f and g return the same result (*agree*) is called the *equalizer* of f and g. Obviously, C is a subset of A.

Now, let's look at the category theoretic version of that. We have *objects* A and B.
We have two arrows f, g : A → B. This is the category analogue of the setup of sets and functions from above. To get to the equalizer, we need to add an object C which is a *subobject* of A (which corresponds to the subset of A on which f and g agree in the set model).

The equalizer of A and B is the pair of the object C, and an arrow i : C → A. (That is, the object and arrow that define C as a subobject of A.) This object and arrow must satisfy the following conditions:

1. f º i = g º i
2. (∀ j : D → A) f º j = g º j ⇒ (∃ 1 k : D → C) i º k = j.

That second one is the mouthful. What it says is: if I have any arrow j from some other object D to A: if f and g agree on composition about j, then there can only be *one* *unique* arrow from C to D which composes with j to get to A. In other words, (C, i) is a *selector* for the arrows on which A and B agree; you can only compose an arrow to A in a way that will compose equivalently with f and g to B if you go through (C, i) Or in diagram form, k in the following diagram is necessarily unique:


i-e2e0cb0ef58b45a389163aa16946366f-equalizer.jpg

There are a couple of interesting properties of equalizers that are worth mentioning. The morphism in an equalizer is a *always* monic arrow (monomorphism); and if it's epic (an epimorphism), then it must also be iso (an isomorphism).

The pullback is very nearly the same construction as the equalizer we just looked at; except it's abstracting one step further.

Suppose we have two arrows pointing to the same target, f : B → A and g : C → A. Then the pullback of of f and g is the triple of an object and two arrows (B×AC, p : B×AC → B, q : B×AC → C). The elements of this triple must meet the following requirements:

1. f º p = g º q
2. (f º p) : B×AC → A
3. For every triple (D, h : D → B , k : D → C), there is exactly one unique arrow A : D → B×AC where pºA = h, and q º A = k.

As happens so frequently in category theory, this is clearer using a diagram.


i-fe95f3e974100750e14569df45b10afe-pullback.jpg

If you look at this, you should definitely be able to see how this corresponds to the categorical equalizer. If you're careful and clever, you can also see the resemblance to categorical product (which is why we use the ×A syntax). It's a general construction that says that f and g are equivalent with respect to the product-like object B×AC.

Here's the neat thing. Work backwards through this abstraction process to figure out what this construction means if objects are sets and arrows are functions, and what's the pullback of the sets A and B?


{ (x,y) ∈ A × B : f(x) = g(y) }

Right back where we started, almost. The pullback is an equalizer; working it back shows that.

More like this

What's a subset? That's easy: if we have two sets A and B, A is a subset of B if every member of A is also a member of B. What's a subgroup? If we have two groups A and B, and the values in group A are a subset of the values in group B, then A is a subgroup of B. For any kind of thing **X**, what…
To get started, what is category theory? Back in grad school, I spent some time working with a thoroughly insane guy named John Case who was the new department chair. When he came to the university, he brought a couple of people with him, to take temporary positions. One of them was a category…
Just like you can define a sub-set of a set, or a sub-object of an object in a category, you can define a sub-*space* of a topological space. It's a pretty easy thing to understand; interestingly, a sub-space of a topological space works in pretty much exactly the same way as a sub-sets and sub-…
Sorry, but I actually jumped the gun a bit on Yoneda's lemma. As I've mentioned, one of the things that I don't like about category theory is how definition-heavy it is. So I've been trying to minimize the number of definitions at any time, and show interesting results of using the techniques of…

Sigh! I must ask again (and I note that you didn't answer my followup question in the last cathegory post, if you have patience with me): Since D shows that the pullback B xA C is a product BxC, shouldn't it be:

{ (x,y) â B Ã C : f(x) = g(y) } ???

By Torbjörn Larsson (not verified) on 08 Jul 2006 #permalink

Torbjörn:

Yes, you're right. That's an error; I'll correct it later today.

Also, sorry about not answering your other question; I didn't notice that you asked a followup. I'll try to get back and find it, and then answer it later, when I have some time.

Ah! So even if I'm still shaky on the objects definition, maybe I get some of the overall picture. (Category rules, eh? ;-) Perhaps the later applications clear up the rest for me.

By Torbjörn Larsson (not verified) on 10 Jul 2006 #permalink

Torbjörn:

Don't worry too much if you're having trouble understanding some of the depths; often, there aren't any :-). One of the things that's hardest to wrap your head around with category theory is that the deep structure isn't there: it's deliberately been abstracted away. We really are working with nothing but these silly arrows. If you can follow things like exponentials and pullbacks, you're definitely getting it.

The other thing is, I'm of the opinion that cat theory is really a tool for describing other things. I don't think there've been any dramatic new mathematical discoveries from the depths of category theory; it's hugely useful for making structures and theorems from other branches of math easier to talk about and understand.

By Mark C. Chu-Carroll (not verified) on 11 Jul 2006 #permalink