ADVANCED COURSE ON LOGIC: 'Distinguishing one structure from another'

Wilfrid Hodges

The course will pick up where Patrick Blackburn's Introductory Course leaves off. But any introductory course in logic should cover the prerequisites. The course will contain more applications than proofs.

Lecture One: The basic idea of model theory. One can distinguish structures by what formal sentences are true in them. We look at examples of some of the main kinds of formal sentence, not only from first-order logic.

Lecture Two: The classical indistinguishability theorems. These theorems tell us that certain kinds of formal language are incapable of making certain kinds of distinction. Compactness, Loewenheim-Skolem and preservation theorems (such as Birkhoff's) are examples.

Lecture Three: Games for comparing structures. These are the Ehrenfeucht-Fraisse games and their descendents. We can use them to measure how different two given structures are, and hence how easy it will be to distinguish between them by formal sentences.

Lecture Four: Ways of cheating. We look at some ways of using weak languages to make strong distinctions. For example Prolog, logically a rather weak language, is in fact a universal programming language; how?