Independent scholarship · Open accessThe monthly digest

Original LaTeX source

Higher Categorical Recursion Theory

\chapter{Preface}

A successful computation gives a value and a record. In classical recursion theory the record often fits a finite piece of the oracle, and the value determines the observable behavior. In higher recursion theory the record may use an admissible ordinal bound or a well-founded family of subcomputations. There is then a question of whether the witnesses can be collected at one stage. In a category of spaces there is the further question of how the witnesses are identified as their inputs vary. A family can have a witness in each fiber and have no coherent choice of witnesses.

This book develops the classical material of Sacks's \emph{Higher Recursion Theory} \cite{Sacks} in that setting. From the first chapter we use a slice over the object of inputs. Successful derivations live in the slice. The image of the derivation object is the predicate of convergence, and its relative truncations exhibit how much of the equivalence data the observations retain. We retain explicit recursive or admissible presentations where an effectiveness claim depends on them. The difference between internal existence and a search in one of these presentations recurs in the proofs.

Part A treats effective trees, hyperarithmetic hierarchies, and positive induction. It develops the comparison with indexed polynomial algebras and gives a forcing interpretation of local witnesses. Part B treats metarecursion, admissibility, priority, and degrees. Collections of successful records, bounded supports, and stabilization of proper initial segments have separate roles in these arguments. Part C treats Normann's set recursion, effective selection and bounding, and descent of computation records. It ends with an explicit equivariant lift of the jump and a criterion for effective selection in group families.

We assume elementary recursion theory, set theory with choice in the metatheory, and some familiarity with categories and homotopy types. The exercises vary the sites, recursive presentations, and witness transport. Worked solutions appear together at the end of the book.

\paragraph{Preparation.} Generative AI assisted with drafting, mathematical exposition, worked solutions, and typesetting. The original classical theorems are cited where used.

End of manuscript · Back to top ↑