Problem solving #1

problem solving
category theory
simmons
Author

Abel Nieto

Published

January 6, 2026

Textbook

Introduction to Category Theory by Michael Simmons

Exercise 1.2.1

  1. To verify that \(\textbf{Pno}\) is a category we need to check that composition of arrows is well-defined and that the identity arrow behaves as expected.

    Let \((A, \alpha, a) \xrightarrow{f} (B, \beta, b)\) and \((B, \beta, b) \xrightarrow{g} (C, \gamma, c)\).

    Then we have:

    • \((g \circ f)(a) = g(f(a)) = c\)
    • The second coherence condition follows from \[\begin{align*} (g \circ f) \circ \alpha &= g \circ (f \circ \alpha) \\ &= g \circ (\beta \circ f) \\ &= (g \circ \beta) \circ f \\ &= (\gamma \circ g) \circ f \\ &= \gamma \circ (g \circ f) \end{align*}\]

    The identify arrow on \(A\) is simply the identify function on \(A\). That this behaves as the identity arrow is immediate.

  2. Here we have to show that \((\mathbb{N}, \textsf{succ}, 0)\) is a \(\textbf{Pno}\) object.

    This follows immediately from \(0 \in \mathbb{N}\) and the fact that \(\textsf{succ} : \mathbb{N} \to \mathbb{N}\).

  3. This asks us to show that \((\mathbb{N}, \textsf{succ}, 0)\) is initial.

    Let \((A, \alpha, a)\) be an object.

    Let \(f : \mathbb{N} \to A\) be recursively defined:

    • \(f(0) = a\)
    • \(f(n + 1) = \alpha(f(n))\)

    To see that that \(f \circ \textsf{succ} = \alpha \circ f\) we proceed by case analysis:

    • If \(n = 0\), then \[\begin{align*} (f \circ \textsf{succ})(0) &= f(1) \\ &= \alpha(f(0)) \\ &= (\alpha \circ f) (0) \end{align*}\]

    • otherwise, \(n = m + 1\) for some \(m \in \mathbb{N}\) and \[\begin{align*} (f \circ \textsf{succ})(m + 1) &= f(m + 2) \\ &= \alpha(f(m + 1)) \\ &= (\alpha \circ f) (m + 1) \end{align*}\]

    This established there’s an arrow from \((\mathbb{N}, \textsf{succ}, 0)\) to \((A, \alpha, a)\).

    To see that it must be unique, suppose there’s another function \(g : \mathbb{N} \to A\) that’s an arrow in \(\textbf{Pno}\).

    We prove by induction that \(g(n) = f(n)\) for all \(n \in \mathbb{N}\).

    • If \(n = 0\), then \(g(0) = a = f(0)\).
    • Otherwise \[\begin{align*} g(m + 1) &= g(\textsf{succ}(m)) \\ &= (g \circ \textsf{succ})(m) \\ &= (\alpha \circ g)(m) \\ &= \alpha(g(m)) \\ &= \alpha(f(m)) \\ &= f(m + 1) \end{align*}\]

    \(\blacksquare\)