### Patrick Stevens

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

# Duality exercises

Exercise 1 is easy: at the end of Chapter 2 the corresponding products statement was proved, and the obvious dual statement turns out to be this one.

Exercise 2 falls out of the appropriate diagram, whose upper triangle is irrelevant.

Exercise 3 I’ve already proved - search on “sleep”.

Exercise 4: Let $$\pi_1: \mathbb{P}(A + B) \to \mathbb{P}(A)$$ be given by $$\pi_1(S) = S \cap A$$, and $$\pi_2: \mathbb{P}(A+B) \to \mathbb{P}(B)$$ likewise by $$S \mapsto S \cap B$$. Claim: this has the UMP of the product of $$\mathbb{P}(A)$$ and $$\mathbb{P}(B)$$. Indeed, if $$z_1: Z \to \mathbb{P}(A)$$ and $$z_2: Z \to \mathbb{P}(B)$$ are given, then $$z: Z \to \mathbb{P}(A + B)$$ is specified uniquely by $$S \mapsto z_1(S) \cup z_2(S)$$ (taking the disjoint union).

Exercise 5: Let the coproduct of $$A, B$$ be their disjunction. Then the “coproduct” property is saying “if we can prove $$Z$$ from $$A$$ and from $$B$$, then we can prove it from $$A \vee B$$”, which is clearly true. The uniqueness of proofs is sort of obvious, but I don’t see how to prove it - I’m not at all used to the syntax of natural deduction. I look at the answer, which makes everything clear, although I still don’t know if I could reproduce it. I understand its spirit, but not the mechanics of how to work in the category of proofs.

Exercise 6: we need that for any two monoid homomorphisms $$f, g: A \to B$$ there is a monoid $$E$$ and a monoid homomorphism $$e: E \to A$$ universal with $$f e = g e$$. Certainly there is a monoid hom $$e: E \to A$$ with that property (namely the trivial hom), so we just need to find one that is “big enough”. Let $$E$$ be the subset of $$A$$ on which $$f = g$$, which is nonempty because they must be equal on $$1_A$$. I claim that it is a monoid with $$A$$’s operation. Indeed, if $$f(a) = g(a)$$ and $$f(b) = g(b)$$ then $$f(ab) = f(a) f(b) = g(a) g(b) = g(ab)$$. This also works with abelian groups - and apparently groups as well.

Finally we need that this structure satisfies the universal property. Let $$Z$$ be a monoid with hom $$h: Z \to A$$, such that $$f h = g h$$. We want a hom $$\bar{h} : Z \to E$$ with $$e \bar{h} = h$$. But if $$f h = g h$$ then we must have the image of $$h$$ being in $$E$$, so we can just take $$\bar{h}$$ to be the inclusion. This reasoning works for abelian groups too. We relied on Mon having a terminal element and monoids being well-pointed.

Finite products: we just need to check binary products and the existence of an initial object. Initial objects are easy: the trivial monoid/group is initial. Binary products: the componentwise direct product satisfies the UMP for the product, since if $$z_1: Z \to A, z_2: Z \to B$$ then take $$z: Z \to A \times B$$ by $$z(y) = \langle z_1(y), z_2(y) \rangle$$. This is obviously homomorphic, while the projections make sure it is unique.

Exercise 7 falls out of another diagram. The (1) label refers to arrows forced by the first step of the argument; the (2) label to the arrow forced by the (1) arrows.

Exercise 8: an injective object is $$I$$ such that for any $$X, E$$ with arrows $$h: X \to I, m: X \to E$$ with $$m$$ monic, there is $$\bar{h}: E \to I$$ with $$\bar{h} m = h$$. Let $$P, Q$$ be posets, and let $$f: P \to Q$$ be monic. Then for any points $$x, y: \{ 1 \} \to P$$ we have $$fx = fy \Rightarrow x=y$$, so $$f$$ is injective. Conversely, if $$f$$ is not monic then we can find $$a: A \to P, b: B \to P$$ with $$fa = fb$$ but $$a \not = b$$. This means $$A = B$$ because the arrows $$fa, fb$$ agree on their domain; so we have $$a, b: A \to P$$ and $$x \in A$$ with $$a(x) \not = b(x)$$. But $$f a(x) = f b(x)$$, so we have $$f$$ not injective.

