A generalization of the Łoś-Tarski preservation theorem

详细信息    查看全文

• 作者：Abhisekh Sankaran ; ^{abhisekh@cse.iitb.ac.in" class="auth_mail" title="E-mail the corresponding author} ; Bharat Adsul ^{adsul@cse.iitb.ac.in" class="auth_mail" title="E-mail the corresponding author} ; Supratik Chakraborty ^{supratik@cse.iitb.ac.in" class="auth_mail" title="E-mail the corresponding author}
• 关键词：03C40 ; 03C52 ; 03C75 ; 03C13
• 刊名：Annals of Pure and Applied Logic
• 出版年：2016
• 出版时间：March 2016
• 年：2016
• 卷：167
• 期：3
• 页码：189-210
• 全文大小：603 K

文摘

We present new parameterized preservation properties that provide for each natural number k  , semantic characterizations of the ∃^k∀^⁎${\exists }^k{\forall }^{⁎}$ and 442431c43deeb64a7e25e7e3f9b7" title="Click to view the MathML source">∀^k∃^⁎${\forall }^k{\exists }^{⁎}$ prefix classes of first order logic sentences, over the class of all structures and for arbitrary finite vocabularies. These properties, that we call preservation under substructures modulo k-cruxes and preservation under k-ary covered extensions respectively, correspond exactly to the classical properties of preservation under substructures and preservation under extensions, when k equals 0. As a consequence, we get a parameterized generalization of the Łoś–Tarski preservation theorem for sentences, in both its substructural and extensional forms. We call our characterizations collectively the generalized Łoś–Tarski theorem for sentences. We generalize this theorem to theories, by showing that theories that are preserved under k  -ary covered extensions are characterized by theories of 442431c43deeb64a7e25e7e3f9b7" title="Click to view the MathML source">∀^k∃^⁎${\forall }^k{\exists }^{⁎}$ sentences, and theories that are preserved under substructures modulo k  -cruxes, are equivalent, under a well-motivated model-theoretic hypothesis, to theories of ∃^k∀^⁎${\exists }^k{\forall }^{⁎}$ sentences. In contrast to existing preservation properties in the literature that characterize the ${\mathrm{\Sigma }}_2^0$ and ${\mathrm{\Pi }}_2^0$ prefix classes of FO sentences, our preservation properties are combinatorial and finitary in nature, and stay non-trivial over finite structures as well.