Independent scholarship · Open accessThe monthly digest

Original LaTeX source

Higher Categorical Recursion Theory

\chapter{Set recursion and spaces of records}
\label{erec:chapter}

\section{Success as an inductive relation}

An instruction for set recursion has a numerical program \(e\) and a finite list \(\vec x\) of set arguments. Write \(\{e\}(\vec x)\downarrow=y\) for the judgment that its computation ends with the value \(y\). The Normann schemes are positive rules for this judgment \cite{Normann,Sacks}. The first three have no premises. They return a projection, a difference \(x_i\setminus x_j\), or an unordered pair \(\{x_i,x_j\}\). An enumeration rule invokes the index supplied as an argument. A composition has premises for the inner calls, with values \(y_1,\ldots,y_k\), and a premise for the outer call at \((y_1,\ldots,y_k)\). The union rule has one premise for each element of a set. Its form, with \(d\) the index of the inner instruction, is
\[
 \frac{\bigl(\{d\}(a,\vec x)\downarrow=y_a\bigr)_{a\in D}}
      {\{e\}(D,\vec x)\downarrow=\displaystyle\bigcup_{a\in D}y_a}.
\]
The numerator is a family of verified judgments. There is no uniform finite upper bound on its size. With singletons in place of the \(y_a\), the same rule forms the set of attained values.

A successful record lists the instructions and values on a well-founded tree, including the output of each preliminary call needed to determine a later input. Its length is the rank of the root. With length zero at a leaf, the length of a compound call is
\(\sup_b(\ell_b+1)\), where \(b\) ranges over its immediate premises. A union with no premises has length zero. For fixed program conventions the checks on the data of a record, including a displayed ordinal ranking, can be made with bounded set quantifiers. Equivalently, convergence has a \(\Sigma_1\) definition by existence of a record \cite[Chapter X]{Sacks}.

\begin{figure}[tbp]
\centering
\begin{tikzpicture}[>=Latex, every node/.style={font=\small}]
\node[draw, rounded corners, align=center] (root) at (0,0)
  {union instruction\\\(\{e\}(D,\vec x)\)};
\node[draw, rounded corners] (a) at (-2.4,-1.45) {\(\{d\}(a,\vec x)\)};
\node[draw, rounded corners] (b) at (0,-1.45) {\(\{d\}(b,\vec x)\)};
\node[draw, rounded corners] (c) at (2.4,-1.45) {\(\{d\}(c,\vec x)\)};
\node at (1.2,-1.45) {\(\cdots\)};
\draw[->] (root) -- (a);
\draw[->] (root) -- (b);
\draw[->] (root) -- (c);
\node at (-2.4,-2.1) {\(y_a,\ell_a\)};
\node at (0,-2.1) {\(y_b,\ell_b\)};
\node at (2.4,-2.1) {\(y_c,\ell_c\)};
\node at (0,-2.8) {\(\displaystyle y=\bigcup_{a\in D}y_a \qquad
 \ell=\sup_{a\in D}(\ell_a+1)\)};
\end{tikzpicture}
\caption{The arrows point from a union instruction to its premises. Each premise must supply a value and a smaller length, including every premise in an infinite family.}
\label{erec:fig-union}
\end{figure}

\begin{proposition}
Any two successful records for the same instruction have the same output.
\end{proposition}
\begin{proof}
Induct on the maximum of the two root lengths. The outer rule is read from the instruction. At a projection, a difference, or a pair the value is fixed. For composition, first compare the records of the inner calls by induction. Their agreed values specify the same outer call, to which induction applies again. Enumeration invokes the same instruction in the two records. In a union the same index set occurs at both roots. The two values at every index agree by induction, and their unions therefore agree.
\end{proof}

\begin{proposition}
Let \(M\) be a transitive admissible set. If \(e,\vec x\in M\) and \(\{e\}(\vec x)\) converges in the universe, then its value and some successful record belong to \(M\).
\end{proposition}
\begin{proof}
Induct along a successful external record. The primitive operations are available in \(M\). For composition and enumeration one assembles finitely many records, using transitivity and the computed inner values for the later inputs. For a union with parameter \(D\in M\), the inductive hypothesis gives an \(M\)-record at each \(a\in D\). Validity with an ordinal ranking is a bounded test. Collection in \(M\) yields a set of such records covering \(D\). Bounded separation and the rudimentary operations extract their values and take the union. Join the certified subrecords under a new root, using an ordinal above all the displayed subrecord ranks. The collecting set and this new record belong to \(M\). Determinacy identifies the resulting value with the external value.
\end{proof}

