Abstract

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 show that the count of existential quantifiers in the $\Sigma_2}0$ sentence equals the size of the smallest bounded core, thus generalizing the classical Los-Tarski theorem for sentences. We look at the notion of relativizations and show its uses in establishing the sharper characterization for special fragments of FO and also over special classes of structures. As a fallout of our studies, we obtain combinatorial proofs of the Los-Tarski theorem for some of the aforementioned cases.

About the speaker: The speaker is a Ph.D. student at IIT Bombay (Mumbai, India) and is currently doing an internship at the Computer Laboratory.