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 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 (cited: 1)
2.
L. D. Beklemishev, “Reflection calculus and conservativity spectra”, Russian Math. Surveys, 73:4 (2018), 569–613
3.
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 (cited: 2)
4.
Gerald Berger, L. D. Beklemishev, Hans Tompits, “A many-sorted variant of Japaridze's polymodal provability logic”, Log. J. IGPL, 26:5 (2018), 505–538
5.
L. D. Beklemishev, A universal Kripke frame for the variable-free fragment of RC∇, 2018 , 5 pp., arXiv: 1804.02641
6.
E. A. Kolmakov, L. D. Beklemishev, “Axiomatizing provable $n$-provability”, Dokl. Math., 98:3 (2018), 582–585
2017
7.
Lev D. Beklemishev, Reflection calculus and conservativity spectra, 2017 , 28 pp., arXiv: 1703.09314
8.
L. D. Beklemishev, “On the Reduction Property for GLP-Algebras”, Dokl. Math., 95:1 (2017), 50–54 (cited: 3) (cited: 3)
9.
Lev D. Beklemishev, “On the reflection calculus with partial conservativity operators”, Lecture Notes in Comput. Sci., 10388, 2017, 48–67 (cited: 3) (cited: 4)
2016
10.
L. D. Beklemishev, “Proof theoretic analysis by iterated reflection”, Turing's revolution, Part II, Birkhäuser/Springer, Cham, 2016, 225–270 (cited: 1)
11.
Lev Beklemishev, Tommaso Flaminio, “Franco Montagna's work on provability logic and many-valued logic”, Studia Logica, 104:1 (2016), 1–46
12.
L. D. Beklemishev, Notes on a reduction property for GLP-algebras, 2016 , 8 pp., arXiv: 1606.00290
13.
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
14.
Gerald Berger, Lev D. Beklemishev, Hans Tompits, A Many-Sorted Variant of Japaridze's Polymodal Provability Logic, 2016 , 15 pp., arXiv: 1601.02857
15.
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
16.
Advances in Modal Logic, v. 11, eds. Lev Beklemishev, Stephane Demri, Andras Mate, College Publications, London, 2016 , xii+570 pp.
2015
17.
L. D. Beklemishev, A note on strictly positive logics and word rewriting systems, 2015 , 8 pp., arXiv: 1509.00666
18.
L. D. Beklemishev, A. A. Onoprienko, “On some slowly terminating term rewriting systems”, Sb. Math., 206:9 (2015), 1173–1190 (cited: 3) (cited: 4)
19.
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.
2014
20.
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 (cited: 9) (cited: 1)
21.
L. Beklemishev, “Positive provability logic for uniform reflection principles”, Ann. Pure Appl. Logic, 165:1 (2014), 82–105 (cited: 7) (cited: 5)
22.
L. Beklemishev, Y. Gurevich, “Propositional primal logic with disjunction”, J. Logic Comput., 24:1 (2014), 257–282 (cited: 6) (cited: 5) (cited: 10)
23.
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
24.
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
25.
L. Beklemishev, D. Gabelaia, “Topological completeness of the provability logic GLP”, Ann. Pure Appl. Logic, 164:12 (2013), 1201–1223 , arXiv: 1106.5693 (cited: 11) (cited: 4) (cited: 8)
26.
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
27.
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
28.
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
29.
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 (cited: 9) (cited: 3) (cited: 3) (cited: 6)
32.
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 (cited: 4) (cited: 3)
33.
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
34.
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.
35.
Algoritmicheskie voprosy algebry i logiki, Sbornik statei. K 80-letiyu so dnya rozhdeniya akademika Sergeya Ivanovicha Adyana, Tr. MIAN, 274, ed. L. D. Beklemishev, E. F. Mischenko, MAIK «Nauka/Interperiodika», M., 2011 , 351 pp.
36.
L. D. Beklemishev, “Foreword”, Proc. Steklov Inst. Math., 274 (2011), 1–3 (cited: 8) (cited: 8)
37.
S. Adian, L. Beklemishev, A. Visser, “Proof and Computation”, J. Logic Computation, 21:4 (2011), 541–542
2010
38.
L. D. Beklemishev, “Gödel incompleteness theorems and the limits of their applicability. I”, Russian Math. Surveys, 65:5 (2010), 857–899 (cited: 1) (cited: 1) (cited: 1) (cited: 2)
39.
L. D. Beklemishev, “Kripke semantics for provability logic GLP”, Ann. Pure Appl. Logic, 161:6 (2010), 756–774 (cited: 14) (cited: 11) (cited: 15)
40.
L. Beklemishev, V. Goranko, V. Shehtman (eds.), Advances in Modal Logic, 8, College Publications, London, 2010 , ix+505 pp.
41.
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
42.
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
43.
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
44.
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 (cited: 11)
45.
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
46.
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
47.
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
48.
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
49.
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 (cited: 9) (cited: 5) (cited: 8)
50.
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 (cited: 14) (cited: 3) (cited: 17)
51.
L. D. Beklemishev, “Reflection principles and provability algebras in formal arithmetic”, Russian Math. Surveys, 60:2 (2005), 197–268 (cited: 29) (cited: 21) (cited: 21) (cited: 35)
52.
S. I. Adian, M. Baaz, L. D. Beklemishev, “Editorial”, J. Logic Computation, 15:4 (2005), 409
2004
53.
L. D. Beklemishev, “Provability algebras and proof-theoretic ordinals. I”, Ann. Pure Appl. Logic, 128:1-3 (2004), 103–123 (cited: 37) (cited: 28) (cited: 40)
2003
54.
L. D. Beklemishev, “Proof-theoretic analysis by iterated reflection”, Arch. Math. Logic, 42:6 (2003), 515–552 (cited: 22) (cited: 16) (cited: 23)
55.
L. D. Beklemishev, “On the induction schema for decidable predicates”, J. Symbolic Logic, 68:1 (2003), 17–34 (cited: 8) (cited: 6) (cited: 7)
56.
L. D. Beklemishev, “Quantifier-Free Induction Schema and the Least Element Principle”, Proc. Steklov Inst. Math., 242 (2003), 50–66
2002
57.
A. L. Rastsvetaev, L. D. Beklemishev, “On the query complexity of finding a local maximum point”, Inform. Process. Lett., 84:6 (2002), 327–332 (cited: 2) (cited: 2)
2001
58.
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 (cited: 3)
61.
L. D. Beklemishev, “Classification of propositional provability logics”, Provability, complexity, grammars, Amer. Math. Soc. Transl. Ser. 2, 192, Amer. Math. Soc., Providence, RI, 1999, 1–56
62.
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.
63.
L. D. Beklemishev, “Parameter free induction and provably total computable functions”, Theoret. Comput. Sci., 224:1-2 (1999), 13–33 (cited: 13) (cited: 13) (cited: 15)
1998
64.
L. D. Beklemishev, “A proof-theoretic analysis of collection”, Arch. Math. Logic, 37:5-6 (1998), 275–296 (cited: 19) (cited: 18) (cited: 20)
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. Beklemishev, “Review of “Aspects of Incompleteness” by P. Lindström”, The Journal of Symbolic Logic, 63:4 (1998), 1606–1608
1997
67.
L. Beklemishev, “Notes on local reflection principles”, Theoria, 63:3 (1997), 139–146 (cited: 8)
68.
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
69.
L. D. Beklemishev, “Induction rules, reflection principles, and provably recursive functions”, Ann. Pure Appl. Logic, 85:3 (1997), 193–242 (cited: 28) (cited: 28) (cited: 31)
1996
70.
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 (cited: 3)
71.
L. D. Beklemishev, “Bimodal logics for extensions of arithmetical theories”, J. Symbolic Logic, 61:1 (1996), 91–124 (cited: 3) (cited: 7) (cited: 7)
72.
L. Beklemishev, “Review of “Diagonalization and Self-reference” by R. Smullyan”, The Journal of Symbolic Logic, 61:3 (1996), 1052–1055
1995
73.
L. Beklemishev, “Iterated local reflection versus iterated consistency”, Ann. Pure Appl. Logic, 75:1-2 (1995), 25–48 (cited: 11) (cited: 5) (cited: 11)
74.
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
75.
L. D. Beklemishev, “On bimodal logics of provability”, Ann. Pure Appl. Logic, 68:2 (1994), 115–159 (cited: 6) (cited: 4) (cited: 8)
1993
76.
S. N. Artemov, L. D. Beklemishev, “On propositional quantifiers in provability logic”, Notre Dame J. Formal Logic, 34:3 (1993), 401–419
77.
L. D. Beklemishev, “On the complexity of arithmetical interpretations of modal formulae”, Arch. Math. Logic, 32:3 (1993), 229–238 (cited: 4) (cited: 1) (cited: 5)
78.
L. Beklemishev, “Review of papers by D. de Jongh, F. Montagna, and A. Carbone”, The Journal of Symbolic Logic, 58 (1993), 715–717 (cited: 5)
1992
79.
L. D. Beklemishev, “Independent enumerations of theories and recursive progressions”, Siberian Math. J., 33:5 (1992), 760–783 (cited: 1) (cited: 2)
80.
L. D. Beklemishev, Klassifikatsiya propozitsionalnykh logik dokazuemosti, Diss. … kand. fiz.-matem. nauk, Matematicheskii institut im. V.A. Steklova RAN, Moskva, 1992
1991
81.
L. D. Beklemishev, “Provability logics for natural Turing progressions of arithmetical theories”, Studia Logica, 50:1 (1991), 107–128 (cited: 2) (cited: 6)
1990
82.
L. D. Beklemishev, “On the classification of propositional provability logics”, Math. USSR-Izv., 35:2 (1990), 247–275
1989
83.
L. D. Beklemishev, “Provability logic without Craig's interpolation property”, Math. Notes, 45:6 (1989), 437–450
1987
84.
L. D. Beklemishev, “Normalization of deductions and interpolation for some logics of provability”, Russian Math. Surveys, 42:6 (1987), 223–224
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
О позитивных логиках доказуемости L. D. Beklemishev Seminar of the Department of Mathematical Logic "Algorithmic problems in algebra and logic" December 10, 2013 18:30
43.
Probably recursive functions L. D. Beklemishev Colloquium of the Steklov Mathematical Institute of Russian Academy of Sciences December 5, 2013 16: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, Tr. Mat. Inst. Steklova, 274, ed. L. D. Beklemishev, E. F. Mishchenko, 2011, 351 с. http://mi.mathnet.ru/book1359
2018
Terms of Use