A finitary outer measure logic. (4th January 2023)

• Record Type: Journal Article
• Authors: Baratella, Stefano
• Is Part Of: Journal of logic and computation. Volume 33:Number 3(2023)
• Page Start: 564
• Page End: 576
• Publication Date: 2023-01-04
• Subjects: probability logic -- submeasure -- outer measure -- weak completeness; Logic programming -- Periodicals; Logic, Symbolic and mathematical -- Periodicals; Computational complexity -- Periodicals; 005.115
• DOI: 10.1093/logcom/exac048
• Languages: English
• ISSNs: 0955-792X

Abstract

Abstract: We extend classical first-order logic with a family of weak probability quantifiers, which we call submeasure quantifiers. Formulas are finitary, but infinitary deduction rules are needed. We consider first-order structures that are equipped with a countable family of submeasures (hence the name of the new quantifiers). We prove that every consistent set of sentences in the resulting logic is satisfiable in some structure as above. Then we restrict the set of formulas by requiring that no submeasure quantifier occurs within the scope of some classical quantifier. By suitably extending the deduction rules, we prove that every consistent set of sentences from the restricted class of formulas is satisfiable in some structure whose submeasures are actually outer measures. To perform the last step, we apply nonstandard techniques à la A. Robinson.