An analysis of first-order logics of probability.

*(English)*Zbl 0723.03007This paper is divided into three main parts: the first part concerns “probabilities on a domain”, and corresponds to a frequency conception of probability; the second concerns probabilities of propositions, construed as sets of possible worlds, and corresponds to a subjective view of probability; and the third attempts to put these two views of probability together. The approach has much in common with the approach of F. Bachus [Representing and reasoning with probabilistic knowledge (MIT Press, 1990)].

Probabilities on a domain: These are given in a two-sorted logic, in which the sorts of objects are ordinary objects in the domain, and objects of a field of objects representing values of probabilities. Models of this logic are triples, (D,\(\pi\),\(\mu\)), where D is a domain, \(\pi\) a standard interpretation of the predicates and operations of the language, and \(\mu\) a measure on the individuals of the domain D. The value of \(\mu (d_ i)\) represents the probability of choosing individual \(d_ i\). Why not count the members of the domain uniformly? The author gives two reasons. First, you can’t have a countably additive probability measure on a countable domain. More important (since in real life, we can get along with finite domains) is the argument that a two-stage probability: where one chooses an urn, and then a ball from the urn, cannot be represented by a measure that gives to each ball equal weight.

While this is true, it should be remarked that there are other, perhaps simpler, ways of dealing with these problems than by imposing a measure \(\mu\) on the domain of individuals - presumably a different one for each problem. We can achieve the same end with a uniform distribution over individuals, combined with conditionalization, as follows: take the individuals to be ordered pairs, consisting of an urn and a ball. Take 2- black to characterize ordered pairs in which the second object is black. The proportion of individuals belonging to 2-black is of course just the proportion of black balls. But if we pick an urn and then a ball from the urn, then we should conditionalize on that information: the individual (pair) we are talking about comes from a subset of our domain, namely, \(\{<x,y>:\) y is chosen from \(x\}\), and the set of 2-black objects in this domain is just what we expect. This approach has the double advantage of eliminating the need for \(\mu\) and of allowing for a general, simultaneous treatment of many problems of this form.

Furthermore, if we do not need to treat urns-and-balls in the way that the author does, it is not clear what function a measure on individuals in the domain serves. It seems somehow unnatural to talk of the probability of an individual and one wonders if one could not accomplish all one’s ends by talk of a relativized measure: the measure of one set in another, as the author does at the end of his discussion of probabilities on a domain. To give a semantics for that measure, say in terms of the ratios of cardinals, one might want to suppose that the reference set was finite, but its exact cardinality would be irrelevant.

Leaving these points to one side, the characterization of probabilities on a domain is clear and valuable. In particular, even if we talk of relative cardinalities or measures rather than sums of probabilities of individuals, Lemma 2.3 will still be true: if \(\phi\) is a closed formula, its probability will be 0 or 1.

Probabilities on possible worlds. Probabilities on closed formulas are just what we need for forming expectations and guiding choices; domain probabilities give us 0 or 1, we often know not which. The author associates a closed formula with a set of possible worlds, and gives us an interpretation which makes use of a discrete probability function over the set S of possible worlds. A type 2-probability structure has the form (D,S,\(\pi\),\(\mu\)), where D is a domain, S a set of possible worlds, \(\pi\) an interpretation function, and \(\mu\) a measure on S. We then have a model for either subjective or logical probability.

The challenge, clearly, is to tie these two notions of probability together. Type-3 structures have the form \((D,S,\pi,\mu_ D,\mu_ S)\), in which we have a measure both on the domain and on the set of possible worlds. This section contains only one theorem (Theorem 4.5): If M is a type-3 structure such that all the predicate and function symbols in \(\phi\) are rigid except for the constant symbol \({\mathfrak a}\), then \[ M\quad \vDash \quad ([w(\phi ({\mathfrak a}))=w_ x(\phi (x))]\quad \equiv \quad \forall r[w(\phi ({\mathfrak a}))| (w_ x(\phi (x))=r))=r]). \] The remainder of the paper concerns completeness and undecidability, and the presentation of some axiom systems providing sound (but incomplete) axiomatizations of these structures.

What is particularly noteworthy about the paper is the fact that it provides semantics for various forms of probabilistic reasoning within an object language, in a clear and explicit way.

Probabilities on a domain: These are given in a two-sorted logic, in which the sorts of objects are ordinary objects in the domain, and objects of a field of objects representing values of probabilities. Models of this logic are triples, (D,\(\pi\),\(\mu\)), where D is a domain, \(\pi\) a standard interpretation of the predicates and operations of the language, and \(\mu\) a measure on the individuals of the domain D. The value of \(\mu (d_ i)\) represents the probability of choosing individual \(d_ i\). Why not count the members of the domain uniformly? The author gives two reasons. First, you can’t have a countably additive probability measure on a countable domain. More important (since in real life, we can get along with finite domains) is the argument that a two-stage probability: where one chooses an urn, and then a ball from the urn, cannot be represented by a measure that gives to each ball equal weight.

While this is true, it should be remarked that there are other, perhaps simpler, ways of dealing with these problems than by imposing a measure \(\mu\) on the domain of individuals - presumably a different one for each problem. We can achieve the same end with a uniform distribution over individuals, combined with conditionalization, as follows: take the individuals to be ordered pairs, consisting of an urn and a ball. Take 2- black to characterize ordered pairs in which the second object is black. The proportion of individuals belonging to 2-black is of course just the proportion of black balls. But if we pick an urn and then a ball from the urn, then we should conditionalize on that information: the individual (pair) we are talking about comes from a subset of our domain, namely, \(\{<x,y>:\) y is chosen from \(x\}\), and the set of 2-black objects in this domain is just what we expect. This approach has the double advantage of eliminating the need for \(\mu\) and of allowing for a general, simultaneous treatment of many problems of this form.

