On the decision problem for quantified probability logics
Stanislav Olegovich Speranski · Izvestiya Mathematics · 2025
Let $\mathsf{QPL}^{\mathrm{e}}$ expand the quantifier-free "polynomial" probability logic of [4] (R. Fagin et al., 1990) by adding quantifiers over arbitrary events; it can be viewed as a one-sorted elementary language for reasoning about probability spaces. We prove that the $\Sigma_2$-fragment of the $\mathsf{QPL}^{\mathrm{e}}$-theory of finite spaces is hereditarily undecidable. By earlier observations, this implies that $\Pi_2$ is the maximal decidable prefix fragment of $\mathsf{QPL}^{\mathrm{e}}$. Moreover, we obtain similar results for two natural one-sorted logics of probability that emerge from [1] (M. Abadi and J. Y. Halpern, 1994).