On provability logics of Niebergall arithmetic. (English. Russian original) Zbl 07877897
Izv. Math. 88, No. 3, 468-505 (2024); translation from Izv. Ross. Akad. Nauk, Ser. Mat. 88, No. 3, 61-100 (2024).
Summary: K. G. Niebergall suggested a simple example of a non-gödelean arithmetical theory \(\text{NA} \), in which a natural formalization of its consistency is derivable. In the present paper we consider the provability logic of \(\text{NA}\) with respect to Peano arithmetic. We describe the class of its finite Kripke frames and establish the corresponding completeness theorem. For a conservative extension of this logic in the language with an additional propositional constant, we obtain a finite axiomatization. We also consider the truth provability logic of \(\text{NA}\) and the provability logic of \(\text{NA}\) with respect to \(\text{NA}\) itself. We describe the classes of Kripke models with respect to which these logics are complete. We establish \(\text{PSpace} \)-completeness of the derivability problem in these logics and describe their variable free fragments. We also prove that the provability logic of \(\text{NA}\) with respect to Peano arithmetic does not have the Craig interpolation property.
MSC:
| 03F45 | Provability logics and related algebras (e.g., diagonalizable algebras) |
References:
| [1] | K.-G. Niebergall, “ ”Natural’ representations and extensions of Gödel’s second theorem“, Logic colloquium ”01, Lect. Notes Log., vol. 20, Assoc. Symbol. Logic, Urbana, IL 2005, pp. 350-368. · Zbl 1081.03058 |
| [2] | S. Feferman, “Arithmetization of metamathematics in a general setting”, Fund. Math. 49 (1960), 35-92. · Zbl 0095.24301 · doi:10.4064/fm-49-1-35-92 |
| [3] | G. Kreisel, “A survey of proof theory”, J. Symb. Log. 33:3 (1968), 321-388. · Zbl 0177.01002 · doi:10.2307/2270324 |
| [4] | D. E. Willard, “Self-verifying axiom systems, the incompleteness theorem and related reflection principles”, J. Symb. Log. 66:2 (2001), 536-596. · Zbl 0991.03053 · doi:10.2307/2695030 |
| [5] | F. Pakhomov, A weak set theory that proves its own consistency, 2019, arXiv: 1907.00877. |
| [6] | S. N. Artemov and L. D. Beklemishev, “Provability logic”, 2nd ed., Handb. Philos. Log., vol. 13, Kluwer, Dordrecht 2005, pp. 189-360. · doi:10.1007/1-4020-3521-7_3 |
| [7] | C. Smoryński, Self-reference and modal logic, Universitext, Springer-Verlag, New York 1985. · Zbl 0596.03001 · doi:10.1007/978-1-4613-8601-8 |
| [8] | G. Boolos, The logic of provability, Cambridge Univ. Press, Cambridge 1993. · Zbl 0891.03004 · doi:10.1017/CBO9780511625183 |
| [9] | R. M. Solovay, “Provability interpretations of modal logic”, Israel J. Math. 25:3-4 (1976), 287-304. · Zbl 0352.02019 · doi:10.1007/BF02757006 |
| [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. · Zbl 0686.03033 · doi:10.1305/ndjfl/1093635077 |
| [11] | V. Yu. Shavrukov, “On Rosser”s provability predicate”, Z. Math. Logik Grundlag. Math. 37:19-22 (1991), 317-330. · Zbl 0726.03042 · doi:10.1002/malq.19910371906 |
| [12] | V. Yu. Shavrukov, “A smart child of Peano”s”, Notre Dame J. Form. Log. 35:2 (1994), 161-185; Preprint ML-92-10, ILLC Prepublication Series, Univ. Amsterdam 1991, https://eprints.illc.uva.nl/id/eprint/1324/1/ML-1992-10.text.pdf. · Zbl 0815.03011 · doi:10.1305/ndjfl/1094061859 |
| [13] | L. D. Beklemishev, “Reflection principles and provability algebras in formal arithmetic”, Russian Math. Surveys 60:2 (2005), 197-268. · Zbl 1097.03054 · doi:10.1070/RM2005v060n02ABEH000823 |
| [14] | K. N. Ignatiev, “On strong provability predicates and the associated modal logics”, J. Symb. Log. 58:1 (1993), 249-290. · Zbl 0795.03082 · doi:10.2307/2275337 |
| [15] | G. K. Japaridze, Modal logic tools of investigation of provability, Candidate (PhD) dissertation, Moscow State Univ., Moscow 1986. (Russian) |
| [16] | G. K. Japaridze [G. K. Dzhaparidze], “Polymodal provability logic”, Intensional logics and the logical structure of theories (Telavi 1985), Metsniereba, Tbilisi 1988, pp. 16-48. (Russian) · Zbl 0725.03038 |
| [17] | A. Chagrov and M. Zakharyaschev, Modal logic, Oxford Logic Guides, vol. 35, The Clarendon Press, Oxford Univ. Press, New York 1997. · Zbl 0871.03007 |
| [18] | L. D. Beklemishev, “Kripke semantics for provability logic GLP”, Ann. Pure Appl. Logic 161:6 (2010), 756-774. · Zbl 1223.03046 · doi:10.1016/j.apal.2009.06.011 |
| [19] | I. Shapirovsky, “PSPACE-decidability of Japaridze”s polymodal logic”, Advances in modal logic, vol. 7, College Publications, London 2008, pp. 289-304. · Zbl 1244.03073 |
| [20] | Lev V. Dvorkin Steklov Mathematical Institute of Russian Academy of Sciences E-mail: lev_135@mail.ru |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
