1. На главную
  2. Электронные версии
  3. Доклады Российской академии наук. Математика, информатика, процессы управления
  4. T. 510, № 1, 2023

Доклады Российской академии наук. Математика, информатика, процессы управления, 2023, T. 510, № 1, стр. 8-12

ЭЛЕМЕНТАРНЫЕ ИНВАРИАНТЫ ДЛЯ КВАНТОРНОЙ ВЕРОЯТНОСТНОЙ ЛОГИКИ

С. О. Сперанский 1, *

1 Математический институт им. В.А. Стеклова Российской академии наук
Москва, Россия

* E-mail: katze.tail@gmail.com

Поступила в редакцию 20.01.2023
После доработки 01.02.2023
Принята к публикации 02.03.2023

Полный текст (PDF)

Аннотация

Пусть QPL – предложенный в [8] двусортный вероятностный язык, который расширяет хорошо известный “полиномиальный” язык, описанный в [3, раздел 6], посредством добавления кванторов по событиям. Мы показываем, что все безатомные пространства имеют одну и ту же QPL-теорию и эта теория разрешима. Также мы вводим понятие элементарного инварианта для QPL и используем его для получения точных верхних оценок на сложность некоторых интересных вероятностных теорий. 

Ключевые слова: вероятностная логика, квантификация по событиям, элементарные инварианты, сложность

1. ВВЕДЕНИЕ

Нас будет интересовать двусортный вероятностный язык QPL, предложенный в [8]. Можно думать о ${\text{QPL}}$ как о естественной комбинации элементарного языка булевых алгебр и языка упорядоченных полей. Его фрагмент, содержащий только кванторы по вещественным числам (но не по событиям), является вариантом хорошо известного “полиномиального” языка, описанного в [3, раздел 6].

Несколько важных сложностных результатов о QPL было получено в [8]. Мы знаем, что если $\mathcal{K}$ – класс вероятностных пространств, который содержит все бесконечные дискретные пространства, то его QPL-теория имеет как минимум ту же сложность, что и полная арифметика второго порядка. QPL-теория конечных вероятностных пространств намного проще, но по-прежнему неразрешима; точнее, она имеет ту же сложность, что и дополнение проблемы остановки. Кроме того, эти результаты остаются справедливы, если мы исключим кванторы по вещественным числам. С другой стороны, для каждого положительного целого числа n QPL-теория пространств с ровно n элементами является разрешимой. Можно задаться вопросом, существуют ли какие-нибудь другие естественные примеры разрешимых вероятностных теорий. Мы отвечаем на этот вопрос утвердительно, показывая, что все безатомные пространства имеют одну и ту же QPL-теорию и эта теория разрешима.

Другая интересная проблема, возникающая в кванторной вероятностной логике, касается верхних оценок сложности. А именно, вероятностные пространства не могут быть непосредственно закодированы в языке арифметики высших порядков, что затрудняет получение верхних оценок сложности для многих вероятностных теорий. Чтобы преодолеть эту трудность, мы разрабатываем теорию элементарных инвариантов для QPL. В отличие от вероятностных про-странств, их инварианты могут быть легко закодированы как множества натуральных чисел, что позволяет нам доказать, что для любого “аналитического” класса вероятностных пространств его QPL-теория имеет как максимум ту же сложность, что и полная арифметика второго порядка. Это решает одну из главных проблем, заявленных в [8].

Настоящую работу можно рассматривать как исследование по элементарным теориям классов вероятностных пространств; ср. [2] и [7].

2. ПРЕДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ

Поскольку многие сложностные результаты о кванторной вероятностной логике формулируются, используя арифметику второго порядка, мы начнем с описания языка последней и лишь затем перейдем к определению QPL.

2.1. Арифметика второго порядка

Напомним, что в арифметике второго порядка имеются: (i) индивидные переменные $x$, $y$, $z$, …, которые предназначены пробегать $\mathbb{N}$; (ii) для каждого положительного целого числа k переменные по множествам Xk, Yk, Zk, … типа k, которые предназначены пробегать подмножества ${{\mathbb{N}}^{k}}$. Обозначим через $\mathfrak{N}$ стандартную модель арифметики и через $\sigma $ – ее сигнатуру. Для удобства мы будем считать, что $\sigma $ содержит символ для любой вычислимой функции или отношения. $\sigma $-Формулы второго порядка строятся из первопорядковых атомарных $\sigma $-формул и выражений вида

