Finite model theory and finite variable logics
Finite model theory and finite variable logics
复制标题
有限模型理论和有限变量逻辑
DOI：
10.1016/j.entcs.2020.09.010
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
Eric Barry Rosen
中科院分区：
文献类型：
--
作者：
Eric Barry Rosen
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, ${\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}(\exists)$ and $L\sbsp{\infty\omega}{k}(\exists),$ 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}(\exists)$-theories are not finitely axiomatizable. I also establish the optimality of a normal form for $L\sbsp{\infty\omega}{k}(\exists),$ 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.
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, ${\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}(\exists)$ and $L\sbsp{\infty\omega}{k}(\exists),$ 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}(\exists)$-theories are not finitely axiomatizable. I also establish the optimality of a normal form for $L\sbsp{\infty\omega}{k}(\exists),$ 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.