Furthermore, if we do not need to treat urns-and-balls in the way that the author does, it is not clear what function a measure on individuals in the domain serves. It seems somehow unnatural to talk of the probability of an individual and one wonders if one could not accomplish all one’s ends by talk of a relativized measure: the measure of one set in another, as the author does at the end of his discussion of probabilities on a domain. To give a semantics for that measure, say in terms of the ratios of cardinals, one might want to suppose that the reference set was finite, but its exact cardinality would be irrelevant.

Leaving these points to one side, the characterization of probabilities on a domain is clear and valuable. In particular, even if we talk of relative cardinalities or measures rather than sums of probabilities of individuals, Lemma 2.3 will still be true: if \(\phi\) is a closed formula, its probability will be 0 or 1.

Probabilities on possible worlds. Probabilities on closed formulas are just what we need for forming expectations and guiding choices; domain probabilities give us 0 or 1, we often know not which. The author associates a closed formula with a set of possible worlds, and gives us an interpretation which makes use of a discrete probability function over the set S of possible worlds. A type 2-probability structure has the form (D,S,\(\pi\),\(\mu\)), where D is a domain, S a set of possible worlds, \(\pi\) an interpretation function, and \(\mu\) a measure on S. We then have a model for either subjective or logical probability.

The challenge, clearly, is to tie these two notions of probability together. Type-3 structures have the form \((D,S,\pi,\mu_ D,\mu_ S)\), in which we have a measure both on the domain and on the set of possible worlds. This section contains only one theorem (Theorem 4.5): If M is a type-3 structure such that all the predicate and function symbols in \(\phi\) are rigid except for the constant symbol \({\mathfrak a}\), then \[ M\quad \vDash \quad ([w(\phi ({\mathfrak a}))=w_ x(\phi (x))]\quad \equiv \quad \forall r[w(\phi ({\mathfrak a}))| (w_ x(\phi (x))=r))=r]). \] The remainder of the paper concerns completeness and undecidability, and the presentation of some axiom systems providing sound (but incomplete) axiomatizations of these structures.

What is particularly noteworthy about the paper is the fact that it provides semantics for various forms of probabilistic reasoning within an object language, in a clear and explicit way.

Reviewer: H.E.Kyburg (Rochester)

##### MSC:

03B48 | Probability and inductive logic |

03B30 | Foundations of classical theories (including reverse mathematics) |

60A05 | Axioms; other general questions in probability |

##### Keywords:

semantics for probabilistic reasoning within an object language; probability logic; probability models; probabilities on a domain; frequency conception of probability; probabilities of propositions; possible worlds; subjective view of probability; two-sorted logic; type 2-probability structure; type-3 structure; completeness; undecidability; axiomatizations
PDF
BibTeX
XML
Cite

\textit{J. Y. Halpern}, Artif. Intell. 46, No. 3, 311--350 (1990; Zbl 0723.03007)

Full Text:
DOI

##### References:

[1] | Abadi, M.; Halpern, J.Y., Decidability and expressiveness for first-order logics of probability, (), 148-153 |

[2] | Bacchus, F., On probability distributions over possible worlds, (), 15-21 |

[3] | Bacchus, F., Representing and reasoning with probabilistic knowledge, (), Tech. rept. CS-88-31, (1988), Waterloo, Ont. |

[4] | Carnap, R., () |

[5] | Carnap, R., () |

[6] | Dreben, B.; Goldfarb, W.D., () |

[7] | Enderton, H.B., () |

[8] | Feldman, Y.A., Probabilistic programming logics, () |

[9] | Feldman, Y.A.; Harel, D., A probabilistic dynamic logic, J. comput. syst. sci., 28, 193-215, (1984) · Zbl 0537.68036 |

[10] | Fenstad, J.E., Representations of probabilities defined on first order languages, (), 156-172 |

[11] | Fagin, R.; Halpern, J.Y., Reasoning about knowledge and probability: preliminary report, (), 277-293 · Zbl 0699.03010 |

[12] | Fagin, R.; Halpern, J.Y., Uncertainty, belief, and probability, (), IBM research rept. RJ 6191, 1161-1167, (1988), Expanded version |

[13] | Fagin, R.; Halpern, J.Y.; Megiddo, N., A logic for reasoning about probabilities, (), IBM research rept. RJ 6190, Inf. comput., 277-291, (1990), To appear in |

[14] | Gaifman, H., Concerning measures in first order calculi, Israel J. math., 2, 1-18, (1964) · Zbl 0192.03302 |

[15] | Garson, J.W., Quantification in modal logic, (), 249-307 · Zbl 0875.03050 |

[16] | Hacking, I., () |

[17] | Halmos, P., () |

[18] | Halpern, J.Y., The relationship between knowledge, belief, and certainty, (), IBM research rept. RJ 6765, 142-151, (1989), Expanded version |

[19] | Keisler, H.J., Probability quantifiers, (), 509-556 |

[20] | Kyburg, H.E., Higher order probabilities and intervals, Int. J. approx. reasoning, 2, 195-209, (1988) · Zbl 0647.68080 |

[21] | Lośś, J., Remarks on the foundations of probability, (), 225-229 |

[22] | Miller, D., A paradox of information, British J. philos. sci., 17, (1966) |

[23] | Nilsson, N., Probabilistic logic, Artif. intell., 28, 71-87, (1986) · Zbl 0589.03007 |

[24] | Scott, D.; Krauss, P., Assigning probabilities to logical formulas, () · Zbl 0202.29905 |

[25] | Shoenfield, J.R., () |

[26] | Skyrms, B., () |

[27] | Skyrms, B., Higher order degrees of belief, () |

[28] | Tarski, A., () |

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.