On Preservation Theorems for Two‐Variable Logic
- 1 January 1999
- journal article
- research article
- Published by Wiley in Mathematical Logic Quarterly
- Vol. 45 (3) , 315-325
- https://doi.org/10.1002/malq.19990450304
Abstract
We show that the existential preservation theorem fails for two‐variable first‐order logic FO2. It is known that for all k ≥ 3, FOk does not have an existential preservation theorem, so this settles the last open case, answering a question of Andreka, van Benthem, and Németi. In contrast, we prove that the homomorphism preservation theorem holds for FO2.Keywords
This publication has 11 references indexed in Scilit:
- On the Decision Problem for Two-Variable First-Order LogicBulletin of Symbolic Logic, 1997
- Syntax vs. semantics on finite structuresPublished by Springer Nature ,1997
- Bounded Variable Logics and CountingPublished by Springer Nature ,1997
- Infinitary Logic and Inductive Definability over Finite StructuresInformation and Computation, 1995
- Finite Model TheoryPublished by Springer Nature ,1995
- Preservation theorems in finite model theoryPublished by Springer Nature ,1995
- Model TheoryPublished by Cambridge University Press (CUP) ,1993
- Toward logic tailored for computational complexityLecture Notes in Mathematics, 1984
- On languages with two variablesMathematical Logic Quarterly, 1975
- A counterexample to a conjecture of Scott and SuppesThe Journal of Symbolic Logic, 1959