×

An analysis of first-order logics of probability. (English) Zbl 0723.03007

This 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.

MSC:

03B48 Probability and inductive logic
03B30 Foundations of classical theories (including reverse mathematics)
60A05 Axioms; other general questions in probability
Full Text: DOI

References:

[1] Abadi, M.; Halpern, J. Y., Decidability and expressiveness for first-order logics of probability, (Proceedings 30th IEEE Symposium on Foundations of Computer Science (1989)), 148-153
[2] Bacchus, F., On probability distributions over possible worlds, (Proceedings Fourth Workshop on Uncertainty in Artificial Intelligence (1988)), 15-21
[3] Tech. Rept. CS-88-31 (1988), Waterloo, Ont.
[4] Carnap, R., (Logical Foundations of Probability (1950), University of Chicago Press: University of Chicago Press Chicago, IL) · Zbl 0040.07001
[5] Carnap, R., (Statistical and Inductive Probability (1955), The Galois Institute of Mathematics and Art)
[6] Dreben, B.; Goldfarb, W. D., (The Decision Problem: Solvable Classes of Quantificational Formulas (1979), Addison-Wesley: Addison-Wesley Reading, MA) · Zbl 0457.03005
[7] Enderton, H. B., (A Mathematical Introduction to Logic (1972), Academic Press: Academic Press New York) · Zbl 0298.02002
[8] Feldman, Y. A., Probabilistic programming logics, (Ph.D. Thesis (1984), Weizmann Institute of Science: Weizmann Institute of Science Renovot, Israel)
[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, (Crossley, J. N., Sets, Models and Recursion Theory: Proceedings of the Summer School in Mathematical Logic and Tenth Logic Colloquium (1967)), 156-172 · Zbl 0207.29501
[11] Fagin, R.; Halpern, J. Y., Reasoning about knowledge and probability: Preliminary report, (Vardi, M. Y., Proceedings Second Conference on Theoretical Aspects of Reasoning about Knowledge (1988), Morgan Kaufmann: Morgan Kaufmann Los Altos, CA), 277-293 · Zbl 0699.03010
[12] IBM Research Rept. RJ 6191 (1988)
[13] Inf. Comput. (1990)
[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, (Gabbay, D.; Guenthner, F., Handbook of Philosophical Logic, Vol. II (1977), Riedel: Riedel Dordrecht, Netherlands), 249-307 · Zbl 0875.03050
[16] Hacking, I., (Logic of Statistical Inference (1965), Cambridge University Press: Cambridge University Press Cambridge) · Zbl 0133.41604
[17] Halmos, P., (Measure Theory (1950), Van Nostrand: Van Nostrand New York) · Zbl 0040.16802
[18] IBM Research Rept. RJ 6765 (1989)
[19] Keisler, H. J., Probability quantifiers, (Barwise, J.; Feferman, S., Model-Theoretic Logics (1985), Springer: Springer New York), 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, (Proceedings 1962 International Congress of Mathematicians (1963)), 225-229 · Zbl 0137.11201
[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, (Hintikka, J.; Suppes, P., Aspects of Inductive Logic (1966), North-Holland: North-Holland Amsterdam) · Zbl 0202.29905
[25] Shoenfield, J. R., (Mathematical Logic (1967), Addison-Wesley: Addison-Wesley Reading, MA) · Zbl 0155.01102
[26] Skyrms, B., (Causal Necessity (1980), Yale University Press: Yale University Press New Haven, CT)
[27] Skyrms, B., Higher order degrees of belief, (Mellor, D. H., Prospects for Pragmatism: Essays in honor of F.P. Ramsey (1980), Cambridge University Press: Cambridge University Press Cambridge)
[28] Tarski, A., (A Decision Method for Elementary Algebra and Geometry (1951), University of California Press: University of California Press Berkeley, CA) · Zbl 0044.25102
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.