\chapter{Families of computations}
\label{ch:families}
\section{Presentations and families}
A partial function on natural numbers can be given by a program, by its graph, or by a family of verified records of its executions. If \(e\) is an index and \(x,y\) are numbers, a predicate \(V(e,x,y,w)\) may state that \(w\) is a successful execution of \(e\) on \(x\) with output \(y\). The projection of the verified tuples onto \((e,x,y)\) gives the graph. The projection onto \((e,x)\) gives the domain of convergence. The projections keep less information than the original relation.
The same description applies when a set of possible subcalls is part of the input. Then a record must justify every required subcall. Even for a deterministic computation, the record may contain choices of a presentation, of a bound, or of an indexing of intermediate data. A family of such records can be studied by retaining its local identifications. We use objects of an \(\infty\)-topos to represent these families, and we keep the data certifying effectivity in the chosen recursive or admissible presentation.
An \(\infty\)-topos \(\mathcal X\) is taken in the sense of \cite{Lurie}. Write \(\mathcal X_{/U}\) for its slice at \(U\). An object there is a map to \(U\), thought of as a family over parameters \(U\). For \(v:V\to U\), substitution is the pullback functor
\[
\Sigma_v \dashv v^* \dashv \Pi_v .
\]
Here \(\Sigma_v\) composes with \(v\), and \(\Pi_v\) takes dependent products. These formulas include the change of the indexing object. For example, over a test map \(b:T\to U\), a section of \(\Pi_v W\) is equivalent to a section of the pulled-back \(W\) over \(T\times_U V\). In sets this is a tuple of choices indexed by the elements of each fiber. In spaces the sections must transport coherently over paths of the test object.
\begin{definition}
A family of execution records with input object \(U\) and output family \(Y\to U\) consists of a map \(W\to Y\) over \(U\). Its behavior is the subobject
\[
\operatorname{im}(W\to Y)\hookrightarrow Y.
\]
Its domain is \(\operatorname{im}(W\to U)\hookrightarrow U\).
\end{definition}
By image we mean the \((-1)\)-truncated part of the effective epimorphism and monomorphism factorization. The record, behavior, and domain are displayed in Figure~\ref{fig:fam-levels}. In a slice there are also intermediate relative truncations \(\tau_{\le n}^{/U}W\). For \(n=0\) the paths within a fiber are collapsed to equivalence classes. For \(n=-1\) all inhabitants of a fiber give the same truth value. The distinctions are fiberwise. Taking connected components of the total space can also identify records from different inputs when those inputs lie in a connected base.
\begin{figure}[htbp]
\centering
\begin{tikzpicture}[node distance=9mm and 8mm]
\node[booksite] (w) {Records\\ \(W\)};
\node[bookbox,right=of w] (g) {Behavior\\ \(\operatorname{im}(W\to Y)\)};
\node[bookbox,right=of g] (d) {Domain\\ \(\operatorname{im}(W\to U)\)};
\draw[bookarr] (w) -- (g);
\draw[bookarr] (g) -- (d);
\node[booknote,below=of g] (n) {The middle object remembers the output.\\ The last remembers whether a computation succeeds.};
\draw[bookarr,draw=accent] (n.north) -- (g.south);
\end{tikzpicture}
\caption{Two projections of a family of successful computations. All three objects have maps to the input object \(U\).}
\label{fig:fam-levels}
\end{figure}
\begin{proposition}[Ordinary partial maps in a slice]
Suppose the behavior \(R\hookrightarrow Y\) has monomorphic projection \(R\to U\). It defines a partial section of \(Y\) on its domain. If the output family is \(0\)-truncated, a partial section \(D\hookrightarrow U\), \(D\to Y\) over \(U\), gives such a behavior, with domain \(D\).
\end{proposition}
\begin{proof}
Factor \(R\to U\) through its image \(D\). The map \(R\to D\) is both an effective epimorphism and a monomorphism, so it is an equivalence. Thus \(R\to Y\) is a section over \(D\). For the converse, the homotopy fiber of \(D\to Y\) at an output is a fiber of a map from a subterminal input fiber to a discrete output fiber. Such a fiber is subterminal. Hence \(D\to Y\) is itself a mono, and its image has the specified domain.
\end{proof}
\begin{remark}
The monomorphism condition on \(R\to U\) is natural for discrete outputs. With higher outputs, a chosen section need not be a mono into \(Y\). The graph is then kept as the span \(U\leftarrow D\to Y\), or as an object of the slice over \(Y\), before taking any image. For instance \(1\to BG\) classifies an output with automorphisms. For nontrivial \(G\) its image is all of \(BG\), whose projection to \(1\) is not a monomorphism.
\end{remark}
\section{Change of parameters}
The image of a map in an \(\infty\)-topos pulls back to the image of its pullback. This follows from stability of effective epimorphisms and monomorphisms. For constructive logic this amounts to the rule that an existential assertion may be pulled back with its witness problem. In the following pullback square \(p\) can be a projection from an index family, and \(q\) is its change of base.
\[
\begin{tikzcd}[column sep=large,row sep=large]
E' \arrow[r,"u"]\arrow[d,"q"']&E\arrow[d,"p"]\\
U' \arrow[r,"v"']&U .
\end{tikzcd}
\]
On objects the corresponding comparisons are
\[
v^*\Sigma_p\simeq\Sigma_q u^*,
\qquad
v^*\Pi_p\simeq\Pi_q u^*.
\]
The first identifies two ways of writing the same composite pullback. For the second, test the left side and the right side against \(T\to U'\). Moving the pullbacks and the dependent product across their adjunctions identifies the two spaces of maps with maps over \(E\) from \(E\times_U T\). This determines the required equivalence naturally.
\begin{proposition}[Composition and existential behavior]
\label{prop:fam-composition}
Let \(W\) be a family over \(A\times B\) and \(Z\) a family over \(B\times C\). Form the record of their successive use as \(W\times_B Z\) over \(A\times C\). Its image is
\[
\exists b\,\bigl(\operatorname{im}(W)(a,b)\wedge
\operatorname{im}(Z)(b,c)\bigr)
\]
in the internal subobject logic. This comparison is compatible with pullback in an additional parameter.
\end{proposition}
\begin{proof}
Write \(R=\operatorname{im}(W\to A\times B)\) and \(S=\operatorname{im}(Z\to B\times C)\). The arrow \(W\times_B Z\to R\times_B S\) is a composite of pullbacks of the two effective epimorphisms onto \(R,S\). It is an effective epimorphism. Thus the two maps to \(A\times C\) have the same image. The image of \(R\times_B S\) is precisely the displayed predicate. Each construction used here commutes with a change of the common parameter by the pullback formulas.
\end{proof}
\begin{figure}[htbp]
\centering
\begin{tikzcd}[column sep=2.2em,row sep=1.8em]
& W\times_B Z \arrow[dl] \arrow[dr]\arrow[dd,draw=accent,dashed] & \\
W\arrow[d]\arrow[dr]& &Z\arrow[dl]\arrow[d]\\
A & B & C
\end{tikzcd}
\par\smallskip
\(\operatorname{im}(W\times_B Z\longrightarrow A\times C)\)
\caption{A composite record contains two records with the same intermediate value. Projection discards that value, and the image asserts the existence of such a pair.}
\label{fig:fam-composite}
\end{figure}
For an arbitrary index family \(D\to U\), local inhabitation of each \(W_d\) does not imply local inhabitation of the whole product over \(D\). The proof of Proposition~\ref{prop:fam-composition} uses only a finite matching of witnesses. The finite locally constant case of dependent products is treated in Chapter~\ref{sel:chapter}. An argument with larger arities must justify the construction of the family of witnesses. In admissible recursion this is where a collection bound can enter. In a sheaf model this is where covers with progressively smaller neighbourhoods can prevent simultaneous choice.
\section{An effective reading of the same diagram}
For a fixed recursive program with oracle \(X\subseteq\omega\), a finite successful run on \(n\) certifies its output under every oracle agreeing on the finitely many queries in that run. With \([s]\) denoting the cylinder determined by a finite initial oracle segment \(s\), we have
\[
\{X:\Phi_e^X(n)\downarrow=m\}
=\bigcup\bigl\{[s]:\text{the run for }e,n\text{ with }s
\text{ returns }m\bigr\}.
\]
In the right side, a run is suspended if its next query leaves the initial segment. Every successful run over a total oracle is captured by a long enough initial segment. Thus the union is uniformly effectively open. The diagrams of this chapter describe its existential projection. The recursive enumeration of the cylinders proves the effective openness. One needs this enumeration to recover the classical theorem from the semantic calculation.
Another treatment uses assemblies based on a partial combinatory algebra. A map of assemblies has a tracking index acting on the realizers. When the underlying partial application is Kleene application, the tracker gives an ordinary computable operation. Quantification and exact completion supply the effective topos of Hyland \cite{Hyland}. Changing the partial combinatory algebra to represent an additional partial function has a separate universal property \cite{OostenRel}. These constructions give places to put the effectiveness data. An univalent family in an \(\infty\)-topos classifies a suitable class of maps and records equivalences between fibers \cite{GepnerKock}. The determination of which presentations are effectively comparable is a further condition on the class and its morphisms.
\begin{example}[A deterministic value with moving records]
Let \(G\) act on a nonempty set \(D\), and consider the family \(EG\times_G D\to BG\) in spaces. Give every record in \(D\) the numerical answer zero. The behavior is the constant answer zero, since each fiber is nonempty. Pullback along a loop \(g\) of \(BG\) transports a record by the permutation \(g\). If \(D\) has no fixed point, the record family has no section. This follows because sections correspond to homotopy fixed points of \(D\), which for a discrete \(D\) are ordinary fixed points. The computation is deterministic at the level of answers, while its records carry nontrivial transport.
\end{example}
The subsequent constructions distinguish three uses of an index. A program is indexed by a natural number. A rank bounds when the record of a branched computation appears. A parameter may itself have paths and acts on its record fibers by transport. A numerical index makes a uniform effective assertion possible. A common rank makes a collection argument possible. The parameter pullback makes a comparison of local witnesses possible. None of these constructions requires identifying an ordinal rank with a homotopy dimension.\index{record of computation}\index{relative truncation}\index{change of base}
\section[Exercises]{Exercises\enspace{\normalfont\normalsize\hyperref[solutions:I]{[Worked solutions]}}}
\begin{exercise}
\label{ex:I.1}
Give a recursive family of finite records for the composition of two partial recursive numerical functions. Show by projection that its domain has precisely the elements on which the composite is defined.
\end{exercise}
\begin{exercise}
\label{ex:I.2}
Let \(W\to U\) and \(Z\to U\) be families. Prove that the image of \(W\times_U Z\to U\) is the intersection of their images, and identify the use of effective epimorphisms.
\end{exercise}
\begin{exercise}
\label{ex:I.3}
In spaces find a map \(Y\to U\) with \(Y\) and \(U\) both connected for which the relative \(0\)-truncation of \(Y\) over \(U\) has a fiber with more than one component.
\end{exercise}
\begin{exercise}
\label{ex:I.4}
Let \(G\) act transitively on a two-element set. Describe the relative image and relative \(0\)-truncation of its family over \(BG\), and decide whether the family admits a section.
\end{exercise}
\begin{exercise}
\label{ex:I.5}
Write down an explicit representation of a finite oracle trace as a cylinder in Cantor space. Determine the condition under which two such cylinders intersect, including when they have different lengths.
\end{exercise}
\begin{exercise}
\label{ex:I.6}
Use Proposition~\ref{prop:fam-composition} to show that three relations compose associatively in the subobject logic. Describe the two parenthesizations before taking the image.
\end{exercise}
Original LaTeX source
Higher Categorical Recursion Theory
End of manuscript · Back to top ↑