\chapter{Selection and bounded forcing}
\label{sel:chapter}
\section{Finding a successful instruction}
For fixed \(x\) let \(S_e(x)=\{n<\omega:\{e\}(n,x)\downarrow\}\). The set is enumerable in the sense of \(E\)-recursion. Numerical search by interleaving one step of each computation does not describe its enumeration. A successful subcall can have arbitrary ordinal length. Gandy selection gives a uniform partial \(E\)-recursive procedure with arguments \(e,x\) which is defined exactly when \(S_e(x)\) is nonempty and returns a member in that case \cite[Chapter X, Theorem 4.1]{Sacks}. The key comparison examines two calls and obtains the shorter successful length, allowing one call to diverge. The recursion in the comparison decreases a bound supplied by a successful call. With an ordinal bound supplied, testing whether a given computation ends below it is \(E\)-recursive.
Consider an index domain \(D\) larger than \(\omega\). If the least successful length \(\gamma\) can be computed from the input, the bounded-length test recovers the entire nonempty set of minimizers, using the union scheme on singletons. Selecting a member from this set is a separate operation. A given effective well-order of \(D\) suffices. The Grilliot and Harrington--MacQueen arguments use access to a power set to compute the minimum for suitable larger domains \cite{GrilliotHM}. A version due to Normann uses a bounded part of a regular cardinal in the relevant \(E\)-closure. These theorems specify resources for both the rank comparison and the selection. The existence of a least ordinal uses none of those resources.
For finding a divergent subcall the index class is usually the complement of an enumerable class. The Kechris basis theorem treats just this situation. If \(D\) is \(E\)-recursive in \(x\), \(A\) is \(E\)-enumerable in \(x\), and \(D\setminus A\ne\varnothing\), there is \(b\in D\setminus A\) with
\(\kappa_r^{x,b}\leq \kappa_r^x\) \cite[Chapter X, Theorem 5.1]{Sacks}. A typical application chooses a subcall without raising the reflection bound. For a sequence of such choices one still needs a choice rule and verification that the records for the chosen edges are visible in the given model. The use of an effective well-ordering in the analysis of Moschovakis witnesses supplies this extra uniformity.
\section{Local existence and simultaneous choice}
Work in an \(\infty\)-topos \(\mathcal X\). Put the possible parameters in \(U\), and let \(R\to D\to U\) be a family of candidate records. A parameter in \(D\) specifies a candidate instruction. The image of \(R\to U\) is the assertion that some candidate has a record. A section of \(R\to U\) supplies both a candidate and a record throughout the parameter object. Even existence in every local fiber need not yield such a section. Proposition~\ref{erec:prop-determinacy} shows that a discrete value can descend under a uniqueness hypothesis. The evidence for that value may still have many paths and nontrivial monodromy.
A rule with premises indexed by \(p:D\to U\) needs a family of records. Its existence predicate is the image of \(\Pi_p R\to U\), where \(R\) is now regarded as an object over \(D\). If this image is all of \(U\), then \(R\to D\) is an effective epimorphism. Indeed the evaluation map pulls every local section of the dependent product back to witnesses over the corresponding part of \(D\). The converse is valid when \(p\) is finite locally constant. To prove it, pass to a cover on which \(D\) is a finite disjoint union of copies of the base. Finite products of effective epimorphisms are effective epimorphisms by stability under pullback and composition. The assertion descends along the cover, since equality of subobjects can be tested after such pullback.
\begin{example}[Individual witnesses on the affine line]
Consider sheaves of spaces on the Zariski space \(X=\mathbb A^1_{\mathbb Q}\). For \(n\geq 1\) let \(U_n=X\setminus\{x=n\}\) and let \(V=X\setminus\{x=0\}\). Regard these opens as subterminals and put \(R_n=U_n\amalg V\). Every \(R_n\to 1\) is an effective epimorphism because the two opens cover \(X\). A section of \(R_n\) over a nonempty open \(O\) must lie in a single summand. The open \(O\) is irreducible and a choice of summand would otherwise decompose it into two disjoint nonempty opens. If \(O\) contains \(x=0\), the \(V\) summand is unavailable. A family of all the \(R_n\)-sections over \(O\) would require \(O\) to omit every positive integer point. Every nonempty Zariski open in \(X\) contains all but finitely many of those points. Thus the product of the \(R_n\) has no local section at \(x=0\). This is a failure to assemble witnesses even if every witness is assigned the same ordinal bound.
\end{example}
\begin{figure}[tbp]
\centering
\begin{tikzpicture}[>=Latex, every node/.style={font=\small}]
\node[draw,rounded corners,align=center] (a) at (-2.8,0)
{\(U_n\)\\excludes \(x=n\)};
\node[draw,rounded corners,align=center] (b) at (2.8,0)
{\(V\)\\excludes \(x=0\)};
\node[draw,rounded corners,align=center] (x) at (0,-1.35)
{\(X\)\\covered for every \(n\)};
\draw[->] (a) -- (x);
\draw[->] (b) -- (x);
\node[align=center] at (0,-2.65)
{A neighbourhood of \(0\) must use \(U_n\) at every \(n\).\\
No such open can omit all the positive integer points.};
\end{tikzpicture}
\caption{The two local domains form a cover for each fixed premise. The countable family has no common neighbourhood of \(0\) carrying all the chosen witnesses.}
\label{sel:fig-zariski}
\end{figure}
\section{Extracting a bound from local records}
An external increasing filtration \(R_{<\gamma}\hookrightarrow R\) of records, indexed by \(\gamma<\lambda\) for a limit ordinal \(\lambda\), can express length restrictions such as those in Chapter~\ref{erec:chapter}. If the colimit of the filtration is \(R\), then the union of the images of all \(R_{<\gamma}\to U\) is the image of \(R\to U\). This follows from the adjunction between image and inclusion of subobjects. One asks when the image can be reached at one particular stage.
\begin{theorem}[Bounding along a small cover]
\label{sel:thm-cover}
Let \(\{V_i\to U\}_{i\in J}\) be jointly effective epimorphic with
\(|J|<\operatorname{cf}(\lambda)\), and let \(R_{<\gamma}\to U\) be an increasing filtration as above. Suppose for each \(i\) there is \(\gamma_i<\lambda\) such that \(V_i\times_U R_{<\gamma_i}\to V_i\) is an effective epimorphism. Then for some \(\gamma<\lambda\) the map \(R_{<\gamma}\to U\) is an effective epimorphism. The assertion for the chosen bound is preserved by any pullback in \(\mathcal X\).
\end{theorem}
\begin{proof}
Take an ordinal \(\gamma<\lambda\) above all the \(\gamma_i\). The image of \(R_{<\gamma}\) pulls back to the whole of every \(V_i\), since images commute with pullback. Therefore every \(V_i\to U\) factors through this image. The \(V_i\) cover \(U\), so their joint image is \(U\). This proves the first assertion. Effective epimorphisms are stable under base change.
\end{proof}
\begin{example}[Pointwise bounds in the topos of spaces]
When \(\mathcal X\) is the topos of spaces, the inclusion of one chosen point in each connected component gives a cover of \(U\). If there are fewer than \(\operatorname{cf}(\lambda)\) components and every point has a bounded record, the theorem applies. Inside a single component an inhabited fiber at one point implies a local record at every point, allowing the same stage bound. A coproduct of \(\lambda\) points can behave differently. Put one record at the point indexed by \(\xi\) and admit it only at stages \(\gamma>\xi\). The images cover their colimit. No stage covers all components. The distinction exists already for sets.
\end{example}
\begin{figure}[tbp]
\centering
\begin{tikzcd}[column sep=large,row sep=large]
V_i\times_U R_{<\gamma}\arrow[r]\arrow[d,two heads]
& R_{<\gamma}\arrow[d,dashed,two heads]\\
V_i\arrow[r] & U
\end{tikzcd}
\caption{At a common bound \(\gamma\) every local pullback covers. Joint coverage by the \(V_i\) makes the right map an effective epimorphism.}
\label{sel:fig-bound}
\end{figure}
The use of \(\operatorname{cf}(\lambda)\) in Theorem~\ref{sel:thm-cover} is external. It gives a bound in the metatheory. For finite covers with a supplied finite list of computable ordinal bounds, an effective maximum gives the bound in the same recursion theory. For an infinite cover this conclusion needs an effective collection of the bounds, or another effective argument. If the local data only assert that some bounded witness exists, there may be no way to extract from them an index computing a bound. Even a computable common bound for all witnesses would leave open the simultaneous choice problem of Figure~\ref{sel:fig-zariski}.
\section{The effective forcing problem}
In classical \(E\)-recursion let \(M=L_\kappa\) be \(E\)-closed, let \(\mathbb P\in M\) be a set forcing, and let \(\dot t\) be a parameter name in the computation forcing language of \cite[Chapter XI]{Sacks}. The relation
\(p\Vdash|\{e\}(\dot t)|=\xi\), with \(\xi\) specified, can be obtained by \(E\)-recursion from the displayed data using the bounded forcing clauses. The clauses for a union instruction first determine the possible preliminary output names and then account for the calls on their members. A fixed bound keeps these operations within the designated sets of codes. Effective bounding says that when \(p\) weakly forces convergence, there is a bound \(\gamma\) computed uniformly from the forcing data and the instruction such that \(p\) weakly forces the length to be less than \(\gamma\). The same bound must work throughout the cone below the condition. A separate search of unbounded length at each extension does not provide it.
Here is a sufficient preservation criterion stated in terms of the computational information. Assume that names for arguments in \(M[G]\) are available in the forcing language, that convergence of a call at \(G\) is witnessed by a condition in \(G\), and that soundness for the forcing clauses holds. Assume further that when \(p\in G\) weakly forces success below some \(\gamma\in M\), the bounded name construction yields a value in \(M[G]\). Under effective bounding, \(M[G]\) is closed under those calls. In fact one obtains \(p\in G\) by the convergence truth lemma and computes the bound from the input data in \(M\). Closure of \(M\) puts the bound in \(M\). Applying the bounded name construction then puts the value in \(M[G]\). This isolates the work the forcing theorems need to do beyond stability of images.
There are two different methods for producing the ground bound. In the countably closed case a path through the tree of possibilities is used to choose a decreasing sequence of conditions. When a code for the sequence exists in the ground structure, countable closure supplies a lower bound forcing the corresponding descent of subinstructions. This conflicts with forced convergence. The proof over a \(\Sigma_1\)-inadmissible \(E\)-closed \(L_\kappa\) constructs the required ground paths by reflection, with the effective ordinal presentations of conditions used in \cite{InadmissibleForcing,SlamanReflection}. The chain-condition method uses antichains and small-domain selection to find sufficiently many possible deciding conditions. The hypotheses and rank comparisons are different from those needed for a lower bound of a sequence \cite[Chapter XI, Theorem 4.1]{Sacks}. Theorem~\ref{sel:thm-cover} explains one feature common to the two approaches. Once local bounds are obtained, the relevant comparison is with a single bound adequate under every allowed refinement.
\section{Sections and envelopes}
For set types start with \(\operatorname{tp}(0)=\omega\), put
\(\operatorname{tp}(\xi+1)=\mathcal P(\operatorname{tp}(\xi))\), and take unions at limits. Fix an oracle \(F\) with its associated \(E\)-recursion and base parameters. A \(\delta\)-section in Sacks's sense records the reachable outputs of type \(\delta\). For successor \(\delta\), the \(\delta\)-envelope records the enumerable subsets of \(\operatorname{tp}(\delta-1)\) with the associated inputs and oracle. The type-two existential functional has the hyperarithmetic reals for its \(1\)-section. The compression at higher types depends on what part of the computation is retained. Write \(\operatorname{sc}_{\delta}(F)\) and \(\operatorname{en}_{\delta}(F)\) for the section and envelope in the conventions of \cite[Chapter XII]{Sacks}. Sacks's plus-one theorem gives \(\operatorname{sc}_{\delta}(G)=\operatorname{sc}_{\delta}(F)\) with \(G\) of type \(\delta+1\), for \(F\) of type \(\alpha+2\), successor \(\delta<\alpha+2\), and successor \(\alpha\) if \(\delta>1\). Harrington's plus-two theorem gives \(\operatorname{en}_{\delta}(G)=\operatorname{en}_{\delta}(F)\) with \(G\) of type \(\delta+2\), for successor \(\delta<\alpha\) and successor \(\alpha\) \cite{HarringtonThesis}. The latter requires preservation of the enumerable traces, whose appearance may depend on the reflection point for the computation.
For the numerical distinction in a topos, use record objects \(R_0\to U\) and \(R_1\to U\) for certificates of the two possible answers. If their image subobjects \(D_0,D_1\) are disjoint and jointly cover \(U\), the canonical arrow \(D_0\amalg D_1\to U\) is both mono and effective epi. It is therefore an equivalence. Sending the two summands to the two points of \(1\amalg1\) gives a total Boolean answer. The corresponding statement when one has only \(R_1\) is local semidecision by its image. In particular the range of total answers may be studied independently of the individual records supplying the answers. The proof shows what a comparison of enumerable domains must preserve in order to recover a total Boolean behavior. Comparison across higher oracle types also needs the effective ability to construct the witnessing records.
\section[Exercises]{Exercises\enspace{\normalfont\normalsize\hyperref[solutions:XI]{[Worked solutions]}}}
\begin{exercise}
\label{ex:XI.1}
Suppose a common length bound for every convergent call and a finite presentation of a candidate domain are given as part of an \(E\)-instruction. Describe the bounded search for the set of successful candidates. Specify the additional datum needed to return its least member.
\end{exercise}
\begin{exercise}
\label{ex:XI.2}
Prove by a local trivialization that a finite locally constant family \(D\to U\) preserves effective epimorphisms under \(\Pi_{D\to U}\). Consider also the case of fibers of size zero.
\end{exercise}
\begin{exercise}
\label{ex:XI.3}
Replace the positive integer points in Figure~\ref{sel:fig-zariski} by any infinite sequence of distinct rational points outside \(0\). Determine the image of the resulting product in the subobject lattice of the terminal sheaf.
\end{exercise}
\begin{exercise}
\label{ex:XI.4}
Give a version of Theorem~\ref{sel:thm-cover} for a filtered partially ordered set of bounds in place of an ordinal. State the assumption on the family \((\gamma_i)\) that replaces the cofinality inequality.
\end{exercise}
\begin{exercise}
\label{ex:XI.5}
Let \(R_{<n}\to\mathbb N\) in sets have one record over each \(k<n\). Compute the least successful bound over each \(k\), the join of all the images, and the image after pulling back along the inclusion of the even integers.
\end{exercise}
\begin{exercise}
\label{ex:XI.6}
Suppose \(D_0,D_1\hookrightarrow U\) are the convergence images of tests for outputs \(0,1\). Give the criterion, in terms of those subobjects, for these tests to induce a map \(U\to 1\amalg1\). Analyze the result when their join is a proper subobject.
\end{exercise}
\begin{exercise}
\label{ex:XI.7}
In the abstract forcing preservation argument, assume the bounds vary over a finite deciding family of conditions and the language supplies names and a finite list of their rank bounds. Give a common effective bound for the family. Explain which step would require a new hypothesis for a ground set of conditions with infinitely many bounds.
\end{exercise}
Original LaTeX source
Higher Categorical Recursion Theory
End of manuscript · Back to top ↑