Independent scholarship · Open accessThe monthly digest

Original LaTeX source

Higher Categorical Recursion Theory

\chapter{Ramification and inductive definitions}
\label{ind:chapter}

\section{Ranks of names}

Sacks uses ordinal ranks to control which names a quantifier can inspect. Their role is especially clear in the ramified analytic hierarchy \cite[III.4]{Sacks}. For a fixed real \(x\), one may start with the number structure and the predicate \(x\), then admit real names defined by formulas using names and set quantifiers of lower rank. A ranked existential quantifier ranges over the names available up to its specified bound. Two names may define the same real. The verification of a bounded truth assertion proceeds by induction on a syntactic rank that decreases when a ranked quantifier is instantiated by an admissible name. This induction leaves open the problem of finding one rank bound for all the instances in a family of assertions.

Here is the semantic form of a ranked existential test. Let \(I\) be an object of inputs in an \(\infty\)-topos \(\mathcal X\). Let \(N\to I\) be a family of names, let \(N_\alpha\hookrightarrow N\) be its increasing filtration by bounds, and let \(W\to N\) be the family of witnesses that the named object passes the test. Put
\[
 W_\alpha=N_\alpha\times_N W,\qquad
 R_\alpha=\operatorname{im}_{I}(W_\alpha\longrightarrow I).
\]
A point of \(W_\alpha\) carries a name and a witness. A point of the subobject \(R_\alpha\) asserts local existence of both. In the category of spaces, restricting to discrete names and proof-irrelevant tests recovers the assertion that some bounded name passes the test.

\begin{figure}[htbp]
\centering
\begin{tikzcd}[column sep=3.2em,row sep=2.5em]
W_\alpha \arrow[r,hook] \arrow[d] \arrow[dr,phantom,"\lrcorner",very near start] &
W \arrow[d] \\
N_\alpha \arrow[r,hook] \arrow[d] & N \arrow[d] \\
I \arrow[r,equal] & I
\end{tikzcd}
\caption{The witness type is restricted to bounded names before its image in the input object is taken.}
\label{ind:fig-rank}
\end{figure}

\begin{proposition}
\label{ind:filtered-image}
Suppose \(N_\lambda=\bigcup_{\alpha<\lambda}N_\alpha\) at a limit stage. Then
\[
 R_\lambda=\bigvee_{\alpha<\lambda}R_\alpha .
\]
The diagram in Figure~\ref{ind:fig-rank}, this equality, and all the individual image tests commute with change of the input base.
\end{proposition}
\begin{proof}
Pullback along \(W\to N\) preserves colimits of subobject diagrams, giving \(W_\lambda\simeq\operatorname{colim}_{\alpha<\lambda} W_\alpha\). The image functor from \(\mathcal X_{/I}\) to \(\operatorname{Sub}(I)\) is a left adjoint. Applying it carries this colimit to the displayed join. For a new input base, pullback preserves the fiber products and the image factorization, since effective epimorphisms and monomorphisms are stable under pullback. It also preserves the join.
\end{proof}

Equality at a limit identifies which inputs pass some bounded test. A uniform effective bound carries more information. Consider a total oracle routine on a fixed input that asks only finitely many membership questions. If a chain of sets increases to its limit, the answers to the finitely many questions on the actual computation path are correct from some stage onward. Determinism then gives exactly the same output. For functions of a numerical input this is a separate argument at each number. The additional bounding principle in the effective theory controls these individual stages by a recursive ordinal when the evidence is given in the required effective form. An arbitrary external list of recursive ordinal notations can have supremum equal to the Church--Kleene ordinal. A countable cover of bounded tests does not supply the effective evidence in that case.

\section{Rules with dependent premises}

