Hostname: page-component-cd9895bd7-7cvxr Total loading time: 0 Render date: 2024-12-22T20:41:01.239Z Has data issue: false hasContentIssue false
  • English
  • Français

Effectively retractable theories and degrees of undecidability1

Published online by Cambridge University Press:  12 March 2014

J. P. Jones
J. P. Jones*
Affiliation:
The University of Calgary
Get access Rights & Permissions [Opens in a new window]

Extract

In this paper a new property of theories, called effective retractability is introduced and used to obtain a characterization for the degrees of subtheories of arithmetic and set theory. By theory we understand theory in standard formalization as defined by Tarski [10]. The word degree refers to the Kleene-Post notion of degree of recursive unsolvability [2]. By the degree of a theory we mean, of course, the degree associated with its decision problem via Gödel numbering.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 34 , Issue 4 , February 1970 , pp. 597 - 604
Copyright
Copyright © Association for Symbolic Logic 1970

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

The results in this paper constitute a part of the author's Dissertation written while the author was a graduate student at the University of Washington. The author wishes to express his thanks to Professors R. W. Ritchie of the University of Washington and M. B. Poúr-El of the University of Minnesota for many helpful suggestions regarding the writing of this paper.

References

[1] Feferman, S., Degrees of unsolvability associated with classes of formalized theories, this Journal , vol. 22 (1957), pp. 161–175.Google Scholar
[2] Kleene, S. C., Introduction to metamathematics, North-Holland, Amsterdam, 1952.Google Scholar
[3] Poúr-El, M. B., Effectively extensible theories, this Journal , vol. 33 (1968), pp. 56–68.Google Scholar
[4] Robinson, J., Definability and decision problems in arithmetic, this Journal , vol. 14 (1949), pp. 98–114.Google Scholar
[5] Rogers, H., Review of [7], this Journal , vol. 27 (1962), pp. 85–86.Google Scholar
[6] Rogers, H., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.Google Scholar
[7] Shoenfield, J. R., Degrees of formal systems, this Journal , vol. 23 (1958), pp. 389–392.Google Scholar
[8] Shoenfield, J. R., Degrees of models, this Journal , vol. 25 (1960), pp. 233–237.Google Scholar
[9] Tarski, A., Grundzüge des Systemenkalküls. II, Fundamenta mathematicae, vol. 26 (1936), pp. 283–301.CrossRefGoogle Scholar
[10] Tarski, A., Mostowski, A. and Robinson, R., Undecidable theories, North-Holland, Amsterdam, 1953.Google Scholar