Hostname: page-component-cd9895bd7-jkksz Total loading time: 0 Render date: 2024-12-22T20:52:14.886Z Has data issue: false hasContentIssue false
  • English
  • Français

Effectively extensible theories1

Published online by Cambridge University Press:  12 March 2014

Marian Boykan Pour-El
Marian Boykan Pour-El*
Affiliation:
University of Minnesota
Get access Rights & Permissions [Opens in a new window]

Extract

It is well known that Gödel's famous undecidability result may be viewed in the following strong form. Suppose we are given a specific presentation (i.e., a specific formulation in terms of axioms and rules of inference) of number theory. Then there exists an effective method which, when applied to a consistent axiomatizable extension of the theory yields an undecidable sentence of this extension. For distinct presentations the undecidable sentences obtained would be distinct. This is because the sentence constructed depends upon the notion of proof and hence ultimately upon the axioms and rules of inference—i.e., upon the specific presentation.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 33 , Issue 1 , 26 April 1968 , pp. 56 - 68
Copyright
Copyright © Association for Symbolic Logic 1968

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

This paper was written while the author held grants awarded by the Institute for Advanced Study from funds the Institute derived from the National Science Foundation. The author wishes to express her sincere thanks to Professor Kurt Gödel for his continued interest over the years in the specific results of this paper.

References

[1]Ehrenfeucht, A., Separable theories, Bulletin de L'Académie Polonaise des Sciences, vol. 9 (1961), pp. 17–19.Google Scholar
[2]Feferman, S., Degrees of unsolvability associated with classes of formalized theories, this Journal, vol. 22 (1957), pp. 161–175.Google Scholar
[3]Feferman, S., Arithmetization of metamathematics in a general setting, Fundamenta mathematicae, vol. 49 (1960), pp. 35–92.CrossRefGoogle Scholar
[4]Kleene, S. C., Introduction to metamathematics, North-Holland, Amsterdam, 1952, x + 550 pp.Google Scholar
[5]Kreisel, G., Relative consistency and translatability, (abstract) this Journal, vol. 23 (1958), pp. 108–109.Google Scholar
[6]Myhill, J., Creative sets, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 1 (1955), pp. 97–108.CrossRefGoogle Scholar
[7]Poul-El, M., Review of [12], this Journal, vol. 30 (1965), pp. 88–90.Google Scholar
[8]Pour-El, M., “Recursive isomorphism” and effectively extensible theories, Bulletin of the American Mathematical Society, vol. 71 (1965), pp. 551–555.CrossRefGoogle Scholar
[9]Pour-El, M. and Kripke, S., Deduction-preserving “recursive isomorphisms” between theories, Bulletin of the American Mathematical Society, vol. 73 (1967), pp. 145–148.CrossRefGoogle Scholar
[10]Putnam, H. and Smullyan, R., Exact separation of recursively enumerable sets within theories, Proceedings of the American Mathematical Society, vol. 11 (1960), pp. 574–577.CrossRefGoogle Scholar
[11]Shepherdson, J. C., Representability of recursively enumerable sets informal theories, Archiv für Mathematische Logik und Grundlagenforschung, vol. 5 (1960/1961), pp. 119–127.CrossRefGoogle Scholar
[12]Smullyan, R., Theory of formal systems, Rev. ed., Annals of mathematics studies, no. 47 (1961), vii + 147 pp.Google Scholar
[13]Tarski, A., Mostowski, A., Robinson, R., Undecidable theories, North-Holland, Amsterdam, 1953, ix + 98 pp.Google Scholar
[14]Wang, H., Arithmetic translations of axiom systems, Transactions of the American Mathematical Society, vol. 71 (1951), pp. 283–293.CrossRefGoogle Scholar