4
$\begingroup$

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.

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

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ > "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. $\endgroup$
    – fosco
    Dec 25, 2022 at 11:36
  • $\begingroup$ @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. $\endgroup$ Dec 25, 2022 at 16:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .