Abstract
We study the monoid of primitive recursive functions and investigate a onestep construction of a kind of exact completion, which resembles that of the familiar category of modest sets, except that the partial equivalence relations which serve as objects are recursively enumerable. As usual, these constructions involve the splitting of symmetric idempotents.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bainbridge, E. S., P. Freyd, A. Scedrov, and P. J. Scott,‘Functorial Polymorphism’, Theoretical Computer Science 70 (1990), 35–64.
Barr, M., et. al., Exact categories and categories of sheaves, Springer Lecture Notes in Mathematics 236, 1971.
Borceux, F., Handbook of Categorical Algebra 1, Cambridge, 1994.
Calenko, M. S., et. al., Ordered Categories with involution, Dissertaiones Mathematicae 227, 1984.
Carboni, A., and E. M. Vitale, ‘Regular and Exact Completions’, Journal of Pure and Applied Algebra 125 (1998), 29–117.
Cutland, N. J., Computability: An Introduction to Recursive Function Theory, Cambridge, 1980.
Freyd, P., and A. Scedrov, Categories, Allegories, North-Holland, 1990.
Hofstra, P., Completions in Realizability, Phd Thesis, Utrecht, 2003.
Kleene, S. C., Introduction to Metamathematics, Van Nostrand, New York, 1952.
Lambek, J., ‘Goursat's theorem and the Zassenhaus lemma’, Can. J. Math. 10 (1957), 45–56.
Lambek, J., ‘Least fixpoints of endofunctors of cartesian closed categories’, Mathematical Structures in Computer Science 3 (1993), 229–257.
Lambek, J., ‘The butterfiy and the serpent’, in Agliano et. al., (eds.), Logic and Algebra, Marcel Dekker, New York, 1996, pp. 161–179.
Lambek, J., ‘Diagram chasing in ordered categores with involution’, J. Pure and Applied Algebra 143 (1999), 293–307.
Lambek, J., and P. J. Scott., Introduction to Higher Order Categorical Logic, Cambridge Studies in Advanced Mathematics 7, Cambridge University Press, 1986.
Longo, G., and E. Moggi, ‘Constructive Natural Deduction and its -set interpretation’, Mathematical Structures in Comp. Sci (1991), 215–254.
Lounsbury, F.G., ‘Another view of Trobriand kinship categories’, in E. A. Hammel, (ed.), ‘Formal Semantics II’, American Anthropologist 67 (1965), 142–185.
Malinowski, B., Sexual life of savages, Routledge and Kegan Paul, London, 1932.
McLarty, C., Elementary Categories, elementary toposes, Clarendon Press, Oxford, 1992.
Rosolini, G., ‘About modest sets’, Internat. J. Found. Comp. Sci. 1 (1990)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Lambek, J., Scott, P. An Exactification of the Monoid of Primitive Recursive Functions. Stud Logica 81, 1–18 (2005). https://doi.org/10.1007/s11225-005-2765-x
Received:
Issue Date:
DOI: https://doi.org/10.1007/s11225-005-2765-x