ICAR Research Data Repository for Knowledge Management
DSpace at IIT Bombay
View Archive InfoMetadata
| Field | Value |
| Title | A generalization of the Los-Tarski preservation theorem |
| Names |
SANKARAN, A
ADSUL, B CHAKRABORTY, S |
| Date Issued | 2016 (iso8601) |
| Abstract | We present new parameterized preservation properties that provide for each natural number k, semantic characterizations of the there exists(k)for all and for all(k)there 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 Los-Tarski preservation theorem for sentences, in both its substructural and extensional forms. We call our characterizations collectively the generalized Los-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 for all(k)there exists* sentences, and theories that are preserved under substructures modulo k-cruxes, are equivalent, under a well-motivated model-theoretic hypothesis, to theories of there exists(k)for all* sentences. In contrast to existing preservation properties in the literature that characterize the Sigma(0)(2) and Pi(0)(2)) prefix classes of FO sentences, our preservation properties are combinatorial and finitary in nature, and stay non-trivial over finite structures as well. (C) 2015 Elsevier B.V. All rights reserved. |
| Genre | Article |
| Topic | FINITE STRUCTURES |
| Identifier | ANNALS OF PURE AND APPLIED LOGIC,167(3)189-210 |