### Patrick Stevens

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

# Hom-sets and exercises

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 $$\phi(g): g \mapsto (f \mapsto g \circ f)$$ a functor from $$C$$ 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 $$f: \mathbb{N} \to \mathbb{R}$$ by $$n \mapsto n$$, when you only ever are interested in the fact that $$f$$ 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 $$X \to P$$ into two child arrows $$X \to A, X \to B$$. 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 $$F$$ preserves products iff $$F(A \times B) \cong FA \times FB$$ canonically, but I’m satisfied with it.

# Exercises

Exercises 1 and 2 I’ve done already. The uniqueness of inverses is easy by the usual group-theoretic argument: $$fg = f g'$$ means $$gfg = gf g'$$, so $$g = g'$$ by cancelling the $$g f = 1$$ term.

The composition of isos is an iso: easy, since $$f^{-1} \circ g^{-1} = (g \circ f)^{-1}$$. $$g \circ f$$ monic implies $$f$$ monic and $$g$$ epic: follows immediately by just writing out the definitions. The counterexample to “$$g \circ f$$ monic implies $$g$$ monic” can be found in the category of sets: we want an injective composition where the second function is not injective. Easy: take $$\{1 \} \to \mathbb{N}$$ and then $$\mathbb{N} \to \{ 1 \}$$. 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 $$f$$ in $$x f = x' f$$, for instance), so we have that a) implies b) and c). If $$f$$ is a mono and a split epi, then it has a right-inverse $$g$$ such that $$fg = 1$$; we claim that $$g$$ is also a left-inverse. Indeed, $$f g f = f 1$$ so $$g f = 1$$ by mono-ness. Therefore b) implies a). Likewise c) implies a).

