2020/07/10 by Anuj Dawar, Dawar, Anuj, Abhisekh Sankaran +1
Computer Science · Psychology · #03C13 #03C40 #03C52 #Advanced Algebra and Logic #F.4.1 #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge #Philosophy and Theoretical Science
paper · pdf · doi:10.48550/arxiv.2007.05459
openalex publication_date 2020/07/10 · openalex created_date 2021/02/15 · openalex updated_date 2026/07/28
It is well known that the classic Lo 's-Tarski preservation theorem fails\nin the finite: there are first-order definable classes of finite structures\nclosed under extensions which are not definable (in the finite) in the\nexistential fragment of first-order logic. We strengthen this by constructing\nfor every n, first-order definable classes of finite structures closed under\nextensions which are not definable with n quantifier alternations. The\nclasses we construct are definable in the extension of Datalog with negation\nand indeed in the existential fragment of transitive-closure logic. This\nanswers negatively an open question posed by Rosen and Weinstein.\n