Preservation under Substructures modulo Bounded Cores

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

• Abhisekh Sankaran, IIT Bombay
• Thursday 30 August 2012, 14:00-15:00
• Room GC22, Computer Laboratory, William Gates Building.

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_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.

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

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge talks
• Computer Laboratory talks
• Computing and Mathematics
• Interested Talks
• Logic and Semantics Seminar (Computer Laboratory)
• Room GC22, Computer Laboratory, William Gates Building
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• yk373's list

Note that ex-directory lists are not shown.