Laboratory of Mathematical Logic at PDMI

Пятница, 31 марта, ПОМИ РАН, ауд. 203. Начало в 17:15.

Докладчик: С.О. Сперанский (СПбГУ).

Тема: О сложности «элементарных» теорий различных классов вероятностных пространств.

Abstract

Речь пойдёт об одном весьма естественном формальном языке для описания свойств вероятностных пространств. Этот язык содержит кванторы по событиям и (опционально) кванторы по вещественным числам, и в нём можно без труда выразить ряд основных свойств, таких как «быть дискретным (по модулю событий меры ноль)» или «быть безатомным». Мы поговорим об алгоритмической сложности теорий различных естественных классов вероятностных пространств в этом языке. В частности, теория класса всех безатомных пространств оказывается алгоритмически разрешимой, теория всех конечных пространств — эквивалентной дополнению проблемы остановки, а теория всех дискретных пространств, ровно как и теория всех пространств, — эквивалентной полной арифметике второго порядка. Мы также поговорим о том, как можно определить понятие «элементарного инварианта» в данном контексте, и о возможных применениях этого понятия в основаниях математики.

Приглашаются все желающие.


Список основной литературы:

S.O. Speranski. Quantifying over events in probability logic: an introduction. Mathematical Structures in Computer Science, published online, 2016.
S.O. Speranski. Complexity for probability logic with quantifiers over propositions. Journal of Logic and Computation 23(5), 1035–1055, 2013.
R. Fagin, J.Y. Halpern and N. Megiddo. A logic for reasoning about probabilities. Information and Computation 87(1–2), 78–128, 1990.