\chapter{Relative computation and support}
\label{rel:chapter}
\section{Whole queries}
Fix \(M=L_\alpha\) as in Chapter~\ref{adm:chapter}. A signed support on \(\alpha\) is a pair \(p=(H,J)\) of disjoint \(\alpha\)-finite subsets of \(\alpha\). An oracle \(A\subseteq\alpha\) satisfies it when \(H\subseteq A\) and \(J\cap A=\varnothing\). Supports are ordered by extension in both signs. Every support is bounded in \(\alpha\) because the union of an \(\alpha\)-finite set of ordinals belongs to \(M\).
A weak relative procedure is an \(\alpha\)-recursively enumerable relation \(R(p,x,y)\) interpreted as a possible certificate for \(f(x)=y\), provided \(A\) satisfies \(p\). The procedure computes \(f\) relative to \(A\) if the witnessed graph with that oracle is exactly the graph of \(f\). It need not be functional with other oracles. A strong reduction of \(A\) to \(B\) gives semidecision procedures, with signed \(B\)-supports, for both predicates
\[
K\subseteq A,\qquad K\cap A=\varnothing
\qquad(K\in M,\ K\subseteq\alpha).
\]
These tests concern entire \(\alpha\)-finite queries. In particular they jointly provide the two answers for a singleton. These are the weak and strong definitions of Sacks \cite[Chs.~V and VII]{Sacks}.
\begin{proposition}[Composition of strong reductions]
\label{rel:composition}
Strong \(\alpha\)-reducibility is transitive.
\end{proposition}
\begin{proof}
Suppose \(A\) is strongly reduced to \(B\), and \(B\) to \(C\). An accepting record for a whole query about \(A\) uses one support \((H,J)\) on \(B\). Substitute an accepting record for \(H\subseteq B\) and one for \(J\cap B=\varnothing\) from the second reduction. Each record has a \(C\)-support. Take the union of the two sets of positive questions and of the two sets of negative questions. Discard incompatible unions. The test that the three enumerated records have the indicated interfaces is bounded once their enumeration witnesses are given, so existence of the three records is a \(\Sigma_1\) condition. With oracle \(C\), a successful record implies truth of the original query by the two hypotheses. If the query is true, choose the first reduction's record and the two records verifying its support. Their unions are compatible because they agree with the same oracle. The negative whole-query test is composed by the same construction.
\end{proof}
\begin{figure}[tbp]
\centering
\begin{tikzpicture}[
node distance=9mm and 11mm,
supportnode/.style={draw,rounded corners,align=center,inner sep=5pt},
>=Stealth]
\node[supportnode] (q) {\(A\)-query};
\node[supportnode,right=of q] (s) {\(B\)-support\\\((H,J)\)};
\node[supportnode,above right=6mm and 11mm of s] (plus) {\(C\)-support for\\\(H\subseteq B\)};
\node[supportnode,below right=6mm and 11mm of s] (minus) {\(C\)-support for\\\(J\cap B=\varnothing\)};
\node[supportnode,right=34mm of s] (dummy) [draw=none,inner sep=0pt] {};
\node[supportnode,right=7mm of dummy] (union) {compatible\\union};
\draw[->] (q) -- (s);
\draw[->] (s) -- (plus);
\draw[->] (s) -- (minus);
\draw[->] (plus.east) -- (union.north west);
\draw[->] (minus.east) -- (union.south west);
\end{tikzpicture}
\caption{Substitution of whole-query records. One intermediate support is discharged by two accepting records.}
\label{rel:fig-composite}
\end{figure}
A weak procedure applied separately to all members of a support would supply a family of new supports. The fact that its index set and every member belong to \(M\) does not put the family in \(M\). For instance, if \((\xi_n)\) is an external cofinal sequence in \(\omega_1^{\mathrm{CK}}\), the supports \((\{\xi_n\},\varnothing)\) are metafinite. Their aggregate positive part is unbounded, so it is not metafinite. This example isolates the missing bound without claiming that this particular sequence has a given relative computability degree. By contrast, the supports \((\{2n\},\varnothing)\) have a graph in \(L_{\omega_1^{\mathrm{CK}}}\), and their aggregate is the recursive set of even integers.
\section{Regularity, hyperregularity, and compression}
An oracle \(A\) is regular if \(A\cap\xi\in M\) for every \(\xi<\alpha\). It is hyperregular if every total weakly \(A\)-recursive function \(\alpha\to\alpha\) has bounded range on each \(\xi<\alpha\). These definitions test different aspects of relative computation. Regularity makes any \emph{given} bounded portion of the oracle available as a set. Hyperregularity bounds the resources demanded by an entire family of relative computations. They are related to the expansion of \((M,\in)\) by the predicate \(A\).
\begin{theorem}[Admissible expansion]
\label{rel:expansion}
The expansion \((L_\alpha,\in,A)\) satisfies bounded Separation and bounded Collection in its expanded language if and only if \(A\) is regular and hyperregular.
\end{theorem}
\begin{proof}
Expanded Separation gives regularity. Any weak oracle graph has a \(\Sigma_1(A)\) definition, because compatibility of a supplied support is a bounded formula in the expanded language. Expanded Collection therefore places the range of each total weakly \(A\)-recursive function on a bounded domain in a set of \(M\). Such a set of ordinals is bounded in \(\alpha\).
For the converse, bounded Separation with a fixed set of parameters requires only a bounded part of \(A\). Indeed, the values reached by bounded quantifiers belong to the transitive closure of the sets being searched and of the parameters. The ordinals there have a single bound in \(\alpha\). The oracle predicate on this domain can be replaced by the set \(A\cap\xi\) at that bound.
For Collection, suppose \((\forall x\in a)(\exists y)\,D(x,y,p,A)\) with \(a,p\in M\) and \(D\) bounded. Use an \(M\)-well-order of \(a\) with ordinal domain \(\gamma<\alpha\), and the usual \(\alpha\)-recursive enumeration of \(M\) with \(M\)-coded bounded prefixes \cite[Ch.~VII, Secs.~1 and 3]{Sacks}. For each index \(i<\gamma\), define \(g(i)\) to be the first ordinal code of a witness \(y\) for its input \(x\). Set \(g=0\) on the other indices below \(\alpha\). Given a proposed witness index, all earlier candidates lie in one bounded prefix of the enumeration. Take the transitive closure of this prefix together with the parameters and the selected input. It bounds the oracle questions in testing \(D\) on all those candidates. A signed table for \(A\) on this ordinal bound exists by regularity. Using the table as support, ordinary \(\Sigma_1\) enumeration certifies that the proposed index is the first success. This describes \(g\) as a total weakly \(A\)-recursive ordinal function. Hyperregularity bounds \(g[\gamma]\). A bounded prefix of the enumeration containing these indices gives the required collecting set.
\end{proof}
Admissibility does not say that every enumerable subset of a given set is available. Let \(\rho_1(\alpha)\) be the least ordinal \(\rho\le\alpha\) admitting an injective \(\alpha\)-recursive map \(\alpha\to\rho\). This is Sacks's first projectum for \(L_\alpha\). It also measures the least ordinal supporting an \(\alpha\)-recursively enumerable subset outside \(M\), with the comparison at \(\alpha\) understood externally \cite[Ch.~VII, Sec.~2]{Sacks}\cite{ChongFriedman}. Each enumerable \(S\subseteq\beta\) has a partial injective \(\alpha\)-recursive enumeration with domain an initial segment of \(\alpha\). This enumeration orders first successful certificates and removes duplicates, recording bounded initial histories. If \(\beta<\rho_1(\alpha)\), its domain cannot be all of \(\alpha\). On a proper initial segment Proposition~\ref{adm:bounded-records} puts its range in \(M\). Conversely the range of an injection witnessing \(\rho_1(\alpha)\) cannot be an \(M\)-set. Its inverse would be a total \(\Sigma_1\) function on that set, and Collection would put its unbounded ordinal range in \(M\).
The projectum measures coding into a short ordinal rather than a cofinal map out of a short ordinal. A total \(\Sigma_1\) map from \(\beta<\alpha\) into \(\alpha\) has bounded range, regardless of how small the projectum is. Cofinality from a shorter domain can occur at higher definability complexity, or when the predicate in an expansion breaks Collection. For example \(\operatorname{cf}(\omega_1^{\mathrm{CK}})=\omega\) externally, and \(\rho_1(\omega_1^{\mathrm{CK}})=\omega\), but there is no cofinal \(\Sigma_1\) map from \(\omega\) over \(L_{\omega_1^{\mathrm{CK}}}\). This distinction constrains the priority schedules that a relative procedure can use.
\section{Amalgamation over a parameter space}
Let \(\mathcal X\) be an \(\infty\)-topos, and work in \(\mathcal X_{/B}\). To represent a family of queries, take an object \(D\) of possible questions and \(2=1+1\) as the object of answers in this slice. An oracle is a point of \(O=2^D\). A signed family of supports indexed by \(S\) consists of maps
\[
U_1\longrightarrow S\times_B D,\qquad U_0\longrightarrow S\times_B D.
\]
Its components give the individual occurrence domains and their signs. Repeated occurrences are allowed. Let \(D_i\hookrightarrow D\) be the image of \(U_i\to D\) for \(i=0,1\). The cylinders defined by the family and by its aggregate can be compared without a section of either image map.
\begin{theorem}[Amalgamation of signed families]
\label{rel:amalgamation}
In \(O\), the subobject of oracles giving answer \(i\) on every \(U_i\) is the subobject of those giving answer \(i\) on \(D_i\). Consequently the simultaneous cylinder for the family is the cylinder of the two image supports. The identity is stable under arbitrary change of base \(B'\to B\). If \(D_0\times_D D_1\) is initial, the aggregate is a disjoint signed support.
\end{theorem}
\begin{proof}
Test the two subobjects on a map \(T\to O\). The corresponding oracle is \(D\times_B T\to 2\times_B T\) over \(T\). The condition that it take value \(i\) on \(D_i\times_B T\) is the condition that a certain equalizer subobject there be top. Its pullback to \(U_i\times_B T\) is top exactly when the original family receives that answer. The map \(U_i\times_B T\to D_i\times_B T\) is an effective epimorphism. Thus it detects top subobjects by image factorization, as in Theorem~\ref{adm:stage}. Equality with the constant answer has a propositional truth value since the target is \(0\)-truncated. Therefore the tests identify the corresponding subobjects on every \(T\). Images, finite limits, and the exponential constructed in the slice satisfy base change, which proves the stability assertion.
\end{proof}
\begin{figure}[tbp]
\centering
\begin{tikzcd}[column sep=large,row sep=large]
U_i \arrow[r,two heads,"e_i"] \arrow[dr] & D_i\arrow[d,hook]\\
& D
\end{tikzcd}
\qquad
\begin{tikzcd}[column sep=large,row sep=large]
U_i\times_B T \arrow[r,two heads]\arrow[d] & D_i\times_B T\arrow[d,hook]\\
2\times_B T & D\times_B T\arrow[l,"o_T"']
\end{tikzcd}
\caption{Aggregation and its test on a generalized oracle. Agreement on occurrences descends along the effective epimorphism at the top right.}
\label{rel:fig-descent}
\end{figure}
\begin{example}[A moving query]
In the \(\infty\)-topos of spaces with \(C_2\)-action, let \(D\) be the discrete two-point torsor. The diagonal \(D\to D\times D\) gives a family of positive singleton queries parametrized by \(S=D\). There is no equivariant global section of \(D\to 1\), so a global choice of one of these queries is unavailable. The aggregate has \(D_1=D\), since the second projection of the diagonal is an equivalence. Its cylinder consists of the oracle that answers \(1\) at both points. After pullback along the torsor the two labels become available, the two singleton equations become separate, and their intersection gives the same result. The aggregate uses every occurrence and thereby avoids the need to choose a global label.
\end{example}
With a discrete set of questions the last theorem recovers ordinary aggregation. For an \(\alpha\)-recursive procedure, the diagram of occurrence domains must be available among the \(\alpha\)-finite data. An arbitrary external family can be aggregated as a set or as an object of an \(\infty\)-topos. It may fall outside the chosen admissible level. For queries on \(\alpha\) with an \(M\)-coded occurrence diagram, Collection puts all the queried ordinals in one set of \(M\), so a bounded subset of \(\alpha\) suffices for \(D\). The theorem then identifies the aggregate and family cylinders at every base receiving those same bounded data.
\section[Exercises]{Exercises\enspace{\normalfont\normalsize\hyperref[solutions:VII]{[Worked solutions]}}}
\begin{exercise}
\label{ex:VII.1}
Write the composite signed rule in Proposition~\ref{rel:composition} as a \(\Sigma_1\) formula over \(L_\alpha\). Indicate which parts of the test are bounded.
\end{exercise}
\begin{exercise}
\label{ex:VII.2}
Suppose a weak oracle procedure \(f<_{w\alpha}A\) is total on \(\alpha\), and \(A\) is regular and hyperregular. Show that the computation records needed for \(f\) on a bounded ordinal can be verified using one bounded oracle table and one bounded enumeration history.
\end{exercise}
\begin{exercise}
\label{ex:VII.3}
Assume \(\beta<\rho_1(\alpha)\) and \(H\in L_\alpha\) has an \(L_\alpha\)-bijection with \(\beta\). Prove that every \(\Sigma_1(L_\alpha)\) subset of \(H\) is in \(L_\alpha\).
\end{exercise}
\begin{exercise}
\label{ex:VII.4}
Replace the binary object \(2\) in Theorem~\ref{rel:amalgamation} by any \(0\)-truncated object \(K\), with specified target values for the different signs. Determine when the prescribed answers agree on overlapping supports.
\end{exercise}
\begin{exercise}
\label{ex:VII.5}
Let \(D\) be the discrete \(C_2\)-torsor in the moving-query example. In the slice over \(D\), construct a family with one positive and one negative occurrence over the two different labels. Compute its cylinder and determine how the generator acts when it exchanges the chosen labels.
\end{exercise}
\begin{exercise}
\label{ex:VII.6}
In spaces take a connected space \(D\), two different points as opposite-signed occurrences, and \(O=2^D\). Evaluate the aggregate cylinder. Explain what the images of the two occurrences say about compatibility here.
\end{exercise}
Original LaTeX source
Higher Categorical Recursion Theory
End of manuscript · Back to top ↑