Finite model theory, fall 2016
- The first lecture is on Monday 5 September at 10-12 in room B321.
- The exercise session on Tuesday 22nd of November is cancelled and moved to the next week.
- The last lecture of the course will be on Thursday 8th December.
- The final exam will be organized on Wednesday 21st December at 10-14 in room B321.
- The lecture of Monday 5.12 is cancelled.
Weeks 36-42 and 44-49, Monday and Thursday 10-12 in room B321. Two hours of exercise classes per week.
- Relations, functions, vocabularies, models, linearly ordered sets, homomorphisms.
- Strong homomorphisms, embeddins, isomorphisms, automorphisms, model reductions, submodels, ordered models. Representation theorem for finite ordered models.
- Partial isomorphisms,
- Terms and atomic sentences.
- First-order sentences, and quantifier rank of a sentence.
- Infinitary logic and Fraïssé systems.
- Ehrenfeucht–Fraïssé game.
- Equivalence of Fraïssé systems and Ehrenfeucht–Fraïssé games.
- Partial isomorphisms up to k equals logical equivalence up to quantifier rank k.
- Pebble game and partial isomorphism up to k variables.
- Partial isomorphisms up to k variables equals logical equivalence in the k-variable infinitary logic,
- Basic concepts of formal language theory.
- Word models, finite automata, and invariance.
- Any language L that is a union of equivalence classes of an invariance that has finitely many equivalence classes if recognizable by a finite automaton,
- Definability of languages by logics,
- Second-order logic.
- Fragments of second-order logic,
- Every language recognized by some finite automaton is definable in monadic Σ11.
- Simulating monadic second-order logic by first-order logic in models with added structure.
- Completed the proof of Büchi's theorem,
- Basics of Turing machines. We follow the textbook of Ebbinghaus and Flum (see Notes.pdf).
- Complexity classes PTIME, NPTIME and PSPACE,
- Basics of fixed-point logics.
Monday 14 and Thursday 17.11.2016:
- Logical characterization of PTIME, PSPACE and NPTIME by IFP, PFP, and existential second-order logic.
- Satisfiability, validity, and model checking problems. Decidability, undecidability, RE, and coRE.
- Normal form for the one-variable fragment of first-order logic. Notes.
- Normal form for the two-variable fragment of first-order logic.
- Finite model property of the two-variable fragment of first-order logic.
- Asymptotic probabilities, 0-1 laws, and extension axioms.
- 0-1 law for first-order logic and FVL.
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?
- Problem set 1
- Problem set 2
- Problem set 3
- Problem set 4
- Problem set 5
- Problem set 6
- Problem set 7
- Problem set 8
- Problem set 9
- Problem set 10
- Problem set 11
|1.||Tuesday||14-16||B321||Juha Kontinen & Jonni Virtema|
Course feedback can be given at any point during the course. Click here.