$\left( {{{t}_{1}}, \ldots ,{{t}_{k}}} \right)\; \in \;{{X}^{k}},$
где k – положительное целое число, Xk – переменная по множествам типа k и ${{t}_{1}}$, …, ${{t}_{k}}$ – $\sigma $-термы, обычным образом. В дальнейшем под $\sigma $-формулой мы будем понимать $\sigma $-формулу второго порядка.

Пусть $n$ – положительное целое число. Напомним, что $\sigma $-формула лежит в $\Pi _{n}^{1}$, если она имеет вид

$\underbrace {\forall {{{\vec {X}}}_{1}}{\kern 1pt} \exists {{{\vec {X}}}_{2}}{\kern 1pt} \ldots {\kern 1pt} {{{\vec {X}}}_{n}}}_{n - 1 {\text{перемена}}\,\,{\text{кванторов}}}{\kern 1pt} \Psi ,$
где ${{\vec {X}}_{1}}$, ${{\vec {X}}_{2}}$, …, ${{\vec {X}}_{n}}$ суть кортежи переменных по множествам и $\Psi $ не содержит кванторов по множествам. Подмножество $\mathbb{N}$ называется: (a) $\Pi _{n}^{1}$-ограниченным, если оно определимо в $\mathfrak{N}$ посредством $\Pi _{n}^{1}$-$\sigma $-формулы; (b) $\Pi _{n}^{1}$-трудным, если к нему $m$-сводимо любое $\Pi _{n}^{1}$-ограниченное подмножество $\mathbb{N}$; (c) $\Pi _{n}^{1}$-полным, если оно одновременно $\Pi _{n}^{1}$-ограничено и $\Pi _{n}^{1}$-трудно. Традиционно $\Pi _{n}^{1}$-ограниченные множества называются $\Pi _{n}^{1}$-множествами. Хорошо известно, что $\Pi _{n}^{1}$-полные множества существуют. В частности, совокупность всех $\Pi _{n}^{1}$-$\sigma $-предложений, истинных в $\mathfrak{N}$, оказывается $\Pi _{n}^{1}$-полной. Аналогично для подмножеств ${{\mathbb{N}}^{2}}$, ${{\mathbb{N}}^{3}}$ и т.д.

Теорема 2.1 (см. [9]). Пусть ${{\sigma }_{ + }}$ обозначает $\langle + ; = \rangle $. Тогда любое $\Pi _{n}^{1}$-подмножество ${{\mathbb{N}}^{k}}$ может быть определено в $\mathfrak{N}$ посредством ${{\sigma }_{ + }}$-формулы вида                                                

$\underbrace {\forall X_{1}^{1}{\kern 1pt} \exists X_{2}^{1}{\kern 1pt} \ldots {\kern 1pt} X_{n}^{1}}_{n - 1 {\text{перемена}}\,\,{\text{кванторов}}}{\kern 1pt} \Psi ,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,( \star )$
где $X_{1}^{1}$, $X_{2}^{1}$, …, $X_{n}^{1}$ суть переменные по множествам типа 1 и $\Psi $ не содержит переменных по множествам.

Давайте называть $\Pi _{n}^{1}$-${{\sigma }_{ + }}$-формулу специальной, если она имеет вид ($ \star $).

Следствие 2.2 (см. [9]). Совокупность всех специальных $\Pi _{n}^{1}$-${{\sigma }_{ + }}$-предложений, истинных в $\mathfrak{N}$, является $\Pi _{n}^{1}$-полной.

Главный (и единственный) результат в [5] тривиальным образом следует из следствия выше. В [1] и [10] он был использован для получения некоторых интересных результатов о нижних оценках сложности для языков, предложенных в [4] и [11] соответственно.

2.2. Кванторная вероятностная логика

Под вероятностным пространстваом мы понимаем пару $\langle \mathcal{A},{\text{P}}\rangle $, где $\mathcal{A}$ – булева алгебра, в которой у всякого счетного множества элементов есть супремум (а потому и инфимум), и P – вероятностная мера на $\mathcal{A}$, т.е. функция из $\mathcal{A}$ в [0, 1] такая, что для любого счетного множества S попарно непересекающихся элементов $\mathcal{A}$,

