Dominical categories: recursion theory without elements

Journal of Symbolic Logic 52 (3):594-635 (1987)

Abstract

Dominical categories are categories in which the notions of partial morphisms and their domains become explicit, with the latter being endomorphisms rather than subobjects of their sources. These categories form the basis for a novel abstract formulation of recursion theory, to which the present paper is devoted. The abstractness has of course its usual concomitant advantage of generality: it is interesting to see that many of the fundamental results of recursion theory remain valid in contexts far removed from their classic manifestations. A principal reason for introducing this new formulation is to achieve an algebraization of the generalized incompleteness theorem, by providing a category-theoretic development of the concepts and tools of elementary recursion theory that are inherent in demonstrating the theorem.Dominical recursion theory avoids the commitment to sets and partial functions which is characteristic of other formulations, and thus allows for an intrinsic recursion theory within such structures as polyadic algebras. It is worthy of notice that much of elementary recursion theory can be developedwithout referencetoelements.By Gödel's generalized incompleteness theorem for consistent arithmetical systemTwe mean any statement of the following sort: if every recursive set is definable inT, thenTis essentially undecidable [41]; or if all recursive functions are definable inT, thenTis essentially undecidable [41]; or if every recursive set is definable inT, thenT0andR0 are recursively inseparable [39]; or if all re sets are representable inT, thenT0is creative [28], [39]; or ifTis a Rosser theory, thenT0andR0are effectively inseparable [39].

Download options

PhilArchive



    Upload a copy of this work     Papers currently archived: 72,660

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Analytics

Added to PP
2009-01-28

Downloads
43 (#267,299)

6 months
1 (#388,784)

Historical graph of downloads
How can I increase my downloads?

Similar books and articles

References found in this work

Introduction to Metamathematics.H. Rasiowa - 1954 - Journal of Symbolic Logic 19 (3):215-216.
Theory of Recursive Functions and Effective Computability.Hartley Rogers - 1971 - Journal of Symbolic Logic 36 (1):141-146.
Theory of Formal Systems.Raymond M. Smullyan - 1965 - Journal of Symbolic Logic 30 (1):88-90.
Undecidable Theories.Martin Davis - 1959 - Journal of Symbolic Logic 24 (2):167-169.
Creative Sets.John Myhill - 1955 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 1 (2):97-108.

View all 18 references / Add more references

Citations of this work

Introduction to Turing Categories.J. Robin B. Cockett & Pieter Jw Hofstra - 2008 - Annals of Pure and Applied Logic 156 (2):183-209.
Diagonal Fixed Points in Algebraic Recursion Theory.Jordan Zashev - 2005 - Archive for Mathematical Logic 44 (8):973-994.
More Existence Theorems for Recursion Categories.Florian Lengyel - 2004 - Annals of Pure and Applied Logic 125 (1-3):1-41.

Add more citations