• DocumentCode
    1960300
  • Title

    Fragments of existential second-order logic without 0-1 laws

  • Author

    Le Bars, Jean-Marie

  • Author_Institution
    Lab. d´´Inf., Caen Univ., France
  • fYear
    1998
  • fDate
    21-24 Jun 1998
  • Firstpage
    525
  • Lastpage
    536
  • Abstract
    We prove that there is a Monadic Σ11 (Minimal Scott without equality) sentence without an asymptotic probability. Our result entails that the 0-1 law fails for the logics Σ11(FO2) 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 Σ 11 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
    formal logic; probability; 0-1 laws; Minimal Godel; Minimal Scott; existential second-order logic; Bars; Logic; Vocabulary;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Logic in Computer Science, 1998. Proceedings. Thirteenth Annual IEEE Symposium on
  • Conference_Location
    Indianapolis, IN
  • ISSN
    1043-6871
  • Print_ISBN
    0-8186-8506-9
  • Type

    conf

  • DOI
    10.1109/LICS.1998.705685
  • Filename
    705685