Fix a diagram
\[
 I\xleftarrow{s} B\xrightarrow{p} A\xrightarrow{t} I
\]
in \(\mathcal X\). An element of \(A_i\), over \(i\in I\), is a rule with conclusion of sort \(i\). For \(a\in A_i\) its premise occurrences form the fiber \(B_a\), and \(s(b)\) is the sort of premise \(b\). These descriptions are made in generalized elements. They include the variation of the rule and of its premises along equivalences in the base. Write
\[
 P(Y)=\Sigma_t\Pi_p s^*Y
\]
for the associated polynomial on \(\mathcal X_{/I}\). We assume this polynomial has an initial algebra \(P(D)\simeq D\), for example by the initial-chain construction for accessible polynomials. Its object \(D\) gives derivations with their choices of rules and constituent derivations. The internal least predicate of derivability is obtained by a second construction. For \(Q\hookrightarrow I\) put
\[
 \Gamma(Q)=\operatorname{im}_I(P(Q)\longrightarrow I).
\]
Then \(\Gamma\) is monotone. Iterate it from the empty subobject, taking joins at limit stages. The stages are increasing by monotonicity, and since \(\operatorname{Sub}(I)\) is a set the iteration stabilizes. Write \(Q_{\mathrm{ind}}\) for the resulting least fixed point. Induction on the stages puts this fixed point below every pre-fixed point.

In sets, \(i\in\Gamma(Q)\) means that some rule for \(i\) has all its premises in \(Q\). The set-theoretic closure ordinal depends on the presentation of the rules. For example, if all premise sets have cardinality less than an infinite regular cardinal \(\kappa\), the chain stabilizes by \(\kappa\). In fact a rule with premises in the union of the first \(\kappa\) stages has those premises in a common earlier stage by regularity. In the recursive setting Spector's result for monotone \(\Pi^1_1\) inductive definitions gives closure by \(\omega_1^{\mathrm{CK}}\) and a lightface \(\Pi^1_1\) definition of the fixed point \cite[III.8]{Sacks}. The cardinal argument concerns the number of premises. Spector's result concerns the definability of the operator, including uniformity in codes.

\begin{theorem}
\label{ind:comparison}
There is a canonical inclusion
\[
 Q_{\mathrm{der}}=\operatorname{im}_I(D\to I)
 \;\leq\; Q_{\mathrm{ind}} .
\]
If \(\Pi_p\) preserves the effective epimorphism
\(s^*D\to s^*Q_{\mathrm{der}}\), this inclusion is an equality. In particular equality holds for a locally finite constant family of premise occurrences over the object \(A\) of rules.
\end{theorem}
\begin{proof}
To give \(Q\hookrightarrow I\) a \(P\)-algebra structure is equivalent to factoring \(P(Q)\to I\) through \(Q\). This is possible precisely when \(\Gamma(Q)\leq Q\). Initiality therefore maps \(D\) over \(I\) to any pre-fixed subobject, in particular \(Q_{\mathrm{ind}}\). Passing to the image gives the inclusion.

Under the stated hypothesis \(P(D)\to P(Q_{\mathrm{der}})\) is an effective epimorphism. Indeed \(\Sigma_t\) composes with \(t\) and leaves the map of total objects unchanged. Its two images over \(I\) agree. The image of \(P(D)\) is \(Q_{\mathrm{der}}\) by the initial-algebra equivalence. The image of \(P(Q_{\mathrm{der}})\) is \(\Gamma(Q_{\mathrm{der}})\). Hence \(Q_{\mathrm{der}}\) is fixed, giving the other inclusion.

For the last assertion, pull back to a cover on which \(p\) is a finite coproduct of copies of the base. There \(\Pi_p\) is a finite product. Finite products of effective epimorphisms in a slice are effective epimorphisms, by stability under pullback and composition. Dependent products commute with this base change, and the effective epimorphism property can be tested on the cover.
\end{proof}

The least predicate is stable under change of a separate parameter object. To see this, treat the signature as a diagram in a slice \(\mathcal X_{/U}\). Pullback along a map \(V\to U\) commutes with the image and dependent-polynomial operations by stability of images and Beck--Chevalley. It commutes with every stage of the predicate chain by induction, using the preservation of joins at limits. Pullback of the stabilized stage is then exactly the stabilized stage for the new base. This stability does not give the extra effective epimorphism in Theorem~\ref{ind:comparison}. The distinction appears even over a real line.

\section{Locally inhabited premises}

