Counterexamples of the 0-1 Law for Fragments of Existential Second-Order Logic: An Overview
The Bulletin of Symbolic Logic 6 (1):67 - 82 (2000)
| Abstract | We propose an original use of techniques from random graph theory to find a Monadic ∑ 1 1 (Minimal Scott without equality) sentence without an asymptotic probability. Our result implies that the 0-1 law fails for the logics ∑ 1 1 (FO 2 ) and ∑ 1 1 (Minimal Gödel without equality). Therefore we complete the classification of first-order prefix classes with or without equality, according to the existence of the 0-1 law for the corresponding ∑ 1 1 fragment. In addition, our counterexample can be viewed as a single explanation of the failure of the 0-1 law of all the fragments of existential second-order logic for which the failure is already known. | |||||||||
| Keywords | No keywords specified (fix it) | |||||||||
| Categories | No categories specified (fix it) | |||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,631 |
| External links |
 |
| Through your library | Configure |
Similar books and articlesJean-Marie Le Bars (2000). Counterexamples of the 0-1 Law for Fragments of Existential Second-Order Logic: An Overview. Bulletin of Symbolic Logic 6 (1):67-82.
Antti Kuusisto (2013). Expressivity of Imperfect Information Logics Without Identity. Studia Logica 101 (2):237-265.
Anne Vedø (1997). Asymptotic Probabilities for Second-Order Existential Kahr-Moore-Wang Sentences. Journal of Symbolic Logic 62 (1):304-319.
Richard Zach (2007). First-Order Gödel Logics. Annals of Pure and Applied Logic 147:23-47.
Frank Wolter (2000). First Order Common Knowledge Logics. Studia Logica 65 (2):249-271.
Roman Kontchakov, Agi Kurucz & Michael Zakharyaschev (2005). Undecidability of First-Order Intuitionistic and Modal Logics with Two Variables. Bulletin of Symbolic Logic 11 (3):428-438.
Erich Grädel (1999). On the Restraining Power of Guards. Journal of Symbolic Logic 64 (4):1719-1742.
Eva Hoogland & Maarten Marx (2002). Interpolation and Definability in Guarded Fragments. Studia Logica 70 (3):373 - 409.
Roman Kontchakov, Carsten Lutz, Frank Wolter & Michael Zakharyaschev (2004). Temporalising Tableaux. Studia Logica 76 (1):91 - 134.
Richard Heck (1996). The Consistency of Predicative Fragments of Frege's Grundgesetze der Arithmetik. History and Philosophy of Logic 17 (1):209-220.
Johan van Benthem (2007). A New Modal Lindström Theorem. Logica Universalis 1 (1).
Yde Venema (1998). Rectangular Games. Journal of Symbolic Logic 63 (4):1549-1564.
B. Courcelle (2012). Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach. Cambridge University Press.
Analytics
Monthly downloads
Sorry, there are not enough data points to plot this chart.
|
Added to index2011-05-29Total downloads2 ( #232,211 of 548,969 )Recent downloads (6 months)1 ( #63,511 of 548,969 )How can I increase my downloads? |
My notes
Discussion
