Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-19T16:47:11.208Z Has data issue: false hasContentIssue false
  • English
  • Français

Dominical categories: recursion theory without elements1 2

Published online by Cambridge University Press:  12 March 2014

Robert A. di Paola  and
Alex Heller
Robert A. di Paola
Affiliation:
Department of Computer Science, Queens College, City University of New York, Flushing, New York 11367 Department of Mathematics, Graduate School and University Center, City University of New York, New York, New York 10036
Alex Heller
Affiliation:
Department of Mathematics, Graduate School and University Center, City University of New York, New York, New York 10036
Get access Rights & Permissions [Opens in a new window]

Extract

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 developed without reference to elements.

By Gödel's generalized incompleteness theorem for consistent arithmetical system T we mean any statement of the following sort:

(1) if every recursive set is definable in T, then T is essentially undecidable [41]; or

(2) if all recursive functions are definable in T, then T is essentially undecidable [41]; or

(3) if every recursive set is definable in T, then T 0 and R 0 (the sets of Gödel numbers of the theorems and refutables of T) are recursively inseparable [39]; or

(4) if all re sets are representable in T, then T 0 is creative [28], [39]; or

(5) if T is a Rosser theory (i.e., all disjoint re sets are strongly separable in T), then T 0 and R 0 are effectively inseparable [39].

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 52 , Issue 3 , September 1987 , pp. 594 - 635
Copyright
Copyright © Association for Symbolic Logic 1987

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

1

Some of the contents of this paper were presented by both authors at the Fifth and Sixth Congresses of the School of Specialization in Mathematical Logic of the University of Siena, held at Siena, Italy in April 1983 and January 1984, respectively. The research leading to the paper was sponsored by the National Science Foundation Cooperative Science Program. Preparation of the paper was also supported by grant PSC-BHE 6-62054 of the City University of New York to the first named author, who would like to acknowledge also early support on this general subject from the Penrose Fund of the American Philosophical Society.

2

This paper formed the basis of an invited address by the first named author at the Annual Meeting of the Association of Symbolic Logic, held in conjunction with the American Philosophical Association in Washington, D.C., December 28–30 1985.

References

REFERENCES

