Hostname: page-component-cd9895bd7-jn8rn Total loading time: 0 Render date: 2024-12-23T09:36:30.565Z Has data issue: false hasContentIssue false

PROVABILITY LOGICS RELATIVE TO A FIXED EXTENSION OF PEANO ARITHMETIC

Published online by Cambridge University Press:  23 October 2018

TAISHI KURAHASHI*
Affiliation:
DEPARTMENT OF NATURAL SCIENCE NATIONAL INSTITUTE OF TECHNOLOGY, KISARAZU COLLEGE 2-11-1 KIYOMIDAI-HIGASHI KISARAZU, CHIBA 292-0041, JAPANE-mail: [email protected]

Abstract

Let T and U be any consistent theories of arithmetic. If T is computably enumerable, then the provability predicate $P{r_\tau }\left( x \right)$ of T is naturally obtained from each ${{\rm{\Sigma }}_1}$ definition $\tau \left( v \right)$ of T. The provability logic $P{L_\tau }\left( U \right)$ of τ relative to U is the set of all modal formulas which are provable in U under all arithmetical interpretations where □ is interpreted by $P{r_\tau }\left( x \right)$. It was proved by Beklemishev based on the previous studies by Artemov, Visser, and Japaridze that every $P{L_\tau }\left( U \right)$ coincides with one of the logics $G{L_\alpha }$, ${D_\beta }$, ${S_\beta }$, and $GL_\beta ^ -$, where α and β are subsets of ω and β is cofinite.

We prove that if U is a computably enumerable consistent extension of Peano Arithmetic and L is one of $G{L_\alpha }$, ${D_\beta }$, ${S_\beta }$, and $GL_\beta ^ -$, where α is computably enumerable and β is cofinite, then there exists a ${{\rm{\Sigma }}_1}$ definition $\tau \left( v \right)$ of some extension of $I{{\rm{\Sigma }}_1}$ such that $P{L_\tau }\left( U \right)$ is exactly L.

Type
Articles
Copyright
Copyright © The Association for Symbolic Logic 2018 

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

Artemov, S. N., Arithmetically complete modal theories. Semiotics and Information Science, vol. 14 (1980), pp. 115133. Translated in American Mathematical Society Translations, vol. 135 (1987), no. 2, pp. 39–54.Google Scholar
Artemov, S. N., On modal logics axiomatizing provability. Izvestiya Akademii Nauk SSSR. Seriya Matematicheskaya, vol. 49 (1985), no. 6, pp. 11231154. Translated in Mathematics of the USSR Izvestiya, vol. 27 (1986), no. 3, pp. 401–429.Google Scholar
Artemov, S. N. and Beklemishev, L. D., Provability logic, Handbook of Philosophical Logic, vol. 13, second ed. (Gabbay, D. and Guenthner, F., editors), Springer, Dordrecht, 2005, pp. 189360.Google Scholar
Beklemishev, L. D., On the classification of propositional provability logics, Izvestiya Akademii Nauk SSSR. Seriya Matematicheskaya, vol. 53 (1989), no. 5, pp. 915943. Translated in Mathematics of the USSR-Izvestiya, vol. 35 (1990), no. 2, pp. 247–275.Google Scholar
Feferman, S., Arithmetization of metamathematics in a general setting. Fundamenta Mathematicae, vol. 49 (1960), pp. 3592.CrossRefGoogle Scholar
Hájek, P. and Pudlák, P., Metamathematics of First-Order Arithmetic, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1993.CrossRefGoogle Scholar
Japaridze, G., Modal logical means of investigating provability (in Russian), Ph.D. thesis, Moscow State University, 1986.Google Scholar
Jeroslow, R. G., Consistency statements in formal theories. Fundamenta Mathematicae, vol. 72 (1971), pp. 1740.CrossRefGoogle Scholar
Kurahashi, T., Arithmetical completeness theorem for modal logic K. Studia Logica, vol. 106 (2018), no. 2, pp. 219235.CrossRefGoogle Scholar
Lindström, P., Aspects of Incompleteness, second ed., Lecture Notes in Logic, vol. 10, A K Peters, Natick, MA, 2003.Google Scholar
Solovay, R. M., Provability interpretations of modal logic, Israel Journal of Mathematics, vol. 25 (1976), no. 3–4, pp. 287304.CrossRefGoogle Scholar
Visser, A., Aspects of diagonalization and provability, Ph.D. thesis, University of Utrecht, Utrecht, The Netherland, 1981.Google Scholar
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), no. 2, pp. 181212.CrossRefGoogle Scholar
Visser, A., Faith & falsity. Annals of Pure and Applied Logic, vol. 131 (2005), no. 1–3, pp. 103131.CrossRefGoogle Scholar