Natural numbers objects

Proof. Define the morphism $b : 1 \to N \times X$ by $b \coloneqq (z,a)$ and the morphism $h : N \times X \to N \times X$ by $h(n,x) \coloneqq (s(n),g(n,x))$. By the universal property of $(N,z,s)$, there is a unique morphism $\Psi : N \to N \times X$ such that:

• $\Psi(z) = b$
• $\Psi(s(n)) = h(\Psi(n))$

Write $\Psi(n) = (\Psi_0(n),\Psi_1(n))$, where $\Psi_0 : N \to N$ and $\Psi_1 : N \to X$. The two equations above then become:

• $\Psi_0(z) = z$
• $\Psi_0(s(n)) = s(\Psi_0(n))$
• $\Psi_1(z) = a$
• $\Psi_1(s(n)) = g(\Psi_0(n),\Psi_1(n))$

The uniqueness in the universal property of $(N,z,s)$ implies $\Psi_0 = \id_N$. Therefore, $\Phi \coloneqq \Psi_1$ is the unique morphism $\Phi : N \to X$ satisfying $\Phi(z)=a$ and $\Phi(s(n)) = g(n,\Phi(n))$. $\square$

Proof. Let $a : 1 \to X$ and $b : N \to X$ be morphisms. We need to show that there is a unique morphism $c : N \to X$ satisfying $c(z) = a$ and $c(s(n)) = b(n)$. This follows by applying Lemma 1 to the morphism $g : N \times X \to X$ defined by $g(n,x) \coloneqq b(n)$. $\square$

Proof. The first statement is immediate from the definition of a natural numbers object. For the second, $(1,\id_1,\id_1)$ is a parametrized natural numbers object if and only if, for all morphisms $f : A \to X$ and all endomorphisms $g : X \to X$, there is a unique morphism $\Phi : A \to X$ such that $\Phi \circ \id_A = f$ and $\Phi \circ \id_A = g \circ \Phi$. These equations simplify to $\Phi = f$ and $f = g \circ f$. Since this must hold for every $f : A \to X$, we must have $g = \id_X$ (by the Yoneda Lemma or by a direct argument). $\square$

Proof. We will use element notation extensively. In particular, for every element $a \in A$ and $n \in \IN$, there is an element $n \otimes a \in \IN \otimes A$, formally defined by the $n$th coproduct inclusion. The morphism $\alpha$ is defined by $$\alpha(n \otimes a) = (a,n \otimes 1).$$

In any category with a terminal object and countable copowers, we can construct the non-parametrized NNO $\IN \otimes 1$ with the element $0 \otimes 1 \in \IN \otimes 1$ and the map $$s : \IN \otimes 1 \to \IN \otimes 1, \quad s(n \otimes 1) \coloneqq (n+1) \otimes 1.$$ See here for a detailed proof. Since, by assumption, $1 \xrightarrow{z} N \xrightarrow{s} N$ is a parametrized NNO, it is also a non-parametrized NNO and is therefore isomorphic to the one just constructed. We may assume without loss of generality that they are equal and hence work with $N = \IN \otimes 1$.

Next, apply the parametrized universal property of the NNO to the diagram $$A \xrightarrow{f} \IN \otimes A \xrightarrow{g} \IN \otimes A$$ defined by $f(a) \coloneqq 0 \otimes a$ and $g(n \otimes a) \coloneqq (n+1) \otimes a$. It gives a morphism $$\Phi : A \times N \to \IN \otimes A$$ satisfying $$\Phi(a,0 \otimes 1) = 0 \otimes a, \quad \Phi(a,s(m)) = g(\Phi(a,m)).$$ For $m \coloneqq n \otimes 1 \in N$, where $n \in \IN$, the second equation becomes $$\Phi(a,(n+1) \otimes 1) = g(\Phi(a,n \otimes 1)).$$ By induction on $n \in \IN$, it follows that $$\Phi(a,n \otimes 1) = n \otimes a,$$ which is exactly the statement that $\Phi \circ \alpha = \id_{\IN \otimes A}$.

It remains to prove $\alpha \circ \Phi = \id_{A \times N}$. We first observe that $$\alpha \circ g = (\id_A \times s) \circ \alpha$$ as morphisms $\IN \otimes A \to A \times (\IN \otimes 1)$. Indeed, for every $n \otimes a \in \IN \otimes A$, $$\alpha(g(n \otimes a)) = \alpha((n+1) \otimes a) = (a, (n+1) \otimes 1),$$ while $$(\id_A \times s)(\alpha(n \otimes a)) = (\id_A \times s)(a, n \otimes 1) = (a, (n+1) \otimes 1).$$ The universal property applied to the diagram $$A \xrightarrow{(\id_A,z)} A \times N \xrightarrow{\id_A \times s} A \times N$$ shows that there is a unique morphism $\Psi : A \times N \to A \times N$ satisfying $$\Psi \circ (\id_A,z) = (\id_A,z)$$ and $$\Psi \circ (\id_A \times s) = (\id_A \times s) \circ \Psi,$$ namely $\id_{A \times N}$. Thus, it suffices to verify that $\alpha \circ \Phi : A \times N \to A \times N$ satisfies these two equations. We have $$\alpha(\Phi(a,z)) = \alpha(0 \otimes a) = (a, 0 \otimes 1) = (a,z),$$ and hence $\alpha \circ \Phi \circ (\id_A,z) = (\id_A,z)$. Moreover, $$\alpha \circ \Phi \circ (\id_A \times s) = \alpha \circ g \circ \Phi = (\id_A \times s) \circ \alpha \circ \Phi.$$ This finishes the proof. $\square$

Proof. For a category $\C$ with a terminal object $1_{\C}$, let $R(\C)$ denote the category of diagrams $$1_{\C} \xrightarrow{x_0} X \xrightarrow{r} X$$ in $\C$. A natural numbers object in $\C$ is precisely an initial object of $R(\C)$. Suppose that $H : \C \to \D$ is a functor between categories with terminal objects that preserves terminal objects. Then $H$ induces a functor $R(H) : R(\C) \to R(\D)$ that maps $$1_{\C} \xrightarrow{x_0} X \xrightarrow{r} X$$ to its image $$1_{\D} \cong H(1_{\C}) \xrightarrow{H(x_0)} H(X) \xrightarrow{H(r)} H(X).$$

In the situation of the lemma, we therefore have two functors

$$\begin{align*} R(F) & : R(\C) \to R(\D),\\ R(G) & : R(\D) \to R(\C). \end{align*}$$

Notice that $G$ preserves terminal objects since it is a right adjoint.

We claim that $R(F)$ is left adjoint to $R(G)$. Indeed, for objects $(X,x_0,r) \in R(\C)$ and $(Y,y_0,s) \in R(\D)$, a morphism $R(F)(X,x_0,r) \to (Y,y_0,s)$ is the same as a morphism $f : F(X) \to Y$ such that $$f \circ F(x_0) = y_0, \quad s \circ f = f \circ F(r).$$ Under the adjunction $F \dashv G$, it corresponds to a morphism $\widetilde{f} : X \to G(Y)$ such that $$\widetilde{f} \circ x_0 = G(y_0), \quad G(s) \circ \widetilde{f} = \widetilde{f} \circ r.$$ This is precisely a morphism $(X,x_0,r) \to R(G)(Y,y_0,s)$.

Since $R(F)$ is a left adjoint, it preserves initial objects. This is precisely the statement that $F$ preserves natural numbers objects. $\square$