Recursive Functionals (studies In Logic And The Foundations Of Mathematics)

This work is a self-contained elementary exposition of the theory of recursive functionals, that also includes a number of advanced results. Although aiming basically at a theory of higher order computability, attention is restricted to second order functionals, where the arguments are numerical functions and the values, when defined, are natural numbers. This theory is somewhat special, for to some extent it can be reduced to first order theory, but when properly extended and relativized it requires the full machinery of higher order computations. In the theory of recursive monotonic functionals the author formulates a reasonable notion of computation which provides the right frame for what appears to be a convincing form of the extended Church's thesis. At the same time, the theory provides sufficient room to formulate the classical results that are usually derived in terms of singular functionals. Presented are complete proofs of Gandy's selector theorem, Kleene's theorem on hyperarithmetical predicates, and Grilliot's theorem on effectively discontinuous functionals. Contents......Page 11 Preface......Page 8 1 Mappings and Domains......Page 13 2 Functionals and Predicates......Page 27 3 Basic Operations......Page 41 4 Primitive Recursive Operations......Page 58 5 Basic Recursion......Page 77 6 Church's Thesis......Page 95 7 Functional Recursion......Page 106 8 Recursive Algorithms......Page 118 9 Formalization: Structural Semantics......Page 133 10 Formalization: Reductional Semantics......Page 148 11 Interpreters......Page 164 12 A Universal Interpreter......Page 178 13 Enumeration......Page 195 14 Continuous Functionals......Page 210 15 A Selector Theorem......Page 223 16 Hyperenumeration......Page 237 17 Recursion in Normal Classes......Page 247 Appendix: Recursion and Church's Thesis......Page 263 References......Page 269 Index......Page 272 List of Symbols......Page 277