ASYMPTOTIC CONDITIONAL PROBABILITIES - THE NON-UNARY CASE

Motivated by problems that arise in computing degrees of belief, rye c onsider the problem of computing asymptotic conditional probabilities for first-order sentences. Given first-order sentences phi and theta, we consider the structures with domain {1,...,N} that satisfy theta, a nd compute the fraction of them in which phi is true. We then consider what happens to this fraction as N gets large. This extends the work on 0-1 laws that considers the limiting probability of first-order sen tences, by considering asymptotic conditional probabilities. As shown by Liogon'kii [24], if there is a non-unary predicate symbol in the vo cabulary, asymptotic conditional probabilities do not always exist. We extend this result to show that asymptotic conditional probabilities do not always exist for any reasonable notion of limit. Liogon'kii als o showed that the problem of deciding whether the limit exists is unde cidable. Wt analyze the complexity of three problems with respect to t his limit: deciding whether it is well-defined, whether it exists, and whether it lies in some nontrivial interval. Matching upper and lower bounds are given for all three problems, showing them to he highly un decidable.