Finite Model Theory - How It All Began

Finite model theory is a study of the logical properties of finite mathematical structures. This talk gives an overview of how finite model theory arose, and of some work that sprang from that. This includes:

(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, without using any notion of machine, computation, or time.

(3) Zero-one 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. Here we consider how complex a formula must be to express a given property.

The goal of this talk is to introduce the audience to the fascinating area of finite model theory.