Finite model theory and finite variable logics
Eric Rosen · Scholarly Commons (University of Pennsylvania) · 1996
Finite Model Theory and Finite Variable Logics Eric Rosen Supervisor: Scott Weinstein 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 (FO), over this class. A second, related, goal is to determine which results from classical model theory remain true when relativized to the class, 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 k (9) and L k 1! (9), the existential fragments of the finite variable logics L k and L k 1! . I show that there are finite models whose L k (9)-theories are not finitely axiomatizable. I also establish the optimality of a normal form for L k 1! (9), and separate certain fragments of this logic. I introduce a notion of a `generalized preser...