Preservation under substructures modulo bounded cores

DOI10.1007/978-3-642-32621-9_22zbMATH Open1362.03029arXiv1205.1358OpenAlexW1506854270MaRDI QIDQ2915035FDOQ2915035

Authors: Abhisekh Sankaran, Bharat Adsul, Vivek Madan, Pritish Kamath, Supratik Chakraborty 

Publication date: 21 September 2012

Published in: Logic, Language, Information and Computation (Search for Journal in Brave)

Abstract: We investigate a model-theoretic property that generalizes the classical notion of "preservation under substructures". We call this property emph{preservation under substructures modulo bounded cores}, and present a syntactic characterization via $Sigm{a}_2^0$ sentences for properties of arbitrary structures definable by FO sentences. As a sharper characterization, we further show that the count of existential quantifiers in the $Sigm{a}_2^0$ sentence equals the size of the smallest bounded core. We also present our results on the sharper characterization 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 sharper characterization 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.

Full work available at URL: https://arxiv.org/abs/1205.1358

Recommendations

• A generalization of the Łoś-Tarski preservation theorem
• On Preservation Theorems for Two-Variable Logic
• A generalization of the Łoś-Tarski preservation theorem over classes of finite structures
• Preservation under Extensions on Well-Behaved Finite Structures
• Automata, Languages and Programming

zbMATH Keywords

first-order logicmodel theorypreservation theorem

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Basic properties of first-order languages and structures (03C07) Interpolation, preservation, definability (03C40)

Cited In (5)

• Preservation and decomposition theorems for bounded degree structures
• Title not available (Why is that?)
• A generalization of the Łoś-Tarski preservation theorem
• Preservation theorem and relativization theorem for cofinal extensions
• A generalization of the Łoś-Tarski preservation theorem over classes of finite structures

This page was built for publication: Preservation under substructures modulo bounded cores

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2915035)