Preservation under substructures modulo bounded cores

DOI10.1007/978-3-642-32621-9_22MaRDI QIDQ2915035zbMATH OpenOpenAlexFDO

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)

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

zbMATH Keywords

first-order logicmodel theorypreservation theorem

Mathematics Subject Classification ID

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

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.

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

Cited in

(6)

• A generalization of the Łoś-Tarski preservation theorem over classes of finite structures
• Preservation theorem and relativization theorem for cofinal extensions
• scientific article; zbMATH DE number 1475195 (Why is no real title available?)
• Preservation and decomposition theorems for bounded degree structures
• Extension preservation in the finite and prefix classes of first-order logic
• A generalization of the Łoś-Tarski preservation theorem

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)