#матлог #учёба #спецсеминар

Семинар «Вероятностные и субструктурные логические системы» (www.mathnet.ru/conf2533) под руководством С.Л. Кузнецова (homepage.mi-ras.ru/~sk/) и С.О. Сперанского (homepage.mi-ras.ru/~speranski/)

Время: 18 марта 2025, начало — в 16:00
Место: МИАН, ком. 303 + Контур.Толк

А.В. Грефенштейн (МИАН)

Инфинитарные исчисления для первопорядковой логики вероятности с распределением на носителе и её фрагментов

Первопорядковая логика вероятности с распределением на носителе — весьма известный формальный язык для рассуждения о вероятностях в теоретической информатике. В односортной версии этой логики имеются кванторы по элементам носителя, а в двухсортной добавляются кванторы по вещественным числам. Как было показано М. Абади и Дж. Хальперном, при почти всех сигнатурах двухсортная версия имеет как минимум ту же сложность, что и полная арифметика второго порядка, а потому для неё невозможно построить адекватное инфинитарное исчисление; см. также доклад С.О. Сперанского (https://www.mathnet.ru/php/seminars.phtml?presentid=45377&option_lang=rus).

Нас будет интересовать аксиоматизируемость односортной версии вышеупомянутой логики. Первый доклад будет посвящён построению сильно полного инфинитарного исчисления для неё. Здесь «инфинитарность» означает, что наше исчисление будет содержать омега-правила, т.е. правила со счётным числом посылок; однако сами формулы будут конечными. На втором докладе мы рассмотрим различные естественные фрагменты данной логики.

➰ ВК