Hostname: page-component-cd9895bd7-p9bg8 Total loading time: 0 Render date: 2024-12-18T06:43:46.040Z Has data issue: false hasContentIssue false
  • English
  • Français

Quantifying over events in probability logic: an introduction

Published online by Cambridge University Press:  29 June 2016

STANISLAV O. SPERANSKI
STANISLAV O. SPERANSKI*
Affiliation:
Sobolev Institute of Mathematics, 4 Koptyug ave., 630090 Novosibirsk, Russia Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

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.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 27 , Special Issue 8: Continuity, Computability, Constructivity: From Logic to Algorithms 2013 , December 2017 , pp. 1581 - 1600
Copyright
Copyright © Cambridge University Press 2016 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Abadi, M. and Halpern, J.Y. (1994). Decidability and expressiveness for first-order logics of probability. Information and Computation 112 (1) 1–36.Google Scholar
Bernays, P. and Schönfinkel, M. (1928). Zum Entscheidungsproblem der mathematischen Logik. Mathematische Annalen 99 (1) 342–372.Google Scholar
Billingsley, P. (1995). Probability and Measure, John Wiley & Sons.Google Scholar
Börger, E., Grädel, E. and Gurevich, Y. (1997). The Classical Decision Problem, Springer.Google Scholar
Fagin, R., Halpern, J.Y. and Megiddo, N. (1990). A logic for reasoning about probabilities. Information and Computation 87 (1–2) 78–128.CrossRefGoogle Scholar
Hoover, D.N. (1978). Probability logic. Annals of Mathematical Logic 14 (3) 287–313.Google Scholar
Keisler, H.J. (1985). Probability quantifiers. In: Barwise, J. and Feferman, S. (eds.) Model-Theoretic Logics, Springer 509–556.Google Scholar
Koppelberg, S. (1989). General theory of Boolean algebras. In: Monk, J.D. and Bonnet, R. (eds.) Handbook of Boolean Algebras, vol. 1, North-Holland 1–311.Google Scholar
Leitgeb, H. (2013). Reducing belief simpliciter to degrees of belief. Annals of Pure and Applied Logic 164 (12) 1338–1389.Google Scholar
Leitgeb, H. (2016). Probability in logic. In: Hájek, A. and Hitchcock, C. (eds.) The Oxford Handbook of Probability and Philosophy, Oxford University Press. To appear.Google Scholar
Nies, A. (1996). Undecidable fragments of elementary theories. Algebra Universalis 35 (1) 8–33.CrossRefGoogle Scholar
Paris, J.B. (2011). Pure inductive logic. In: Horsten, L. and Pettigrew, R. (eds.) The Continuum Companion to Philosophical Logic, Continuum 428–449.Google Scholar
Rogers, H. (1967). Theory of Recursive Functions and Effective Computability, McGraw-Hill.Google Scholar
Simpson, S.G. (2009). Subsystems of Second Order Arithmetic, Cambridge University Press.CrossRefGoogle Scholar
Solovay, R.M., Arthan, R.D. and Harrison, J. (2012). Some new results on decidability for elementary algebra and geometry. Annals of Pure and Applied Logic 163 (12) 1765–1802.Google Scholar
Speranski, S.O. (2011). Quantification over propositional formulas in probability logic: decidability issues. Algebra and Logic 50 (4) 365–374.Google Scholar
Speranski, S.O. (2013a). Complexity for probability logic with quantifiers over propositions. Journal of Logic and Computation 23 (5) 1035–1055.Google Scholar
Speranski, S.O. (2013b). A note on definability in fragments of arithmetic with free unary predicates. Archive for Mathematical Logic 52 (5–6) 507–516.CrossRefGoogle Scholar
Speranski, S.O. (2013c). Collapsing probabilistic hierarchies. I, Algebra and Logic 52 (2) 159–171.Google Scholar
Suppes, P., de Barros, J.A. and Oas, G. (1998). A collection of probabilistic hidden-variable theorems and counterexamples. In: Pratesi, R. and Ronchi, L. (eds.) Conference Proceedings Vol. 60, Waves, Information and Foundations of Physics, Bologna 267–291.Google Scholar
Tarski, A. (1951). A Decision Method for Elementary Algebra and Geometry, University of California Press.Google Scholar
Terwijn, S.A. (2005). Probabilistic logic and induction. Journal of Logic and Computation 15 (4) 507–515.Google Scholar