Abstract

In this dissertation, I investigate some questions about the model theory of finite structures. One goal is to better understand the expressive power of various logical languages, including first-order logic , over this class. A second, related, goal is to determine which results from classical model theory remain true when relativized to the class, ${\cal F}$, of finite structures. As it is well-known that many such results become false, I also consider certain weakened generalizations of classical results. ;I prove some basic results about the languages $L\sp{k}$ and $L\sbsp{\infty\omega}{k},$ the existential fragments of the finite variable logics $L\sp{k}$ and $L\sbsp{\infty\omega}{k}$. I show that there are finite models whose $L\sp{k}$-theories are not finitely axiomatizable. I also establish the optimality of a normal form for $L\sbsp{\infty\omega}{k},$ and separate certain fragments of this logic. I introduce a notion of a 'generalized preservation theorem', and establish certain partial positive results. I then show that existential preservation fails for the language $L\sbsp{\infty\omega}{k}$, both over ${\cal F}$ and over the class of all structures. I also examine other preservation properties, e.g. for classes closed under homomorphisms. ;In the final chapter, I investigate the finite model theory of propositional modal logic. I show that, in contrast to more expressive logics, modal logic is 'well-behaved' over ${\cal F}$. In particular, I establish that various theorems that are true over the class of all structures also hold over ${\cal F}$. I prove that, over ${\cal F}$, a class of models is FO-definable and closed under bisimulations iff it is defined by a modal FO sentence. In addition, I prove that, over ${\cal F}$, a class is defined by a modal sentence and closed under extensions iff it is defined by a D-modal sentence