Collapsing probabilistic hierarchies. I

S. O. Speranskii

Algebra i logika, Tome 52 (2013) no. 2, pp. 236-254

Résumé

We study hierarchies of validity problems for prefix fragments in probability logic with quantifiers over propositional formulas, denoted $\mathcal{QPL}$, and its versions. It is proved that if a subfield $\mathfrak F$ of reals is definable in the standard model of arithmetic by a second-order formula without set quantifiers, then the validity problem over $\mathfrak F$-valued probability structures for $\Sigma_4$-$\mathcal{QPL}$-sentences is $\Pi^1_1$-complete; as a consequence, the corresponding hierarchy of validity problems collapses. Moreover, in proving this fact, we state that an $\Pi^1_1$-полнота $\forall\exists$-theory of Presburger arithmetic with a single free unary predicate is $\Pi^1_1$-complete, which generalizes a well-known result of Halpern relating to the entire theory mentioned.

Détail

Keywords: probability logic, computational complexity, expressiveness.
Mots-clés : quantifiers over propositions