Finite Model Theory

This is the first edition. The second edition was published in the "Springer Monographs in Mathematics" series in 2005.
The branch of model theory described in the present book and called finite
model theory has its roots in classical model theory but owes its systematic
development to research from complexity theory.
Model theory or the theory of models, as it was first named by Tarski in
1954, may be considered as the part of the semantics of f.Qrmalized languages
that is concerned with the interplay between the syntactic structure of an
axiom system on the one hand and (algebraic, set-theoretic, ... ) properties
of its models on the other hand. As it turned out, first-order language (we
mostly speak of first-order logic) became the most prominent language in this
respect, the reason being that it obeys some fundamental principles such as
the compactness theorem and the completeness theorem. These principles are
valuable modeltheoretic tools and, at the same time, reflect the expressive
weakness of first-order logic. This weakness is the breeding ground for the
freedom which modeltheoretic methods rest upon.