Traditional recursion theory is the study of computable functions on the natural numbers. This thesis considers recursion theory in first-order arithmetical theories and categories, thus expanding the work of Ritchie and Young, Lambek, Scott, and Hofstra.
We give a complete characterisation of the representability of computable functions in arithmetical theories, paying attention to the differences between intuitionistic and classical theories and between theories with and without induction. When considering recursion theory from a category-theoretic perspective, we examine syntactic categories of arithmetical theories. In this setting, we construct a strong parameterised natural numbers object and give necessary and sufficient conditions to construct a Turing category associated to an intuitionistic arithmetical theory with induction.
| Identifer | oai:union.ndltd.org:uottawa.ca/oai:ruor.uottawa.ca:10393/39877 |
| Date | 25 November 2019 |
| Creators | Steimle, Yan |
| Contributors | Scott, Philip |
| Publisher | Université d'Ottawa / University of Ottawa |
| Source Sets | Université d’Ottawa |
| Language | English |
| Detected Language | English |
| Type | Thesis |
| Format | application/pdf |
Page generated in 0.0108 seconds