Finite-model theory - a personal perspective

Abstract

Finite-model theory is a study of the logical properties of finite mathematical structures. This paper is a very personalized view of finite-model theory, where the author focuses on his own personal history, and results and problems of interest to him, especially those springing from work in his Ph.D. thesis. Among the topics discussed are: 1. Differences between the model theory of finite structures and infinite structures. Most of the classical theorems of logic fail for finite structures, which gives us a challenge to develop new concepts and tools, appropriate for finite structures. 2. The relationship between finite-model theory and complexity theory. Surprisingly enough, it turns out that, in some cases, we can characterize complexity classes (such as NP) in terms of logic, where there is no notion of machine, computation, or time. 3. 0-1 laws. There is a remarkable phenomenon which says that certain properties (such as those expressible in first-order logic) are either almost surely true or almost surely false. 4. Descriptive complexity theory. Here we consider how complex a formula must be to express a given property. In recent years, there has been a re-awakening of interest in finite-model theory. One goal of this paper is to help "fan the flames" of interest, by introducing more researchers to this fascinating area. © 1993.