Finite Model Theory
Finite Model Theory (FMT) is a subarea of Model Theory (MT). MT is the branch of mathematical logic which deals with the relation between a formal language (syntax) and its interpretations (semantics). FMT is a restriction of MT to finite structures, such as finite graphs or strings. Since many central theorems of MT do not hold when restricted to finite structures, FMT is quite different from MT in methods and application areas. FMT has become an "unusually effective" instrument in computer science, for example in database theory, model checking or for gaining new perspectives on computational complexity.
The three main areas of FMT are presented here: Expressive Power of Languages, Descriptive Complexity, and Random Structures. But first the results fundamental for all areas are introduced on the level of first order languages.
Basics
Why? (Motivation)
What is it? (Definition and Background)
Why is it special? (... compared to 'common' Model Theory)
What is it about? (Typical Logics and Structures studied)
What is required? (Preliminaries)
What to start with? (Basic Concepts)
Ehrenfeucht-Fraisse-Games for FO
The Problem (Expressibility of Properties)
The Idea I (Fraisse's Theorem)
The Idea II (Ehrenfeucht's Games)
The Tool (Ehrenfeucht-Fraisse-Method)
Some Utilities (Localities)
Some Solutions (for some Structures)
Complexity?
Expressive Power of Languages
Typical problem: Given a finite graph, can the property of being an acyclic be expressed in a first order language?
Descriptive Complexity
Random Structures
