University of Cambridge > > Logic and Semantics Seminar (Computer Laboratory) > Preservation under Substructures modulo Bounded Cores

Preservation under Substructures modulo Bounded Cores

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Bjarki Holm.

Note special date and location (GC22)

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_20$ 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_20$ 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.

This talk is part of the Logic and Semantics Seminar (Computer Laboratory) series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2023, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity