×

Fibrations and recursivity. (English) Zbl 0833.03017

This paper, a contribution to category-theoretic recursion theory, uses the language of fibred categories and presheaves to formulate abstract versions of some results from the classical theory. In particular, this work generalizes that of P. S. Mulry [“Generalized Banach-Mazur functionals in the topos of recursive sets,” J. Pure Appl. Algebra 26, 71-83 (1982; Zbl 0491.03017)], who considered recursive topoi. The main offering here is a (least) fixed-point theorem, generalizing Kleene’s recursion theorem; also there are the beginnings of an abstract approach to partial functions using a generalization of presheaf over a locale, initiated by M. P. Fourman and D. S. Scott [“Sheaves and logic”, in: “Applications of sheaves”, Lect. Notes Math. 753, 302-401 (1979; Zbl 0415.03053)].

MSC:

03D75 Abstract and axiomatic computability and recursion theory
18F20 Presheaves and sheaves, stacks, descent conditions (category-theoretic aspects)
18D30 Fibered categories
PDF BibTeX XML Cite
Full Text: DOI EuDML

References:

[1] 1. J. BÉNABOU, Fibered categories and the foundation of naïve category theotry, Journal of symbolic logic, 1985, 50, No. 1. Zbl0564.18001 MR780520 · Zbl 0564.18001
[2] 2. J. BÉNABOU, Fibrations petites et localement petites, C. R. Acad. Sc. Paris, t. 281, 1975, pp. 897-900. Zbl0349.18006 MR393181 · Zbl 0349.18006
[3] 3. Y. ERSOV, La théorie des énumérations, Actes du congrès international des mathématiciens, 1970, 1, Gauthier Villars, 1971. Zbl0388.03019 MR457173 · Zbl 0388.03019
[4] 4. M. P. FOURMAN and D. S. SCOTT, Sheaves and logic, in: Applications of Sheaf theory to algebra, analysis and topology, Lectures Notes in Mathematics, Springer Verlag, 1979. Zbl0415.03053 MR555551 · Zbl 0415.03053
[5] 5. A. GROTHENDIECK, Catégories fibrées et descente, Lecture Notes in Mathematics, 1971, 224, Springer-Verlag.
[6] 6. J. M. E. HYLAND, P. T. JOHNSTONE and A. M. PITTS, Tripos theory, Mathematical proceedings of the Cambridge philosophical society, 1980, 88. Zbl0451.03027 MR578267 · Zbl 0451.03027
[7] 7. R. MIJOULE, L’universalité des semi-fonctions récursives universelles, Diagrammes, 12, Paris, 1984. Zbl0564.18002 MR800499 · Zbl 0564.18002
[8] 8. R. MIJOULE, La théorie des fonctions indexées en récursivité, Archivum mathematicum, 1987, 23, No. 4. Zbl0639.03050 MR930780 · Zbl 0639.03050
[9] 9. R. MIJOULE, Introduction à la récursivité synthétique, Rapport de recherche Cedric No. 92-13, Paris, 1992.
[10] 10. P. S. MULRY, Generalized Banach-Mazur functionnels in the topos of recursive sets, Journal of pure and applied algebra, 1982, 26. Zbl0491.03017 MR669844 · Zbl 0491.03017
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.