Premium
On Preservation Theorems for Two‐Variable Logic
Author(s) -
Gradel Erich,
Rosen Eric
Publication year - 1999
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.19990450304
Subject(s) - mathematics , homomorphism , variable (mathematics) , discrete mathematics , second order logic , order (exchange) , pure mathematics , higher order logic , computer science , theoretical computer science , mathematical analysis , description logic , finance , economics
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 .