Independent scholarship · Open accessThe monthly digest

Original LaTeX source

Higher Categorical Recursion Theory

\chapter{Jump hierarchies and oracle families}
\label{hyp:chapter}

\section{Construction on an ordinal notation}

\index{Turing jump}\index{hyperarithmetic hierarchy}Let \(X\subseteq\omega\) be an oracle. The Turing jump of \(X\) is
\(X'=\{e:\varphi_e^X(e)\downarrow\}\), for a fixed effective numbering
of the oracle programs. If \(X\leq_T Y\), an oracle program for \(X\)
from \(Y\) can be substituted into every query in a computation
relative to \(X\). Thus \(X'\leq_T Y'\). Also \(X\leq_T X'\) by asking
whether a program halts after a positive answer to one prescribed
query. If \(X'\leq_T X\), a program with oracle \(X\) would halt on its
own index exactly when that index does not belong to \(X'\), a
contradiction. The jump is monotone on Turing degrees, and the jump
of a degree is strictly above that degree.

\index{recursive ordinal}\index{ordinal notation}A recursive ordinal is the order type of a recursive well-order on a
recursive subset of \(\omega\). The recursive ordinals form an initial
segment with supremum \(\omega_1^{\mathrm{CK}}\). The notations
\(\mathcal O\) give presentations of these ordinals with instructions
for effective transfinite recursion \cite[Ch.~I]{Sacks}. Use the
convention in which \(1\) denotes zero, \(2^b\) the successor of
\(|b|\), and \(3\cdot5^e\) the limit of an effectively given sequence
of notations \(b_n\) increasing in the notation order. A valid limit
code includes a program computing those notations. It does not include
an algorithm recognizing all valid codes.

For \(a\in\mathcal O\) and initial oracle \(X\), set
\[
 H^X_1=X,\qquad H^X_{2^b}=(H^X_b)',\qquad
 H^X_{3\cdot5^e}=\bigoplus_{n\in\omega}H^X_{b_n}.
\]
The join uses one fixed recursive pairing of integers, so a bit of a
limit oracle is specified by its column and its row. The notation can
also be relative to \(X\). In that case \(\mathcal O^X\) uses
\(X\)-recursive sequences, and the possible order types are those
below the first non-\(X\)-recursive ordinal \(\omega_1^X\).

\begin{figure}[!ht]
\centering
\begin{tikzpicture}[
box/.style={draw,rounded corners=2pt,inner sep=5pt,font=\small},
edge/.style={-{Latex[length=1.7mm]},thin},
every node/.style={font=\small}]
\node[box] (s) at (-3.3,0) {\(H_b^X\)};
\node[box] (j) at (-3.3,-1.4) {\(H_{2^b}^X\)};
\draw[edge] (s) -- node[left] {jump} (j);
\node[box] (b0) at (-1.25,0) {\(H_{b_0}^X\)};
\node[box] (b1) at (.45,0) {\(H_{b_1}^X\)};
\node (d) at (2.1,0) {\(\cdots\)};
\node[box] (bn) at (3.55,0) {\(H_{b_n}^X\)};
\node[box] (l) at (.95,-1.4) {\(H_{3\cdot5^e}^X=\bigoplus_n H_{b_n}^X\)};
\foreach \source in {b0,b1,bn}{\draw[edge] (\source) -- (l);}
\node[anchor=west] at (-1.9,-2.15) {A projection reads one indicated column.};
\end{tikzpicture}
\caption{Two constructors in the jump hierarchy. The successor
asks for halting information. The limit preserves all columns and
uses the displayed numerical access procedure.}
\label{hyp:constructors}
\end{figure}

For a fixed valid notation, one real can code the columns at its
syntactically reachable subnotations. All equations on this real are
arithmetical. At a successor the jump condition uses a finite
positive computation for each asserted halting fact and quantifies
over stages for a negative one. At a limit the equation is a
reindexing of bits. Existence and uniqueness follow by induction on
rank among the reachable subnotations. Consequently both bit values
of the last column have a \(\Sigma^1_1(X)\) definition. The reachable
subnotations and equations can be specified arithmetically in the
original notation and \(X\), even when their rank cannot be read
directly from the notation.

The converse is the Kleene--Spector characterization. Every
\(\Delta^1_1(X)\) subset of \(\omega\) is recursive in
\(H_a^X\) for some \(a\in\mathcal O^X\)
\cite[Ch.~II]{Sacks}\cite{Spector}. In the separation argument of
Chapter~\ref{tree:chapter}, the common bound is a recursive ordinal
relative to the base oracle. Translating the pruning equations into
a jump computation along a notation above that bound yields the
effective decision procedure. Another theorem of Spector compares
\(H^X_a\) and \(H^X_b\) when the notation ordinals are comparable. In
particular \(|a|=|b|\) gives equality of Turing degrees. The separate
notations still specify separate columns and separate programs for
answering queries. Equality of degree alone does not identify these
presentations. The hyperjump, represented by \(\mathcal O^X\) or the
well-foundedness test for recursive-in-\(X\) trees, gives a complete
\(\Pi^1_1(X)\) predicate. It tests a proposed valid code by a stronger
oracle operation than any single jump in the displayed hierarchy.

\section{The relative halting predicate}

\index{halting predicate}Let \(\mathcal X\) be an \(\infty\)-topos, with natural numbers
\(\mathbb N=\coprod_{n\geq0}1\) and \(2=1\amalg 1\). Write
\(\Omega\) for its subobject classifier. An oracle over \(U\) is an
arrow \(Q:U\times\mathbb N\to2\). A bounded oracle computation is
specified using the ordinary instruction table, finite
configurations, and evaluations of \(Q\). The resulting subobject
\[
 C_Q\ \lhook\joinrel\longrightarrow\
 U\times\mathbb N_e\times\mathbb N_t
\]
says that program \(e\) halts on input \(e\) by stage \(t\).
Use \(J_Q\hookrightarrow U\times\mathbb N_e\) for the image of \(C_Q\)
under projection. It is classified by an arrow to \(\Omega\).
Currying also describes this construction as a map
\(2^{\mathbb N}\to\Omega^{\mathbb N}\) of oracle and predicate
objects. At a fixed machine input one can retain \(C_Q\) as the
object of witness times over the halting locus.

\begin{proposition}[Base change and decidability]
\label{hyp:haltingbc}
For \(f:V\to U\), reindexing \(C_Q\) and \(J_Q\) gives \(C_{f^*Q}\)
and \(J_{f^*Q}\), respectively. The halting predicate gives an oracle
over \(U\) precisely when its inclusion is complemented in
\(U\times\mathbb N\).
\end{proposition}

\begin{proof}
For each numerical \(e,t\), bounded simulation is a finite
composition of primitive recursive configuration maps and oracle
queries. Reindexing commutes with these operations and with
assembling the cases indexed by the two copies of \(\mathbb N\).
This gives the formula for the witness object. Images commute with
pullback, giving the formula for \(J_Q\). An arrow to \(2\) gives the
decomposition into its two disjoint pullbacks. Conversely a
decomposition into a subobject and its complement gives the map to
\(2\) which is constant on the two summands. These two operations
are inverse.
\end{proof}

\begin{example}[An oracle whose jump cannot be read continuously]
\label{hyp:cantor}
In sheaves of spaces on Cantor space \(K=2^\omega\), let \(Q\) be the
generic binary real. Its \(n\)-th bit is the continuous function
\(x\mapsto x(n)\) to \(2\). A program that queries the bits in order
and stops at the first \(1\) has halting locus
\[
 U_e=\{x\in K:\exists n\,x(n)=1\}=K\setminus\{0^\omega\}.
\]
A subobject of the terminal sheaf is an open, and complemented
subobjects correspond to clopen sets. Each basic neighbourhood of
\(0^\omega\) meets \(U_e\). Consequently \(U_e\) has no open complement
and the jump of \(Q\) cannot be a binary oracle. Every bounded stage
has a clopen halting locus, and their union is precisely \(U_e\).
\end{example}

\begin{figure}[!ht]
\centering
\begin{tikzpicture}[
box/.style={draw,rounded corners=2pt,inner sep=4pt,font=\small},
edge/.style={-{Latex[length=1.5mm]},thin},
every node/.style={font=\small}]
\node[box] (r) at (-.3,0) {\([\langle\rangle]\)};
\node[box] (z1) at (-.3,-.75) {\([0]\)};
\node[box] (z2) at (-.3,-1.5) {\([00]\)};
\node[box] (z3) at (-.3,-2.25) {\([000]\)};
\node (dots) at (-.3,-3.32) {\(\vdots\)};
\node[box,fill=soft] (one) at (1.6,-.75) {\([1]\)};
\node[box,fill=soft] (two) at (1.6,-1.5) {\([01]\)};
\node[box,fill=soft] (three) at (1.6,-2.25) {\([001]\)};
\foreach \p/\q in {r/z1,r/one,z1/z2,z1/two,z2/z3,z2/three}
{\draw[edge] (\p) -- (\q);}
\node[anchor=west,align=left] at (2.3,-1.45) {First \(1\) found\\ on each shaded cylinder};
\draw[edge] (z3.south) -- (-.3,-2.87);
\node[anchor=east] at (-.85,-3.27) {Branch \(0^\omega\)};
\end{tikzpicture}
\caption{Halting is the union of the cylinders branching off the
all-zero ray. The ray itself is a point of the closure of that open
union.}
\label{hyp:boundary}
\end{figure}

The example shows the difference between closure under truth-valued
quantification and closure of a class of total oracles under jumps.
At each classical point the oracle and its jump are binary
sequences. With the variable base, the same semantic construction
gives a predicate that may have no coherent binary decision
function. It is already possible for this obstruction to occur in
the subobjects of a \(1\)-topos.

\section{A hierarchy over locally constant inputs}

\index{locally constant oracle}There is a class of observable inputs on which the entire hierarchy
can be transported. Denote by \(\Delta E=\coprod_{e\in E}1\) the
constant object associated to a set \(E\). Take a fixed ordinary
notation \(a\in\mathcal O\). A locally constant input real here is an
arrow \(x:U\to\Delta(2^\omega)\), using the set \(2^\omega\) of
classical reals on the right. Evaluation gives an internal oracle
\[
 U\times\mathbb N \longrightarrow
 \Delta(2^\omega)\times\Delta\omega
 \longrightarrow 2.
\]
Such a presentation locally specifies the real as a unit. The
internal oracle in Example~\ref{hyp:cantor} has each bit locally
constant, but the real as a unit has no such presentation.

\begin{theorem}[Locally constant jump families]
\label{hyp:transport}
For each fixed valid notation \(a\) and each such input \(x\), the
classical columns reachable from \(a\) determine internal oracles
over \(U\). These satisfy the successor equations with the halting
predicate of Proposition~\ref{hyp:haltingbc} and the limit equations
with the designated column join. They are uniquely determined by
these equations and the given base oracle. The hierarchy so
constructed commutes with pullback in \(U\).
\end{theorem}

\begin{proof}
Each external rule \(X\mapsto H_b^X\) on the set of reals gives an
arrow of constant objects. Compose it with \(x\) and evaluate every
column to get its oracle. Extensivity and universality of coproducts
give a cover of \(U\) by the inverse images of the summands indexed
by the real \(X\). Over each such piece the initial real is
specified. The bounded simulations for each \(e,t\) are then either
true or false everywhere according to the corresponding classical
simulation. Formation of the image over \(t\) gives exactly the
classical jump, interpreted on that piece. At a limit, each bit is
the value read off from the indicated preceding column. These local
equations imply the global equations by descent. At a successor the
characteristic map of a complemented subobject is determined by
its support and at a limit the individual column equations
determine all bits. Induction on the fixed notation gives
uniqueness. Restriction along a base map preserves the stipulated
pieces and the equations, which proves the base-change assertion.
\end{proof}

For a varying notation one can use a map to a constant object of
valid pairs \((X,a)\) with \(a\in\mathcal O^X\). This gives a
presentation and a classical validity hypothesis in each summand.
It does not give an internal decision procedure for being such a
pair. In particular the theorem does not assert that
\(\Delta(2^\omega)\simeq2^{\mathbb N}\). Infinite products need not
be preserved by the constant-object functor.

\begin{example}[Transport of ports]
\label{hyp:ports}
Let \(\pi:I\to BG\) be the local system of ports associated to a
finite \(G\)-set \(F\) for a discrete group \(G\). Assign a
classical oracle to each orbit, then view this as a locally
constant family over \(I\). Apply
Theorem~\ref{hyp:transport} there. For a test of a bit in one of the
resulting columns, take the subobject \(I_e\subseteq I\) on which the
test succeeds. The dependent sum along \(\pi\) retains the successful
ports over \(BG\), and its relative \((-1)\)-truncation says that at
least one port succeeds. An action of \(G\) which exchanges two
successful indices preserves this proposition. It can still obstruct a
global choice of a successful index. Base change controls the
family of answers and the fibers of the success object
even where there is no global enumeration respecting transport.
\end{example}

The classical recursion equations are arithmetical in the hierarchy code and its ordinal presentation. Iteration over arbitrary internal oracles requires a query operation whose results admit the same kinds of successor and limit rules.

\section[Exercises]{Exercises\enspace{\normalfont\normalsize\hyperref[solutions:III]{[Worked solutions]}}}

\begin{exercise}
\label{ex:III.1}
Construct a many-one reduction \(X'\leq_m Y'\) from an index
witnessing \(X\leq_T Y\), uniformly in that index. Analyze the role of
diagonal input in the compiler.
\end{exercise}

\begin{exercise}
\label{ex:III.2}
Give two limit presentations of \(\omega\), one using all positive
finite ordinals and one using only the positive even ordinals.
Construct a Turing reduction of either of the limit joins to the other
using the reduction on the finite stages.
\end{exercise}

\begin{exercise}
\label{ex:III.3}
Replace the search for a first \(1\) in Example~\ref{hyp:cantor} by a
search for two successive \(1\)'s. Describe the bounded halting
opens, their union, and the interior of its complement.
\end{exercise}

\begin{exercise}
\label{ex:III.4}
Pull the oracle of Example~\ref{hyp:cantor} back along the point
\(0^\omega\) and along the open of nonzero sequences. Compare the
decidability of the specified jump bit on each restricted base.
\end{exercise}

\begin{exercise}
\label{ex:III.5}
Take \(G=\mathbb Z\) and make \(F\) the disjoint union of a transitive
two-element orbit and a singleton. Give an orbitwise assignment
of real oracles and a bit test for which \(I_e\to BG\) is
surjective and has no section. Give a second test for which there is
a section.
\end{exercise}

\begin{exercise}
\label{ex:III.6}
Use Proposition~\ref{hyp:haltingbc} to determine which open of Cantor
space classifies simultaneous halting of a specified finite collection
of searches. Compare the image of the fiber product of their
witness-time objects with the intersection of the separate images.
\end{exercise}

\begin{exercise}
\label{ex:III.7}
An \(\infty\)-topos admits internal families of reals whose coordinates
are decidable. Formulate a sufficient condition on a chosen subobject
of \(2^{\mathbb N}\) for the successor and limit steps of a fixed
notation to stay in that subobject. Explain the difference between
the data needed at the two steps.
\end{exercise}

End of manuscript · Back to top ↑