Elements of finite model theory. (Q703864)

Finite model theory is the study of the expressive power and, more generally, the behaviour of logics on finite structures. This is a textbook on finite model theory that gains much of its motivation from the tight connections between this field and the field of computer science, as can best be exemplified in computational complexity theory, database theory, and formal language theory. After an introduction with examples taken from the just mentioned areas and after pointing out that prominent results from traditional model theory (compactness theorem, Löwenheim-Skolem theorem) do not hold in the finite setting, the author turns to a development of the main tools that are important here: Ehrenfeucht-Fraïssé games (chap.~3) and locality (chap.~4). An important topic in the study of the expressive power of first-order logic is whether the universe is ordered. This is the focus of chap.~5. Most of the subsequent chapters study the expressive power of first-oder logic (chap.~6) and some of its extensions: monadic second-order logic (chap.~7), counting quantifiers (chap.~8), fixed-point operators (chaps.~10 and 11). An intermediate chapter (9) addresses the principles of encoding Turing machines as finite structures from a somewhat more general point of view. The remaining three chapters study zero-one laws, hybrid structures, and further applications of finite model theory in computer science. The audience of the book, as intended by the author, is formed by theoretical computer scientists. This does not mean, however, that a computer science background is a prerequisite. It just means that the book is a basic textbook on finite model theory that presents the most important results from the field (though, in my personal opinion, an imporant topic, the connection between FO and uniform circuit complexity, is missing) in a way accessible with only very basic acquaintance with mathematics or traditional logics. It contains a chapter with a very brief introduction of important concepts from logic, formal languages, computability, and complexity. Every chapter ends with a set of exercises ranging from immediately solvable to research problems. This excellent textbook will be a great help for teachers and students of finite model theory, but also for researchers in other fields of mathematics or computer science that want to gain familiarity with the most important concepts and results from finite model theory.