David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Ezio Di Nucci
Jack Alan Reynolds
Learn more about PhilPapers
Journal of Symbolic Logic 64 (4):1751-1773 (1999)
Many known tools for proving expressibility bounds for first-order logic are based on one of several locality properties. In this paper we characterize the relationship between those notions of locality. We note that Gaifman's locality theorem gives rise to two notions: one deals with sentences and one with open formulae. We prove that the former implies Hanf's notion of locality, which in turn implies Gaifman's locality for open formulae. Each of these implies the bounded degree property, which is one of the easiest tools for proving expressibility bounds. These results apply beyond the first-order case. We use them to derive expressibility bounds for first-order logic with unary quantifiers and counting. We also characterize the notions of locality on structures of small degree
|Keywords||No keywords specified (fix it)|
|Categories||categorize this paper)|
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
|Through your library|
References found in this work BETA
No references found.
Citations of this work BETA
Martin Grohe & Stefan Wöhrle (2004). An Existential Locality Theorem. Annals of Pure and Applied Logic 129 (1-3):131-148.
Marcelo Arenas, Pablo Barceló & Leonid Libkin (2008). Game-Based Notions of Locality Over Finite Models. Annals of Pure and Applied Logic 152 (1):3-30.
Similar books and articles
Jeremy Butterfield (2001). Book Review:Quantum Chance and Non-Locality: Probablity and Non-Locality in the Interpretations of Quantum Mechanics W. Michael Dickson. [REVIEW] Philosophy of Science 68 (2):263-.
Miklos Redei (1995). Logical Independence in Quantum Logic. Foundations of Physics 25 (3):411-422.
Allen Stairs (1988). Jarrett's Locality Condition and Causal Paradox. PSA: Proceedings of the Biennial Meeting of the Philosophy of Science Association 1988:318 - 325.
Miklos Redei (1993). Are Prohibitions of Superluminal Causation by Stochastic Einstein Locality and by Absence of Lewisian Probabilistic Counterfactual Causality Equivalent? Philosophy of Science 60 (4):608-618.
Stephen David Ross (1989). Inexhaustibility and Human Being: An Essay on Locality. Fordham University Press.
W. Michael Dickson (1996). Determinism and Locality in Quantum Systems. Synthese 107 (1):55 - 82.
Arthur Fine (1980). Correlations and Physical Locality. PSA: Proceedings of the Biennial Meeting of the Philosophy of Science Association 1980:535 - 562.
Added to index2009-01-28
Total downloads194 ( #15,653 of 1,792,259 )
Recent downloads (6 months)77 ( #8,007 of 1,792,259 )
How can I increase my downloads?