\begin{example}[A rule with countably many premises]
\label{ind:countable-failure}
Work in sheaves of spaces on \(\mathbb R\), with its usual topology. For each \(n\geq 1\) take the subterminal sheaves determined by the opens
\[
 U_n=(-1/n,1/n), \qquad V=\mathbb R\setminus\{0\},
 \qquad E_n=U_n\amalg V.
\]
There are countably many premise sorts \(n\) and a conclusion sort \(*\). The nullary rules for sort \(n\) form \(E_n\). The conclusion has one rule with one premise of each sort \(n\). The initial algebra has components \(D_n=E_n\) and \(D_* =\prod_{n\geq 1} E_n\), since every derivation at \(*\) has nullary derivations as children.

Each \(E_n\to 1\) is an effective epimorphism because \(U_n\) and \(V\) cover the line. In the least predicate every premise is therefore true at stage one, and the conclusion is true at stage two. Figure~\ref{ind:intervals} depicts the covers. A section of \(\prod_n E_n\) near \(0\) would restrict to a connected interval \(J\) containing \(0\). For each \(n\) its projection to \(E_n\) makes a locally constant choice of summand on \(J\). This choice is constant. Since \(0\notin V\), it must be the \(U_n\) summand. Thus \(J\subseteq\bigcap_n U_n=\{0\}\), a contradiction. Away from \(0\) every premise can be obtained from \(V\), so the image of \(D_*\) is exactly \(V\). The conclusion has strictly smaller derivation support than its least predicate.
\end{example}

\begin{figure}[htbp]
\centering
\begin{tikzpicture}[x=1cm,y=0.82cm,>=Latex,every node/.style={font=\small}]
\draw[gray!65,->] (-3.6,0) -- (3.6,0);
\draw[thick] (0,-.13) -- (0,.15) node[below=4pt] {\(0\)};
\foreach \k/\l in {1/2.6,2/1.3,3/.87} {
  \draw[very thick,blue!66!black,{Circle[open,length=3pt]}-{Circle[open,length=3pt]}]
     (-\l,\k*.57) -- (\l,\k*.57);
  \node[anchor=west,blue!66!black] at (\l+.12,\k*.57) {\(U_\k\)};
}
\draw[very thick,gray!75!black,<-] (-3.5,-.55) -- (-.19,-.55);
\draw[very thick,gray!75!black,->] (.19,-.55) -- (3.5,-.55);
\draw[gray!75!black,line width=.75pt] (0,-.55) circle[radius=2.7pt];
\node[anchor=north] at (0,-.7) {\(V=\mathbb R\smallsetminus\{0\}\)};
\end{tikzpicture}
\caption{Each row supplies a cover by \(U_n\) and \(V\). Their product provides no common witness on any interval around zero.}
\label{ind:intervals}
\end{figure}

\begin{example}[A coherent obstruction to a global derivation]
Let \(U=B C_2\) in spaces and take the double cover \(E\to U\) associated to the free transitive \(C_2\)-set. In the slice over \(U\) consider one sort, nullary rules parametrized by \(E\), and a unary rule that adds one delay. The associated endofunctor is \(Y\mapsto E\amalg Y\), whose initial algebra is \(E\times\mathbb N\to U\). The algebra follows either from its initial chain or by evaluating one nullary rule followed by a finite number of delays. Its image is all of \(U\). It has no section. A section would give an invariant element of the discrete fiber \(C_2\times\mathbb N\), but the nonidentity loop in \(U\) interchanges the two elements with each fixed delay. In this case all arities are finite and the two predicates in Theorem~\ref{ind:comparison} agree. The obstruction concerns the global choice of a derivation.
\end{example}


\begin{proposition}[The arity test in spaces]
\label{ind:arity-test}
In the category of spaces, fix an arity space \(K\). The dependent product \(\mathcal S_{/K}\to\mathcal S\) preserves all effective epimorphisms if and only if \(K\) is \(0\)-truncated. Consequently, for a map of spaces \(p:B\to A\), preservation of effective epimorphisms by all base changes of \(\Pi_p\) is equivalent to \(0\)-truncation of its homotopy fibers.
\end{proposition}
\begin{proof}
If \(K\) is discrete up to equivalence, the dependent product is a product of spaces indexed by the set \(\pi_0K\). An effective epimorphism is surjective on path components, and a product of such maps is surjective on components by Choice. This uses the identification of the components of a product of spaces with the product of components.

