2013/02/18 by Abhisekh Sankaran, Sankaran, Abhisekh, Bharat Adsul +3
Computer Science · #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #cs.LO
paper · pdf · doi:10.48550/arxiv.1302.4350
Added 2 new results: (a) A preservation theorem providing a semantic characterization of Σ^0_n theories for each natural number n (which builds on our generalization of the existential amalgamation theorem) (b) Theories in PSC(k) and PSC_f are equivalent to Σ^0_2 theories and that the latter are strictly more general than the former. These results are in Sections 8 and 9
arxiv created 2013/06/17 · arxiv updated 2013/06/18
We present new preservation theorems that semantically characterize the ∃k ∀^* and ∀k ∃^* prefix classes of first order logic, for each natural number k. Unlike preservation theorems in the literature that characterize the ∃^* ∀^* and ∀^* ∃^* prefix classes, our theorems relate the count of quantifiers in the leading block of the quantifier prefix to natural quantitative properties of the models. As special cases of our results, we obtain the classical Los-Tarski preservation theorem for sentences in both its extensional and substructural versions. For arbitrary finite vocabularies, we also generalize the extensional version of the Los-Tarski preservation theorem for theories. We also present an interpolant-based approach towards these results. Finally, we present partial results towards generalizing to theories, the substructural version of the Los-Tarski theorem and in the process, we give a preservation theorem that provides a semantic characterization of Σ0n theories for each natural number n.