Introduction to model theory

Natasha Alechina
School of Computer Science and IT
University of Nottingham

Model theory studies structures (which are usually models of some formal language): their construction, classification, and relations between them. Given that databases, graphs, and mathematical constructs studied in theoretical computer science (categories, domains, Chu spaces) can all be seen as (relational) structures, model theory provides a set of tools potentially useful for any computer scientist.

The aim of the course is to introduce basic notions of model theory and describe the kind of questions it asks, so that the students will be able to recognise this type of problems in the future and know where to look up the techniques for solving them.

Below is the preliminary schedule of lectures:

Lecture 1: Introduction. Language and models of first order logic, definition of truth and entailment. Handout for the first lecture . Answers to the exercises.
Lecture 2: Maps and formulas they preserve (isomorphism, homomorphism, embeddings, substructures, direct products). Handout.
Lecture 3: Ehrenfeucht-Fraisse games. Handout. .
Lecture 4: Language and models of modal logic. Handout. .
Lecture 5: Bisimulation. Handout. .

Recommended textbook: for the first three lectures, any textbook on model theory; for example, Wilfrid Hodges, Model Theory, Cambridge Unuversity Press, 1993 (Chapter 1, 2.4, 3.2, 3.3). For lectures 4 and 5: any textbook on modal logic; for example, Patrick Blackburn, Maarten de Rijke and Yde Venema, Modal Logic, (Chapters 1, 2.2), available electronically from this site.

This course will be taught at the University of Nottingham during February and March 2000, as part of the recently formed Midlands Graduate School in the Foundations of Computer Science.