\chapter{Supported reductions and degree structure}
\label{deg:chapter}
\section{Composition with bounded queries}
A reduction computes an output from an oracle. In the supported version the computation presents its requests and a rule for interpreting their answers. The requests have their own size condition. With a fixed arity budget, a reduction on each individual query might exist even when the complete family of requested reductions exceeds the budget. In ordinal recursion a similar question arises when the input and the supports are required to belong to the ground level.
We first give a parallel model of supported computation. It is useful for showing exactly where the condition on a composite enters. Work in an \(\infty\)-topos \(\mathcal X\), and fix a base \(U\). All the following diagrams are in the slice \(\mathcal X_{/U}\). An answer family is a map \(A\to I\) with request object \(I\). Its fiber at \(i\) is the space of permissible answers to that request. Fix a class \(\mathcal A\) of allowed support maps, containing equivalences and closed under pullback and composition. In spaces one may take the maps with discrete fibers of cardinality less than a fixed infinite regular cardinal \(\kappa\). Composition then uses regularity of \(\kappa\) to bound a sum of fewer than \(\kappa\) cardinals below \(\kappa\).
\begin{definition}
A parallel reduction of \(A\to I\) to \(B\to J\) consists of a span \(I\xleftarrow{p}K\xrightarrow{q}J\) with \(p\in\mathcal A\) and an evaluator
\[
\Pi_p q^* B\longrightarrow A
\]
over \(I\). An equivalence of reductions is an equivalence of their support spans equipped with compatibility with the evaluator.
\end{definition}
In sets, at \(i\in I\) one queries \(q(k)\) for each \(k\in K_i\). The input to the evaluator is an element of \(\prod_{k\in K_i}B_{q(k)}\). In a slice, this product is dependent and includes the appropriate coherences. No choice of a whole family of answers has been assumed. The evaluator acts when that family is supplied. For the composition framework for polynomial functors in locally cartesian closed categories see \cite{GambinoKock}.
\begin{figure}[htbp]
\centering
\begin{tikzcd}[column sep=2.15em,row sep=2.55em]
&&K\times_J L \arrow[ld] \arrow[rd]&&\\
&K \arrow[ld,"p"']\arrow[rd,"q"]&&
L\arrow[ld,"r"']\arrow[rd,"t"] &\\
I&&J&&M
\end{tikzcd}
\caption{Substituting the support \(L\) for the intermediate requests in \(K\). The pullback indexes the actual requests in the composite to \(M\).}
\label{deg:composition}
\end{figure}
\begin{theorem}[Substitution and symmetry]
\label{deg:substitute}
Parallel reductions compose with identity reductions and associative substitution up to canonical equivalence. In an ordinary locally cartesian closed category they give a bicategory with invertible \(2\)-morphisms. In an \(\infty\)-topos the construction and its comparisons are stable under change of base.
\end{theorem}
\begin{proof}
For the second reduction, use \(J\xleftarrow{r}L\xrightarrow{t}M\) and \(\Pi_r t^* C\to B\). In Figure~\ref{deg:composition} write \(u,v\) for the two pullback projections to \(K,L\) respectively. The composite evaluator is
\[
\Pi_{p u}(t v)^*C
\simeq \Pi_p q^*\Pi_r t^* C
\longrightarrow \Pi_p q^*B
\longrightarrow A.
\]
The equivalence is the composition law for right adjoints to pullback followed by dependent-product base change. The support \(p u\) is in \(\mathcal A\) by the two closure hypotheses. The identity span and identity evaluator give identity reductions. For three spans the two ways of forming the composite support are limits of the same diagram, with the same projections. The evaluations agree under their canonical comparison. This can be checked by adjunction, since after pulling back to the request objects the counits evaluate the same answers in the same order. The same comparison for four spans identifies the two associativity paths by the universal property of the limit. Reparametrizing by equivalences of spans commutes with these operations. Pullback on slices preserves the support pullbacks and commutes with their dependent products by base change. This proves the last assertion.
\end{proof}
If evaluators must belong to a specified effective calculus, one must also require that the displayed composite evaluator belongs to it. A condition of this kind is necessary for the reflexive and transitive relation \(A\leq B\) defined by existence of an admitted reduction. Quotienting by mutual reduction then gives a poset. That poset does not retain the space of presentations of a given reduction.
\begin{example}[Symmetries of query indices]
Let \(I,J,A,B\) each be terminal in sets, and let \(K\) be a two-element set requesting the same terminal answer twice. The evaluator is unique. The reduction has the transposition of its queries as a nonidentity automorphism. Its connected component in the groupoid of reductions is equivalent to \(B(\mathbb Z/2)\). Replacing reductions by their existence relation discards this loop.
\end{example}
\begin{example}[Local solvability and monodromy]
Take \(\mathcal X\) to be spaces, \(U=BG\) for a nontrivial discrete group \(G\), and \(I=J=U\) as objects over \(U\). Use \(B=U\to J\) as the uninformative answer family, and \(A=EG\to BG\) as the result family. Every product of the uninformative family is terminal over its request object. A reduction would thus supply a section of \(EG\to BG\). Such a section is impossible by \(\pi_1\), since \(EG\) is contractible. After pullback along \(*\to BG\), the result family has the nonempty discrete fiber \(G\), so a reduction exists there. Its descent would require a choice fixed by the monodromy, which acts freely on that fiber.
\end{example}
\section{A split and the information it preserves}
Let \(\alpha\) be admissible. Write \(\leq_\alpha\) for strong \(\alpha\)-reducibility in the bounded-support sense. In particular one can use an oracle to certify full positive and negative answers on an \(\alpha\)-finite support. A set \(D\subseteq\alpha\) is regular when \(D\cap\eta\in L_\alpha\) for every \(\eta<\alpha\). For regular \(D\), the complete answer table on an \(\alpha\)-finite request exists in \(L_\alpha\) and can be sought via the two signs of the support. Use \(B_0\oplus B_1\) for the oracle whose two tagged columns are \(B_0,B_1\).
\begin{lemma}[The degree of an enumerated partition]
\label{deg:split}
If \(C\) is regular and \(\alpha\)-recursively enumerable, and \(C=B_0\sqcup B_1\) with both parts \(\alpha\)-recursively enumerable, then both parts are regular and \(C\equiv_\alpha B_0\oplus B_1\).
\end{lemma}
\begin{proof}
Fix an \(\alpha\)-finite set of requests \(D\). Regularity makes \(C\cap D\) a set in \(L_\alpha\). Each of its elements appears in the enumeration of exactly one part. Apply \(\Sigma_1\) Collection in the ground structure to certificates of those appearances. Once both enumerations are run beyond the resulting bound, they give the correct partition on \(D\). This proves regularity of the parts.
To compute the split from \(C\), acquire its answer table on the projections of the requests. Find one stage of the two ground enumerations at which all the positive entries have been assigned their tags. Such a stage exists by the preceding argument. All other entries are negative in both parts. The answer on \(D\) thus has a single bounded support in \(C\) and a ground certificate for its labeling. For the reverse reduction, obtain complete support tables from the two columns and take their union on the positive side. The negative answer requires absence from both columns. This is again a computation on the entire support, so the equivalence is strong.
\end{proof}
\begin{figure}[htbp]
\centering
\begin{tikzpicture}[>=Latex,node distance=1.35cm and 1.25cm,font=\small,
box/.style={draw,rounded corners=2pt,inner xsep=8pt,inner ysep=5pt}]
\node[box] (c) {oracle \(C\)};
\node[box,right=of c] (a) {positive table};
\node[box,right=of a] (s) {assigned tags};
\node[box,below=of s] (b) {oracle \(B_0\oplus B_1\)};
\draw[->] (c)--(a);
\draw[->] (a)--(s);
\draw[->] (s)--(b);
\draw[->] (b) -| node[pos=.27,below]{forget the tags} (c);
\end{tikzpicture}
\caption{Forgetting tags gives the union. Computing the tags requires reaching a stage that accounts for every positive entry of the requested table.}
\label{deg:labels}
\end{figure}
Shore's splitting theorem has further content. For a nonrecursive regular \(\alpha\)-recursively enumerable \(C\), it chooses the partition so that \(C\not\leq_\alpha B_i\) for \(i=0,1\) \cite[IX.1]{Sacks}\cite{ShoreSplitting}. The resulting degrees are incomparable. If one part were below the other, their join would have that other degree, contrary to the strict inequality. It is the priority proof that supplies both strict inequalities. The bounded table argument works for any enumerated partition under its hypotheses.
Shore's density theorem begins instead with \(D<_\alpha C\) among the \(\alpha\)-recursively enumerable sets and produces an \(\alpha\)-recursively enumerable \(B\) strictly between them \cite[IX.5]{Sacks}\cite{ShoreDensity}. The lower oracle must be encoded into \(B\), and successful searches relative to it have to be distinguished from provisional searches against a stage approximation. Splitting an upper oracle without these relative conditions does not establish density. Over \(E\)-closed levels the need for an explicit hypothesis is even more apparent. Sacks requires the computation trees of a reduction to belong to the ground structure. Direct composition is available when the target oracle preserves that closure, and transitivity on the enumerably presented oracles over an \(E\)-closed \(L_\kappa\) requires a separate argument \cite[XIII.1]{Sacks}.
\section{Bounded records over weaker levels}
At a limit level \(L_\beta\), the basic operations of pairing, union and bounded separation are available even when admissible collection fails. A \(\Sigma_1(L_\beta)\) description of each certificate separately does not ensure that an entire supported computation can be transcribed there. At \(L_{\omega+\omega}\), for example, each finite successor chain starting at \(\omega\) is a set. The function sending \(n\in\omega\) to the last ordinal in the chain of length \(n+1\) has a \(\Sigma_1\) graph with parameter \(\omega\). Its range is cofinal in \(\omega+\omega\). A single collecting set in the level cannot contain that range. This isolates the failure regardless of how a map of the corresponding spaces of certificates is presented.
The weak admissibility condition of \(\beta\)-recursion compares the first projectum to the first definable cofinality. In the convention of \cite[IX.6]{Sacks}, the cofinality must be at least the projectum. Bounds on proper initial segments can then substitute for particular instances of collection. At the point where a composed reduction needs all its subsidiary trees, a suitable sufficient condition is a ground certificate that all required data have a bounded joint record, together with a ground operation assembling the record. Such hypotheses should be checked for the construction under discussion. Once they hold, the composite is computed by that bounded record and can use the categorical substitution of Theorem~\ref{deg:substitute}. The theorem itself does not turn a definable class of ground certificates into a set of that ground structure.
\section[Exercises]{Exercises\enspace{\normalfont\normalsize\hyperref[solutions:IX]{[Worked solutions]}}}
\begin{exercise}
\label{ex:IX.1}
Give two consecutive reductions on finite bit strings, each using at most two nonadaptive oracle queries per output bit, whose exhibited composition requires four. Show that a function realized by this example cannot be computed with only two queries.
\end{exercise}
\begin{exercise}
\label{ex:IX.2}
For three spans as in Theorem~\ref{deg:substitute}, write the common support as an iterated pullback and compare the two evaluators using the counits. Specify the maps over which the dependent products are taken.
\end{exercise}
\begin{exercise}
\label{ex:IX.3}
Generalize the two-query symmetry example to \(n\) requests. Determine its loop group when all queries are distinct labels and when each label occurs with a specified positive multiplicity.
\end{exercise}
\begin{exercise}
\label{ex:IX.4}
Replace the universal torsor example by a finite \(G\)-set \(T\to *\) regarded as a family over \(BG\). Characterize reductions using the trivial answer family as oracle in terms of the fixed points of \(T\), and relate this to descent over the Čech nerve of \(*\to BG\).
\end{exercise}
\begin{exercise}
\label{ex:IX.5}
For an enumerably presented \(C\) and an enumerated disjoint partition, specify the local hypothesis on a single \(\alpha\)-finite support used in the proof of Lemma~\ref{deg:split}. Determine which direction of the equivalence can be evaluated from already supplied complete tables.
\end{exercise}
\begin{exercise}
\label{ex:IX.6}
Build a transitive, rudimentarily closed limit level other than \(L_{\omega+\omega}\) with a bounded domain supporting a definable cofinal sequence in its height. Describe the resulting obstruction to a supported composite with that domain.
\end{exercise}
Original LaTeX source
Higher Categorical Recursion Theory
End of manuscript · Back to top ↑