Syntax vs. Semantics on Finite Structures
- Natasha Alechina ,
- Yuri Gurevich
Structures in Logic and Computer Science: A Selection of Essays in Honor of Andrzej Ehrenfeucht, Lecture Notes in Computer Science. |
Published by Springer-Verlag, Heidelberg
Logic preservation theorems often have the form of a syntax/semantics correspondence. For example, the Tarski-Los theorem asserts that a first-order sentence is preserved by extensions if and only if it is equivalent to an existential sentence. Many of these correspondences break when one restricts attention to finite models. In such a case, one may attempt to find a new semantical characterization of the old syntactical property or a new syntactical characterization of the old semantical property. The goal of this paper is to provoke such a study. In particular, we give a simple semantical characterization of existential formulas on finite structures.