Laboratory of Mathematical Logic at PDMI

Пятница, 23 февраля, комната 106. Начало в 17:00.

Докладчик: Б. Конев.

НИЖНИЕ ОЦЕНКИ ДЛЯ СИСТЕМ ФРЕГЕ С ОГРАНИЧЕННОЙ ГЛУБИНОЙ
Состоится доклад по статье P.Beame, S.Riis "More on the relative strength of counting principles".
Будет доказана нижняя экспоненциальная оценка размера доказательства версии "на" принципа Дирихле (onto-PHP^{n+n^{\epsilon\log n}_n}) для систем Фреге с ограниченной глубиной (bounded-depth Frege) даже в случае, если в качестве схемы аксиом добавляются все "считающие" тавтологии Count_p (т.е. тавтологии, выражающие факт, что не существует совершенного разбиения множества из M элементов на блоки по p элементов, если M!=0 (mod p)).