${\text{P}}\left( {\mathop \vee \limits_ S} \right) = \sum\limits_{E \in S} {{\text{P}}\left( E \right)} ,$
и к тому же ${\text{P}}\left( \top \right) = 1$, где $ \top $ обозначает наибольший элемент $\mathcal{A}$.

Поскольку само наше определение вероятностной меры подразумевает два различных рода объектов, нам нужны два сорта переменных: (a) булевы переменные X, Y, Z, …, которые предназначены бегать по событиям; (b) переменные по полю $x$, $y$, $z$, …, которые предназначены бегать по вещественным числам. Это, в свою очередь, приводит к расмотрению двух множеств символов:

$\left\{ { \bot , \top , \wedge , \vee ,\neg } \right\}\quad {\text{и}}\quad \left\{ {0,1, + ,{\kern 1pt} \cdot {\kern 1pt} , - , \leqslant } \right\},$
а именно функциональных символов языка булевых алгебр и символов языка упорядоченных полей (где $ - $ соответствует одноместной операции). Для обозначения данной меры будет использоваться cпециальный символ $\mu $.

Булевы термы строятся из $ \bot $, $ \top $ и булевых переменных с использованием $ \wedge $, $ \vee $ и $\neg $ следующим образом: если ${{T}_{1}}$ и ${{T}_{2}}$ – булевы термы, то таковы и $\left( {{{T}_{1}} \wedge {{T}_{2}}} \right)$, $\left( {{{T}_{1}} \vee {{T}_{2}}} \right)$ и $\neg {{T}_{1}}$. Они представляют булевы комбинации событий. Под атомарной ${\text{QPL}}$-формулой мы понимаем выражение вида

$f\left( {\vec {x},\mu \left( {{{T}_{1}}} \right), \ldots ,\mu \left( {{{T}_{m}}} \right)} \right)\; \leqslant g\left( {\vec {y},\mu \left( {{{T}_{{m + 1}}}} \right), \ldots ,\mu \left( {{{T}_{{m + n}}}} \right)} \right),$
где f и g суть полиномы с целыми коэффициентами, $\vec {x}$ и $\vec {y}$ – кортежи переменных по полю и ${{T}_{1}}$, …, ${{T}_{{m + n}}}$ – булевы термы.

Мы будем использовать $ \wedge $, $ \vee $ и $\neg $ для обозначения не только булевых операций, но также и обычных логических связок. Поскольку их булевы версии не будут встречаться вне области действия $\mu $, интерпретации $ \wedge $, $ \vee $ and $\neg $ будут всегда ясны из контекста. В качестве наших кванторных символов возьмем $\forall $ и $\exists $. Тогда QPL-формулы строятся из атомарных ${\text{QPL}}$-формул с использованием символов логических связок и кванторов – связывающих булевы переменные или переменные по полю – обычным образом. Мы сокращаем $\neg \Phi \vee \Psi $ как $\Phi \to \Psi $ и $\left( {\Phi \to \Psi } \right) \wedge \left( {\Psi \to \Phi } \right)$ – как $\Phi \leftrightarrow \Psi $. Кроме того, = и < трактуются как определенные в терминах $ \leqslant $.

Отношение выполнимости $ \Vdash $ для ${\text{QPL}}$ может быть определено очевидным образом, и оно ведет себя так, как можно ожидать. Например, рассмотрим

$\Theta : = \forall x{\kern 1pt} \left( {0 \leqslant x \leqslant 1 \to \exists Y{\kern 1pt} \mu \left( Y \right) = x} \right).$

Пусть $\mathcal{P} = \langle \mathcal{A},{\text{P}}\rangle $ – вероятностное пространство. Тогда $\mathcal{P} \Vdash \Theta $, если и только если для каждого $r \in \left[ {0,1} \right]$ существует $E \in \mathcal{A}$ такое, что ${\text{P}}\left( E \right) = r$.

Замечание 2.3. Фрагмент ${\text{QPL}}$, содержащий только кванторы по вещественным числам (но не по событиям), можно воспринимать как “полиномиальную” логику, описанную ранее в [3], разделе 6. В этой логике булевы переменные трактуются как константные символы и называются “пропозициональными переменными”; поэтому булевы термы становятся “пропозициональными формулами”.

