Lectures: Finite Model Theory

Summer term. Last update: 2024-01-04.

This is a joint lecture for Czech and English students students of the Czech Technical University.

The full information about the course is available in KOS and regular updates about the course will appear on courses.fit.cvut.cz (a login needed for both).


  1. Course overview, motivation and relation to the theory of database systems
  2. Ehrenfeucht-Fraı̈ssé games
  3. Inexpressibility theorems in first-order logic
  4. Hanf’s locality theorem
  5. Gaifman’s locality theorem
  6. Descriptive complexity and second-order logic
  7. Logics with the ability to calculate
  8. Turing machines and finite models
  9. Logics with a finite number of variables
  10. Constraints satisfaction problem and logic
  11. Game comonads and one-way games
  12. Coalgebras of game comonads
  13. Game Comonads and Logic


Web Analytics