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

We prove that there is a Monadic /spl Sigma//sub 1//sup 1/ (Minimal Scott without equality) sentence without an asymptotic probability. Our result entails that the 0-1 law fails for the logics /spl Sigma//sub 1//sup 1/(FO/sup 2/) and /spl Sigma//sub 1//sup 1/ (Minimal Godel without equality). Theref...

Full description

Saved in:
Bibliographic Details
Main Author: Le Bars, J.-M.
Format: Conference Proceeding
Language:English
Subjects:
Bars
Logic
Vocabulary
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We prove that there is a Monadic /spl Sigma//sub 1//sup 1/ (Minimal Scott without equality) sentence without an asymptotic probability. Our result entails that the 0-1 law fails for the logics /spl Sigma//sub 1//sup 1/(FO/sup 2/) and /spl Sigma//sub 1//sup 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 /spl Sigma//sub 1//sup 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.
ISSN:1043-6871
2575-5528
DOI:10.1109/LICS.1998.705685