Show that for each $\mathbf{Pno}$ object $(A, \alpha, a)$ there is a unique arrow $(\mathbb{N}, \mathrm{succ}, 0) \to (A, \alpha, a)$

The objects of $$\mathbf{Pno}$$ are structures $$(A, \alpha, a)$$ where $$A$$ is a set, and where $$\alpha \colon A \longrightarrow A$$ is a function and $$a \in A$$ is a nominated element. Given two such structures a morphism $$(A, \alpha, a) \longrightarrow (B, \beta, b)$$ is a function $$f \colon A \longrightarrow B$$ which preserves the structure in the sense that $$f \circ \alpha = \beta \circ f \,, \quad f(a) = b \,.$$

Show that for each $$\mathbf{Pno}$$ object $$(A, \alpha, a)$$ there is a unique arrow $$(\mathbb{N}, \mathrm{succ}, 0) \longrightarrow (A, \alpha, a)$$ and describe the behaviour of the carrying function.

This exercise is in the Introduction to Category Theory by Harold Simmons. Context it is being a while since I have any mathematical classes, and I never had this course so I am just curious, and probably my attempt won't be formal:

Per the definition of a morphism in this category: $$f(0) = a \,.$$ We also know that $$f \circ \mathrm{succ} = \alpha \circ f \,.$$ Thus: $$f(\mathrm{succ}(0)) = \alpha(f(0)) \,.$$ Since $$f(0) = a$$, then $$f(\mathrm{succ}(0)) = \alpha(a) \,.$$

And here is where I am lost. I know that somehow I have to use the successor function, and the fact that the object we are mapping has $$\mathbb{N}$$ as its set. However, I am lost in how to use this information.

• Do you recall how to define a function out of N by induction? You're very much on the right track though Dec 24, 2022 at 17:19
• See the recursion theorem. Dec 24, 2022 at 18:35

The precise proof of this depends on a precise definition of $$\mathbb{N}$$. In set theory, we typically define $$\mathbb{N}$$ and $$<$$ first before getting to anything more complicated.

Lemma: for all $$n \in \mathbb{N}$$, there exists a unique $$g_n : \{m \in \mathbb{N} \mid m < n\}$$ such that (1) if $$0 < n$$, then $$g_n(0) = a$$, and (2) for all $$j$$, if $$succ(j) < n$$ then $$g_n(succ(j)) = \alpha(g_n(j))$$.

Proof: we proceed by induction on $$n$$. In the base case, the unique function $$\emptyset \to A$$ clearly satisfies (1) and (2).

For the inductive step, suppose we have the unique $$g_k : \{0, \ldots, k - 1\} \to A\}$$. Note that if we had $$g_{k + 1} : \{0, \ldots, k\} \to A\}$$ satisfying (1) and (2), we must have $$g_{k + 1}|_{\{0, \ldots, k - 1\}} = g_k$$. And we would necessarily have

$$g_{k + 1}(k) = \begin{cases} a & k = 0 \\ \alpha(g_k(j)) & k = succ(j) \end{cases}$$

This shows uniqueness. And we can simply define $$g_{k + 1}$$ in this way and verify it satisfies (1) and (2), showing existence. $$\square$$

With this Lemma in hand, we note that if we had such an $$f$$, then $$f|_{\{0, \ldots, n - 1\}}(n) = g_n$$. Thus, we would have $$g_{n + 1}(n) = f(n)$$ for all $$n$$. This shows uniqueness. Taking $$f(n) = g_{n +1}(n)$$ as a definition and checking properties shows existence.

• > "The precise proof of this depends on a precise definition of $\mathbb N$" It highly does not: the proof of a universal property can't depend on the set-theoretic technicalities of a definition, because said universal property can't see any difference between isomorphic universal objects. Dec 25, 2022 at 11:36
• @fosco This is inaccurate. Proofs which rely on a universal property do not depend on the specifics of the object satisfying the property. But the proof that a particular object satisfies a universal property clearly must depend on the nature of the specific object. If (as in ETCS) we define $(\mathbb{N}, succ, 0)$ to be an NNO, then the proof is quite different - it’s just 1 line. If we take a type-theoretic approach, the proof is again different. Dec 25, 2022 at 16:05