Stanislav O. Speranski Made a Report "Reasoning with probability spaces"

Febrary 1, Stanislav O. Speranski, Scientific Researcher  Laboratory of Logical Systems Sobolev Institute of Mathematics, gave a presentation at the session of the seminar of International Laboratory for Intelligent Systems and Structural Analysis.

Since interest in probabilistic logics has been growing during the last three decades, different sorts of computer scientists and mathematicians — such as Halpern, Keisler, Scott, Terwijn, and others — approach the matter in different ways. In this talk I shall present a formal language L for reasoning about probabilities with quantifiers over events (and over reals if needed), arising very natually from Kolmogorov's notion of probability space. I am going to discuss computational and metamathematical aspects of L. As we shall see, L has many nice features that are not shared by the logics of Halpern and others. Among them are:

i. There exists an algorithm for deciding whether a given L-sentence is true in all Lebesgue-like (i.e. atomless) probability spaces or not.

ii. Within this framework we can obtain some new results about the relationship between computability and continuity.

iii. Further — by analogy with the case of Boolean algebras — we can define `elementary' invariants of probability spaces.

Thus (i) generalises Tarski's famous result that the first-order theory of the ordered field of reals is decidable (which has recently been used to provide computational complexity bounds for certain statistical problems). (ii) leads to a deeper understanding of the above-mentioned relationship (which plays an important role in computing with continuous data and various parts of constructive mathematics). Finally (iii) gives an analogue of the famous elementary classification of Boolean algebras — this throws new light on foundational issues in reverse mathematics (which is an influential research programme in logic and computability).

Some references

(2015). Quantifying over events in probability logic: an introduction.Mathematical Structures in Computer Science. Cambridge: Accepted.

(2013). Complexity for probability logic with quantifiers over propositions.Journal of Logic and Computation 23:5, 1035–1055. Oxford.

 R. Fagin, J.Y. Halpern and N. Megiddo (1990). A logic for reasoning about probabilities.

Information and Computation 87:1–2, 78–128. Elsevier.