For the converse choose a point in each component and consider the resulting map \(e:\pi_0 K\to K\) from a discrete space. The map \(e\to\operatorname{id}_K\) in the slice is an effective epimorphism. If its dependent product is an effective epimorphism, then the space of sections of \(e\) maps onto the point, so \(e\) has a section. A section would exhibit the identity of each connected component of \(K\) as homotopic to a constant map, since every map from that component to a discrete space is constant up to homotopy. Each component is then contractible. This proves the first assertion. For the second, necessity follows by base change to a point of \(A\), and sufficiency by testing an effective epimorphism on the homotopy fibers over those points.
\end{proof}

The arity test gives a strict inequality in Theorem~\ref{ind:comparison} even in spaces. Take the premise sorts to form the space \(B C_2\) and the nullary rules to form its contractible universal double cover \(E C_2\). Add one rule of a distinct conclusion sort whose premise family is the identity of \(B C_2\). Each premise sort passes the predicate test, so the added conclusion passes it as well. A derivation of that conclusion would be a section of \(E C_2\to B C_2\). This is impossible by the arity test. Ordinary Choice handles arbitrarily large discrete arities in spaces, while the proposed section here must be coherent around loops.

The examples separate failures at different points of an induction. The sheaf example fails at the dependent product before the conclusion is formed. The unary-delay example over \(B C_2\) passes the image test at every stage, but the actual witness type retains its monodromy. A uniform computation over a parameter object must specify which of these two levels of information its witnesses are supposed to provide.

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

\begin{exercise}
\label{ex:IV.1}
Let \(N_\alpha\hookrightarrow N\) be a filtration as in Proposition~\ref{ind:filtered-image}. Formulate a hypothesis on an input subobject \(K\hookrightarrow I\) under which \(K\leq R_\lambda\) implies \(K\leq R_\alpha\) for some \(\alpha<\lambda\). Test it for compact and noncompact open subobjects in sheaves on a space.
\end{exercise}

\begin{exercise}
\label{ex:IV.2}
For a monotone operator on a set-sized subobject lattice, verify that the ascending iteration from bottom is below each pre-fixed point. Construct a rule system on \(\mathbb N\amalg\{*\}\) whose first fixed point occurs at \(\omega+1\), and explain the role of the additional premise arity.
\end{exercise}

\begin{exercise}
\label{ex:IV.3}
In the category of sets with Choice, establish equality in Theorem~\ref{ind:comparison} for arbitrary small premise sets. Identify the choice instance used when the conclusions and rules are indexed by arbitrary sets.
\end{exercise}

\begin{exercise}
\label{ex:IV.4}
Work in sheaves on a connected space \(X\). Take opens \(U_n\) and a point \(x\in\bigcap_n U_n\). Set \(V=X\smallsetminus\{x\}\) and assume \(V\) is open. If \(X\) is locally connected, compute the support of \(\prod_n(U_n\amalg V)\to1\) in terms of the interior of \(\bigcap_n U_n\).
\end{exercise}

\begin{exercise}
\label{ex:IV.5}
Let \(H\leq G\) be finite groups. Replace the free transitive fiber in the last example by the transitive \(G\)-set \(G/H\). Determine precisely which subgroup maps \(B K\to B G\) admit a section after base change. Include the effect of conjugating the inclusion of \(K\).
\end{exercise}

\begin{exercise}
\label{ex:IV.6}
Suppose all rules of a signature have either zero or one premise. Interpret derivations as finite strings of unary rules terminating in a nullary rule. Formulate the appropriate homotopy pullbacks when the objects of sorts and rules are spaces, and show how the finite strings assemble into the initial algebra.
\end{exercise}

\begin{exercise}
\label{ex:IV.7}
Give two encodings of the same operator on subsets of \(\mathbb N\) by polynomial signatures whose initial algebras are inequivalent as spaces over \(\mathbb N\). Fix a sort whose derivation object has different positive-dimensional homotopy in the two encodings.
\end{exercise}

End of manuscript · Back to top ↑