Пусть $\mathcal{K}$ – класс вероятностных пространств. Под QPL-теорией $\mathcal{K}$, обозначаемой ${\text{Th}}\left( \mathcal{K} \right)$, мы понимаем совокупность всех QPL-предложений, истинных в любом пространстве из $\mathcal{K}$. Мы используем ${\text{T}}{{{\text{h}}}^{{\text{e}}}}\left( \mathcal{K} \right)$ для обозначения множества предложений из ${\text{Th}}\left( \mathcal{K} \right)$, которые не содержат кванторов по вещественным числам. Мы будем часто писать ${\text{Th}}\left( \mathcal{P} \right)$ и ${\text{T}}{{{\text{h}}}^{{\text{e}}}}\left( \mathcal{P} \right)$ вместо ${\text{Th}}\left( {\left\{ \mathcal{P} \right\}} \right)$ и ${\text{T}}{{{\text{h}}}^{{\text{e}}}}\left( {\left\{ \mathcal{P} \right\}} \right)$ соответственно. Два пространства ${{\mathcal{P}}_{1}}$ и ${{\mathcal{P}}_{2}}$ называются элементарно эквивалентными, если их QPL-теории совпадают, т.е. ${{\mathcal{P}}_{1}}$ и ${{\mathcal{P}}_{2}}$ не различимы посредством QPL-предложений.

Используя следствие 2.2, можно получить следующее.

Теорема 2.4 (см. [8]). Пусть $\mathcal{K}$ – класс вероятностных пространств, который содержит все бесконечные дискретные пространства. Тогда теория второго порядка $\mathfrak{N}$ $m$-сводима к ${\text{T}}{{{\text{h}}}^{{\text{e}}}}\left( \mathcal{K} \right)$.

3. ФАКТОР-ПРОСТРАНСТВА

Пусть $\mathcal{P} = \langle \mathcal{A},{\text{P}}\rangle $ – вероятностное пространство. Рассмотрим формулу

$X \approx Y\;: = \mu \left( {\left( {X \wedge \neg Y} \right) \vee \left( {Y \wedge \neg X} \right)} \right) = 0.$

Она определеляет весьма естественное отношение эквивалентности на $\mathcal{A}$, а именно

$\mathcal{E}: = \left\{ {\left( {{{E}_{1}},{{E}_{2}}} \right) \in \mathcal{A} \times \mathcal{A}\,{\text{|}}\,\mathcal{P} \Vdash {{E}_{1}} \approx {{E}_{2}}} \right\}.$

Для каждого $E \in \mathcal{A}$ обозначим через ${{\left[ E \right]}_{ \approx }}$ класс эквивалентности E по $\mathcal{E}$. Теперь возмем ${{\mathcal{A}}_{ \approx }}$ равным совокупности всех таких классов эквивалентности и определим функцию ${{{\text{P}}}_{ \approx }}$ из ${{\mathcal{A}}_{ \approx }}$ в [0, 1] посредством

${{{\text{P}}}_{ \approx }}\left( {{{{\left[ E \right]}}_{ \approx }}} \right)\;: = {\text{P}}\left( E \right).$

Нетрудно проверить, что ${{\mathcal{P}}_{ \approx }} = \langle {{\mathcal{A}}_{ \approx }},{{{\text{P}}}_{ \approx }}\rangle $ является вероятностным пространством, которое называется фактор-пространством $\mathcal{P}$ по модулю $\mathcal{E}$. Более того, ${\text{QPL}}$-теории $\mathcal{P}$ и ${{\mathcal{P}}_{ \approx }}$ совпадают.

Замечание 3.1. Что касается языков из [4], мы не можем безопасно переходить от структур к их фактор-структурам по модулю событий меры ноль, поскольку теория данной структуры может отличаться от теории ее фактор-структуры (см. дискуссию в [8]).

Напомним, что $E \in \mathcal{A}$ является атомом $\mathcal{A}$, если $E \ne \, \bot $ (где $ \bot $ обозначает наименьший элемент $\mathcal{A}$) и для каждого $F \in \mathcal{A}$ мы имеем $E \wedge F = \, \bot $ или $E \wedge F = E$. Рассмотрим формулу

