Scope: 10 cr
Type: Advanced studies
Teaching: Four hours of lectures and two hours of exercises per week
Topics: Model theory studies mathematical objects, so-called models, with logical tools. Both algebraic structures, like groups, rings and fields, and objects studied in discrete mathematics, like graphs, trees and linear orderings, are examples of models. The interest in finite models is largely motivated by connections with discrete mathematics and theoretical computer science; therefore one could describe finite-model theory as model theory for discrete mathematics. Classical model theory, on the other hand, studies infinite models almost exclusively, and it is more algebraically oriented.
The course starts with an introduction of the general concept of a model and different ways of measuring the similarity of given models: homomorphisms, isomorphisms and combinatorial games. The close relationship between the games and some logical concepts is studied next. Finite models can also be regarded as inputs to a computer programs (a finite model is practically the same thing as a relational database), which leads to descriptive complexity theory. We will discuss Büchi's Theorem relating monadic second-order logic intimately with finite automata and regular languages. We will also discuss Fagin's theorem characterizing the complexity class non-deterministic polynomial time by existential second-order logic. Time permitting, we will also discuss the zero-one law of first-order logic.
Weeks 36-42 and 44-49, Monday and Thursday 10-12 in room B321. Two hours of exercise classes per week.
Monday 14 and Thursday 17.11.2016:
The final exam will be organized on Wednesday 21st December at 10-14 in room B321.
We will follow the structure of K. Luosto's lecture notes:
Luosto, Äärellisten mallien teoria (in Finnish).
All material covered during the course can be also found in:
Ebbinghaus and Flum, Finite Model Theory.
Väänänen, A Short Course in Finite Model Theory.
The slides of Lauri Hella's summer course in Aix-en-Provence.
Did you forget to register? What to do?
|1.||Tuesday||14-16||B321||Juha Kontinen & Jonni Virtema|
Course feedback can be given at any point during the course. Click here.