Finite model theory

Summary

Finite model theory is the part of model theory that studies logics on finite structures. Many classical tools fail there; for example, the compactness theorem does not hold when only finite structures are allowed. Instead the field uses combinatorial tools such as Ehrenfeucht–Fraïssé games and locality arguments. It is closely tied to computer science, through databases and descriptive complexity, where Fagin's theorem matches a logic with a complexity class.