Элементарные теории классов вероятностных пространств

В доказательствах многих сложностных результатов, связанных с кванторными вероятностными логическими системами, существенно используется операция умножения вероятностей. Возникает естественный вопрос о том, что происходит при отсутствии операции умножения. В качестве основного примера можно рассмотреть следующий результат: если класс вероятностных пространств содержит все дискретные пространства, то его односортная элементарная теория (в языке с кванторами по событиям) имеет как минимум ту же сложность, что и полная арифметика второго порядка. В [1] получено усиление этого результата: вышеупомянутая оценка сложности остаётся верной, если вместо равенств и неравенств между полиномами от вероятностей мы будем использовать лишь равенства между вероятностями с постоянными натуральными коэффициентами. Также получены аналогичные результаты для обогащений известных вероятностных логик Хальперна–Фейгина–Мегиддо (без кванторов либо с кванторами по вещественным числам) посредством добавления кванторов по пропозициональным формулам.
В работе [2] построен перевод из двухсортного элементарного языка вероятностных пространств (с кванторами по событиям и кванторами по вещественным числам) в язык арифметики второго порядка, где каждое пространство определённым образом сводится к своей атомарной части. С помощью этого перевода доказано, что теория практически любого разумного ‒ в некотором смысле «аналитического» ‒ класса пространств не сложнее, чем полная арифметика второго порядка; при этом теория безатомных пространств оказывается полной и алгоритмически разрешимой.

Список литературы

1. Stanislav O. Speranski, “Sharpening complexity results in quantified probability logic”, Log. J. IGPL, 2024, jzae114, 1–21  
2. Stanislav O. Speranski, “An ‘elementary’ perspective on reasoning about probability spaces”, Log. J. IGPL, 2024, jzae042, 1–23