Completeness theorems for \(\sigma \)-additive probabilistic semantics.

*(English)*Zbl 07160777This paper on logics with languages containing probability operators is the latest installment of a steady stream of research outputs from Belgrade on such logics. This paper studies propositional logics to which operators of the form \(P_{\geq r}\) have been added, the intended interpretation is that the probability of the sentence following this operator is greater or equal than \(r\). Furthermore, conjunctions of infinite length shorter than a specified cardinal \(\kappa\) are allowed. The logic under consideration is \(LPP_{\kappa,\lambda}\), it has \(\lambda\) propositional variables, allows conjunctions of \(<\kappa\)-many formulae, and allows iterations of probability operators.

The first two of the six sections of this paper introduce the topic, discuss related work and introduce the formal apparatus (notation, syntax, semantics, etc.).

The third section is start of the paper proper explaining the non-compactness of \(LPP\)-logics and also providing a reason for this phenomenon (non-Archimedean order types). The authors thus strive for an axiomatisation that is strongly complete with respect to the class of the \(\sigma\)-additive models on as many fragments of \(LPP\) as possible. The remainder of this section is devoted to showing that \(LPP_{\kappa,\lambda}\)-logics are not countably compact for all \(\lambda\geq\omega_1\) and that the class of \(\sigma\)-additive models satisfies a continuity property.

Section 4 presents axioms and inference rules which are shown to be sound. It furthermore contains a deduction theorem and demonstrates the equivalence of Hoover’s and Goldblatt’s approaches to capturing \(\sigma\)-additivity.

Section 5 begins with a demonstration that if iterations of probability operators are not allowed, then the resulting logic is strongly complete with respect to the class of all \(\sigma\)-additive models. If iterations of probability operators are allowed, things become more messy, and the authors thus distinguish between strong and weak completeness. Theorem 5.5 is a derivation of strong completeness for “admissible” fragments of \(LPP_{\omega_1,\omega}\).

The final section lists the theorems proved and neatly displays them in a table.

The first two of the six sections of this paper introduce the topic, discuss related work and introduce the formal apparatus (notation, syntax, semantics, etc.).

The third section is start of the paper proper explaining the non-compactness of \(LPP\)-logics and also providing a reason for this phenomenon (non-Archimedean order types). The authors thus strive for an axiomatisation that is strongly complete with respect to the class of the \(\sigma\)-additive models on as many fragments of \(LPP\) as possible. The remainder of this section is devoted to showing that \(LPP_{\kappa,\lambda}\)-logics are not countably compact for all \(\lambda\geq\omega_1\) and that the class of \(\sigma\)-additive models satisfies a continuity property.

Section 4 presents axioms and inference rules which are shown to be sound. It furthermore contains a deduction theorem and demonstrates the equivalence of Hoover’s and Goldblatt’s approaches to capturing \(\sigma\)-additivity.

Section 5 begins with a demonstration that if iterations of probability operators are not allowed, then the resulting logic is strongly complete with respect to the class of all \(\sigma\)-additive models. If iterations of probability operators are allowed, things become more messy, and the authors thus distinguish between strong and weak completeness. Theorem 5.5 is a derivation of strong completeness for “admissible” fragments of \(LPP_{\omega_1,\omega}\).

The final section lists the theorems proved and neatly displays them in a table.

Reviewer: Jürgen Landes (München)

##### MSC:

03B42 | Logics of knowledge and belief (including belief change) |

03B48 | Probability and inductive logic |

03C10 | Quantifier elimination, model completeness and related topics |

PDF
BibTeX
XML
Cite

\textit{N. Ikodinović} et al., Ann. Pure Appl. Logic 171, No. 4, Article ID 102755, 27 p. (2020; Zbl 07160777)

Full Text:
DOI

##### References:

[1] | Alechina, N., Logic with probabilistic operators, (Proc. of the ACCOLADE ’94 (1995)), 121-138 |

