On the decision problem for quantified probability logics

Abstract

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).