Preservation under Substructures modulo Bounded Cores

2012/05/07 by Abhisekh Sankaran, Bharat Adsul, Sankaran, Abhisekh +7
Computer Science · Mathematics · #Advanced Topology and Set Theory #Computability, Logic, AI Algorithms #FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO) #Logic in Computer Science (cs.LO) #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1205.1358

openalex publication_date 2012/05/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 Σ₂⁰ 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 Σ₂⁰ 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 Łoś-Tarski preservation theorem holds. As a fallout of our studies, we obtain combinatorial proofs of the Łoś-Tarski theorem for some of the aforementioned cases.

Related

• A Generalization of the Łoś-Tarski Preservation Theorem over Classes of Finite Structures
• A Generalization of the Łoś-Tarski Preservation Theorem
• Generalizations of the Los-Tarski Preservation Theorem
• A Generalization of the Łoś-Tarski Preservation Theorem - Dissertation Summary
• A note on the submodel preservation property in fragments of first-order logic