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:
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.
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.
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) } ???
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.
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.