## Paper: Fragments of Existential Second-Order Logic without 0-1 Laws (at LICS 1998)

*Winner of the Kleene Award in 1998***Jean-Marie Le Bars**

### Abstract

We prove that there is a Monadic Σ_{1}^{1}
(Minimal Scott without equality) sentence without an asymptotic
probability. Our result entails that the 0-1 law fails for the logics
Σ_{1}^{1}(FO^{2}) and Σ_{1}
^{1} (Minimal Godel without equality). Therefore we achieve 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

### BibTeX

@InProceedings{LeBars-FragmentsofExistent, author = {Jean-Marie Le Bars}, title = {Fragments of Existential Second-Order Logic without 0-1 Laws}, booktitle = {Proceedings of the Thirteenth Annual IEEE Symposium on Logic in Computer Science (LICS 1998)}, year = {1998}, month = {June}, pages = {525--536 }, location = {Indianapolis, IN, USA}, publisher = {IEEE Computer Society Press} }