[2] | Ash, R.; Doleans-Dade, C., Probability and Measure Theory (1999), Harcourt/Academic Press |

[3] | Barwise, J., Admissible Sets and Structures (1975), Springer · Zbl 0316.02047 |

[4] | Bhaskara Rao, K. P.S.; Bhaskara Rao, M., Theory of Charges (1983), Academic Press · Zbl 0516.28001 |

[5] | Đorđević, R.; Rašković, M.; Ognjanović, Z., Completeness theorem for propositional probabilistic models whose measures have only finite ranges, Arch. Math. Logic, 43, 557-563 (2004) · Zbl 1057.03028 |

[6] | Fagin, R.; Halpern, J.; Megiddo, N., A logic for reasoning about probabilities, Inform. and Comput., 87, 1-2, 78-128 (1990) · Zbl 0811.03014 |

[7] | Fattorosi-Barnaba, M.; Amati, G., Modal operators with probabilistic interpretations I, Studia Logica, 46, 4, 383-393 (1989) · Zbl 0645.03016 |

[8] | Gaifman, H., A theory of higher order probabilities, (Halpern, J. Y., Proceedings of the Theoretical Aspects of Reasoning about Knowledge (1986), Morgan-Kaufmann: Morgan-Kaufmann San Mateo, California), 275-292 |

[9] | Goldblatt, R., Deduction systems for coalgebras over measurable spaces, J. Logic Comput., 20, 5, 1069-1100 (2010) · Zbl 1220.03054 |

[10] | Heifetz, A.; Mongin, P., Probability logic for type spaces, Games Econom. Behav., 35, 31-53 (2001) · Zbl 0978.03017 |

[11] | Hailperin, T., Probability logic, Notre Dame J. Form. Log., 35, 3, 198-212 (1984) · Zbl 0547.03018 |

[12] | Halpern, J. Y., An analysis of first-order logics of probability, Artificial Intelligence, 46, 311-350 (1990) · Zbl 0723.03007 |

[13] | Hoover, D., Probability logic, Ann. Math. Logic, 14, 287-313 (1978) · Zbl 0394.03033 |

[14] | Hughes, G. E.; Cresswell, M. J., A New Introduction to Modal Logic (1996), Routledge: Routledge New York · Zbl 0855.03002 |

[15] | Ilić Stepić, A.; Ognjanović, Z.; Ikodinović, N.; Perović, A., A p-adic probability logic, MLQ Math. Log. Q., 58, 4-5, 263-280 (2012) · Zbl 1251.03027 |

[16] | Ilić Stepić, A.; Ognjanović, Z., Complex valued probability logics, Publ. Inst. Math. (N.S.), 95, 109, 73-86 (2014) · Zbl 06694531 |

[17] | Karp, C., Languages with Expressions of Infinite Length (1964), North-Holland · Zbl 0127.00901 |

[18] | Keisler, H. J., Model Theory for Infinitary Logic (1971), North-Holland: North-Holland Amsterdam · Zbl 0222.02064 |

[19] | Keisler, H. J., Hyperfinite model theory, (Gandy, R. O.; Hyland, J. M.E., Logic Colloquim 76 (1977), North-Holland), 5-110 |

[20] | Keisler, H. J., Probability quantifiers, (Barwise, J.; Feferman, S., Model Theoretic Logics (1985), Springer-Verlag: Springer-Verlag Berlin), 509-556 |

[21] | Keisler, J., Hyperfinite models of adapted probability logic, Ann. Pure Appl. Logic, 31, 71-86 (1986) · Zbl 0601.03005 |

[22] | Kozen, D.; Larsen, K. G.; Mardare, R.; Panangaden, P., Stone duality for Markov processes, (Proceedings of the 28th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2013) (2013)), 321-330 · Zbl 1433.06006 |

[23] | Loeb, P., Conversion from nonstandard to standard measure spaces and applications in probability theory, Trans. Amer. Math. Soc., 211, 113-122 (1975) · Zbl 0312.28004 |

