Trudy Matematicheskogo Instituta imeni V.A. Steklova
 RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Forthcoming papers Archive Impact factor Guidelines for authors License agreement Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Trudy Mat. Inst. Steklova: Year: Volume: Issue: Page: Find

 Trudy Mat. Inst. Steklova, 2015, Volume 289, Pages 206–226 (Mi tm3627)

On elementary theories of ordinal notation systems based on reflection principles

F. N. Pakhomov

Steklov Mathematical Institute of Russian Academy of Sciences, Moscow, Russia

Abstract: L.D. Beklemishev has recently introduced a constructive ordinal notation system for the ordinal $\varepsilon _0$. We consider this system and its fragments for smaller ordinals $\omega _n$ (towers of $\omega$-exponentiations of height $n$). These systems are based on Japaridze's well-known polymodal provability logic. They are used in the technique of ordinal analysis of the Peano arithmetic $\mathbf {PA}$ and its fragments on the basis of iterated reflection schemes. Ordinal notation systems can be regarded as models of the first-order language. We prove that the full notation system and its fragments for ordinals ${\ge } \omega _4$ have undecidable elementary theories. At the same time, the fragments of the full system for ordinals ${\le } \omega _3$ have decidable elementary theories. We also obtain results on decidability of the elementary theory for ordinal notation systems with weaker signatures.

 Funding Agency Grant Number Russian Science Foundation 14-50-00005

DOI: https://doi.org/10.1134/S0371968515020120

Full text: PDF file (317 kB)
References: PDF file   HTML file

English version:
Proceedings of the Steklov Institute of Mathematics, 2015, 289, 194–212

Bibliographic databases:

UDC: 510.227

Citation: F. N. Pakhomov, “On elementary theories of ordinal notation systems based on reflection principles”, Selected issues of mathematics and mechanics, Collected papers. In commemoration of the 150th anniversary of Academician Vladimir Andreevich Steklov, Trudy Mat. Inst. Steklova, 289, MAIK Nauka/Interperiodica, Moscow, 2015, 206–226; Proc. Steklov Inst. Math., 289 (2015), 194–212

Citation in format AMSBIB
\Bibitem{Pak15} \by F.~N.~Pakhomov \paper On elementary theories of ordinal notation systems based on reflection principles \inbook Selected issues of mathematics and mechanics \bookinfo Collected papers. In commemoration of the 150th anniversary of Academician Vladimir Andreevich Steklov \serial Trudy Mat. Inst. Steklova \yr 2015 \vol 289 \pages 206--226 \publ MAIK Nauka/Interperiodica \publaddr Moscow \mathnet{http://mi.mathnet.ru/tm3627} \crossref{https://doi.org/10.1134/S0371968515020120} \elib{https://elibrary.ru/item.asp?id=23738470} \transl \jour Proc. Steklov Inst. Math. \yr 2015 \vol 289 \pages 194--212 \crossref{https://doi.org/10.1134/S0081543815040124} \isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000358577300012} \scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84938882322} 

• http://mi.mathnet.ru/eng/tm3627
• https://doi.org/10.1134/S0371968515020120
• http://mi.mathnet.ru/eng/tm/v289/p206

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. L. Beklemishev, T. Flaminio, “Franco Montagna's work on provability logic and many-valued logic”, Studia Logica, 104:1 (2016), 1–46
2. F. N. Pakhomov, “Linear $\mathrm{GLP}$-algebras and their elementary theories”, Izv. Math., 80:6 (2016), 1159–1199
3. L. D. Beklemishev, “On the reflection calculus with partial conservativity operators”, Logic, Language, Information, and Computation, WoLLIC 2017 (London, UK, July 18–21, 2017), Lecture Notes in Computer Science, 10388, eds. J. Kennedy, R. DeQueiroz, Springer International Publishing Ag, 2017, 48–67
4. L. D. Beklemishev, “Reflection calculus and conservativity spectra”, Russian Math. Surveys, 73:4 (2018), 569–613
•  Number of views: This page: 238 Full text: 36 References: 22