$\begin{gathered} {\text{At}}\left( X \right)\;: = \mu \left( X \right) \ne 0 \wedge \\ \forall Y{\kern 1pt} \left( {\mu \left( {X \wedge Y} \right) = 0 \vee X \wedge Y \approx X} \right). \\ \end{gathered} $

Очевидно, $\mathcal{P} \Vdash {\text{At}}\left( E \right)$ тогда и только тогда, когда ${{\left[ E \right]}_{ \approx }}$ является атомом ${{\mathcal{A}}_{ \approx }}$. Мы называем $\mathcal{P}$ безатомным, если $\mathcal{P} \Vdash \neg \exists X{\kern 1pt} {\text{At}}\left( X \right)$. Например, пространство Лебега на [0, 1] является безатомным. Разумеется, существуют альтернативные определения безатомности, но приведенное выше – в духе булевых алгебр; ср. [6].

Теорема 3.2. Любые два безатомных вероятностных пространства элементарно эквивалентны. Кроме того, QPL-теория безатомных вероятностных пространств разрешима.

Это наводит на мысль, что хорошая “элементарная” классификация вероятностных пространств должна основываться на понятии атома (ср. [6]). Вместе с тем теорема выше обобщает результат Тарского о том, что первопорядковая теория упорядоченного поля вещественных чисел является разрешимой; см. [12].

4. ЭЛЕМЕНТАРНЫЕ ИНВАРИАНТЫ

Пусть $\mathcal{P} = \langle \mathcal{A},{\text{P}}\rangle $ – вероятностное пространство. Возьмем $\mathcal{D}$ равным совокупности всех атомов ${{\mathcal{A}}_{ \approx }}$. Под элементарным инвариантом $\mathcal{P}$ мы понимаем функцию ${{\sharp }_{\mathcal{P}}}$ из $\left( {0, + \infty } \right)$ в $\mathbb{N}$, заданную посредством

${{\sharp }_{\mathcal{P}}}\left( r \right)\;: = {\text{число}}\;{\text{элементов}}\;{\text{в}} \left\{ {D \in \mathcal{D}\,{\text{|}}\,{{{\text{P}}}_{ \approx }}\left( D \right) = r} \right\}.$

Значит, в частности, $\mathcal{P}$ является безатомным, если и только если ${{\sharp }_{\mathcal{P}}}$ – функция, тождественно равная нулю.

Поскольку дискретные пространства состоят из атомов, их элементарные инварианты могут рассматривать как их абстрактные представления. К примеру, рассмотрим дискретное распределение g на $\mathbb{N}$, заданное посредством

$g\left( n \right): = \frac{1}{{{{2}^{{n + 1}}}}}.$

Пусть $\mathcal{P} = \langle \mathcal{A},{\text{P}}\rangle $ – соответствующее вероятностное пространство. Значит, $\mathcal{A}$ – совокупность всех подмножеств $\mathbb{N}$ и для каждого $E \subseteq \mathbb{N}$ мы имеем

${\text{P}}\left( E \right) = \sum\limits_{n \in E} {g\left( n \right)} .$

Тогда $\mathcal{D} = \left\{ {\left\{ n \right\}\,{\text{|}}\,n \in \mathbb{N}} \right\}$ и для любого положительного $r \in \mathbb{R}$,

