On Finite Model Theory (Extended Abstract)
Yuri G. Gurevich · Birkhäuser Boston eBooks · 1990
The subject of this paper is the part of finite model theory intimately related to the classical model theory. In the very beginning of our career in computer science, we attended a few lectures on database theory where databases were inconspicuously allowed to be infinite and then classical model-theoretical theorems were applied. The use of infinite databases aroused our suspicion and prompted us to investigate the status of some most famous model-theoretical theorems in the case of finite structures [Gu84]. The theorems miserably fail. One theorem (a theorem of Roger Lyndon: Every sentence monotone in a predicate P is logically equivalent to a sentence positive in P [Ly59]) resisted the attack and was refuted by Miklos Ajtai and ourselves later [AG87]. In Section 1, we give some old and new counter-examples to classical mo del-theoretic theorems in the finite case. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.