Decidability and expressiveness for first-order logics of probability (Q1327387): Difference between revisions

There are two relatively common ways of associating probabilities with first-order languages. According to one association, probabilities are assigned to the sentences of the language (best known proponent: Carnap). According to the other, probabilities are assigned to open formulas of the language (best known proponent: von Mises). On the first view, probabilities are given to worlds; models may be taken to have the form \(\langle D,S,\pi, \mu\rangle\): domain \(D\), set of worlds \(S\), interpretation function \(\pi\) for predicates and functions, measure \(\mu\) on the possible worlds. On the other view, models may be taken to have the form \(\langle D,\pi, \mu\rangle\), where \(\mu\) assigns probabilities to individuals of the domain \(D\), and while the probability of a sentence in a model is either 0 or 1, the probability of an open formula is the measure of the set of \(n\)-tuples that make the formula true in a model. In both cases probability assertions are represented by formulas of the object language. We may therefore raise the question of the complexity of these languages, and the possibilities of their axiomatization, as well as of the relative expressiveness of these languages. The present paper provides very general and elegant answers to these questions. In short, it is shown that: If the probability is given on the domain \(D\), then: if the language contains only unary predicates, the validity problem is decidable; if the language contains at least one binary predicate, then the validity problem is \(\Pi^ 2_ 1\) complete; with equality, the validity problem is at least \(\Pi^ 2_ \infty\) hard. If the probability is given on possible worlds, then the validity problem is \(\Pi^ 2_ 1\) complete. Of course, if the domain is bounded, then the logics are decidable in either case. The techniques used to arrive at these results are not uncommon, though in this context, they might give one pause. For example, to show that if the probability is given on the domain, a single binary predicate is enough to generate strong undecidability, the authors take a prodicate \(B\), assumed to be in the language, and constrain its meaning by means of axioms. They then show how to translate an arbitrary \(\Pi^ 2_ 1\) formula into a formula in our first-order language that can be expressed in terms of the predicate \(B\). This may strike some of those who are concerned with applications of first-order languages to the real world as beside the point: If we are working with a specific applied language, we need not suppose there is any predicate in the language that satisfies the axioms required. So while the results are true in general, they may not bear interestingly on a given attempt to provide an empirical probabilistic system. Furthermore, the technique depends on being able to translate a higher- order arithmetical statement into the first-order language in question. Probability statements in the object language play an important role in this translation. (For example, ``\((x=0)\)'' in the arithmetic language is translated into ``\(w_ z(B (z,x))= {1\over 2}\)''. This is loosely read, ``the probability of the \(z\)'s that stand in the relation \(B\) to \(x\) is a half''. The results thus might be read as a caution about taking probability to be real-valued function within the object language, rather than a metalinguistic function whose range is a set of expressions in the object language. The final result of the study is that the two languages are, in a sense, equally expressive.