Asymptotic conditional probabilities: The non-unary case

Journal of Symbolic Logic 61 (1):250-276 (1996)

Authors
Joseph Y. Halpern
Cornell University
Abstract
Motivated by problems that arise in computing degrees of belief, we consider the problem of computing asymptotic conditional probabilities for first-order sentences. Given first-order sentences φ and θ, we consider the structures with domain {1,..., N} that satisfy θ, and compute the fraction of them in which φ 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 sentences, by considering asymptotic conditional probabilities. As shown by Liogon'kii [24], if there is a non-unary predicate symbol in the vocabulary, 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 also showed that the problem of deciding whether the limit exists is undecidable. We analyze the complexity of three problems with respect to this 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 be highly undecidable
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.2307/2275609
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 38,992
Through your library

References found in this work BETA

Almost Sure Theories.James F. Lynch - 1980 - Annals of Mathematical Logic 18 (2):91-135.

Add more references

Citations of this work BETA

Infinity and Verifiability in Carnapʼs Inductive Logic.Ruurik Holm - 2013 - Journal of Applied Logic 11 (4):487-504.

Add more citations

Similar books and articles

Modus Tollens Probabilized.Carl G. Wagner - 2004 - British Journal for the Philosophy of Science 55 (4):747-753.
Unknown Probabilities.Richard Jeffrey - 1996 - Erkenntnis 45 (2-3):327 - 335.
Declarations of Independence.Branden Fitelson & Alan Hájek - 2017 - Synthese 194 (10):3979-3995.
Probability and Conditionals.Robert C. Stalnaker - 1970 - Philosophy of Science 37 (1):64-80.
The Extent of Dilation of Sets of Probabilities and the Asymptotics of Robust Bayesian Inference.Timothy Herron, Teddy Seidenfeld & Larry Wasserman - 1994 - PSA: Proceedings of the Biennial Meeting of the Philosophy of Science Association 1994:250 - 259.

Analytics

Added to PP index
2009-01-28

Total views
227 ( #24,942 of 2,319,686 )

Recent downloads (6 months)
2 ( #605,822 of 2,319,686 )

How can I increase my downloads?

Monthly downloads

My notes

Sign in to use this feature