Independent scholarship · Open accessThe monthly digest

Original LaTeX source

Higher Categorical Recursion Theory

\chapter{Admissible bounds and witness objects}
\label{adm:chapter}

\section{Set-sized domains of search}

Ordinary finite computation has two bounds. A completed run uses finitely many instructions, and a finite family of completed runs can be stored together. The second bound has to be proved anew when finite sets are replaced by sets of an admissible level. It is the bound that permits a family of computations to serve as the input to another computation.

Let \(M=L_\alpha\) be a transitive admissible set. The case in which \(\omega\in M\) has infinite internal domains. The level \(L_\omega\) gives the separate case of hereditary finiteness. We use the following fragment of Kripke--Platek set theory. Pairing, Union and bounded Separation construct sets from given data. Bounded Collection says that if
\[
 M\models (\forall x\in a)\,(\exists w)\,R(x,w,p)
\]
for \(a,p\in M\) and bounded \(R\), there is a \(b\in M\) containing at least one witness for each \(x\in a\). Here a formula is bounded when every quantifier ranges over a set displayed in the formula. Transitivity makes its truth on parameters in \(M\) absolute. Packing any extra witnesses into \(w\) gives the corresponding form of \(\Sigma_1\)-Collection. We allow parameters from \(M\) in definitions over \(M\). A set of \(M\) is called \(\alpha\)-finite. A subset or graph on \(\alpha\) is \(\alpha\)-recursively enumerable when it is \(\Sigma_1\) over \(M\). A predicate is \(\alpha\)-recursive when it and its complement are both so enumerable. These conventions give Sacks's ordinal recursion theory \cite[Ch.~VII]{Sacks}\cite{Barwise}.

The first admissible ordinal above \(\omega\) is \(\omega_1^{\mathrm{CK}}\), the supremum of the recursive ordinals. At this level \(\alpha\)-finite is called metafinite, and ordinal recursion has the notation presentation called metarecursion. To see why hyperarithmeticity occurs in this presentation, fix a coanalytic system of unique notations for the recursive ordinals. The image by that notation map of an \(\omega_1^{\mathrm{CK}}\)-finite set of ordinals is hyperarithmetic. The equivalence with the constructible presentation uses the coanalytic normal form for \(\Sigma_1(L_{\omega_1^{\mathrm{CK}}})\) and the translation of well-founded hyperarithmetic codes to their collapses. In particular a set of integers belongs to \(L_{\omega_1^{\mathrm{CK}}}\) exactly when it is hyperarithmetic \cite[Chs.~III, V and VII]{Sacks}. Thus infinite sets of integers can be metafinite, and a union chosen by an arbitrary external sequence of metafinite sets need not be metafinite.

\begin{proposition}[Bounded records]
\label{adm:bounded-records}
Suppose \(a,p\in M\), and a partial function on \(a\) is specified over \(M\) by
\[
 f(x)=y \quad\Longleftrightarrow\quad
 M\models(\exists z)\,D(x,y,z,p)
\]
with \(D\) bounded. If \(f\) is total on \(a\), its graph belongs to \(M\). Moreover one set in \(M\) contains a pair \((y,z)\) witnessing \(f(x)=y\) for each \(x\in a\).
\end{proposition}
\begin{proof}
Apply Collection to the bounded matrix saying that the two components of a proposed record verify \(D\). Read the first components of the collecting set and form their product with \(a\). Apply bounded Separation to this product, using a bounded existential quantifier over the collected records. Functionality identifies the result with the graph of \(f\).
\end{proof}

A \(\Sigma_1\) predicate on \(a\) may have a partial domain outside \(M\). The proposition uses totality to ensure that Collection applies before the graph is formed. It explains why a uniform enumeration in the theory requires more than an external list of correct local decisions.


\section{A certificate for coanalytic predicates}