Now, a non-injective poset: we want to set up a situation where we force some extra structure on $$X$$. If $$I$$ is has two distinct nontrivial chunks which have no elements comparable between the chunks, then $$I$$ is not injective. Indeed, let $$X = I$$. Then the inclusion $$X \to I$$ does not lift across the map which sends one chunk “on top of” the other: say one chunk is $$\{a \leq b \}$$ and the other $$\{c \leq d\}$$, then the map would have image $$a \leq b \leq c \leq d$$.

What about an injective poset? The dual of “posets” is “posets”, so we can just take the dual of any projective poset - for instance, any discrete poset. Anything well-ordered will also do, suggests my intuition, but I looked it up and apparently the injective posets are exactly the complete lattices. Therefore a wellordering will almost never do. I couldn’t see why $$\omega$$ failed to be injective, so I asked a question on Stack Exchange; midway through, I realised why.

Exercise 9: $$\bar{h}$$ is obviously a homomorphism. Indeed, $$\bar{h}(a) \bar{h}(b) = h i(a) h i(b) = h(i(a) i(b))$$ because $$h$$ is a homomorphism. But $$i(a)$$ is the wordification of the letter $$a$$, and $$i(b)$$ likewise of $$b$$, so we have $$i(a) i(b)$$ is the word $$(a, b)$$, which is itself the inclusion of the product $$ab$$.

Exercise 10: Functors preserve the structure of diagrams, so we just need to show that that the unique arrow guaranteed by the coequaliser UMP corresponds to a unique arrow in Sets. We need to show that given a function $$\vert M \vert \to \vert N \vert$$ there is only one possible homomorphism $$M \to N$$ which forgetful-functors down to it. But a homomorphism $$M \to N$$ does specify where every single set element in $$\vert M \vert$$ goes, so uniqueness is indeed preserved.

Exercise 11: Let $$R$$ be the smallest equiv rel on $$B$$ with $$f(x) \sim g(x)$$ for all $$x \in A$$. Claim: the projection $$\pi: B \to B/R$$ is a coequaliser of $$f, g: A \to B$$. Indeed, let $$C$$ be another set, with a function $$c: B \to C$$. Then there is a unique function $$q: B/R \to C$$ with $$q \pi = c$$: namely, $$q([b]) = c(b)$$. This is well-defined because if $$b \sim b'$$ then $$c(b') = q([b']) = q([b]) = c(b)$$.

Exercise 12 I’ve already done - search on “wrestling”, though I didn’t write this up.

Exercise 13: I left this question to the end and couldn’t be bothered to decipher the notation.

Exercise 14: The equaliser of $$f p_1$$ and $$f p_2$$ is universal $$e: E \to A \times A$$ such that $$f p_1 e = f p_2 e$$. Let $$E = \{ (a, b) \in A \times A : f(a) = f(b) \}$$ and $$e$$ the inclusion. It is an equivalence relation manifestly: if $$f(a) = f(b)$$ and $$f(b) = f(c)$$ then $$f(a) = f(c)$$, and so on.

The kernel of $$\pi: A \mapsto A/R$$, the quotient by an equiv rel $$R$$, is $$\{ (a, b) \in A \times A : \pi(a) = \pi(b) \}$$. This is obviously $$R$$, since $$a \sim b$$ iff $$\pi(a) = \pi(b)$$. That’s what it means to take the quotient.

The coequaliser of the two projections $$R \to A$$ is the quotient of $$A$$ by the equiv rel generated by the pairs $$\langle \pi_1(x), \pi_2(x) \rangle$$, as in exercise 11. This is precisely the specified quotient.

The final part of the exercise is a simple summary of the preceding parts.

Exercise 15 is more of a “check you follow this construction” than an actual exercise. I do follow it.