Patrick Stevens bio photo

Patrick Stevens

Former mathematics student at the University of Cambridge; now a software engineer.

Email Twitter Github Stackoverflow

This is on pages 48 through 52 of Awodey, covering the hom-sets section and the exercises at the end of Chapter 2. Only eight more chapters after this, and I imagine they’ll be more difficult - I should probably step up the speed at which I’m doing this.

Awodey assumes we are working with locally small categories - recall that such categories have “given any two objects, there is a bona fide set of all arrows between those objects”. That is, all the hom-sets are really sets.

We see the idea that any arrow induces a function on the hom-sets by composing on the left. Awodey doesn’t mention currying here, but that seems to be the same phenomenon. Why is the map a functor from to the category of sets? I agree with the step-by-step proof Awodey gives, but I don’t really have intuition for it. It feels a bit misleading to me that this is thought of as a functor into the category of sets, because that category contains many many more things than we’re actually interested in. It’s like saying by , when you only ever are interested in the fact that takes integer values. I’m sure it’ll become more natural later when we look at representable functors.

Then an alternative explanation of the product construction, as a way of exploding an arrow into two child arrows . A diagram is a product iff that explosion is always an isomorphism. Then a functor preserves binary products if it… preserves binary products. I had to draw out a diagram to convince myself that preserves products iff canonically, but I’m satisfied with it.


Exercises 1 and 2 I’ve done already. The uniqueness of inverses is easy by the usual group-theoretic argument: means , so by cancelling the term.

The composition of isos is an iso: easy, since . monic implies monic and epic: follows immediately by just writing out the definitions. The counterexample to “ monic implies monic” can be found in the category of sets: we want an injective composition where the second function is not injective. Easy: take and then . The composition is the identity, but the second function is very non-injective.

Exercise 5: a) and d) are equivalent by definition of “iso” and “split mono/epi”. Isos are monic and epic, as we’ve already seen in the text (because we can cancel in , for instance), so we have that a) implies b) and c). If is a mono and a split epi, then it has a right-inverse such that ; we claim that is also a left-inverse. Indeed, so by mono-ness. Therefore b) implies a). Likewise c) implies a).

Exercise 6: Let be a monic graph hom. Let be homs from the graph with one vertex and no edges. Then implies , so in fact is injective. Likewise with edges, using the graph with one edge and two vertices, and the graph with one edge and one vertex. Conversely, suppose is not monic. Then there are with but . Since , we must have that “their types match”: . We will denote that by . Then there is some vertex or edge on which and have different effects. If it’s a vertex: then for that vertex , but , so can’t be injective. Likewise if it’s an edge.

Exercises 7 and 8 I’ve done already.

Exercise 9: the epis among posets are the surjections-on-elements. Let be an epi of posets, so implies . Suppose is not surjective, so there is it doesn’t hit. Then let , disagreeing at . We have so must agree at . This is a contradiction. Conversely, any surjection-on-elements is an epi, because if then we may write for some , whence . The one-element poset is projective: let be an epi (surjective), and . Then has an element, say, since is surjective. Then we may lift over by letting , so that the composite . (Quick check in my mind that this works for the empty poset - it does.)

Exercise 10: Sets (implemented as discrete posets) are projective in the category of posets: the one-element poset is projective, and retracts of projective objects are projective. Let be an arbitrary discrete poset. Define by selecting an element, and . Then is a retraction of , so is projective. Afterwards, I looked in the solutions, and Awodey’s proof is much more concrete than this. I asked on Stack Exchange whether my proof was valid, and the great Qiaochu Yuan himself pointed out that I had mixed up what “retract” meant, and had actually showed that was a retract of . Back to the drawing board.

Exercise 10 revisited: Take a discrete poset , and let be an epi - that is, surjection. Let be a poset and an arrow (monotone map). For each we have appearing in some form in ; pick any inverse image such that . I claim that the function is monotone (whence we’re done). Indeed, if then so so because are monotone.

Example of a non-projective poset: let be the poset , and let the inclusion. Let be the poset , with its obvious inclusion as the epi. Then doesn’t lift across that epi, because must map to and to , but and .

Now, all projective posets are discrete: suppose the comparison exists in the poset , and let be but where we break that comparison. Let the epi be the obvious inclusion. Then the inclusion doesn’t lift across .

Exercise 11: Of course, the first thing is a diagram. An initial object in is such that there is precisely one arrow from to any other object: that is, precisely one commutative triangle exists. A free monoid on is such that there is , and for any function there is a unique monoid hom with . If is initial, it is therefore clear that has the UMP of the free monoid on , just by looking at the diagram. Initial objects are unique up to isomorphism, and free monoids are too, so we automatically have the converse.

Exercise 12 I did in my head to my satisfaction while I was following the text.

Exercise 13: I wrote out several lines for this, amounting to showing that the unique guaranteed by the UMP of is in fact an iso. The symbol shunting isn’t very enlightening, so I won’t reproduce it here.

Exercise 14: the UMP for an -indexed product should be: with arrows is a product iff for every object with collections of arrows, there is a unique with for each . Then in the category of sets, the product of over satisfies that for all with arrows, there is a unique with . If we let , we do get this result: let . This works if , so we just need to define the projection by . I think that makes sense.

Exercise 15: I first draw a diagram. has a terminal object iff there is some such that for all , there is precisely one arrow . and have a product in iff there is and such that for every there is unique with the appropriate diagram commuting. If we let then it becomes clear that if have a product then has a terminal object - namely . Conversely, if has a terminal object , then our unique arrow in corresponds to a unique product arrow in , so the UMP for products is satisfied.

Exercise 16: Is this really as easy as it looks? The product functor takes . Maybe I’ve misunderstood something, but I can’t see that it’s any harder than that. There’s a functor , given by coslicing out by . I’ve squinted at the answers Awodey supplies, and this isn’t an exercise he gives. I’ll just shut my eyes and pretend this exercise didn’t exist.

Exercise 17: The given morphism is indeed monic, because implies , and implies because of the projection we may perform on the pair . is a functor from sets to relations, clearly, but we’ve already done that in Section 1 question 1b).

Exercise 18: It would really help if Awodey had told us what a representable functor was, rather than just giving an example. Is he asking us to show that “the representable functor of Mon is the forgetful functor”? I’m going to hope that I can just drop Mon in for the category C in section 2.7. If we let be the trivial monoid, then is a functor taking a monad to its set of underlying elements (each identified with a different hom ) - but hang on, there’s only one such hom, so that line is nonsense. It would work in Sets, but not in Mon. We need to be isomorphic in some way to the set , and I just don’t see how that’s possible. Infuriatingly, this exercise doesn’t have a solution in the answers section. I ended up looking this up, and the trick is to pick . Then the homomorphisms precisely determine elements of , by . So that proves the result. Why did I not think of instead of ? Probably just lack of experience.