 ### 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 $% $ 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.