Quantifying over events in probability logic: An introduction

?

Quantifying over events in probability logic: An introduction

Mathematical Structures in Computer Science. 2017. Vol. 27. No. 8. P. 1581–1600.

In this article we describe a bunch of probability logics with quantifiers over events, and develop primary techniques for proving computational complexity results (in terms of m-degrees) about these logics, mainly over discrete probability spaces. Also the article contains a comparison with some other probability logics and a discussion of interesting analogies with research in the metamathematics of Boolean algebras, demonstrating a number of attractive features and intuitive advantages of the present proposal.

Language: English

DOI

О замыкающих ординалах инфинитарных вероятностных исчислений

Speranski S. O., Математические заметки 2026 Т. 120 № 3 С. 470–483

We show that, in terms of closure ordinals, many infinitary calculi for ‘first-order’ logics of probability (i.e., for languages similar to those in [Abadi & Halpern 1994]) are as hard as possible: the corresponding closure ordinals coincide with the least non-constructive ordinal, denoted by $\omega_1^{\mathrm{CK}}$. ...

Added: August 12, 2026

On the complexity of first-order logics of probability

Speranski S. O., Grefenshtein A., Izvestiya. Mathematics 2026 Vol. 90 No. 4 P. 754–775

The article is concerned with Halpern's first-order logics of probability, which we denote by L_1 and L_2 – the first of these deals with probability distributions on the domain, while the second employs distributions on external sets of possible worlds. The proofs of [Abadi & Halpern 1994] of the complexity lower bound results for L_1 and L_2 ...

Added: August 12, 2026

Complexity for probability logic with quantiﬁers over propositions

Speranski S. O., Journal of Logic and Computation 2013 Vol. 23 No. 5 P. 1035–1055

In the present article, the quantifiers over propositions are first introduced into the language for reasoning about probability, then the complexity issues for validity problems dealing with the corresponding hierarchy of probabilistic sentences are investigated. We prove, among other things, the $\Pi^1_1$-completeness for the general validity and also indicate the least level in the hierarchy ...

Added: December 27, 2025

On the decision problem for quantified probability logics

Speranski S. O., Izvestiya. Mathematics 2025 Vol. 89 No. 3 P. 609–627

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

Added: December 26, 2025

An ‘elementary’ perspective on reasoning about probability spaces

Speranski S. O., Logic Journal of the IGPL 2025 Vol. 33 No. 2 Article jzae042

This paper is concerned with a two-sorted probabilistic language, denoted by QPL, which contains quantifiers over events and over reals, and can be viewed as an elementary language for reasoning about probability spaces. The fragment of QPL containing only quantifiers over reals is a variant of the well-known ‘polynomial’ language from [Fagin et al. 1990, Section 6]. ...

Added: December 26, 2025

Sharpening complexity results in quantified probability logic

Speranski S. O., Logic Journal of the IGPL 2025 Vol. 33 No. 3 Article jzae114

We shall be concerned with two natural expansions of the quantifier-free ‘polynomial’ probability logic of [Fagin et al. 1990]. One of these, denoted by QPL-e, is obtained by adding quantifiers over arbitrary events, and the other, denoted by p-QPL-e, uses quantifiers over propositional formulas — or equivalently, over events expressible by such formulas. The earlier proofs ...

Added: December 26, 2025