\begin{proposition}[The numerical Spector--Gandy comparison]
A lightface \(\Pi^1_1\) predicate on \(\omega\) is \(\Sigma_1\) over \(L_{\omega_1^{\mathrm{CK}}}\). Conversely, a numerical predicate with a \(\Sigma_1\) definition over this admissible level, allowing a fixed parameter from the level, is lightface \(\Pi^1_1\).
\end{proposition}
\begin{proof}
For the forward direction, take a recursive family \(T_m\) whose path predicate is the complementary \(\Sigma^1_1\) predicate. A certificate of well-foundedness of \(T_m\) is an isomorphism between its Kleene--Brouwer order and an ordinal. For a recursive well-founded tree the order, its order type, and its collapse are all in \(L_{\omega_1^{\mathrm{CK}}}\). The collapse can be obtained by external induction on the well-order, using Collection in the admissible level to assemble the initial-segment collapses. The test of an isomorphism to a given ordinal is bounded. Existence of this certificate is therefore a \(\Sigma_1\) predicate over the level. Conversely, code the sets of \(L_{\omega_1^{\mathrm{CK}}}\) by well-founded hyperarithmetic relations. The collapse of a valid code belongs to the level. Relative to well-founded codes, the bounded test and its denial have effective inductive evaluations on the coded membership relations. The Spector--Gandy restricted existential theorem applies to this coding, since the witnesses range over hyperarithmetic reals. It makes the resulting numerical predicate \(\Pi^1_1\). A code for the fixed parameter is itself hyperarithmetic and can be substituted without increasing that pointclass. See \cite[Chs.~III and VII]{Sacks} for the restricted existential theorem and the code comparison.
\end{proof}

The certificate in the forward direction is highly rigid. For a fixed presentation the isomorphism to the ordinal, if it exists, is unique. Under transport that preserves the presentation of the order, composition with the transport is the induced map of certificates. It is sometimes preferable to use the ordinal-valued rank function on the tree itself. In the tree consisting of a root with two leaves, the permutation of the leaves preserves the rank assignment, since both leaves have rank zero. It exchanges the labels that determine their relative order in a fixed Kleene--Brouwer presentation. A witness family over \(BC_2\) can use this permutation as transport on the tree. The rank certificate respects that transport. A linearization that assigns a fixed order to the two leaves would instead require a choice of one of two exchanged orderings. Its existence on fibers is compatible with its failure to descend. Thus two equivalent numerical tests of well-foundedness give different requirements on their higher presentations.\index{Spector--Gandy theorem}\index{rank certificate}

\section{Bounded sets as a regular category}

Write \(\mathsf{Set}(M)\) for the category whose objects are the sets in \(M\) and whose arrows are the functions with graphs in \(M\). This is an ordinary category viewed from the metatheory. A choice of product, equalizer or union in it comes from the bounded set operations, and its variable \(a\) ranges only over \(M\).

