Counterexamples of the 0-1 Law for Fragments of Existential Second-Order Logic: An Overview
Bars, Jean-Marie Le
Bull. Symbolic Logic, Tome 6 (2000) no. 1, p. 67-82 / Harvested from Project Euclid
We propose an original use of techniques from random graph theory to find a Monadic $\sum_{1}^{1}$ (Minimal Scott without equality) sentence without an asymptotic probability. Our result implies that the 0-1 law fails for the logics $\sum_{1}^{1}(\text{FO}^{2})$ and $\sum_{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 $\sum_{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.
Publié le : 2000-03-14
Classification: 
@article{1182353667,
     author = {Bars, Jean-Marie Le},
     title = {Counterexamples of the 0-1 Law for Fragments of Existential Second-Order Logic: An Overview},
     journal = {Bull. Symbolic Logic},
     volume = {6},
     number = {1},
     year = {2000},
     pages = { 67-82},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1182353667}
}
Bars, Jean-Marie Le. Counterexamples of the 0-1 Law for Fragments of Existential Second-Order Logic: An Overview. Bull. Symbolic Logic, Tome 6 (2000) no. 1, pp.  67-82. http://gdmltest.u-ga.fr/item/1182353667/