**
Natasha Alechina School of Computer Science and ITUniversity 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. .

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.