Hostname: page-component-78c5997874-g7gxr Total loading time: 0 Render date: 2024-11-05T11:54:54.883Z Has data issue: false hasContentIssue false
  • English
  • Français

On first-order theories with provability operator

Published online by Cambridge University Press:  12 March 2014

Sergei Artëmov  and
Franco Montagna
Sergei Artëmov
Affiliation:
Steklov Mathematical Institute, 42, Vavilov Str., Moscow, 117966, Russia, E-mail: [email protected]
Franco Montagna
Affiliation:
Dipartimento di Matematica, Universita di Siena, 53100-Siena, Italia, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper the modal operator “x is provable in Peano Arithmetic” is incorporated into first-order theories. A provability extension of a theory is defined. Presburger Arithmetic of addition, Skolem Arithmetic of multiplication, and some first order theories of partial consistency statements are shown to remain decidable after natural provability extensions. It is also shown that natural provability extensions of a decidable theory may be undecidable.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 59 , Issue 4 , December 1994 , pp. 1139 - 1153
Copyright
Copyright © Association for Symbolic Logic 1994

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.)

References

REFERENCES

[1]Artëmov, S., Arifmeticeski polnyje modal′nyje teorii, Semiotika i informatika, vol. 14 (1980), pp. 115–133; English translation, Arithmetically complete modal theories, American Mathematical Society Translations (2), vol. 135 (1987), pp. 39–54.Google Scholar
[2]Artëmov, S., Nonarithmeticity of truth predicate logics of provability, Doklady Akaclemii Nauk SSSR, vol. 284, no. 2 (1985), pp. 270–271; English Translation, Soviet Mathematics Doklady, vol. 33 (1986), pp. 403–405.Google Scholar
[3]Artëmov, S., On modal logics axiomatizing provability, Mathematics of the USSR-Izvestia, vol. 27, no. 3 (1986), pp. 401–429.CrossRefGoogle Scholar
[4]Artëmov, S. and Dzhaparidze, G., Finite Kripke models and predicate logics of probability, this Journal, vol. 55 (1990), pp. 1090–1098.Google Scholar
[5]Boolos, G., The unprovability of consistency: an essay in modal logic, Cambridge University Press, Cambridge, 1979.Google Scholar
[6]Boolos, G. and Jeffrey, R., Computability and logic, Cambridge University Press, Cambridge, 1974.Google Scholar
[7]Boolos, G. and Gee, V. M., The degree of the set of sentences of predicate provability logic that are true under every interpretation, this Journal, vol. 52 (1987), pp. 165–171.Google Scholar
[8]Feferman, S., Arithmetization of matemathematics in a general setting, Fundamenta Mathematicae, vol. 49 (1960), pp. 35–92.CrossRefGoogle Scholar
[9]Montagna, F., The predicate modal logic of provability, Notre Dame Journal of Formal Logic, vol. 25 (1984), pp. 179–189.CrossRefGoogle Scholar
[10]Vardanyan, V., Arithmetical complexity of predicate logics of provability and their fragments, Doklady Akademii Nauk SSSR, vol. 288 no. 1 (1986), pp. 11–14; English translation, Soviet Mathematics Doklady, vol. 34 (1986), pp. 384–387.Google Scholar
[11]Visser, A., The provability logics of recursively enumerable theories extending Peano arithmetic at arbitrary theories extending Peano arithmetic, Journal of Philosophical Logic, vol. 13 (1984), pp. 97–113.CrossRefGoogle Scholar
[12]Skolem, T., Über einige satzfunktionen in der arithmetik, Skrifter utgitt av Det Norske Videnskaps-Akademi i Oslo, I., Matematisk-naturvidenskapelig klasse, 1931, pp. 1–28.Google Scholar
[13]Smoryński, C., Self-reference and modal logic, Springer-Verlag, New York, Berlin, Heidelberg, and Tokyo, 1985.CrossRefGoogle Scholar
[14]Rogers, H., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.Google Scholar