Premium
SO(∀∃*) Sentences and Their Asymptotic Probabilities
Author(s) -
Rosen Eric,
Tyszkiewicz Jerzy
Publication year - 2000
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/1521-3870(200010)46:4<435::aid-malq435>3.0.co;2-e
Subject(s) - unary operation , mathematics , quantifier (linguistics) , fragment (logic) , prefix , simple (philosophy) , order (exchange) , discrete mathematics , type (biology) , parametric statistics , combinatorics , algorithm , linguistics , statistics , computer science , artificial intelligence , ecology , philosophy , epistemology , finance , economics , biology
We prove a 0‐1 law for the fragment of second order logic SO(∀∃*) over parametric classes of finite structures which allow only one unary atomic type. This completes the investigation of 0‐1 laws for fragments of second order logic defined in terms of first order quantifier prefixes over, e.g., simple graphs and tournaments. We also prove a low oscillation law, and establish the 0‐1 law for Σ 1 4 (∀∃*) without any restriction on the number of unary types.