06084911

a

06084911 Sankaran, Abhisekh Adsul, Bharat Madan, Vivek Kamath, Pritish Chakraborty, Supratik Preservation under substructures modulo bounded cores. Ong, Luke (ed.) et al., Logic, language, information and computation. 19th international workshop, WoLLIC 2012, Buenos Aires, Argentina, September 3--6, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-32620-2/pbk). Lecture Notes in Computer Science 7456, 291-305 (2012). 2012 Berlin: Springer EN model theory first order logic preservation theorem

doi:10.1007/978-3-642-32621-9_22

Summary: We investigate a model-theoretic property that generalizes the classical notion of preservation under substructures. We call this property preservation under substructures modulo bounded cores, and present a syntactic characterization via $\Sigma_2^0$ sentences for properties of arbitrary structures definable by FO sentences. Towards a sharper characterization, we conjecture that the count of existential quantifiers in the $\Sigma_2^0$ sentence equals the size of the smallest bounded core. We show that this conjecture holds for special fragments of FO and also over special classes of structures. We present a (not FO-definable) class of finite structures for which the conjecture fails, but for which the classical {\L}o\'s-Tarski preservation theorem holds. As a fallout of our studies, we obtain combinatorial proofs of the {\L}o\'s-Tarski theorem for some of the aforementioned cases.