[1] Bellissima, F., On the modal logic corresponding to diagonalizable algebra theory, Bollettino dell'Unione Matematica Italiana B, ser. 5, vol. 15 (1978), pp. 915–930.Google Scholar
[2] Bernardi, C., On the eguational class of diagonalizable algebras, Studia Logica, vol. 34 (1975), pp. 322–331.CrossRefGoogle Scholar
[3] Bernardi, C., The fixed point theorem for diagonalizable algebras, Studia Logica, vol. 34 (1975), pp. 239–251.CrossRefGoogle Scholar
[4] Bernardi, C. and Mirolli, M., Hyperdiagonalizable algebras, Algebra Universalis, vol. 21 (1986), pp. 89–102.CrossRefGoogle Scholar
[5] Blum, M., A machine-independent theory of the complexity of the recursive functions, Journal of the Association for Computing Machinery, vol. 14 (1967), pp. 322–336.CrossRefGoogle Scholar
[6] Boolos, G., Extremely undecidable sentences, this Journal, vol. 47 (1982), pp. 191–196.Google Scholar
[7] Davis, M., Computability and unsolvability, McGraw-Hill, New York, 1958.Google Scholar
[8] Di Paola, R. A., A uniform, extremely nonextensional formula of arithmetic with many undecidable fixed points in many theories, Proceedings of the American Mathematical Society, vol. 91 (1984), pp. 291–297.CrossRefGoogle Scholar
[9] Di Paola, R. A., A lift of a theorem of Friedberg: a Banach-Mazur functional that coincides with no α-recursive functional on the class of α-recursive functions, this Journal, vol. 46 (1981), pp. 216–232.Google Scholar
[10] Di Paola, R. A., The basic theory of partial α-recursive operators, Annali di Matematica Pura ed Applicata, ser. 4, vol. 134 (1983), pp. 169–199.CrossRefGoogle Scholar
[11] Fitting, M. C., Fundamentals of generalized recursion theory, North-Holland, Amsterdam, 1981.Google Scholar
[12] Halmos, P. R., Algebraic logic, Chelsea, New York, 1962.Google Scholar
[13] Hennie, P. C., Introduction to computability, Addison-Wesley, Reading, Massachusetts, 1977.Google Scholar
[14] Jensen, R. B., The fine structure of the constructible hierarchy, Annals of Mathematical Logic, vol. 4 (1972), pp. 229–308.CrossRefGoogle Scholar
[15] Kleene, S. C., Introduction to metamathematics, Van Nostrand, New York, 1952.Google Scholar
[16] Kleene, S. C., Arithmetical predicates and functional quantifiers, Transactions of the American Mathematical Society, vol. 79 (1955), pp. 312–340.CrossRefGoogle Scholar
[17] Kleene, S. C., Recursive functionals and quantifiers of finite types. I, Transactions of the American Mathematical Society, vol. 91 (1959), pp. 1–52.Google Scholar
[18] Kleene, S. C., Extension of an effectively generated class of functions by enumeration, Colloquium Mathematicum, vol. 6 (1958), pp. 67–78.CrossRefGoogle Scholar
[19] Kozen, D., Indexings of subrecursive classes, Theoretical Computer Science, vol. 11 (1980), pp. 277–301.CrossRefGoogle Scholar
[20] Lane, S. Mac, Categories for the working mathematician, Springer-Verlag, Berlin, 1971.CrossRefGoogle Scholar
[21] Magari, R., Problemi aperti sulle algebre diagonali, Rendiconti del Seminario Matematico e Fisico di Milano, vol. 44 (1974/1975), pp. 75–90.CrossRefGoogle Scholar
[22] Magari, R., The diagonalizable algebras, Bollettino dell'Unione Matematica Italiana, ser. 4, vol. 12 (1975), no. 3, suppl., pp. 117–125.Google Scholar
[23] Magari, R., Representation and duality theory for diagonalizable algebras, Studia Logica, vol. 34 (1975), pp. 305–313.CrossRefGoogle Scholar
[24] Magari, R., Modal diagonalizable algebras, Bollettino dell'Unione Matematica Italiana B, ser. 5, vol. 15 (1978), pp. 303–320.Google Scholar
[25] Mirolli, M., On the axiomatization of the finite frames of the modal system GL, Bollettino dell'Unione Matematica Italiana B, ser. 5, vol. 17 (1980), pp. 1075–1085.Google Scholar
[26] Montagna, F., On the diagonalizable algebras of Peano arithmetic, Bollettino dell'Unione Matematica Italiana B, ser. 5, vol. 16 (1979), pp. 795–812.Google Scholar
[27] Montagna, F., The predicate modal logic of provability, Notre Dame Journal of Formal Logic, vol. 25 (1984), pp. 179–189.CrossRefGoogle Scholar
[28] Myhill, J., Creative sets, Zeitschrift für Mathematische Logic und Grundlagen der Mathematik, vol. 1 (1955), pp. 97–108.CrossRefGoogle Scholar
[29] Post, E. L., Recursively enumerable sets of positive integers and their decision problems, Bulletin of the American Mathematical Society, vol. 50 (1944), pp. 284–316.CrossRefGoogle Scholar
[30] Rice, H. G., Classes of recursively enumerable sets and their decision problems, Transactions of the American Mathematical Society, vol. 74 (1953), pp. 358–366.CrossRefGoogle Scholar
[31] Ritchie, R. W., Classes of predictably computable functions, Transactions of the American Mathematical Society, vol. 106 (1963), pp. 139–173.CrossRefGoogle Scholar
[32] Rogers, H. Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.Google Scholar
[33] Sacks, G. E. and Simpson, S. G., The α-finite injury method, Annals of Mathematical Logic, vol. 4 (1972), pp. 343–367.CrossRefGoogle Scholar
[34] Sambin, G., An effective fixed point theorem in intuitionistic diagonalizable algebras, Studia Logica, vol. 35 (1976), pp. 345–361.Google Scholar
[35] Sambin, G. and Valentini, S., The modal logic of provability. The sequential approach, Journal of Philosophical Logic, vol. 11 (1982), pp. 311–342.CrossRefGoogle Scholar
[36] Shofnfield, J. R., Mathematical logic, Addison-Wesley, Reading, Massachusetts, 1967.Google Scholar
[37] Shore, R. A., α-recursion theory, Handbook of mathematical logic (Barwise, J., editor), North-Holland, Amsterdam, 1977, pp. 653–680.CrossRefGoogle Scholar
[38] Smoryński, C., Fixed point algebras, Bulletin (New Series) of the American Mathematical Society, vol. 6 (1982), pp. 317–356.CrossRefGoogle Scholar
[39] Smullyan, R. M., Theory of formal systems, Annals of Mathematics Studies, no. 47, Princeton University Press, Princeton, New Jersey, 1961.CrossRefGoogle Scholar
[40] Solovay, R. M., Provability interpretations of modal logic, Israel Journal of Mathematics, vol. 25 (1976), pp. 287–304.CrossRefGoogle Scholar
[41] Tarski, A., Mostowski, A., and Robinson, R. M., Undecidable theories, North-Holland, Amsterdam, 1951.Google Scholar
[42] Wagner, E., Uniformly reflexive structures: on the nature of Gödelizations and relative computability, Transactions of the American Mathematical Society, vol. 144 (1969), pp. 1–41.Google Scholar