On provability logics of Niebergall arithmetic

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

Abstract

K. G. Niebergall suggested a simple example of a non-gödelean arithmeticaltheory $\mathrm{NA}$, in which a natural formalization of its consistencyis derivable. In the present paper we consider the provability logicof $\mathrm{NA}$ with respect to Peano arithmetic. We describe the class of itsfinite Kripke frames and establish the corresponding completeness theorem.For a conservative extension of this logic in the language with an additionalpropositional constant, we obtain a finite axiomatization. We also considerthe truth provability logic of $\mathrm{NA}$ and the provability logic of $\mathrm{NA}$ with respect to $\mathrm{NA}$ itself. We describe the classes of Kripkemodels with respect to which these logics are complete. We establish$\mathrm{PSpace}$-completeness of the derivability problem in these logicsand describe their variable free fragments. We also prove thatthe provability logic of $\mathrm{NA}$ with respect to Peano arithmeticdoes not have the Craig interpolation property.

About the authors

Lev Veniaminovich Dvorkin

Steklov Mathematical Institute of Russian Academy of Sciences

Author for correspondence.
Email: dgdfgd@mail.ru
ORCID iD: 0009-0001-3117-1318

without scientific degree, no status

References

  1. K.-G. Niebergall, ““Natural” representations and extensions of Gödel's second theorem”, Logic colloquium '01, Lect. Notes Log., 20, Assoc. Symbol. Logic, Urbana, IL, 2005, 350–368
  2. S. Feferman, “Arithmetization of metamathematics in a general setting”, Fund. Math., 49 (1960), 35–92
  3. G. Kreisel, “A survey of proof theory”, J. Symb. Log., 33:3 (1968), 321–388
  4. D. E. Willard, “Self-verifying axiom systems, the incompleteness theorem and related reflection principles”, J. Symb. Log., 66:2 (2001), 536–596
  5. F. Pakhomov, A weak set theory that proves its own consistency, 2019
  6. S. N. Artemov, L. D. Beklemishev, “Provability logic”, Handb. Philos. Log., 13, 2nd ed., Kluwer, Dordrecht, 2005, 189–360
  7. C. Smorynski, Self-reference and modal logic, Universitext, Springer-Verlag, New York, 1985, xii+333 pp.
  8. G. Boolos, The logic of provability, Cambridge Univ. Press, Cambridge, 1993, xxxvi+276 pp.
  9. R. M. Solovay, “Provability interpretations of modal logic”, Israel J. Math., 25:3-4 (1976), 287–304
  10. A. Visser, “Peano's smart children: a provability logical study of systems with built-in consistency”, Notre Dame J. Form. Log., 30:2 (1989), 161–196
  11. V. Yu. Shavrukov, “On Rosser's provability predicate”, Z. Math. Logik Grundlag. Math., 37:19-22 (1991), 317–330
  12. V. Yu. Shavrukov, “A smart child of Peano's”, Notre Dame J. Form. Log., 35:2 (1994), 161–185
  13. Л. Д. Беклемишев, “Схемы рефлексии и алгебры доказуемости в формальной арифметике”, УМН, 60:2(362) (2005), 3–78
  14. K. N. Ignatiev, “On strong provability predicates and the associated modal logics”, J. Symb. Log., 58:1 (1993), 249–290
  15. Г. К. Джапаридзе, Модально-логические средства исследования доказуемости, Дисс. … канд. филос. наук, МГУ, М., 1986, 177 с.
  16. Г. К. Джапаридзе, “Полимодальная логика доказуемости”, Интенсиональные логики и логическая структура теорий (Телави, 1985), Мецниереба, Тбилиси, 1988, 16–48
  17. A. Chagrov, M. Zakharyaschev, Modal logic, Oxford Logic Guides, 35, The Clarendon Press, Oxford Univ. Press, New York, 1997, xvi+605 pp.
  18. L. D. Beklemishev, “Kripke semantics for provability logic GLP”, Ann. Pure Appl. Logic, 161:6 (2010), 756–774
  19. I. Shapirovsky, “PSPACE-decidability of Japaridze's polymodal logic”, Advances in modal logic, v. 7, College Publications, London, 2008, 289–304

Supplementary files

Supplementary Files
Action
1. JATS XML

Copyright (c) 2024 Дворкин Л.V.

Согласие на обработку персональных данных

 

Используя сайт https://journals.rcsi.science, я (далее – «Пользователь» или «Субъект персональных данных») даю согласие на обработку персональных данных на этом сайте (текст Согласия) и на обработку персональных данных с помощью сервиса «Яндекс.Метрика» (текст Согласия).