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 Commutative diagram; see the PDF for its LaTeX source 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 Commutative diagram; see the PDF for its LaTeX source 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 Commutative diagram; see the PDF for its LaTeX source 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\).

From Section 10.2, The natural numbers.