${{\sharp }_{\mathcal{P}}}\left( r \right) = \left( {\begin{array}{*{20}{l}} {1\;}&{{\text{если}} {\kern 1pt} r = \frac{1}{2},\frac{1}{4},\frac{1}{8}, \ldots } \\ {0\;}&{{\text{иначе}}.} \end{array}} \right.$

Таким образом, ${{\sharp }_{\mathcal{P}}}$ очень похож на g. Как было показано в [8], ${\text{Th}}\left( \mathcal{P} \right)$ и ${\text{T}}{{{\text{h}}}^{{\text{e}}}}\left( \mathcal{P} \right)$ обе m-эквивалентны теории второго порядка $\mathfrak{N}$.

Теорема 4.1. Для любых вероятностных пространств ${{\mathcal{P}}_{1}}$ и ${{\mathcal{P}}_{2}}$,

${{\sharp }_{{{{\mathcal{P}}_{1}}}}} = {{\sharp }_{{{{\mathcal{P}}_{2}}}}} \Leftrightarrow {\text{Th}}\left( {{{\mathcal{P}}_{1}}} \right) = {\text{Th}}\left( {{{\mathcal{P}}_{2}}} \right).$

Другими словами, два пространства имеют один и тот же инвариант, если и только если они элементарно эквивалентны.

Замечание 4.2. Аналогичные формулировки возникают в метаматематике булевых алгебр; ср. [6]. Хотя эти два направления исследований явно связаны, они в некотором смысле несравнимы, поскольку QPL имеет дело с мерами на булевых алгебрах специального рода.

Для наших текущих целей мы можем отождествить каждое пространство с его элементарным инвариантом. Отметим, что такие инварианты могут быть легко закодированы как подмножества $\mathbb{N}$. Назовем класс пространств $\mathcal{K}$ аналитическим, если $\left\{ {{{\sharp }_{\mathcal{P}}}\,{\text{|}}\,\mathcal{P} \in \mathcal{K}} \right\}$ определимо в $\mathfrak{N}$ (как множество подмножетсв $\mathbb{N}$).

Теорема 4.3. Пусть $\mathcal{K}$ – аналитический класс пространств. Тогда ${\text{Th}}\left( \mathcal{K} \right)$ m-сводима к теории второго порядка $\mathfrak{N}$.

Это приводит к следующему.

Следствие 4.4. Пусть $\mathcal{K}$ – аналитический класс пространств, который содержит все бесконечные дискретные пространства. Тогда ${\text{Th}}\left( \mathcal{K} \right)$ m-эквивалентна теории второго порядка $\mathfrak{N}$.

Доказательство. Непосредственно из Теорем 2.4 и 4.3.

В частности, Следствие 4.4 применимо к классу всех пространств и классу всех бесконечных пространств. Это решает одну из главных проблем, заявленных в [8].

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

  1. Abadi M., Halpern J.Y. Decidability and expressiveness for first-order logics of probability // Information and Computation. 1994. V. 112. № 1. P. 1–36.

  2. Ershov Yu.L., Lavrov I.A., Taimanov A.D., Taitslin M.A. Elementary theories // Russian Mathematical Surveys. 1965. V. 20. № 4. P 35–105.

  3. Fagin R., Halpern J.Y., Megiddo N. A logic for reasoning about probabilities // Information and Computation. 1990. V. 87. № 1–2. P. 78–128.

  4. Halpern J.Y. An analysis of first-order logics of probability // Artificial Intelligence. 1990. V. 46. № 3. P. 311–350.

  5. Halpern J.Y. Presburger arithmetic with unary predicates is $\Pi _{1}^{1}$ complete // Journal of Symbolic Logic. 1991. V. 56. № 2. P. 637–642.

  6. Koppelberg S. General theory of Boolean algebras // in Handbook of Boolean Algebras, Vol. 1, Ed. by Monk J.D., Bonnet R. (North-Holland, 1989), P. 1–311.

  7. Solovay R.M., Arthan R.D., Harrison J. Some new results on decidability for elementary algebra and geometry // Annals of Pure and Applied Logic. 2012. V. 163. № 12. P. 1765–1802.

  8. Speranski S.O. Quantifying over events in probability logic: an introduction // Mathematical Structures in Computer Science. 2017. V. 27. № 8. P. 1581–1600.

  9. Speranski S.O. A note on definability in fragments of arithmetic with free unary predicates // Archive for Mathematical Logic. 2013. V. 52. № 5–6. P. 507–516.

  10. Speranski S.O. Complexity for probability logic with quantifiers over propositions // Journal of Logic and Computation. 2013. V. 23. № 5. P. 1035–1055.

  11. Speranski S.O. Quantification over propositional formulas in probability logic: decidability issues // Algebra and Logic. 2011. V. 50. № 4. P. 365–374.

  12. Tarski A. A Decision Method for Elementary Algebra and Geometry (University of California Press, 1951).

Дополнительные материалы отсутствуют.

Инструменты

следующая статья выпуска предыдущая статья выпуска содержание выпуска

Доклады Российской академии наук. Математика, информатика, процессы управления

Архивы выпусков Информация о журнале Отправить рукопись в журнал