Theorem 10.2.9 (Dependent recursion for natural numbers). Let \(p\colon P \to \N\) and \(f\colon P \to P\) be functors equipped with a commutative square
Evaluation at zero defines an equivalence
\[
\ev_0\colon\operatorname{Rec}(p,f)\iso P_0.
\]
Consequently, for every object \(x_0:P_0\), the category of recursive
sections equipped with an identification \(s(0) = x_0\) is contractible.
Proof
Iterate the given square as an endomorphism of \(p\) in
\(\Fun([1],\Cat)\), using Construction 10.2.4. Uncurrying
gives a commutative square
The covariant representable \(\B\N(\base,-)\colon\B\N\to\An\) sends
the generating endomorphism to \(\succ\). Its action on \(\N\) is
\((n,m)\mapsto n\circ m=m+n\), so \(\succ^n(m) = m+n\).
Restriction to \(\N\times P_0\) therefore gives a functor to \(P\) over
\(\N\). Currying, together with the comparison \(f^{n+1} = f\circ f^n\),
defines
\[
R\colon P_0\longrightarrow\operatorname{Rec}(p,f),
\qquad x\longmapsto(n\mapsto f^n(x)).
\]
The comparison lies over \(\N\) because we iterated the square, including
its specified commutativity. Thus it gives an isomorphism in
\(\operatorname{Sect}_{\succ}(p)\), as required by the defining pullback.
Since \(f^0 = \id_P\), we have \(\ev_0R = \id_{P_0}\).
To construct \(R\ev_0 = \id\), put \(C=\operatorname{Rec}(p,f)\) and let
\(U\colon\N\times C\to P\) be the universal section. Write
\(K(n,c)=f^n(U(0,c))\) for the section underlying \(R\ev_0\).
Their recursive isomorphisms will be denoted by \(\vartheta_U\) and
\(\vartheta_K\). Form the pullback
where \(\Iso_{\N}(P)=\N\times_{\Iso(\N)}\Iso(P)\) is the relative
isomorphism category from Corollary 5.3.15.
Thus \(E\) parametrizes isomorphisms \(u\colon K(n,c)\iso U(n,c)\) in \(P_n\).
Composition of relative isomorphisms defines an endofunctor \(h\) of \(E\)
over \(\succ\times\id_C\) by
\[
h(u)=\vartheta_{U,n}^{-1}\circ f(u)\circ\vartheta_{K,n}.
\]
The identity \(f^0 = \id_P\) gives a functor \(j\colon C\to E\) over
\(c\mapsto(0,c)\).
Now iterate the square \(qh = (\succ\times\id_C)q\) in \(\Fun([1],\Cat)\) and evaluate its iterates on \(j\). Since \(\succ^n(0) = n\), this gives a section \[ L\colon\N\times C\to E,\qquad L(n,c)=h^n(j(c)), \] together with an isomorphism \(L\circ(\succ\times\id_C) = h\circ L\) over \(\succ\times\id_C\). Projection to \(\Iso_{\N}(P)\) gives an isomorphism \(\alpha\colon K\iso U\) over \(\N\), and the iteration comparison says \[ \alpha_{n+1}=\vartheta_{U,n}^{-1}\circ f(\alpha_n)\circ\vartheta_{K,n}. \] Equivalently, \(\vartheta_{U,n}\circ\alpha_{n+1}=f(\alpha_n)\circ\vartheta_{K,n}\), which is the square required of a morphism of recursive sections. All these constructions are functorial over \(C\), so \(\alpha\) defines \(R\ev_0 = \id_C\). Hence \(R\) is inverse to \(\ev_0\). The last assertion follows by taking the fiber at \(x_0\).