We investigate properties of propositional modal logic over the classof finite structures. In particular, we show that certain knownpreservation theorems remain true over this class. We prove that aclass of finite models is defined by a first-order sentence and closedunder bisimulations if and only if it is definable by a modal formula.We also prove that a class of finite models defined by a modal formulais closed under extensions if and only if it is defined by a -modal formula.

We search for a set-up in which results from the theory of infinite models hold for finite models. As an example we prove results from stability theory.

We establish a general hierarchy theorem for quantifier classes in the infinitary logic L∞ωωon finite structures. In particular, it is shown that no infinitary formula with bounded number of universal quantifiers can express the negation of a transitive closure.This implies the solution of several open problems in finite model theory: On finite structures, positive transitive closure logic is not closed under negation. More generally the hierarchy defined by interleaving negation and transitive closure operators is strict. This proves a conjecture of (...) Immerman.We also separate the expressive power of several extensions of Datalog, giving new insight in the fine structure of stratified Datalog. (shrink)

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.

We give a survey of results obtained in the model theory of finite and pseudo-finite fields.

Hrushovski originated the study of “flat” stable structures in constructing a new strongly minimal set and a stable 0-categorical pseudoplane. We exhibit a set of axioms which for collections of finite structure with dimension function δ give rise to stable generic models. In addition to the Hrushovski examples, this formalization includes Baldwin's almost strongly minimal non-Desarguesian projective plane and several others. We develop the new case where finite sets may have infinite closures with respect to the dimension function δ. In (...) particular, the generic structure need not be ω-saturated and so the argument for stability is significantly more complicated. We further show that these structures are “flat” and do not interpret a group. (shrink)

Djordjević [Dj 1] proved that under natural technical assumptions, if a complete L n -theory is stable and has amalgamation over sets, then it has arbitrarily large finite models. We extend his study and prove the existence of arbitrarily large finite models for classes of models of L n -theories (maybe omitting types) under weaker amalgamation properties. In particular our analysis covers the case of vector spaces.