**Przedmiot zostanie uruchomiony przy przynajmniej 10ciu chętnych. Termin ćwiczeń zostanie ustalony podczas pierwszego wykładu.**
**Przedmiot będzie prowadzony wspólnie przez B. Bednarczyka oraz V. Micheliniego.**
(Finite) model theory is a vital area of mathematical logic, which, from our perspective, serves as the foundation of relational database theory.
The classes will be about some selected topics from classical and finite model theory, which I found interesting or/and important. The lecture will be quite theoretical and the difficulty level of the presented content will vary.
The classes are dedicated to students interested in theoretical computer science and math. Nevertheless, they should be accessible to students after their 3rd semester of bachelor studies.
For students interested in doing research or writing a thesis on related topics, the classes are a good opportunity to kick-start something.
The lecture will contain:
1. An introduction + a few examples. The compactness theorem with a proof via Gödel's theorem. Some consequences of Compactness Theorem with application to inexpressibility in FO.
2. Some important model-theoretic properties of FO: Craig Interpolation, Projective Beth Definability, Łoś-Tarski preservation theorem, Homomorphism preservation theorem.
A bit about failures of the above theorems in the finite realm.
3. Zero-one laws of FO, i.e. a property of FO that the probability of satisfaction of a first-order formula in a random structure is either 0 or 1. Inexpressivity via 0-1 law. Rado graphs, Fraisse limits, and a bit about omega-categoricity and complete theories.
4. Ehrenfeucht-Fraisse games as the universal method for showing inexpressivity in FO. Games on linear orders, types, back-and-forth equivalence. Proof of Fraisse's theorem. We will discuss also some modifications of E-F games, e.g. pebble games and MSO games.
5. FO can express only local properties. Hanf's and Gaifman's localities, with proofs. Applications of localities to inexpressivity and to the construction of fixed-parameters-tractable meta-algorithms for query evaluation over structures of bounded degree.
Model theory can make formulae large.
7. Modal logic as a tamed fragment of FO. Characterisation theorems of Van-Benthem and Rosen. Some model theory of modal logic.
8. Order-invariant First-Order Logic, so a few words about how beautiful the finite model theory is. Is there a logic for PTime, and how the logicians are trying to show that P != NP.
9. Fagin's theorem that problems definable in ESO are precisely those decidable in NP. A bit about FO spectra and the quest for a logic for P.
Lectures and exercise sessions will be given by Bartosz Bednarczyk. Preferably in English.
Some of the lectures will be based on "Elements of Finite Model Theory" by Libkin (freely accessible here: https://homepages.inf.ed.ac.uk/libkin/fmt/fmt.pdf), lecture notes by Martin Otto (https://www2.mathematik.tu-darmstadt.de/~otto/LEHRE/FMT16.pdf), "A shorter model theory" book by Hedges and some recent papers.
**WARNING!**
The lectures and exercise sessions will be from 16:15pm to 6pm on **MONDAYS**. Please take this into account when voting for my class. There will be no way to change it as I'm in Dresden on Tuesdays, Wednesdays and Thursdays.
**Exam:**
The exam will be oral. You will be asked to prepare and present to me some of the proofs discussed during the lecture.
**Requirements:**
The class is dedicated to ambitious students that already had fun during "Logic for Computer Scientists" and enjoy theoretical results (and would like to learn something other than algorithms or programming languages). An obvious requirement is to have a good grade in the 1st-semester logic course.
When in doubt, contact BBE via email.
