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
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, 91–109; arXiv: 2407.10198
3.
L. D. Beklemishev, D. S. Shamkanov, I. N. Smirnov, “Fragments of arithmetic and cyclic proofs”, Mat. Sb.
2024
4.
Lev D. Beklemishev, Yunsong Wang, Periodic frames, 2024 , 32 pp., arXiv: 2407.10190
5.
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
2022
6.
L. D. Beklemishev, “Conservativity spectra and Joosten–Fernández model”, Dokl. Math., 106:1 (2022), 213–217
7.
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
2020
9.
L. Beklemishev, A. Dmitrieva, J. Makowsky, Axiomatizing Origami planes, 2020 , 25 pp., arXiv: 2012.03250
2019
10.
Lev D. Beklemishev, Fedor N. Pakhomov, Reflection algebras and conservation results for theories of iterated truth, 2019 , 48 pp., arXiv: 1908.10302
11.
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
14.
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
L. D. Beklemishev, Notes on a reduction property for GLP-algebras, 2016 , 8 pp., arXiv: 1606.00290
24.
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
25.
Gerald Berger, Lev D. Beklemishev, Hans Tompits, A Many-Sorted Variant of Japaridze's Polymodal Provability Logic, 2016 , 15 pp., arXiv: 1601.02857
26.
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
2015
27.
L. D. Beklemishev, A note on strictly positive logics and word rewriting systems, 2015 , 8 pp., arXiv: 1509.00666
28.
L. D. Beklemishev, A. A. Onoprienko, “On some slowly terminating term rewriting systems”, Sb. Math., 206:9 (2015), 1173–1190
2014
29.
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, “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
35.
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
36.
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
39.
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, V. Goranko, V. Shehtman (eds.), Advances in Modal Logic, 8, College Publications, London, 2010 , ix+505 pp.
43.
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
44.
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
2006
45.
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
46.
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
2005
48.
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, Skhemy refleksii v formalnoi arifmetike, Diss. … dokt. fiz.-matem. nauk, Matematicheskii institut im. V.A. Steklova, Moskva, 1998 , 149 pp.
1997
63.
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
67.
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
70.
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
1989
77.
L. D. Beklemishev, “Provability logic without Craig's interpolation property”, Math. Notes, 45:6 (1989), 437–450
1987
78.
L. D. Beklemishev, “Normalization of deductions and interpolation for some logics of provability”, Russian Math. Surveys, 42:6 (1987), 223–224
Presentations in Math-Net.Ru
1.
Lecture 10. Non-Standard Models of Arithmetic L. D. Beklemishev, S. O. Speranski Course by L. D. Beklemishev and S. O. Speranski "Non-Standard Models of Arithmetic" December 2, 2025 16:00
2.
Lecture 9. Non-standard models of arithmetic L. D. Beklemishev, S. O. Speranski Course by L. D. Beklemishev and S. O. Speranski "Non-Standard Models of Arithmetic" November 25, 2025 16:00
3.
Lecture 8. Non-standard models of arithmetic L. D. Beklemishev, S. O. Speranski Course by L. D. Beklemishev and S. O. Speranski "Non-Standard Models of Arithmetic" November 18, 2025 16:00
4.
Lecture 7. Non-standard models of arithmetic L. D. Beklemishev, S. O. Speranski Course by L. D. Beklemishev and S. O. Speranski "Non-Standard Models of Arithmetic" November 11, 2025 16:00
5.
Lecture 6. Non-standard models of arithmetic L. D. Beklemishev, S. O. Speranski Course by L. D. Beklemishev and S. O. Speranski "Non-Standard Models of Arithmetic" October 28, 2025 16:00
6.
Lecture 5. Non-standard models of arithmetic L. D. Beklemishev, S. O. Speranski Course by L. D. Beklemishev and S. O. Speranski "Non-Standard Models of Arithmetic" October 21, 2025 16:00
7.
Lecture 4. Non-standard models of arithmetic L. D. Beklemishev, S. O. Speranski Course by L. D. Beklemishev and S. O. Speranski "Non-Standard Models of Arithmetic" October 7, 2025 16:00
8.
Lecture 3. Non-standard models of arithmetic L. D. Beklemishev, S. O. Speranski Course by L. D. Beklemishev and S. O. Speranski "Non-Standard Models of Arithmetic" September 30, 2025 16:00
9.
Lecture 2. Non-standard models of arithmetic L. D. Beklemishev, S. O. Speranski Course by L. D. Beklemishev and S. O. Speranski "Non-Standard Models of Arithmetic" September 23, 2025 16:00
10.
Lecture 1. Non-standard models of arithmetic L. D. Beklemishev, S. O. Speranski Course by L. D. Beklemishev and S. O. Speranski "Non-Standard Models of Arithmetic" September 16, 2025 16:00
Отдел математической логики 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
50.
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
51.
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
52.
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
53.
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
54.
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
55.
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
56.
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
57.
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
58.
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
61.
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
62.
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
125.
Лекция 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