Доказана теорема о классификации пропозициональных логик доказуемости. Получена характеризация ограниченных правил индукции в арифметике в терминах итерированных схем рефлексии. Найдены классы доказуемо тотальных вычислимых функций для фрагментов арифметики с беспараметрической индукцией. В частности, беспараметрическая индукция для Π2-формул соответствует классу примитивно рекурсивных функций. Предложен подход к ординальной теории доказательств на основе понятия алгебры доказуемости.
Научная биография:
Окончил механико-математический факультет МГУ в 1989 г. (кафедра математической логики и теории алгоритмов). В 1989–92 гг. — аспирант, с 1992 г. — сотрудник МИАН им. В. А. Стеклова. Кандидатская диссертация — 1992 г. Название: Классификация пропозициональных логик доказуемости. Докторская диссертация — 1998 г. Название: Схемы рефлексии в формальной арифметике.
В 2000–05 гг. сотрудник Утрехтского университета (Нидерланды).
Премия Московского математического общества для молодых ученых присуждена в 1994 г. за работу «О классификации пропозициональных логик доказуемости». Стипендия А. Гумбольдта (Германия) присуждена в 1998 г. В 2006 г. избран членом-корреспондентом РАН.
Основные публикации:
Л. Д. Беклемишев, “О классификации пропозициональных логик доказуемости”, Изв. АН СССР, сер. матем., 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
Л. Д. Беклемишев, “Схемы рефлексии и алгебры доказуемости в формальной арифметике”, Успехи математических наук, 60:2 (2005), 3–78; English transl. Russian Mathematical Surveys, 60:2 (2005), 197–268
Lev D. Beklemishev, “A universal algebra for the variable-free fragment of $RC^\nabla$”, Logical Foundations of Computer Science, International Symposium, LFCS 2018 (Deerfield Beach, FL, USA, January 8–11, 2018), Lecture Notes in Comput. Sci., 10703, eds. Sergei Artemov, Anil Nerode, Springer, Berlin, Heidelberg, 2018, 91–106 (cited: 1)
2.
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
3.
Gerald Berger, L. D. Beklemishev, Hans Tompits, “A many-sorted variant of Japaridze's polymodal provability logic”, Log. J. IGPL, 2018, jzy012 (Published online)
4.
Л. Д. Беклемишев, “Исчисление для схем рефлексии и спектры консервативности”, УМН, 73:4(442) (2018), 3–52
2017
5.
Lev D. Beklemishev, Reflection calculus and conservativity spectra, 2017 , 28 pp., arXiv: 1703.09314
6.
Л. Д. Беклемишев, “О свойстве редукции для $GLP$-алгебр”, Докл. РАН, 472:4 (2017), 378–382 (цит.: 1) (цит.: 1) ; L. D. Beklemishev, “On the Reduction Property for GLP-Algebras”, Dokl. Math., 95:1 (2017), 50–54 (cited: 1) (cited: 1)
7.
Lev D. Beklemishev, “On the reflection calculus with partial conservativity operators”, Lecture Notes in Comput. Sci., 10388, 2017, 48–67 (cited: 1) (cited: 2)
2016
8.
L. D. Beklemishev, “Proof theoretic analysis by iterated reflection”, Turing's revolution, Part II, Birkhäuser/Springer, Cham, 2016, 225–270
9.
Lev Beklemishev, Tommaso Flaminio, “Franco Montagna's work on provability logic and many-valued logic”, Studia Logica, 104:1 (2016), 1–46
10.
L. D. Beklemishev, Notes on a reduction property for GLP-algebras, 2016 , 8 pp., arXiv: 1606.00290
11.
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
12.
Gerald Berger, Lev D. Beklemishev, Hans Tompits, A Many-Sorted Variant of Japaridze's Polymodal Provability Logic, 2016 , 15 pp., arXiv: 1601.02857
13.
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
14.
Advances in Modal Logic, v. 11, eds. Lev Beklemishev, Stephane Demri, Andras Mate, College Publications, London, 2016 , xii+570 pp.
2015
15.
L. D. Beklemishev, A note on strictly positive logics and word rewriting systems, 2015 , 8 pp., arXiv: 1509.00666
16.
Л. Д. Беклемишев, А. А. Оноприенко, “О некоторых медленно сходящихся системах преобразований термов”, Матем. сб., 206:9 (2015), 3–20 (цит.: 3) (цит.: 2) ; L. D. Beklemishev, A. A. Onoprienko, “On some slowly terminating term rewriting systems”, Sb. Math., 206:9 (2015), 1173–1190 (cited: 2) (cited: 3)
17.
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
18.
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: 5) (cited: 6) (cited: 1)
19.
L. Beklemishev, “Positive provability logic for uniform reflection principles”, Ann. Pure Appl. Logic, 165:1 (2014), 82–105 (cited: 1) (cited: 3) (cited: 1)
20.
L. Beklemishev, Y. Gurevich, “Propositional primal logic with disjunction”, J. Logic Comput., 24:1 (2014), 257–282 (cited: 2) (cited: 5) (cited: 5) (cited: 9)
21.
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
22.
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
23.
L. Beklemishev, D. Gabelaia, “Topological completeness of the provability logic GLP”, Ann. Pure Appl. Logic, 164:12 (2013), 1201–1223 , arXiv: 1106.5693 (cited: 3) (cited: 9) (cited: 4) (cited: 6)
24.
Л. Д. Беклемишев, “Позитивные логики доказуемости”, Международная конференция “Мальцевские чтения”. Тезисы докладов (Новосибирск, 11–15 ноября 2013 г.), ФГБУН Институт математики им. С.Л. Соболева СО РАН; Новосибирский государственный университет, Новосибирск, 2013, 10www.math.nsc.ru/conference/malmeet/13/maltsev13.pdf
2012
25.
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
26.
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
27.
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
Л. Д. Беклемишев, “Упрощëнное доказательство теоремы об арифметической полноте для логики доказуемости GLP”, Тр. МИАН, 274, 2011, 32–40 (цит.: 7) (цит.: 3) (цит.: 7) (цит.: 2); L. D. Beklemishev, “A simplified proof of arithmetical completeness theorem for provability logic GLP”, Proc. Steklov Inst. Math., 274:1 (2011), 25–33 (cited: 7) (cited: 3) (cited: 4)
30.
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: 3) (cited: 3) (cited: 3)
31.
Л. Д. Беклемишев, В. М. Бухштабер, И. Г. Лысëнок, А. А. Мальцев, С. П. Новиков, А. А. Разборов, А. Л. Семëнов, “Сергей Иванович Адян (к восьмидесятилетию со дня рождения)”, УМН, 66:1(397) (2011), 199–200; 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
32.
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.
33.
Алгоритмические вопросы алгебры и логики, Сборник статей. К 80-летию со дня рождения академика Сергея Ивановича Адяна, Тр. МИАН, 274, ред. Л. Д. Беклемишев, Е. Ф. Мищенко, МАИК «Наука/Интерпериодика», М., 2011 , 351 с.
34.
Л. Д. Беклемишев, “Предисловие”, Алгоритмические вопросы алгебры и логики, Сборник статей. К 80-летию со дня рождения академика Сергея Ивановича Адяна, Тр. МИАН, 274, МАИК, М., 2011, 7–9; L. D. Beklemishev, “Foreword”, Proc. Steklov Inst. Math., 274 (2011), 1–3 (cited: 6) (cited: 6)
35.
S. Adian, L. Beklemishev, A. Visser, “Proof and Computation”, J. Logic Computation, 21:4 (2011), 541–542
2010
36.
Л. Д. Беклемишев, “Теоремы Гëделя о неполноте и границы их применимости. I”, УМН, 65:5(395) (2010), 61–106 (цит.: 2) (цит.: 1) (цит.: 7); 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: 2)
37.
L. D. Beklemishev, “Kripke semantics for provability logic GLP”, Ann. Pure Appl. Logic, 161:6 (2010), 756–774 (cited: 9) (cited: 12) (cited: 11) (cited: 13)
38.
L. Beklemishev, V. Goranko, V. Shehtman (eds.), Advances in Modal Logic, 8, College Publications, London, 2010 , ix+505 pp. (cited: 1)
39.
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 (cited: 4)
40.
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 (cited: 3)
2007
41.
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
42.
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: 9) (cited: 9)
43.
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 (cited: 4)
44.
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
45.
Л. Д. Беклемишев, И. Г. Лысëнок, А. А. Мальцев, С. П. Новиков, М. Р. Пентус, А. А. Разборов, А. Л. Семëнов, В. А. Успенский, “Сергей Иванович Адян (к 75-летию со дня рождения)”, УМН, 61:3(369) (2006), 179–191; 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
46.
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
47.
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: 5) (cited: 8) (cited: 5) (cited: 7)
48.
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: 10) (cited: 13) (cited: 3) (cited: 16)
49.
Л. Д. Беклемишев, “Схемы рефлексии и алгебры доказуемости в формальной арифметике”, УМН, 60:2(362) (2005), 3–78 (цит.: 32) (цит.: 17) (цит.: 26) ; L. D. Beklemishev, “Reflection principles and provability algebras in formal arithmetic”, Russian Math. Surveys, 60:2 (2005), 197–268 (cited: 26) (cited: 21) (cited: 32)
50.
S. I. Adian, M. Baaz, L. D. Beklemishev, “Editorial”, J. Logic Computation, 15:4 (2005), 409
2004
51.
L. D. Beklemishev, “Provability algebras and proof-theoretic ordinals. I”, Ann. Pure Appl. Logic, 128:1-3 (2004), 103–123 (cited: 22) (cited: 32) (cited: 28) (cited: 36)
2003
52.
L. D. Beklemishev, “Proof-theoretic analysis by iterated reflection”, Arch. Math. Logic, 42:6 (2003), 515–552 (cited: 13) (cited: 20) (cited: 16) (cited: 21)
53.
L. D. Beklemishev, “On the induction schema for decidable predicates”, J. Symbolic Logic, 68:1 (2003), 17–34 (cited: 8) (cited: 8) (cited: 6) (cited: 7)
54.
Л. Д. Беклемишев, “Бескванторная индукция и принцип наименьшего числа”, Математическая логика и алгебра, Сборник статей. К 100-летию со дня рождения академика Петра Сергеевича Новикова, Тр. МИАН, 242, Наука, М., 2003, 59–76 (цит.: 2) ; L. D. Beklemishev, “Quantifier-Free Induction Schema and the Least Element Principle”, Proc. Steklov Inst. Math., 242 (2003), 50–66
2002
55.
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) (cited: 2)
2001
56.
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) (cited: 3)
59.
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
60.
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. (cited: 1)
61.
L. D. Beklemishev, “Parameter free induction and provably total computable functions”, Theoret. Comput. Sci., 224:1-2 (1999), 13–33 (cited: 11) (cited: 12) (cited: 13) (cited: 14)
1998
62.
L. D. Beklemishev, “A proof-theoretic analysis of collection”, Arch. Math. Logic, 37:5-6 (1998), 275–296 (cited: 14) (cited: 18) (cited: 18) (cited: 20)
63.
Л. Д. Беклемишев, Схемы рефлексии в формальной арифметике, Дисс. … докт. физ.-матем. наук, Математический институт им. В.А. Стеклова, Москва, 1998 , 149 с.
64.
L. Beklemishev, “Review of “Aspects of Incompleteness” by P. Lindström”, The Journal of Symbolic Logic, 63:4 (1998), 1606–1608
1997
65.
L. Beklemishev, “Notes on local reflection principles”, Theoria, 63:3 (1997), 139–146 (cited: 5) (cited: 8)
66.
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 (cited: 1)
67.
L. D. Beklemishev, “Induction rules, reflection principles, and provably recursive functions”, Ann. Pure Appl. Logic, 85:3 (1997), 193–242 (cited: 20) (cited: 28) (cited: 28) (cited: 31)
1996
68.
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) (cited: 3)
69.
L. D. Beklemishev, “Bimodal logics for extensions of arithmetical theories”, J. Symbolic Logic, 61:1 (1996), 91–124 (cited: 2) (cited: 3) (cited: 7) (cited: 7)
70.
L. Beklemishev, “Review of “Diagonalization and Self-reference” by R. Smullyan”, The Journal of Symbolic Logic, 61:3 (1996), 1052–1055
1995
71.
L. Beklemishev, “Iterated local reflection versus iterated consistency”, Ann. Pure Appl. Logic, 75:1-2 (1995), 25–48 (cited: 5) (cited: 10) (cited: 5) (cited: 9)
72.
Л. Д. Беклемишев, “Об ограниченном правиле индукции и итерированных схемах рефлексии над кальмаровской элементарной арифметикой”, Теоретические и прикладные аспекты математических исследований, ред. О. Б. Лупанов, МГУ, Москва, 1995, 36–39
1994
73.
L. D. Beklemishev, “On bimodal logics of provability”, Ann. Pure Appl. Logic, 68:2 (1994), 115–159 (cited: 1) (cited: 6) (cited: 4) (cited: 8)
1993
74.
S. N. Artemov, L. D. Beklemishev, “On propositional quantifiers in provability logic”, Notre Dame J. Formal Logic, 34:3 (1993), 401–419 (cited: 5)
75.
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)
76.
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
77.
Л. Д. Беклемишев, “Независимые нумерации теорий и рекурсивных прогрессий”, Сиб. матем. журн., 33:5 (1992), 22–46; L. D. Beklemishev, “Independent enumerations of theories and recursive progressions”, Siberian Math. J., 33:5 (1992), 760–783 (cited: 1) (cited: 1)
78.
Л. Д. Беклемишев, Классификация пропозициональных логик доказуемости, Дисс. … канд. физ.-матем. наук, Математический институт им. В.А. Стеклова РАН, Москва, 1992
1991
79.
L. D. Beklemishev, “Provability logics for natural Turing progressions of arithmetical theories”, Studia Logica, 50:1 (1991), 107–128 (cited: 2) (cited: 5)
1989
80.
Л. Д. Беклемишев, “О классификации пропозициональных логик доказуемости”, Изв. АН СССР. Сер. матем., 53:5 (1989), 915–943 (цит.: 1) (цит.: 2) ; L. D. Beklemishev, “On the classification of propositional provability logics”, Math. USSR-Izv., 35:2 (1990), 247–275
81.
Л. Д. Беклемишев, “Логика доказуемости без интерполяционного свойства Крейга”, Матем. заметки, 45:6 (1989), 12–22 (цит.: 1) (цит.: 1) ; L. D. Beklemishev, “Provability logic without Craig's interpolation property”, Math. Notes, 45:6 (1989), 437–450
1987
82.
Л. Д. Беклемишев, “Нормализация выводов и интерполяция для некоторых логик доказуемости”, УМН, 42:6(258) (1987), 179–180; L. D. Beklemishev, “Normalization of deductions and interpolation for some logics of provability”, Russian Math. Surveys, 42:6 (1987), 223–224
Позитивная логика для схем рефлексии в арифметике Л. Д. Беклемишев Общеинститутский семинар «Математика и ее приложения» Математического института им. В.А. Стеклова Российской академии наук 22 января 2015 г. 16:00
О позитивных логиках доказуемости Л. Д. Беклемишев Семинар отдела математической логики «Алгоритмические вопросы алгебры и логики» 10 декабря 2013 г. 18:30
Алгебры доказуемости и фрагменты арифметики Л. Д. Беклемишев Общеинститутский семинар «Математика и ее приложения» Математического института им. В.А. Стеклова Российской академии наук 19 октября 2006 г. 16:00
2018
Пользовательское соглашение