Asymptotic conditional probabilities for first-order logic

Abstract

Motivated by problems that arise in computing degrees of belief, we consider the problem of computing asymptotic conditional probabilities for first-order formulas. That is, given first-order formulas (ℓ and θ, we consider the number of structures with domain {l,..,N} that satisfy θ, and compute the fraction of them in which ℓ is true. We then consider what happens to this probability as N gets large. This is closely connected to the work on 0-1 laws that considers the limiting probability of first-order formulas, except that now we are considering asymptotic conditional probabilities. Although work has been done on special cases of asymptotic conditional probabilities, no general theory has been developed. This is probably due in part to the fact that it has been known that, if there is a binary predicate symbol in the vocabulary, asymptotic conditional probabilities do not always exist. We show that in this general case, almost all the questions one might want to ask (such as deciding whether the asymptotic probability exists) are highly undecidable. On the other hand, we show that the situation with unary predicates only is much better. If the vocabulary consists only of unary predicate and constant symbols, it is decidable whether the limit exists, and if it does, there is an effective algorithm for computing it. The complexity depends on two parameters: whether there is a fixed finite vocabulary or an infinite one, and whether there is a bound on the depth of quantifier nesting.