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)
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)
3.
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
4.
L. D. Beklemishev, “Conservativity spectra and Joosten–Fernández model”, Dokl. Math., 106:1 (2022), 213–217
5.
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
7.
E. A. Kolmakov, L. D. Beklemishev, “Axiomatization of provable $n$-provability”, J. Symb. Log., 84:2 (2019), 849–869
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
10.
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
17.
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
18.
L. D. Beklemishev, A. A. Onoprienko, “On some slowly terminating term rewriting systems”, Sb. Math., 206:9 (2015), 1173–1190
19.
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
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, “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
25.
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. D. Beklemishev, “A simplified proof of arithmetical completeness theorem for provability logic GLP”, Proc. Steklov Inst. Math., 274:1 (2011), 25–33
27.
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. 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
31.
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
32.
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
33.
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
35.
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. 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, “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
52.
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
55.
L. D. Beklemishev, “On bimodal logics of provability”, Ann. Pure Appl. Logic, 68:2 (1994), 115–159
L. D. Beklemishev, “On the classification of propositional provability logics”, Math. USSR-Izv., 35:2 (1990), 247–275
61.
L. D. Beklemishev, “Provability logic without Craig's interpolation property”, Math. Notes, 45:6 (1989), 437–450
62.
L. D. Beklemishev, “Normalization of deductions and interpolation for some logics of provability”, Russian Math. Surveys, 42:6 (1987), 223–224
Books
63.
L. Beklemishev, V. Goranko, V. Shehtman (eds.), Advances in Modal Logic, 8, College Publications, London, 2010 , ix+505 pp.
64.
L. Beklemishev, M. Pentus, N. Vereshchagin, Provability, complexity, grammars, Amer. Math. Soc. Transl. Ser. 2, 192, Amer. Math. Soc., Providence, RI, 1999 , x+172 pp.
Thesis
65.
L. D. Beklemishev, Skhemy refleksii v formalnoi arifmetike, Diss. … dokt. fiz.-matem. nauk, Matematicheskii institut im. V.A. Steklova, Moskva, 1998 , 149 pp.
66.
L. D. Beklemishev, Klassifikatsiya propozitsionalnykh logik dokazuemosti, Diss. … kand. fiz.-matem. nauk, Matematicheskii institut im. V.A. Steklova RAN, Moskva, 1992
Proceedings
67.
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
68.
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
L. Beklemishev, A. Dmitrieva, J. Makowsky, Axiomatizing Origami planes, 2020 , 25 pp., arXiv: 2012.03250
72.
Lev D. Beklemishev, Fedor N. Pakhomov, Reflection algebras and conservation results for theories of iterated truth, 2019 , 48 pp., arXiv: 1908.10302
73.
L. D. Beklemishev, A universal Kripke frame for the variable-free fragment of $RC^\nabla$, 2018 , 5 pp., arXiv: 1804.02641
74.
Lev D. Beklemishev, Reflection calculus and conservativity spectra, 2017 , 28 pp., arXiv: 1703.09314
75.
L. D. Beklemishev, Notes on a reduction property for GLP-algebras, 2016 , 8 pp., arXiv: 1606.00290
76.
Gerald Berger, Lev D. Beklemishev, Hans Tompits, A Many-Sorted Variant of Japaridze's Polymodal Provability Logic, 2016 , 15 pp., arXiv: 1601.02857
77.
L. D. Beklemishev, A note on strictly positive logics and word rewriting systems, 2015 , 8 pp., arXiv: 1509.00666
Popular science or education materials
78.
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/
Information matherials
79.
L. D. Beklemishev, Mat. Pros., 28, MCCME, Moscow, 2021, 9–14
80.
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
Personalia
81.
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
82.
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
83.
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
84.
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
85.
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
86.
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
87.
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
Critic, bibliography
88.
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
89.
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
90.
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
91.
L. Beklemishev, “Review of “Aspects of Incompleteness” by P. Lindström”, The Journal of Symbolic Logic, 63:4 (1998), 1606–1608
92.
L. Beklemishev, “Review of “Diagonalization and Self-reference” by R. Smullyan”, The Journal of Symbolic Logic, 61:3 (1996), 1052–1055
93.
L. Beklemishev, “Review of papers by D. de Jongh, F. Montagna, and A. Carbone”, The Journal of Symbolic Logic, 58 (1993), 715–717
Advances in Modal Logic, v. 11, eds. Lev Beklemishev, Stephane Demri, Andras Mate, College Publications, London, 2016 , xii+570 pp.
96.
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.
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
98.
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. 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.
101.
L. D. Beklemishev, “Foreword”, Proc. Steklov Inst. Math., 274 (2011), 1–3
102.
S. Adian, L. Beklemishev, A. Visser, “Proof and Computation”, J. Logic Computation, 21:4 (2011), 541–542
103.
S. I. Adian, M. Baaz, L. D. Beklemishev, “Editorial”, J. Logic Computation, 15:4 (2005), 409; arXiv: 2407.10198; ;
Отдел математической логики 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
Contact us: