\chapter{Effective oracles with transport}
\label{ch:effective-transport}
\section{A jump in a family of symmetries}
The degree of an oracle compares which answers can be computed when that oracle is supplied. For a family of oracles there is also a question about the program used to compare them. It may compute the same degree in every fiber and fail to transport its certificates. This chapter gives a class of effective presentations in which both questions can be asked explicitly.
Let \(G\) be a discrete group with an effective presentation on a recursive set of natural-number codes, with recursive multiplication and inverse. Assume \(G\) acts on the query alphabet \(\omega\) by a uniformly recursive family of permutations. Its action on oracles \(A\subseteq\omega\) is direct image. Let \(K(A)=\{e:\Phi_e^A(e)\downarrow\}\), using a fixed effective programming system with parameters. For each \(g\in G\) use the same machine numbering on \(g^{-1}A\). Put
\[
J(A)=\{(g,e)\in G\times\omega:e\in K(g^{-1}A)\}.
\]
Give \(G\times\omega\) the action \(h(g,e)=(hg,e)\). The group coordinate records the presentation of the query alphabet in which the machine is run. The value at the identity coordinate is \(K(A)\).
\begin{theorem}[Equivariant lift of the jump]
\label{thm:equiv-jump}
The assignment \(J\) is equivariant and \(J(A)\equiv_T K(A)\) uniformly in the given recursive group presentation. The successful finite execution records of \(J\) also transport equivariantly. If an equivariant transformation \(F\) of a \(G\)-invariant class of oracles is computed by one oracle program, the induced reduction of \(J(F(A))\) to \(J(A)\) can be given by a recursive map commuting with the action on \(G\times\omega\).
\end{theorem}
\begin{proof}
For \(h\in G\), the membership test for \((hg,e)\) in \(J(hA)\) runs the machine with oracle
\[
(hg)^{-1}(hA)=g^{-1}A .
\]
It runs the very same computation with the same answers to its oracle questions. This proves equivariance of membership and of finite successful records. The identity coordinate reduces \(K(A)\) to \(J(A)\). In the other direction, a query to \(g^{-1}A\) at \(n\) is the query to \(A\) at \(gn\). Substitute this call in a simulation of \(e\) and use the parameter theorem to give the simulator an index uniformly from \((g,e)\). The ambient jump \(K(A)\) tests its convergence. This gives a many-one reduction, after the standard encoding of the product query alphabet.
For the last assertion let \(\Psi^A\) compute the characteristic function of \(F(A)\). There is a recursive transformation \(e\mapsto r(e)\) that replaces every query in the machine \(e\) by a call to \(\Psi\) with the new oracle. Thus \(e\in K(F(B))\) iff \(r(e)\in K(B)\), for every \(B\) in the domain of \(F\). Equivariance gives \(F(g^{-1}A)=g^{-1}F(A)\). Apply the same simulator with \(B=g^{-1}A\). The map \((g,e)\mapsto(g,r(e))\) gives the claimed reduction and commutes with each left translation on the tag.
\end{proof}
The construction is external and uses a recursive presentation of \(G\). Nevertheless the resulting families are genuinely parametrized by groupoids. An equivariant map on sets induces a map between their action groupoids, preserving the labels of the transport arrows. Applying the nerve and regarding those groupoids as spaces retains every stabilizer and the paths it induces. The map from the action groupoid of successful records to the action groupoid of program-input pairs has image the associated family of convergence predicates. Applying Theorem~\ref{thm:equiv-jump} at the level of those predicates gives the ordinary jump at every untwisted base point. The construction does not require computably quotienting oracles by their orbits.
\begin{figure}[htbp]
\centering
\begin{tikzcd}[column sep=2.7em,row sep=1.9em]
(A,g,e) \arrow[r,"h"]\arrow[d,"\text{oracle and machine}"']&
(hA,hg,e)\arrow[d,"\text{oracle and machine}"]\\
(g^{-1}A,e)\arrow[r,equal] & ((hg)^{-1}hA,e)
\end{tikzcd}
\caption{The transported tag compensates for the change of oracle. The same finite trace certifies both endpoints of the top arrow.}
\label{fig:oracles-jump}
\end{figure}
For example, let \(C_2\) exchange \(2n\) and \(2n+1\) for all \(n\). A program testing the very first bit of the oracle need not have the same convergence on \(A\) and on the translated \(A\). If one translates its group tag together with the oracle, the one-bit record is preserved. For an oracle fixed by the exchange the records over the two tags lie in the same orbit. The underlying numerical jump still has its usual degree. This is a change of presentation allowing transport, rather than an increase in computational power.
\section{Selection in an action groupoid}
Let \(X\) be a \(G\)-set of inputs and let \(Y\) be a \(G\)-set of proposed witnesses. Let \(R\subseteq X\times Y\) be invariant under simultaneous action. Assume that \(R_x=\{y:(x,y)\in R\}\) is nonempty for every \(x\). A selector compatible with transport is an equivariant section of \(R\to X\). Write \(G_x=\{g:gx=x\}\).
\begin{theorem}[Selection and stabilizers]
\label{thm:stabilizer-select}
With choice in the metatheory, an equivariant section exists iff \(R_x^{G_x}\) is nonempty for one representative \(x\) of every orbit. Suppose moreover that the actions and their recursive domains are uniformly computable, \(R\) is recursively enumerable, and the presentation effectively gives the following data on an input \(x\).
\begin{enumerate}
\item A representative \(r(x)\) depending only on the orbit of \(x\).
\item A transporter \(g(x)\) with \(g(x)r(x)=x\).
\item A finite generating list for \(G_{r(x)}\) depending only on the representative.
\end{enumerate}
Then, under the fixed point condition, an equivariant section is recursive.
\end{theorem}
\begin{proof}
At a representative \(r\), an equivariant section must be fixed by \(G_r\). Conversely choose \(y_r\in R_r^{G_r}\) for each representative and prescribe the section at \(g r\) to be \(g y_r\). If \(g r=g' r\), then \(g'^{-1}g\) fixes \(r\) and hence fixes \(y_r\). Thus the prescription is well defined. It is equivariant and respects \(R\) by its invariance.
For the effective version, enumerate \(R_r\). A candidate \(y\) is fixed by \(G_r\) iff it is fixed by every member of the finite generating list. Equality of coded witnesses and the action are recursive, so apply this finite test to the enumerated candidates. The search halts by the fixed point hypothesis. Use the first accepted \(y_r\) and apply the specified transporter. To ensure the same choice throughout an orbit, run the enumerator with the same representative and list. The proof of well-definedness also proves equivariance of this recursive implementation.
\end{proof}
\begin{figure}[htbp]
\centering
\begin{tikzpicture}[node distance=11mm and 21mm]
\node[booksite] (r) {\(r\)};
\node[booksite,right=of r] (x) {\(x\)};
\node[bookbox,below=of r] (yr) {\(y_r\in R_r^{G_r}\)};
\node[bookbox,below=of x] (yx) {\(g y_r\in R_x\)};
\draw[bookarr] (r) to[bend left=16] node[above,booknote] {\(g\)} (x);
\draw[bookarr] (r) to[bend right=16] node[below,booknote] {\(gk\)} (x);
\draw[bookarr,draw=accent] (yr) -- (yx);
\draw[bookarr] (yr) -- (r);
\draw[bookarr] (yx) -- (x);
\end{tikzpicture}
\caption{The transporters \(g\) and \(gk\) give the same transported witness when \(k\in G_r\) fixes \(y_r\).}
\label{fig:oracles-select}
\end{figure}
This calculation is the discrete case of selection over a space with transport. Indeed \(R//G\to X//G\) is the map of action groupoids, with discrete fibers \(R_x\) over points of \(X//G\). A section over a connected component \(BG_r\) is equivalent to a homotopy fixed point of \(R_r\). Since \(R_r\) is discrete, this is an ordinary fixed point. For instance take \(X=\{*\}\), \(G=C_2\), and \(Y=C_2\) with its regular action. Both witnesses verify the same assertion on the sole input, and an ordinary recursive selector is available. The equivariant selector fails because neither witness is fixed. Changing the witness space to a connected space does not remove all obstructions, as \(BC_4\to BC_2\) in Chapter~\ref{ch:compute-descent} demonstrates.
If the parameterized family supplies recursive finite generators only after choosing the representatives, that choice is part of the computational specification. A statement asserting such generators locally, or a classical axiom of choice supplying them, does not give the effective routine in Theorem~\ref{thm:stabilizer-select}. This is one of the points at which external computability conditions are needed in the higher treatment.
\section{Ranks and relative closure}
The transport calculation respects any rank defined by the call structure of well-founded records. If the transport arrow is an isomorphism of such labeled trees when one changes parameters, an induction from the leaves shows that the rank at each corresponding node is unchanged. At a leaf both ranks are zero. At any other node the correspondence of children identifies the ordinals whose strict supremum gives the rank. Hence the sets of ranks agree on ordinary orbits. This use of transport is entirely extensional. It does not prove that a bound on the ranks of one record in each orbit can be found effectively from a code for the family. The distinction persists even if all ranks have been specified internally as ordinal-valued annotations.
For set recursion the classical test on relative degree comparisons already requires care about which records stay in the ground structure. Sacks's theorem on Post's problem for the \(E\)-recursively enumerable degrees uses \(E\)-closure, ordinal indexing, and, on inadmissible levels of \(L\), witnesses to divergence \cite[Ch.~XIII]{Sacks}. The split and density constructions use bounds on proper priority blocks \cite{SlamanDensity,SlamanPriority}. Equivariant refinements of such comparisons would in addition have to preserve the support of the selected successful or divergent records under transport. A construction on extensional degree classes can erase that requirement, as in the passage from supported reductions to degrees in Chapter~\ref{deg:chapter}. The finite-group examples of this chapter show its independence from pointwise enumerability and from the strength of the underlying numerical oracle.
There are accordingly several precise specialization tests for a proposed higher recursion theory. Restricting a record presentation to discrete inputs and outputs should recover the intended partial function or relation. Restricting to its recursive codes should recover the uniform tests and ordinal bounds of the classical theory. Transporting across a cover should identify compatible records, and projecting to behavior should recover the existential predicates. The first two tests can succeed on fibers in examples where the third gives a genuine obstruction to selection. This supplies a reason to retain the records themselves in the higher construction.\index{jump!equivariant lift}\index{selection!stabilizers}\index{record!rank}
\section[Exercises]{Exercises\enspace{\normalfont\normalsize\hyperref[solutions:XIII]{[Worked solutions]}}}
\begin{exercise}
\label{ex:XIII.1}
For the \(C_2\)-action exchanging even and odd queries, compute the two coordinates of \(J(A)\) for programs that halt exactly when the answer to their sole oracle query is affirmative.
\end{exercise}
\begin{exercise}
\label{ex:XIII.2}
Show that the identity-coordinate many-one reduction in Theorem~\ref{thm:equiv-jump} need not be equivariant if the target of the reduction uses the translated tags and the source uses a trivial action. Compare the two actions without changing the ordinary equivalence of degrees.
\end{exercise}
\begin{exercise}
\label{ex:XIII.3}
A partial computable oracle transformation is given on a \(G\)-invariant domain on which every output is a total characteristic function. State conditions under which the simulation part of Theorem~\ref{thm:equiv-jump} still applies there. Verify the induced reduction for a composition of two such transformations.
\end{exercise}
\begin{exercise}
\label{ex:XIII.4}
Let \(G=S_3\) act on the vertices and on the edges of a triangle. Take incidence as a relation between vertices and edges. Determine the existence of an equivariant selector in each direction. Repeat with edges disjoint from a given vertex as witnesses.
\end{exercise}
\begin{exercise}
\label{ex:XIII.5}
Present two \(G\)-invariant families of recursive trees with the same pointwise nonemptiness of branch sets. Arrange that one has an equivariant assignment of branches and that the other fails the fixed point test of Theorem~\ref{thm:stabilizer-select}.
\end{exercise}
\begin{exercise}
\label{ex:XIII.6}
Construct a group action on a family of countably branching well-founded trees such that transport is faithful on some fiber, but all trees in the family have the same rank. Explain which data are visible to the classical rank predicate.
\end{exercise}
Original LaTeX source
Higher Categorical Recursion Theory
End of manuscript · Back to top ↑