Пятница, 20 марта, комната 106. Начало в 18:00.
Докладчик: А. Смаль.
Тема: Мини-курс: 'Логические основы теории сложности доказательств'. Лекция 1.
Abstract
Лекция начнется с рассказа о Генценовской системе для пропозициональной логики (
![$ \mathbf{PK} $](../../../sites/default/files/tex/4935ba689e132f5a6065c6e77a4a99f5c464aec8/index.png)
) и логики первого порядка (
![$ \mathbf{LK} $](../../../sites/default/files/tex/51ac75d8fcafcc9aa5548c0d0fd51c6590070370/index.png)
). Потом будет обсуждаться арифметика Пеано и некоторые её подсистемы. Основной упор будет сделан на систему
![$ \mathbf{I}\Delta_0 $](../../../sites/default/files/tex/05e10bd57398892a5643c2cc9bccf58c85bf51a1/index.png)
, с помощью которой в дальнейшем мы установим связь между ограниченной арифметикой и полиномиальной иерархией.