Exercise 6: Let $$h: G \to H$$ be a monic graph hom. Let $$v_1, v_2: 1 \to G$$ be homs from the graph with one vertex and no edges. Then $$h v_1 = h v_2$$ implies $$v_1 = v_2$$, so in fact $$h$$ 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 $$h: G \to H$$ is not monic. Then there are $$v_1: F_1 \to G, v_2: F_2 \to G$$ with $$h v_1 = h v_2$$ but $$v_1 \not = v_2$$. Since $$h v_1 = h v_2$$, we must have that “their types match”: $$F_1 = F_2$$. We will denote that by $$F$$. Then there is some vertex or edge on which $$v_1$$ and $$v_2$$ have different effects. If it’s a vertex: then $$v_1(v) \not = v_2(v)$$ for that vertex $$v$$, but $$h v_1 (v) = h v_2(v)$$, so $$h$$ 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 $$f: P \to Q$$ be an epi of posets, so $$x f = y f$$ implies $$x = y$$. Suppose $$f$$ is not surjective, so there is $$q \in Q$$ it doesn’t hit. Then let $$x, y: Q \to \{ 1, 2 \}$$, disagreeing at $$q$$. We have $$x f = y f$$ so $$x, y$$ must agree at $$q$$. This is a contradiction. Conversely, any surjection-on-elements is an epi, because if $$x(q) \not = y(q)$$ then we may write $$q = f(p)$$ for some $$p$$, whence $$x f(p) \not = y f(p)$$. The one-element poset is projective: let $$s: X \to \{1\}$$ be an epi (surjective), and $$\phi: P \to \{ 1 \}$$. Then $$X$$ has an element, $$u$$ say, since $$s$$ is surjective. Then we may lift $$\phi$$ over $$s$$ by letting $$\bar{\phi}: p \mapsto u$$, so that the composite $$s \circ \bar{\phi} = \phi$$. (Quick check in my mind that this works for $$P$$ 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 $$A$$ be an arbitrary discrete poset. Define $$r: 1 \to A$$ by selecting an element, and $$s: A \to \{1\}$$. Then $$A$$ is a retraction of $$B$$, 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 $$\{1\}$$ was a retract of $$A$$. Back to the drawing board.

Exercise 10 revisited: Take a discrete poset $$P$$, and let $$f: X \to P$$ be an epi - that is, surjection. Let $$A$$ be a poset and $$\phi: A \to P$$ an arrow (monotone map). For each $$a \in A$$ we have $$\phi(a)$$ appearing in some form in $$X$$; pick any inverse image $$x_a$$ such that $$f(x_a) = \phi(a)$$. I claim that the function $$a \mapsto x_a$$ is monotone (whence we’re done). Indeed, if $$a \leq b$$ then $$\phi(a) \leq \phi(b)$$ so $$f(x_a) \leq f(x_b)$$ so $$x_a \leq x_b$$ because $$f, \phi$$ are monotone.

Example of a non-projective poset: let $$A = P$$ be the poset $$0 \leq 1 \leq 2$$, and let $$i:A \to P$$ the inclusion. Let $$E$$ be the poset $$0 \leq 2, 1 \leq 2$$, with its obvious inclusion as the epi. Then $$i$$ doesn’t lift across that epi, because $$0_A$$ must map to $$0_E$$ and $$1_A$$ to $$1_E$$, but $$0 \leq_A 1$$ and $$0 \not \leq_E 1$$.

Now, all projective posets are discrete: suppose the comparison $$a < b$$ exists in the poset $$P$$, and let $$X$$ be $$P$$ but where we break that comparison. Let the epi $$X \to P$$ be the obvious inclusion. Then the inclusion $$\text{id}: P \to P$$ doesn’t lift across $$X$$.

Exercise 11: Of course, the first thing is a diagram. An initial object in $$A-\mathbf{Mon}$$ is $$(I, i)$$ such that there is precisely one arrow from $$(I, i)$$ to any other object: that is, precisely one commutative triangle exists. A free monoid $$M(A)$$ on $$A$$ is such that there is $$j: A \to \vert M(A) \vert$$, and for any function $$f: A \to \vert N \vert$$ there is a unique monoid hom $$\bar{f}: M(A) \to N$$ with $$\vert \bar{f} \vert \circ j = f$$. If $$(I, i)$$ is initial, it is therefore clear that $$I$$ has the UMP of the free monoid on $$A$$, 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 $$x: (A \times B) \times C \to A \times (B \times C)$$ guaranteed by the UMP of $$A \times (B \times C)$$ 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 $$I$$-indexed product should be: $$P$$ with arrows $$\{ (p_i: P \to A_i) : i \in I \}$$ is a product iff for every object $$X$$ with collections $$\{ (x_i: X \to A_i) : i \in I \}$$ of arrows, there is a unique $$x : X \to P$$ with $$p_i \circ x = x_i$$ for each $$i \in I$$. Then in the category of sets, the product of $$X$$ over $$i \in I$$ satisfies that for all $$T$$ with $$\{ (t_i: T \to X): i \in I \}$$ arrows, there is a unique $$t: T \to P$$ with $$p_i \circ t = t_i$$. If we let $$P = \{ f: I \to X \} = X^I$$, we do get this result: let $$t(\tau) : i \mapsto t_i(\tau)$$. This works if $$p_i \circ (\tau \mapsto (i \mapsto t_i(\tau))) = (\tau \mapsto t_i(\tau))$$, so we just need to define the projection $$p_i: X^I \to X$$ by $$p_i(i \mapsto x) = x$$. I think that makes sense.

Exercise 15: I first draw a diagram. $$\mathbb{C}_{A, B}$$ has a terminal object iff there is some $$(X, x_1, x_2)$$ such that for all $$(Y, y_1, y_2)$$, there is precisely one arrow $$(Y, y_1, y_2) \to (X, x_1, x_2)$$. $$A$$ and $$B$$ have a product in $$\mathbb{C}$$ iff there is $$P$$ and $$p_1: P \to A, p_2: P \to B$$ such that for every $$x_1: X \to A, x_2: X \to B$$ there is unique $$x: X \to P$$ with the appropriate diagram commuting. If we let $$(Y, y_1, y_2) = (P, p_1, p_2)$$ then it becomes clear that if $$A, B$$ have a product then $$\mathbb{C}_{A, B}$$ has a terminal object - namely $$(Y, y_1, y_2)$$. Conversely, if $$\mathbb{C}_{A, B}$$ has a terminal object $$(Y, y_1, y_2)$$, then our unique arrow $$x: X \to Y$$ in $$\mathbb{C}_{A, B}$$ corresponds to a unique product arrow in $$\mathbb{C}$$, so the UMP for products is satisfied.

Exercise 16: Is this really as easy as it looks? The product functor takes $$a: A, b: B \mapsto \langle a, b \rangle : A \times B$$. Maybe I’ve misunderstood something, but I can’t see that it’s any harder than that. There’s a functor $$X \mapsto (A \to X)$$, given by coslicing out by $$A$$. 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 $$1_A x = 1_A y$$ implies $$x = y$$, and $$\Gamma(f)x = \Gamma(f)y$$ implies $$1_A x = 1_A y$$ because of the projection we may perform on the pair $$\langle 1_A, f \rangle$$. $$\Gamma$$ 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 $$A$$ be the trivial monoid, then $$\text{Hom}(A, -)$$ is a functor taking a monad $$M$$ to its set of underlying elements (each identified with a different hom $$\{ 1 \} \to M$$) - 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 $$\text{Hom}(M, N)$$ to be isomorphic in some way to the set $$\vert N \vert$$, 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 $$M = \mathbb{N}$$. Then the homomorphisms $$\phi: \mathbb{N} \to N$$ precisely determine elements of $$N$$, by $$\phi(1)$$. So that proves the result. Why did I not think of $$\mathbb{N}$$ instead of $$\{ 1 \}$$? Probably just lack of experience.