\begin{proposition}[Regular images and substitution]
\label{adm:regular-category}
The category \(\mathsf{Set}(M)\) is regular. The regular image of \(f:C\to A\) is the subset \(\{a\in A:(\exists c\in C)\, f(c)=a\}\). For an arrow \(u:A'\to A\) the corresponding substitution identity is
\[
 u^*\operatorname{im}(f)=\operatorname{im}(u^*f)
\]
as subobjects of \(A'\).
\end{proposition}
\begin{proof}
Products, equalizers and the terminal set belong to \(M\), by Collection and bounded Separation. The image formula is bounded. The resulting surjection \(e:C\to\operatorname{im}(f)\) is the coequalizer of its kernel pair in this category. Indeed a map \(g:C\to D\) equalizing that pair determines a unique map on the image. Its graph is the bounded separation of \(\operatorname{im}(f)\times D\) using the existential witness \(c\in C\) with \(f(c)=a\) and \(g(c)=d\). Pullback preserves surjectivity, and a map into \(A\) factors through its ordinary set image by the same argument. Thus the surjection--injection factorizations are regular and stable, which gives both assertions.
\end{proof}

\begin{figure}[tbp]
\centering
\begin{tikzcd}[column sep=large,row sep=large]
  C\times_A A' \arrow[r]\arrow[d,two heads] & C \arrow[d,two heads]\\
  I\times_A A' \arrow[r]\arrow[d,hook] & I \arrow[d,hook]\\
  A' \arrow[r,"u"'] & A
\end{tikzcd}
\caption{Substitution of a bounded witness relation. The middle row is the image before and after substitution.}
\label{adm:fig-regular}
\end{figure}

In a slice the same proof gives left and right adjoints to substitution on subobjects. For \(v:Y\to X\) and \(S\subseteq Y\) in \(M\), write \(\exists_v S\) for the image in \(X\), and let \(\forall_v S\) consist of the \(x\) such that every member of \(v^{-1}(x)\) lies in \(S\). Both predicates are bounded and both satisfy change of base because their witnessing fibers pull back. These operations concern subobjects represented by elements of \(M\). The corresponding class of all external subsets of an \(a\in M\) can be larger. In particular these constructions do not require a power object in \(\mathsf{Set}(M)\).

\begin{example}[A classified predicate and an unclassified one]
Take \(M=L_{\omega_1^{\mathrm{CK}}}\) and \(A=\omega\). Take a uniformly recursive family \(T_e\) for which the assertion \(P(e)\) that \(T_e\) is well founded is \(\Pi^1_1\)-complete. The uniform tree normal form gives such a family. Ranking the tree as a well-founded relation is expressible by a \(\Sigma_1\) witness in \(M\), and the ranking of a recursive well-founded tree belongs to \(M\). The extension of \(P\) is therefore not an element of \(M\) \cite[Chs.~I--III]{Sacks}. For a fixed ordinal cutoff \(\beta\in M\), the set of indices with a rank less than \(\beta\) is hyperarithmetic. Thus it is a subobject in \(\mathsf{Set}(M)\). The full external union of these approximations can fail to lie in \(M\), even though each approximation is represented there. Adding the complement as another semidecidable predicate would give a total two-valued decision on \(\omega\) and invoke Proposition~\ref{adm:bounded-records}.
\end{example}

\section{Bounds in an infinity-topos}

In an \(\infty\)-topos \(\mathcal X\), fix a base \(B\) and a diagram of witnesses \(W_\xi\to X\) in \(\mathcal X_{/B}\), indexed by a nonempty limit ordinal \(\lambda\). Each transition commutes with the maps to \(X\). Write \(W=\operatorname{colim}_{\xi<\lambda}W_\xi\) in the slice and
\[
 I_\xi=\operatorname{im}(W_\xi\to X), \qquad
 I=\operatorname{im}(W\to X).
\]
Here the image is the relative \((-1)\)-truncation. The map from the witness object to its image is an effective epimorphism. An \(X\)-parametrized assertion that witnesses exist locally is expressed by \(I=X\). A uniform stage bound is an ordinal \(\xi<\lambda\) for which \(I_\xi=X\). Neither assertion requires a section of the corresponding witness map \cite{Lurie}.

\begin{theorem}[Transfer and detection of a bound]
\label{adm:stage}
Let \(v:B'\to B\). Pullback along \(v\) preserves each \(I_\xi\), their join \(I\), and every uniform stage bound. If \(v\) is an effective epimorphism, it also detects a proposed bound at any fixed \(\xi\). If \(X\) is \(\kappa\)-compact in \(\mathcal X_{/B}\) and \(\operatorname{cf}(\lambda)\ge\kappa\) for a regular infinite cardinal \(\kappa\), then \(I=X\) implies the existence of a uniform stage bound.
\end{theorem}
\begin{proof}
Relative \((-1)\)-truncation to subobjects is left adjoint to the inclusion of subobjects in the slice over \(X\). It therefore sends the colimit of the witness diagram to the join of the images. Colimits in an \(\infty\)-topos are universal and effective epimorphisms are stable under base change. Uniqueness of the image factorization gives the preservation assertion. If \(v\) is an effective epimorphism, so is \(X\times_B B'\to X\). If \(I_\xi\) pulls back to the top subobject then this effective epimorphism factors through \(I_\xi\), so \(I_\xi\) was already top.

For the last assertion the indexing ordinal is \(\kappa\)-filtered by the cofinality assumption. Filtered colimits in an \(\infty\)-topos commute with finite limits, so the colimit of the chain of monomorphisms \(I_\xi\to X\), in the slice over \(B\), is monic into \(X\) and represents their join. Compactness factors the identity of \(X\), up to homotopy, through one \(I_\xi\). A monomorphism with such a section is an equivalence.
\end{proof}

\begin{figure}[tbp]
\centering
\begin{tikzcd}[column sep=large,row sep=normal]
  W_\xi \arrow[r,two heads] \arrow[d] & I_\xi \arrow[r,hook]\arrow[d,hook] & X\arrow[d,equal]\\
  W_\eta \arrow[r,two heads] \arrow[d] & I_\eta \arrow[r,hook]\arrow[d,hook] & X\arrow[d,equal]\\
  W \arrow[r,two heads] & \bigvee_{\xi<\lambda} I_\xi \arrow[r,hook] & X
\end{tikzcd}
\caption{Witnesses at stages \(\xi\le\eta<\lambda\), projected to truth values over \(X\). A uniform bound is a stage at which the middle entry equals \(X\). A section would choose witnesses in the left column.}
\label{adm:fig-stage}
\end{figure}

The compactness argument uses the size of the externally given indexing diagram and compactness of the object of inputs. Proposition~\ref{adm:bounded-records} instead uses the definability of the relation and Collection in a particular transitive model. An internal domain can be infinite even when its definable total family has a single bound. Conversely an externally chosen stage assignment on \(\omega\in L_{\omega_1^{\mathrm{CK}}}\) can be cofinal in that model, since the model is countable in the ambient universe. Such an assignment cannot have a total \(\Sigma_1\) graph over the model.

\begin{example}[Local existence without a uniform bound]
In \(\mathsf{Sh}_\infty(\mathbb R)\) let \(B=X=1\) and \(W_n\) be the open subobject \((-n,n)\) for positive integers \(n\). The join of their images is \(1\), but no one stage has image \(1\). Over a bounded open, one stage does suffice. This gives local uniform bounds which cannot be promoted to a single global bound.
\end{example}

\begin{example}[A bound without a section]
In spaces, let \(X=B C_2\) and take \(W_0\to X\) to be the point equipped with the canonical map. Its fiber is \(C_2\) and the map is an effective epimorphism. Its section would make the identity of \(B C_2\) homotopic to a constant map, which is impossible on \(\pi_1\). Take a constant stage system with this witness object. Stage zero is a uniform bound and the action on the two witnesses around the generating loop exchanges them. Thus a stage bound does not remove monodromy from the witness family.
\end{example}

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

\begin{exercise}
\label{ex:VI.1}
Prove directly that a jointly specified \(\Sigma_1\) relation on a set in \(L_\alpha\) that gives both signs of a predicate has its positive part in \(L_\alpha\). State where the two signs are used.
\end{exercise}
\begin{exercise}
\label{ex:VI.2}
In \(\mathsf{Set}(M)\), prove that a bounded equivalence relation on \(A\in M\) has a quotient in \(M\). Determine its behavior under pullback along a map into the quotient.
\end{exercise}
\begin{exercise}
\label{ex:VI.3}
Give an example of a sequence of metafinite sets whose union is an element of \(M\) although the sequence itself is not. Explain why this does not give a converse to bounded Collection.
\end{exercise}
\begin{exercise}
\label{ex:VI.4}
Replace the ordinal diagram in Theorem~\ref{adm:stage} by a small \(\kappa\)-filtered diagram. Give the precise hypotheses needed for compactness to imply that one image is top.
\end{exercise}
\begin{exercise}
\label{ex:VI.5}
Let \(K\) be a compact Hausdorff space. Prove that a directed family of open truth values in \(\mathsf{Sh}_\infty(K)\) with join \(1\) has a stage equal to \(1\). Compare the conclusion with the example on \(\mathbb R\).
\end{exercise}
\begin{exercise}
\label{ex:VI.6}
Pull back \(*\to B C_2\) along the basepoint \(*\to B C_2\). Draw its homotopy pullback and compute the action on its fiber obtained by transporting around the fundamental loop.
\end{exercise}

\begin{exercise}
\label{ex:VI.7}
Replace the two-leaf tree by a root with \(d\) leaves and transport by a subgroup \(G\leq S_d\). Compare global sections of the finite family of linear orders of the leaves with global sections of the ordinal-rank certificate family.
\end{exercise}

End of manuscript · Back to top ↑