Classification theorem for propositional provability logics is proved. A characterization of restricted induction rules in arithmetic in terms of iterated reflection principles is obtained. Classes of provably total computable functions for fragments of arithmetic with parameter-free induction are characterized. In particular, parameter-free induction for Π2-formulas corresponds to the class of primitive recursive functions. An approach to the theory of proof-theoretic ordinals on the basis of a notion of provability algebra is suggested.
Biography
Graduated from Faculty of Mathematics and Mechanics of M. V. Lomonossov Moscow State University in 1989 (department of Mathematical Logic); 1989–1992 — a Ph.D. student; since 1992 — staff member of V. A. Steklov Mathematical Institute of Russian Academy of Sciences. Ph.D. thesis was defended in 1992. Title: Classification of propositional provability logics. D.Sci. thesis was defended in 1998. Title: Reflection principles in formal arithmetic.
In 2000–2005 L. Beklemishev was a faculty member of Utrecht University (the Netherlands).
Moscow Mathematical Society prize was awarded in 1994 for the paper "On the classification of propositional provability logics". A. von Humboldt Fellowship (Germany) was awarded in 1998. In 2006 L. Beklemishev was elected a corresponding member of Russian Academy of Sciences.
Main publications:
L. D. Beklemishev, “On the classification of propositional provability logics”, Izv. Akad. Nauk SSSR Ser. Mat., 53:5 (1989), 915–943; English transl. Math. USSR-Izv., 35:2 (1990), 247–275
L. D. Beklemishev, “Iterated local reflection versus iterated consistency”, Ann. Pure Appl. Logic, 75 (1995), 25–48
L. D. Beklemishev, “A proof-theoretic analysis of collection”, Arch. Math. Logic, 37:5-6 (1998), 275–296
L. D. Beklemishev, “Parameter-free induction and provably total computable functions”, Theoret. Comput. Sci., 224 (1999), 13–33
L. D. Beklemishev, “Reflection principles and provability algebras in formal arithmetic”, Uspekhi Matematicheskikh Nauk, 60:2 (2005), 3–78; English transl. Russian Mathematical Surveys, 60:2 (2005), 197–268
L. D. Beklemishev, “On the unification problem for GLP”, Izv. RAN. Ser. Mat. (to appear)
2025
2.
Lev D. Beklemishev, Fedor N. Pakhomov, “Automatic structures and the problem of natural well-orderings”, Model Theory, Computer Science, and Graph Polynomials: Festschrift in honor of Johann A. Makowsky, Trends in Mathematics, eds. K. Meyer, A. Rabinovich, E. Ravve, A. Villaveces, Birkhäuser, 2025, 1–19 (to appear); arXiv: 2407.10198
2024
3.
Lev D. Beklemishev, Yunsong Wang, Periodic frames, 2024 , 32 pp., arXiv: 2407.10190
4.
Lev Beklemishev, Anna Dmitrieva, Johann A. Makowsky, “Axiomatizing Origami Planes”, Dick de Jongh on Intuitionistic and Provability Logics, Outst. Contrib. Log., 28, Springer, Cham, 2024, 353–377;
5.
A. N. Abyzov, L. D. Beklemishev, S. S. Goncharov, Yu. L. Ershov, I. Sh. Kalimullin, V. L. Selivanov, A. L. Semenov, A. Tuganbaev, M. Kh. Faizrahmanov, “Marat Mirzaevich Arslanov (on his eightieth birthday)”, Russian Math. Surveys, 79:2 (2024), 369–373
2023
6.
S. N. Artemov, L. D. Beklemishev, L. Ya. Borkin, A. M. Vershik, E. A. Hirsch, E. Ya. Dantsin, I. A. Ibragimov, E. V. Kalmens, V. Ya. Kreinovich, D. A. Koubenski, A. A. Lodkin, Yu. V. Matiyasevich, B. A. Novikov, V. P. Orevkov, A. L. Semenov, A. O. Slissenko, A. Kh. Shen, “Gregory Samuilovich Tseytin (obituary)”, Russian Math. Surveys, 78:3 (2023), 555–561
2022
7.
L. D. Beklemishev, “Conservativity spectra and Joosten–Fernández model”, Dokl. Math., 106:1 (2022), 213–217
8.
Lev D. Beklemishev, Fedor N. Pakhomov, “Reflection algebras and conservation results for theories of iterated truth”, Ann. Pure Appl. Logic, 173:5 (2022), 103093 , 41 pp. ;
V. S. Atabekyan, L. D. Beklemishev, V. S. Guba, I. G. Lysenok, A. A. Razborov, A. L. Semenov, “Questions in algebra and mathematical logic. Scientific heritage of S. I. Adian”, Russian Math. Surveys, 76:1 (2021), 1–27
10.
V. S. Atabekyan, L. D. Beklemishev, V. M. Buchstaber, S. S. Goncharov, V. S. Guba, Yu. L. Ershov, V. V. Kozlov, I. G. Lysenok, S. P. Novikov, Yu. S. Osipov, M. R. Pentus, V. V. Podolskii, A. A. Razborov, V. A. Sadovnichii, A. L. Semenov, A. L. Talambutsa, D. V. Treschev, L. N. Shevrin, “Sergei Ivanovich Adian (obituary)”, Russian Math. Surveys, 76:1 (2021), 177–181
11.
L. D. Beklemishev, Mat. Pros., 28, MCCME, Moscow, 2021, 9–14
2020
12.
L. Beklemishev, A. Dmitrieva, J. Makowsky, Axiomatizing Origami planes, 2020 , 25 pp., arXiv: 2012.03250
13.
L. D. Beklemishev, A. V. Vasil'ev, E. P. Vdovin, S. S. Goncharov, V. V. Kozlov, P. S. Kolesnikov, V. D. Mazurov, Yu. V. Matiyasevich, A. S. Morozov, A. N. Parshin, V. G. Puzarenko, M. V. Schwidefsky, “Yurii Leonidovich Ershov (on his 80th birthday)”, Russian Math. Surveys, 75:3 (2020), 581–585
2019
14.
Lev D. Beklemishev, Fedor N. Pakhomov, Reflection algebras and conservation results for theories of iterated truth, 2019 , 48 pp., arXiv: 1908.10302
15.
E. A. Kolmakov, L. D. Beklemishev, “Axiomatization of provable $n$-provability”, J. Symb. Log., 84:2 (2019), 849–869
S. I. Adian, N. N. Andreev, L. D. Beklemishev, S. S. Goncharov, Yu. L. Ershov, Yu. V. Matiyasevich, Yu. S. Osipov, M. R. Pentus, V. A. Plungyan, E. V. Rakhilina, V. A. Sadovnichii, A. L. Semenov, S. G. Tatevosov, V. M. Tikhomirov, A. Kh. Shen, “Vladimir Andreevich Uspensky (27/11/1930–27/6/2018)”, Russian Math. Surveys, 74:4 (2019), 735–753
17.
V. A. Alexandrov, L. D. Beklemishev, V. M. Buchstaber, A. Yu. Vesnin, A. A. Gaifullin, N. P. Dolbilin, N. Yu. Erokhovets, M. D. Kovalev, V. S. Makarov, S. P. Novikov, D. O. Orlov, A. N. Parshin, I. Kh. Sabitov, D. V. Treschev, O. K. Sheinman, E. V. Shchepin, “Mikhail Ivanovich Shtogrin (on his 80th birthday)”, Russian Math. Surveys, 74:6 (2019), 1159–1162
18.
L.D. Beklemishev, “Matematika i logika”, Matematicheskaya sostavlyayuschaya, eds. N.N. Andreev, S.P. Konovalov i N.A. Panyunin, 2019, 242–261book.etudes.ru/toc/mathnlogic/
2018
19.
Lev Beklemishev, “A note on strictly positive logics and word rewriting systems”, Larisa Maximova on Implication, Interpolation, and Definability, Outst. Contrib. Log., 15, eds. Sergei Odintsov, Springer, Berlin, Heidelberg, 2018, 61–70
L. D. Beklemishev, “Reflection calculus and conservativity spectra”, Russian Math. Surveys, 73:4 (2018), 569–613
21.
Lev D. Beklemishev, “A universal algebra for the variable-free fragment of $RC^\nabla$”, Logical Foundations of Computer Science, International Symposium, LFCS 2018, Lecture Notes in Comput. Sci., 10703, Springer, Berlin, Heidelberg, 2018, 91–106
Lev Beklemishev, Tommaso Flaminio, “Franco Montagna's work on provability logic and many-valued logic”, Studia Logica, 104:1 (2016), 1–46
31.
L. D. Beklemishev, Notes on a reduction property for GLP-algebras, 2016 , 8 pp., arXiv: 1606.00290
32.
Lev Beklemishev, Daniyar Shamkanov, “Some abstract versions of Gödel's second incompleteness theorem based on non-classical logics”, Liber Amicorum Alberti: A tribute to Albert Visser, Tributes, 30, eds. Jan van Eijck, Rosalie Iemhoff and Joost J. Joosten, College Publications, London, 2016, 15–29url, arXiv: 1602.05728
33.
Gerald Berger, Lev D. Beklemishev, Hans Tompits, A Many-Sorted Variant of Japaridze's Polymodal Provability Logic, 2016 , 15 pp., arXiv: 1601.02857
34.
Lev Beklemishev, “Notes on a reduction property of GLP-algebras”, 11th International Conference on Advances in Modal Logic, Short Papers (Budapest, 30 August – 2 September, 2016), 2016, 7–13
35.
Advances in Modal Logic, v. 11, eds. Lev Beklemishev, Stephane Demri, Andras Mate, College Publications, London, 2016 , xii+570 pp.
2015
36.
L. D. Beklemishev, A note on strictly positive logics and word rewriting systems, 2015 , 8 pp., arXiv: 1509.00666
37.
L. D. Beklemishev, A. A. Onoprienko, “On some slowly terminating term rewriting systems”, Sb. Math., 206:9 (2015), 1173–1190
38.
L. D. Beklemishev, D. V. Musatov (eds.), Computer Science – Theory and Applications, 10th International Computer Science Symposium in Russia, CSR 2015, Listvyanka, Russia, July 13–17, 2015, Proceedings, Lecture Notes in Computer Science, 9139, Springer, 2015 , xx+443 pp.
L. D. Beklemishev, D. Fernández-Duque, J. J. Joosten, “On provability logics with linearly ordered modalities”, Studia Logica, 102:3 (2014), 541–566 , arXiv: 1210.4809
L. Beklemishev, D. Gabelaia, “Topological interpretations of provability logic”, Leo Esakia on duality in modal and intuitionistic logics, Outstanding Contributions to Logic, 4, eds. G. Bezhanishvili, Springer, 2014, 257–290 , arXiv: 1210.7317
Lev Beklemishev, Ruy De Queiroz, Andre Scedrov, “Editors' foreword”, Journal of Computer and System Sciences, 80:6, Special Issue: 18th Workshop on Logic, Language, Information and Computation (WoLLIC 2011) (2014), 1037
2013
44.
L. Beklemishev, D. Gabelaia, “Topological completeness of the provability logic GLP”, Ann. Pure Appl. Logic, 164:12 (2013), 1201–1223 , arXiv: 1106.5693
L. D. Beklemishev, “Pozitivnye logiki dokazuemosti”, Mezhdunarodnaya konferentsiya “Maltsevskie chteniya”. Tezisy dokladov (Novosibirsk, 11–15 noyabrya 2013 g.), FGBUN Institut matematiki im. S.L. Soboleva SO RAN; Novosibirskii gosudarstvennyi universitet, Novosibirsk, 2013, 10www.math.nsc.ru/conference/malmeet/13/maltsev13.pdf
2012
46.
L. D. Beklemishev, “Calibrating provability logic: from modal logic to reflection calculus”, Advances in Modal Logic, 9, eds. T. Bolander, T. Braüner, S. Ghilardi, L. Moss, College Publications, London, 2012, 89–94
47.
L. Beklemishev, “DKAL: A Distributed Knowledge Authorization Language and Its Logic of Information”, Computer Science – Theory and Applications. 7th International Computer Science Symposium in Russia, CSR 2012 (Nizhny Novgorod, Russia, July 3–7, 2012), Lecture Notes in Computer Science, 7353, eds. E. Hirsch, J. Karhumäki, A. Lepistö, M. Prilutskii, Springer, 2012, XIII–XIV
L. Beklemishev, G. Bezhanishvili, D. Mundici, Y. Venema, “Foreword [Special issue dedicated to the memory of Leo Esakia]”, Studia Logica, 100:1-2 (2012), 1–7
L. D. Beklemishev, “A simplified proof of arithmetical completeness theorem for provability logic GLP”, Proc. Steklov Inst. Math., 274:1 (2011), 25–33
51.
L. Beklemishev, “Ordinal completeness of bimodal provability logic GLB”, Logic, language, and computation, 8th International Tbilisi Symposium TbiLLC 2009, Lecture Notes in Comput. Sci., 6618, eds. N. Bezhanishvili et al., Springer, Heidelberg, 2011, 1–15
L. D. Beklemishev, V. M. Buchstaber, I. G. Lysenok, A. A. Mal'tsev, S. P. Novikov, A. A. Razborov, A. L. Semenov, “Sergei Ivanovich Adian (on his eightieth birthday)”, Russian Math. Surveys, 66:1 (2011), 197–198
53.
L. Beklemishev, R. de Queiroz (eds.), Logic, language, information, and computation, 18th International Workshop, WoLLIC 2011 (Philadelphia, PA, USA, May 18–20, 2011), Proceedings, Lecture Notes in Comput. Sci., 6642, Springer, 2011 , x+311 pp.
Algoritmicheskie voprosy algebry i logiki, Sbornik statei. K 80-letiyu so dnya rozhdeniya akademika Sergeya Ivanovicha Adyana, Trudy MIAN, 274, ed. L. D. Beklemishev, E. F. Mischenko, MAIK «Nauka/Interperiodika», M., 2011 , 351 pp.
55.
L. D. Beklemishev, “Foreword”, Proc. Steklov Inst. Math., 274 (2011), 1–3
56.
S. Adian, L. Beklemishev, A. Visser, “Proof and Computation”, J. Logic Computation, 21:4 (2011), 541–542
2010
57.
L. D. Beklemishev, “Gödel incompleteness theorems and the limits of their applicability. I”, Russian Math. Surveys, 65:5 (2010), 857–899
58.
L. D. Beklemishev, “Kripke semantics for provability logic GLP”, Ann. Pure Appl. Logic, 161:6 (2010), 756–774
L. Beklemishev, V. Goranko, V. Shehtman (eds.), Advances in Modal Logic, 8, College Publications, London, 2010 , ix+505 pp.
60.
L. Beklemishev, G. Bezhanishvili, T. Icard, “On topological models of GLP”, Ways of proof theory, Ontos Mathematical Logic, 2, eds. R. Schindler, Ontos Verlag, Frankfurt, 2010, 133–153
61.
L. Beklemishev, “On the Craig interpolation and the fixed point properties of GLP”, Proofs, categories and computations, Tributes, 13, eds. S. Feferman et al., College Publications, London, 2010, 49–60
2007
62.
L. Beklemishev, “Review of “Gödel's Theorem: an incomplete guide to its use and abuse” by Torkel Franzén”, Bulletin of Symbolic Logic, 13:2 (2007), 241–243
2006
63.
L. D. Beklemishev, “The Worm principle”, Logic Colloquium '02 (Münster, 2002), Lect. Notes Log., 27, Assoc. Symbol. Logic, La Jolla, CA, 2006, 75–95
64.
L. Beklemishev, A. Visser, “Problems in the logic of provability”, Mathematical problems from applied logic. I, Int. Math. Ser. (N. Y.), 4, Springer, New York, NY, 2006, 77–136
L. Beklemishev, “Representing Worms as a term rewriting system”, Logic, combinatorics and independence results, Oberwolfach Report, 52/2006, eds. A. Bovykin, L. Carlucci, A. Weiermann, Mathematisches Forschungsinstitut Oberwolfach, 2006, 7–9
66.
L. D. Beklemishev, I. G. Lysenok, A. A. Mal'tsev, S. P. Novikov, M. R. Pentus, A. A. Razborov, A. L. Semenov, V. A. Uspenskii, “Sergei Ivanovich Adian (on his 75th birthday)”, Russian Math. Surveys, 61:3 (2006), 575–588
67.
L. Beklemishev, “Review of “David Hilbert and the axiomatization of physics (1898–-1918)” by Leo Corry”, Studies In History and Philosophy of Science, Part B: Studies In History and Philosophy of Modern Physics, 37:2 (2006), 388–390
2005
68.
L. D. Beklemishev, A. Visser, “On the limit existence principles in elementary arithmetic and $\Sigma^0_n$-consequences of theories”, Ann. Pure Appl. Logic, 136:1-2 (2005), 56–74
L. D. Beklemishev, J. J. Joosten, M. Vervoort, “A finitary treatment of the closed fragment of Japaridze's provability logic”, J. Logic Comput., 15:4 (2005), 447–463
L. Beklemishev, “Review of “On the arithmetical content of restricted forms of comprehension, choice and general uniform boundedness” by U. Kohlenbach”, Bulletin of Symbolic Logic, 7:1 (2001), 75–77
L. D. Beklemishev, “Open least element principle and bounded query computation”, Computer science logic (Madrid, 1999), Lecture Notes in Comput. Sci., 1683, Springer, Berlin, 1999, 389–404
L. D. Beklemishev, Skhemy refleksii v formalnoi arifmetike, Diss. … dokt. fiz.-matem. nauk, Matematicheskii institut im. V.A. Steklova, Moskva, 1998 , 149 pp.
85.
L. Beklemishev, “Review of “Aspects of Incompleteness” by P. Lindström”, The Journal of Symbolic Logic, 63:4 (1998), 1606–1608
1997
86.
L. Beklemishev, “Notes on local reflection principles”, Theoria, 63:3 (1997), 139–146
L. D. Beklemishev, “Parameter free induction and reflection”, Computational logic and proof theory (Vienna, 1997), Lecture Notes in Comput. Sci., 1289, Springer, Berlin, 1997, 103–113
L. Beklemishev, “Remarks on Magari algebras of $\mathrm{PA}$ and $\mathrm{I}\Delta_0+\mathrm{EXP}$”, Logic and algebra (Pontignano, 1994), Lecture Notes in Pure and Appl. Math., 180, Marcel Dekker, New York, 1996, 317–325
90.
L. D. Beklemishev, “Bimodal logics for extensions of arithmetical theories”, J. Symbolic Logic, 61:1 (1996), 91–124
L. D. Beklemishev, “Ob ogranichennom pravile induktsii i iterirovannykh skhemakh refleksii nad kalmarovskoi elementarnoi arifmetikoi”, Teoreticheskie i prikladnye aspekty matematicheskikh issledovanii, eds. O. B. Lupanov, MGU, Moskva, 1995, 36–39
1994
94.
L. D. Beklemishev, “On bimodal logics of provability”, Ann. Pure Appl. Logic, 68:2 (1994), 115–159
Отдел математической логики L. D. Beklemishev Conference MIAN-90, dedicated to the 90th anniversary of Steklov Mathematical Institute May 15, 2024 10:00
Lecture 13. Provability and Formal Arithmetic L. D. Beklemishev, T. L. Yavorskaya Course by L. D. Beklemishev and T. L. Yavorskaya "Provability and Formal Arithmetic II" December 12, 2023 16:45
21.
Lecture 12. Provability and Formal Arithmetic L. D. Beklemishev, T. L. Yavorskaya Course by L. D. Beklemishev and T. L. Yavorskaya "Provability and Formal Arithmetic II" December 5, 2023 16:45
22.
Lecture 11. Provability and Formal Arithmetic L. D. Beklemishev, T. L. Yavorskaya Course by L. D. Beklemishev and T. L. Yavorskaya "Provability and Formal Arithmetic II" November 21, 2023 16:45
23.
Lecture 10. Provability and Formal Arithmetic L. D. Beklemishev, T. L. Yavorskaya Course by L. D. Beklemishev and T. L. Yavorskaya "Provability and Formal Arithmetic II" November 14, 2023 16:45
24.
Lecture 9. Provability and Formal Arithmetic L. D. Beklemishev, T. L. Yavorskaya Course by L. D. Beklemishev and T. L. Yavorskaya "Provability and Formal Arithmetic II" November 7, 2023 16:45
25.
Lecture 8. Provability and Formal Arithmetic L. D. Beklemishev, T. L. Yavorskaya Course by L. D. Beklemishev and T. L. Yavorskaya "Provability and Formal Arithmetic II" October 31, 2023 16:45
26.
Lecture 7. Provability and Formal Arithmetic L. D. Beklemishev, T. L. Yavorskaya Course by L. D. Beklemishev and T. L. Yavorskaya "Provability and Formal Arithmetic II" October 24, 2023 16:45
27.
Lecture 6. Provability and Formal Arithmetic L. D. Beklemishev, T. L. Yavorskaya Course by L. D. Beklemishev and T. L. Yavorskaya "Provability and Formal Arithmetic II" October 17, 2023 16:45
28.
Lecture 5. Provability and Formal Arithmetic L. D. Beklemishev, T. L. Yavorskaya Course by L. D. Beklemishev and T. L. Yavorskaya "Provability and Formal Arithmetic II" October 10, 2023 16:45
29.
Lecture 4. Provability and Formal Arithmetic L. D. Beklemishev, T. L. Yavorskaya Course by L. D. Beklemishev and T. L. Yavorskaya "Provability and Formal Arithmetic II" October 3, 2023 16:45
Lecture 3. Provability and Formal Arithmetic L. D. Beklemishev, T. L. Yavorskaya Course by L. D. Beklemishev and T. L. Yavorskaya "Provability and Formal Arithmetic II" September 26, 2023 16:45
32.
Lecture 2. Provability and Formal Arithmetic L. D. Beklemishev, T. L. Yavorskaya Course by L. D. Beklemishev and T. L. Yavorskaya "Provability and Formal Arithmetic II" September 19, 2023 16:45
33.
Lecture 1. Provability and Formal Arithmetic L. D. Beklemishev, T. L. Yavorskaya Course by L. D. Beklemishev and T. L. Yavorskaya "Provability and Formal Arithmetic II" September 12, 2023 16:45
Лекция 18. Интуиционистская арифметика L. D. Beklemishev L. D. Beklemishev, S. L. Kuznetsov. Computational proof theory and lambda calculus April 14, 2020 16:30
Лекция 11. Модели лямбда-исчисления L. D. Beklemishev, S. L. Kuznetsov L. D. Beklemishev, S. L. Kuznetsov. Computational proof theory and lambda calculus February 10, 2020 16:30
96.
Лекция 10. Комбинаторная логика L. D. Beklemishev L. D. Beklemishev, S. L. Kuznetsov. Computational proof theory and lambda calculus December 9, 2019 16:30
Positive provability logic and reflection calculus L. D. Beklemishev Mathematical Logic, Algebra and Computation: A two-day conference dedicated to 85-th anniversary of S. I. Adian July 19, 2016 11:00
Provability algebra and sparse topology L. D. Beklemishev Traditional Christmas session MIAN-POMI, 2009 "Logic and Theoretical Computer Science" December 17, 2009 12:50
Algorithmic aspects of algebra and logic, Collected papers. Dedicated to Academician Sergei Ivanovich Adian on the occasion of his 80th birthday, Trudy Mat. Inst. Steklova, 274, ed. L. D. Beklemishev, E. F. Mishchenko, 2011, 351 с. http://mi.mathnet.ru/book1359
2025
Contact us: