\chapter{Descent of computation records}
\label{ch:compute-descent}
\section{Algebras over a cover}
Fix an \(\infty\)-topos \(\mathcal X\), a base \(U\), and an indexed rule signature in \(\mathcal X_{/U}\),
\[
I\xleftarrow{s} B\xrightarrow{p} A\xrightarrow{t} I .
\]
The existence of a rule instance is indexed by \(A\). The corresponding premises are indexed by its fiber in \(B\), with result and argument sorts determined by \(t\) and \(s\). Write \(P_U=\Sigma_t\Pi_p s^*\) for the polynomial on objects over \(I\). For a map \(U'\to U\), write \(P_{U'}\) for the change of the whole signature. The comparisons of Chapter~\ref{ch:families} give \(v^*P_U\simeq P_{U'}v^*\). They are natural in \(v\). Thus a \(P_U\)-algebra can be restricted with its algebra structure.
Let \(V\to U\) be an effective epimorphism, and put \(V^{[n]}=V\times_U\cdots\times_U V\), with \(n+1\) factors. An algebra over \(V\) has descent data if its restrictions to \(V^{[1]}\) are identified and these identifications extend to the coherent system on the whole Čech nerve. The higher conditions matter when rule instances or their fibers have paths. An equality of the images of the record objects does not include any such identification.
\begin{theorem}[Descent and local initiality]
\label{thm:alg-descent}
The restriction of algebras gives an equivalence
\[
\operatorname{Alg}(P_U)\simeq
\lim_{[n]\in\Delta}\operatorname{Alg}(P_{V^{[n]}}).
\]
If a compatible algebra on the right is initial at every Čech level, its descended algebra is initial over \(U\).
\end{theorem}
\begin{proof}
Apply descent for slices of an \(\infty\)-topos to
\(I_V=I\times_U V\to I\), an effective epimorphism \cite[Ch.~6]{Lurie}. It gives \(\mathcal X_{/I}\simeq\lim_n\mathcal X_{/I_{V^{[n]}}}\). The base change equivalences identify \(P_U\) with the functor on this limit given levelwise by the \(P_{V^{[n]}}\). The category of algebras for an endofunctor \(Q\) of \(\mathcal C\) is the pullback in \(\mathrm{Cat}_\infty\) of
\[
\operatorname{Fun}(\Delta^1,\mathcal C)
\xrightarrow{\ (d_1,d_0)\ } \mathcal C\times\mathcal C
\xleftarrow{\ (Q,\mathrm{id})\ } \mathcal C ,
\]
where the pair in the first map is ordered as source and target. Its object is precisely an object \(W\) and an arrow \(QW\to W\). Arrow categories and the displayed pullbacks commute with limits. This proves the first assertion. A mapping space from the candidate algebra to any algebra is the limit of the corresponding mapping spaces at the Čech levels. These are all contractible for the compatible family in the hypothesis, so their limit is contractible. This proves initiality.
\end{proof}
\begin{figure}[htbp]
\centering
\begin{tikzpicture}[node distance=8mm and 9mm]
\node[booksite] (local) {Initial algebra\\ over \(V\)};
\node[bookbox,right=of local] (overlap) {Identifications\\ over \(V^{[1]}\)};
\node[bookbox,right=of overlap] (coh) {Higher conditions\\ over \(V^{[n]}\)};
\node[booksite,below=of overlap] (global) {Initial algebra over \(U\)};
\draw[bookarr] (local) -- (overlap);
\draw[bookarr] (overlap) -- (coh);
\draw[bookarr,draw=accent] (overlap) -- (global);
\end{tikzpicture}
\caption{The data used to descend an initial algebra. The existence of a local algebra alone supplies only the first object of the diagram.}
\label{fig:descent-algebra}
\end{figure}
For small signatures with initial algebras stable under base change, the comparisons between the restrictions of initial algebras have contractible spaces of choices. Thus initiality supplies coherence in this situation. A choice of a particular element of an initial algebra has no such uniqueness. A descent theorem for algebras therefore says little by itself about the existence of a globally chosen execution.
An effective comparison asks for more than the equivalence of Theorem~\ref{thm:alg-descent}. The effective structure must be transported too. For example, a local ordinal clock ought to agree with its other presentations under the identifications of records. The necessary bounds are often obtained using the next proposition.
\section{Descent through a bounded stage}
Let \((W_\xi)_{\xi<\lambda}\) be an increasing family of subobjects of \(W\) over \(U\). Assume \(\lambda\) is a limit ordinal. We view the subobject \(W_\xi\) as the records available at stage \(\xi\). If a section \(w:U\to W\) factors through \(W_\xi\), the factorization is unique in the sense of a contractible space of choices. If the section restricts over a cover and each restriction factors through the same stage, the pullback of \(W_\xi\hookrightarrow W\) to \(U\) contains the cover and is all of \(U\). This gives a global factorization of the given section.
\begin{proposition}[Common stage]
\label{prop:common-stage}
Let \(\coprod_{j\in J}V_j\to U\) be an effective epimorphism, with \(|J|<\operatorname{cf}(\lambda)\) in the metatheory. Suppose the restriction of a section \(w\) has a factorization through \(W_{\xi_j}\) over each \(V_j\). Then \(w\) has a factorization through some \(W_\xi\) over \(U\).
If only the image of \(W_{\xi_j}\) covers \(V_j\) after pullback, the same bound \(\xi\) gives that the image of \(W_\xi\) is \(U\).
\end{proposition}
\begin{proof}
Take \(\xi=\sup_j\xi_j<\lambda\). In the first case, the pullback of the monomorphism \(W_\xi\to W\) along \(w\) contains all the cover maps. Its image in \(U\) is therefore all of \(U\), so the mono is an equivalence. In the second case, \(\operatorname{im}(W_\xi\to U)\) restricts to all of \(V_j\) by stability of images and comparison with \(W_{\xi_j}\). The same cover argument proves the assertion about the image.
\end{proof}
The assertion about images is the covering calculation of Theorem~\ref{sel:thm-cover}. The first assertion gives the additional factorization when an entire coherent section has been chosen. The rank comparison is a cofinality calculation on a collection already given. In forcing applications the collection may consist of names and records whose ranks must first be found in the ground structure. In admissible computations it may consist of outputs from a total bounded family, with the \(\Sigma_1\) record predicate used to collect the lengths. The argument here applies after these ranks are available. An unbounded cover can indeed fail to supply one stage. Let \(U=\omega\) be discrete, \(W=U\) with its identity map, and \(W_n=\{0,\ldots,n-1\}\). Singletons cover \(U\), every restriction of the identity has a finite stage, and no finite stage covers \(U\).
\section{An obstruction invisible to components}
A connected cover can exhibit a different failure. Consider the nonsplit exact sequence of finite groups
\[
1\longrightarrow C_2 \xrightarrow{\ i\ } C_4
\xrightarrow{\ q\ } C_2\longrightarrow 1 ,
\qquad i(1)=2,\qquad q(k)=k\bmod 2 .
\]
Let \(W=BC_4\) over \(U=BC_2\) by \(Bq\). Think of its points over a parameter as successful records, each with the same fixed numerical output. The homotopy fiber of \(Bq\) is \(BC_2\). The relative image of \(W\to U\) and its relative \(0\)-truncation are both \(U\). Over the base point, the pulled-back family \(BC_2\) has a section. The map \(1\to BC_2\) is an effective epimorphism, so this is a local choice on a cover.
\begin{proposition}
The record family \(BC_4\to BC_2\) has no section. The obstruction is already visible on the fundamental groups of the total and base spaces.
\end{proposition}
\begin{proof}
A section would induce a section \(C_2\to C_4\) of \(q\) on fundamental groups, up to conjugation. The groups in question are abelian. A possible image of the generator is odd, hence has order four. This does not define a homomorphism from \(C_2\), so no section exists.
\end{proof}
\begin{figure}[htbp]
\centering
\begin{tikzcd}[column sep=2.4em,row sep=2em]
BC_2 \arrow[r] \arrow[d] & BC_4 \arrow[d,"Bq"]\\
1 \arrow[r] & BC_2
\end{tikzcd}
\par\smallskip
{\small The lift of the base generator squares to the nonidentity kernel element.}
\caption{The square is a homotopy pullback. Each record fiber is connected, but the compatibility on loops obstructs a section over the base.}
\label{fig:descent-cyclic}
\end{figure}
One can see the obstruction directly on the local data. Choose the lift \(0\mapsto 0,\ 1\mapsto1\) of the elements of \(C_2\). The lift of a product differs from the product of the lifts by an element of the kernel. At \((1,1)\) this element is \(2\in C_4\). Replacing the chosen odd lift by the other odd lift leaves its square unchanged. Thus the defect cannot be removed by changing this choice. In the nerve description the failed equality is the composition requirement over the next overlap. Its relative \(0\)-truncated family has a section, since all the fibers there are singletons, and hence cannot see that requirement.
The same family has discrete computational data. At each parameter a verifier may accept the empty trace with output zero. Attaching the group of record identifications does not change this verifier. It changes the question from whether there is a successful result to whether the full record can be chosen compatibly under transport. Thus changing the output test cannot by itself repair the obstruction.\index{descent}\index{record!coherent choice}\index{effective epimorphism}
\section{Successive truncations}
Suppose the natural map \(W\to\lim_n\tau_{\le n}^{/U}W\) in the slice is an equivalence. This is an explicit hypothesis on the family, and it holds in spaces. A compatible system of sections of the relative truncations then gives a section of \(W\). Indeed the mapping-space functor out of the terminal slice object preserves limits. In using this fact it is the compatible system of sections, with higher coherences, which determines the point in the limit. Statements of separate inhabitation at a collection of stages have no such consequence for a general inverse diagram. For example the discrete sets \(\{k\in\omega:k\ge n\}\) form a tower with nonempty terms and empty limit. The relevance of truncation is that it permits a sequence of progressively stronger compatibility checks on the same family. It is distinct from the ordinal filtration that bounds the formation of the original records.
\section[Exercises]{Exercises\enspace{\normalfont\normalsize\hyperref[solutions:XII]{[Worked solutions]}}}
\begin{exercise}
\label{ex:XII.1}
Prove the local initiality conclusion of Theorem~\ref{thm:alg-descent} assuming the object is initial over \(V\) and all its further restrictions to \(V^{[n]}\) preserve initiality.
\end{exercise}
\begin{exercise}
\label{ex:XII.2}
Let \(U\) be discrete and \(W_\xi\hookrightarrow W\) be a \(\lambda\)-chain as in Proposition~\ref{prop:common-stage}. For a singular limit \(\lambda\), construct a cover of size \(\operatorname{cf}(\lambda)\) on which a section factors locally through stages with no single global stage.
\end{exercise}
\begin{exercise}
\label{ex:XII.3}
Let \(1\to K\to H\to G\to1\) be an exact sequence of discrete groups. Determine the relative \(0\)-truncation and the relative \(1\)-truncation of \(BH\to BG\). Prove that a section exists iff the group extension splits.
\end{exercise}
\begin{exercise}
\label{ex:XII.4}
Compute the Čech nerve of the cover \(1\to BG\) in spaces. Express a compatible family of records over its levels in terms of the action of \(G\) on a homotopy fiber.
\end{exercise}
\begin{exercise}
\label{ex:XII.5}
Give a site and a covering family for which nonemptiness of all selected fibers is visible on the cover but a section of their product fails. State exactly which conclusion of Proposition~\ref{prop:common-stage} still holds for a filtration containing those local witnesses.
\end{exercise}
\begin{exercise}
\label{ex:XII.6}
Use a family over \(S^1\) with fiber a nonempty set and prescribed permutation monodromy. Determine the components of its section space and compare them with the domain of its convergence predicate.
\end{exercise}
Original LaTeX source
Higher Categorical Recursion Theory
End of manuscript · Back to top ↑