On the decision problem for quantified probability logics

Izvestiya. Mathematics. 2025. Vol. 89. No. 3. P. 193–211.

Speranski S. O.

Let QPL-e expand the quantifier-free ‘polynomial’ probability logic of [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 QPL-e-theory of finite spaces is hereditarily undecidable. By earlier observations, this implies that $\Pi_2$ is the maximal decidable prefix fragment of QPL-e. Moreover, we obtain similar results for two natural one-sorted logics of probability that emerge from [Abadi & Halpern 1994].

Keywords: probability logic, decidability, elementary theories, prefix fragments