[24] | Loéve, M., Probability Theory I (2012), Springer · Zbl 0359.60001 |

[25] | Meier, M., An infinitary probability logic for type spaces, Israel J. Math., 192, 1, 1-58 (2012) · Zbl 1276.91039 |

[26] | Nilsson, N., Probabilistic logic, Artificial Intelligence, 28, 71-87 (1986) · Zbl 0589.03007 |

[27] | Ognjanović, Z.; Rašković, M., A logic with higher order probabilities, Publ. Inst. Math. (N.S.), 60, 74, 1-4 (1996) · Zbl 0884.03019 |

[28] | Ognjanović, Z.; Rašković, M., Some probability logics with new types of probability operators, J. Logic Comput., 9, 2, 181-195 (1999) · Zbl 0941.03022 |

[29] | Ognjanović, Z.; Rašković, M., Some first-order probability logics, Theoret. Comput. Sci., 247, 1-2, 191-212 (2000) · Zbl 0954.03024 |

[30] | Ognjanović, Z.; Marković, Z.; Rašković, M., Completeness theorem for a logic with imprecise and conditional probabilities, Logic Colloquium ’05, Athens, Greece, July 28 - August 3, 2005. Logic Colloquium ’05, Athens, Greece, July 28 - August 3, 2005, Bull. Symbolic Logic, 12, 02, 357 (June 2006) |

[31] | Ognjanović, Z.; Perović, A.; Rašković, M., Logics with the qualitative probability operator, Log. J. IGPL, 16, 2, 105-120 (2008) · Zbl 1138.03024 |

[32] | Ognjanović, Z.; Rašković, M.; Marković, Z., Probability logics, (Zbornik Radova. Zbornik Radova, Subseries Logic in Computer Science, vol. 12(20) (2009), Matematički institut), 35-111 · Zbl 1224.03005 |

[33] | Ognjanović, Z.; Rašković, M.; Marković, Z., Probability Logics (2016), Springer · Zbl 0954.03024 |

[34] | Perović, A.; Ognjanović, Z.; Rašković, M.; Radojević, D., Finitely additive probability measures on classical propositional formulas definable by Gödel’s t-norm and product t-norm, Fuzzy Sets and Systems, 163, 1, 65-90 (2011) · Zbl 1233.03032 |

[35] | Rašković, M., Model theory for \(L_{A M}\) logic, Publ. Inst. Math. (N.S.), 37, 51, 17-22 (1985) |

[36] | Rašković, M., Completeness theorem for biprobability models, J. Symbolic Logic, 51, 3, 586-590 (1986) · Zbl 0626.03031 |

[37] | Rašković, M.; Ognjanović, Z., A first order probability logic, \(L P_Q\), Publ. Inst. Math. (N.S.), 65, 79, 1-7 (1999) · Zbl 1006.03018 |

[38] | Rašković, M.; Đorđević, R.; Marković, Z., A logic of approximate reasoning, Publ. Inst. Math. (N.S.), 69, 83, 8-12 (2001) · Zbl 0991.03027 |

[39] | Rašković, M.; Ognjanović, Z.; Marković, Z., A probabilistic approach to default reasoning, (Delgrande, James; Schaub, Torsten, Proceedings of the 10th International Workshop on Non-monotonic Reasoning NMR 2004, Whistler, BC, Canada, June 6-8, 2004 (2004)), 6-8 |

[40] | Rašković, M.; Marković, Z.; Ognjanović, Z., A logic with approximate conditional probabilities that can model default reasoning, Internat. J. Approx. Reason., 49, 1, 52-66 (2008) · Zbl 1184.68520 |

[41] | van der Hoeck, W., Some consideration on the logics \(P_F D\), J. Appl. Non-Classical Logics, 7, 3, 287-307 (1997) · Zbl 0885.03022 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.