Complexity for probability logic with quantifiers over propositions (Q2863169)

This dense paper consists of four sections and an appendix. The first section contains a brief introduction to probability logic and complexity issues therein as well as a summary of some of the results which are derived at a later point in this paper.NEWLINENEWLINENEWLINEIn Section 2, the author introduces \textit{quantified probability logic}, \(\mathcal{QPL}\), by giving the syntax, the semantics and how it relates to other well-known languages. \(\mathcal{QPL}\) is build up from the usual propositional formulae, polynomials with rational coefficients of \(\mathcal{QPL}\)-terms and Boolean combinations of \(t\leq t'\) where \(t,t'\) are \(\mathcal{QPL}\)-terms. The author goes on to state that \(\mathcal{QPL}\) is an extension of \(\mathcal L_{\mathrm{FHM}-5}\) and a very small fragment of Hoover-Keisler logic.NEWLINENEWLINENEWLINEWith quantifiers present in the language, the validity and satisfiability hierarchies \(\mathrm{Val}-\Pi_i-\mathcal{QPL}\), \(\mathrm{Val}-\Sigma_i-\mathcal{QPL}\), \(\mathrm{Sat}-\Pi_i-\mathcal{QPL}\), and \(\mathrm{Sat}-\Sigma_i-\mathcal{QPL}\) are defined in Section 3. The main result in this section is Theorem~3.6 which states that NEWLINE\[NEWLINE \Pi_0^0\equiv_m \mathrm{Val}-\Sigma_1-\mathcal{QPL} \lneq_m \mathrm{Val}-\Sigma_2-\mathcal{QPL}\leq_m \mathrm{Val}-\Sigma_3-\mathcal{QPL}\leq_m\ldots .NEWLINE\]NEWLINE Section 4 contains a complex proof of NEWLINE\[NEWLINE\text{Theorem 4.1. The validity problem for }\mathcal{QPL}\text{ is }\Pi_1^1\text{-complete}.NEWLINE\]NEWLINE In the appendix, Hilbert's tenth problem for rational coefficients \(\mathrm{DE}(\mathbb Q)\), rather than integer coefficients, is related to the material in this paper. The author shows that \(\mathrm{Sat}-\Pi_0-\mathcal{QPL}\leq_m \mathrm{DE}(\mathbb Q)\).