A transitive set closed under all such values is called \(E\)-closed. The least one containing \(x\) is denoted by \(E(x)\). The relative constructible presentation uses the transitive closure \(T_x=\operatorname{TC}(\{x\})\) as its base. In Sacks's convention, \(E(x)=L(\kappa^x,T_x)\), where \(\kappa^x=\operatorname{Ord}\cap E(x)\) and the zero stage of the relative hierarchy is \(T_x\) \cite[Chapter X, Proposition 2.10]{Sacks}. The bound \(\kappa^x\) ranges over results with additional arguments from \(T_x\). The ordinal \(\kappa_0^x\) is the supremum of the lengths of computations using \(x\) and numerical indices and parameters. A length is the ordinal of an execution. An ordinal returned by a program is a value, and the two spectra need not agree. Even a projection can return an arbitrarily large input ordinal at length zero. The case \(E(\omega)=L_{\omega_1^{\mathrm{CK}}}\) recovers the hyperarithmetic hierarchy at its admissible bound.

\section{Indexed signatures and contexts}

Work in an \(\infty\)-topos \(\mathcal X\) and fix a parameter object \(U\). A small presentation of rules in the slice \(\mathcal X_{/U}\) has objects \(I,A,B\) and maps
\[
  I \xleftarrow{s} B \xrightarrow{p} A \xrightarrow{t} I .
\]
Here \(I\) is the object of judgments, \(A\) is the object of rule instances, and \(B\) describes their premises. A point of \(A\) for an ordinary composition rule displays the inner results as local data. A point for a union rule displays the local family of values and its union. The inputs of every premise are then determined, even when the underlying program syntax has dependencies between calls. In the set case one may take a set of allowed arguments and outputs and include exactly the rule instances with data in that set. This gives a fragment of the class theory and recovers every derivation whose data lie in the fragment.

The operation on families of records \(Z\) over \(I\) is \(P(Z)=\Sigma_t\Pi_p s^*Z\). For dependent polynomials in the ordinary setting see \cite{GambinoHyland}. In a slice, the fiberwise product is a dependent product of evidence. Its arguments include one premise record for every branch, and path and higher path data of the indexing objects are respected. A small accessible polynomial gives an initial algebra \(W\) by the initial chain, with \(W_0=0,\ W_{\alpha+1}=P(W_\alpha)\) and a colimit at a limit stage. The maps into \(W\) are monomorphisms. Indeed these properties hold initially, polynomial functors preserve monomorphisms, and an increasing directed colimit of subobjects computes their join. Thus the stages give a filtration in the slice. For set signatures \(W_\alpha\) consists of the trees of length strictly less than \(\alpha\). The assertion follows by induction, since the strict supremum of the child lengths is at most \(\alpha\) exactly when every child has length less than \(\alpha\).

\begin{theorem}[Transport of the stage filtration]
\label{erec:thm-transport}
Let \(P,Q\) be small accessible polynomials on \(\mathcal X_{/I}\) with the same judgment object. Suppose the rule map from \(P\) to \(Q\) preserves conclusions and identifies each family of premises with the corresponding family over the image rule, including its map of premise sorts. The induced map from \(W^P\) to \(W^Q\) satisfies
\[
 W^P_\alpha \simeq W^P\times_{W^Q}W^Q_\alpha
\]
for every stage \(\alpha\). In particular the map preserves and reflects membership in each stage.
\end{theorem}
\begin{proof}
The hypotheses give a cartesian transformation \(P\to Q\). In fact the rule data of \(P(Z)\) over a rule of \(P\) are the pullback of those of \(Q(Z)\) over its image, because the premise families are identified. The initial chain induces the map of initial algebras. At stage zero the claim follows from stability of the initial object under pullback. If it holds at \(\alpha\), apply \(P\) to the pullback and then use the cartesian transformation for the map \(W^Q_\alpha\to W^Q\). Polynomials preserve pullbacks and the initial algebras are fixed points. This gives the required pullback at \(\alpha+1\). At a limit, pullback commutes with the colimit of the earlier stages. Induction proves the result.
\end{proof}

\begin{figure}[tbp]
\centering
\begin{tikzcd}[column sep=large,row sep=large]
W^P_\alpha\arrow[r]\arrow[d,hook] & W^Q_\alpha\arrow[d,hook]\\
W^P\arrow[r] & W^Q
\end{tikzcd}
\caption{Preserving the indexed premises makes every stage square a pullback. Instruction labels can change while the bound on a derivation is preserved.}
\label{erec:fig-rank}
\end{figure}

\begin{example}[A homogeneous family of union nodes]
Suppose the inputs are unordered configurations of \(m\) distinct points of \(\mathbb R^2\). The ordered configuration space is a finite covering of the unordered space. Let the \(m\) premises of a node be the associated family of configuration points. On a simply connected open set one can order the points and write the premises as a product of \(m\) named factors. A loop interchanging two points permutes the corresponding factors. The rule that takes the union of their set values descends along the covering, by invariance under the permutation. The ordered rule presentation changes only the labels on the same premise family, so its comparison with the unordered presentation preserves the stage filtration by Theorem~\ref{erec:thm-transport}. A choice of an ordering for all configurations would be a section of the covering. For \(m>1\) the loop exchanging two entries rules out such a section.
\end{example}

