id: 06084911
dt: a
an: 06084911
au: Sankaran, Abhisekh; Adsul, Bharat; Madan, Vivek; Kamath, Pritish;
    Chakraborty, Supratik
ti: Preservation under substructures modulo bounded cores.
so: 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).
py: 2012
pu: Berlin: Springer
la: EN
cc: 
ut: model theory; first order logic; preservation theorem
ci: 
li: doi:10.1007/978-3-642-32621-9_22
ab: 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 $Σ_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 $Σ_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 Łoś-Tarski preservation theorem
    holds. As a fallout of our studies, we obtain combinatorial proofs of
    the Łoś-Tarski theorem for some of the aforementioned cases.
rv: