On Preservation Theorems for Two-Variable Logic

✍ Scribed by Erich Gradel; Eric Rosen

• Publisher: John Wiley and Sons
• Year: 1999
• Tongue: English
• Weight: 736 KB
• Volume: 45
• Category: Article
• ISSN: 0044-3050
• DOI: 10.1002/malq.19990450304

✦ Synopsis

Abstract

We show that the existential preservation theorem fails for two‐variable first‐order logic FO^2^. It is known that for all k ≥ 3, FO^k^ 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 FO^2^.