\begin{proposition}[Determinacy descends]
\label{erec:prop-determinacy}
Let \(R\to C\) be a space of records over instructions and \(v:R\to Y\) a map over \(U\) to a \(0\)-truncated object over \(U\). Assume that the two outputs agree on \(R\times_C R\). Let \(D\hookrightarrow C\) be the image of \(R\to C\). There is a unique output map \(D\to Y\) over \(U\) extending \(v\).
\end{proposition}
\begin{proof}
The map \(R\to D\) is an effective epimorphism and its \v{C}ech nerve has colimit \(D\). Mapping this colimit into \(Y\) over \(U\) gives a limit of discrete spaces. Compatibility in degree one implies all higher compatibilities, since both maps from a higher multiple intersection are restrictions of the same agreement on pairs. The resulting unique compatible map is the claimed extension.
\end{proof}

\begin{example}[A stable output with higher evidence]
Let \(U=K(\mathbb Z,2)\) in spaces and let \(R=*\to U\) be the chosen base point. Interpret \(R\) as the object of a single kind of nullary rule over instruction \(C=U\). The evidence fiber is equivalent to \(K(\mathbb Z,1)\), the loop space of \(U\). The image of \(R\to U\) is \(U\), and the output of every record can be the same element of the terminal value object over \(U\). All inhabited record fibers occur at rank zero. A global record would be a section of \(*\to U\), making the identity of \(U\) homotopic to a constant map. The second homotopy group of \(U\) rules this out. The output descends and its evidence retains a higher obstruction.
\end{example}

\section{Divergence certificates}

Once the successful preliminary calls of an instruction have been determined, the operational immediate-subinstruction relation is defined as in the set theory. A Moschovakis witness to divergence is a sequence of immediate subinstructions descending from the given instruction. It can be accompanied by the successful records justifying edges that depend on earlier returns. A sequence of that kind and a successful record for the same instruction cannot coexist, since the successful record supplies a descending sequence of ordinals along the branch. In the classical universe a well-founded operational tree of valid instructions yields a record by recursion, so a divergent valid instruction has an infinite path by dependent choice. Existence of that path in a specified transitive model is a further problem.

An ordinal \(\delta\) is \(x\)-reflecting when the \(\Sigma_1\) sentences with parameter \(x\) true in \(L(\delta,T_x)\) are already true in \(L(\kappa_0^x,T_x)\). Sacks uses the greatest such ordinal \(\kappa_r^x\) to control the level where divergence witnesses appear. When an \(E\)-recursive well-ordering of the transitive base is available, a divergent instruction has a witness definable over \(L(\kappa_r^x,T_x)\) \cite[Chapter X, Lemma 5.3]{Sacks}. Inside an \(\infty\)-topos one can form objects of successful records and of sequences satisfying the witness relation. Their images are disjoint whenever rank decrease along a certified edge has been verified. Their union need not be the entire instruction object. Reflection and dependent choice are the additional ingredients in the classical witness analysis.

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

\begin{exercise}
\label{ex:X.1}
Write a union instruction whose subcalls return singletons. Compute its output and rank in the cases of empty, finite, and infinite input domains, assuming each subcall is an elementary instruction of rank zero.
\end{exercise}

\begin{exercise}
\label{ex:X.2}
Build a set signature with one judgment for each ordinal below a fixed \(\lambda\), with one rule at \(\eta\) having premises indexed by \(\xi<\eta\). Determine the first stage containing the judgment \(\eta\).
\end{exercise}

\begin{exercise}
\label{ex:X.3}
Suppose the map of rule presentations is an effective epimorphism on rules and identifies the premise families. Find sufficient hypotheses on the arities under which it induces an effective epimorphism on records at every stage. Examine the role of simultaneous local choices in a successor step.
\end{exercise}

\begin{exercise}
\label{ex:X.4}
Give two presentations of the same total operation on a singleton input, one with a longer successful derivation than the other. Explain which hypothesis of Theorem~\ref{erec:thm-transport} is absent from a comparison that erases the longer derivation's extra rule.
\end{exercise}

\begin{exercise}
\label{ex:X.5}
In the configuration example, fix the ordered presentation locally and give an action of a loop on the space of a two-branch record. Decide when an ordered pair of premise records descends along that loop.
\end{exercise}

\begin{exercise}
\label{ex:X.6}
Let \(R\to D\) be the base-point map \(*\to K(A,n)\) for \(n\geq2\) and \(A\ne0\) abelian. Treat it as a nullary rule and compute its evidence fiber and image. Determine for which \(n\) that fiber is \(1\)-truncated.
\end{exercise}

\begin{exercise}
\label{ex:X.7}
For a tree with a specified ordinal rank, show that any alleged infinite operational path produces a descending sequence of ordinals. Formulate the argument in a slice so that it is preserved by pullback.
\end{exercise}

End of manuscript · Back to top ↑