Finite model theory, fall 2016


Teacher: Juha Kontinen and Jonni Virtema

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.

Introduction to Logic I&II


Teaching schedule

Weeks 36-42 and 44-49, Monday and Thursday 10-12 in room B321. Two hours of exercise classes per week. 

Course diary

Monday 5.9.2016:

Thursday 8.9.2016

Monday 12.9.2016:

Thursday 15.9.2016:

Monday 19.9.2016:

Thursday 22.9.2016:

Monday 26.9.2016:

Thursday 29.9.2016:

Monday 3.10.2016:

 Thursday 6.10.2016:

Monday 10.10.2016:

Thursday 13.10.2016:

Monday 17.10.2016:

Thursday 20.10.2016:

Monday 31.10.2016:

Thursday 3.11.2016:

Monday 14 and Thursday 17.11.2016:

Monday 21.11.2015:

Thursday 24.11.2016:

Monday 28.11.2016:

Thursday 1.12.2016:

Thursday 8.12.2016:

Final exam

The final exam will be organized on Wednesday 21st December at 10-14 in room B321.

Course material

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.

Other reading:

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?



Exercise classes

1.Tuesday 14-16 B321 Juha Kontinen & Jonni Virtema

Course feedback

Course feedback can be given at any point during the course. Click here.