Introduction to Mathematical Logic and Model-Theory, 2004

Grades

Examinations

Exams that we have done, with solutions, are available.

There will have been two exams in term, and a final exam:

1. The first exam is October 28, in the regular time and place for lecture (except that the university is supposedly on holiday that afternoon). The subject is propositional logic as we have covered it.
2. The second exam is December 2, on first-order logic, up to and including the Compactness Theorem and the applications of it that we shall have discussed.

It was permitted to treat the second exam (or parts of it) as a take-home exam, for half the credit. Collaboration was permitted, not simple copying. Yet the same seriously wrong solutions appeared on a number of papers. Therefore the final exam will not have a take-home component.

I have chosen the exam dates in consultation with the students who come to class. Those who do not come to class cannot complain about the dates and times. Moreover, a student who does not come to class regularly and who does not earn more than 10% on at least two exams will receive a grade of NA (not FF).

Homework assignments

Some exercises are given during the course of the lectures; others I type up and make available here.

I shall not grade homework exercises, but you should consult with me to check your solutions. I may ask some of these problems on exams. (I may ask others also.)

1. Review your notes from the first lecture. (If you didn't come to the lecture, then find somebody who did, and copy the notes.)
2. From Ahmet Bey, get “Introductory Notes on the Foundations of Mathematics”; review §§ 2.1–7 (and more, as you are inclined; for example, the definition of structure is in § 4.7).
3. Some problems will be given in class, October 7.
4. Problems may be given in any class; it's up to you to get them.
5. I typed up some problems on first-order logic. (In Problem 3, “definable” should be “0-definable”; otherwise (a) and (b) are trivial.)
6. I typed up some more problems, on the Compactness Theorem.
7. I made some notes, with exercises, on the Completeness Theorem.
8. I prepared some last problems, on various topics.

The text

The official text for the course will be the notes that you take in class. (I think that to write down the notes with one's own hand is more beneficial than to photocopy somebody else's notes; see some recollections of the logician Alonzo Church.)

However, if you want also to look at something in print, try any book on mathematical logic. One of the original developers of model-theory was Abraham Robinson; his books might be of interest. A standard text in model-theory for many years has been the book by Chang and Keisler. There are more recent texts by Hodges, by Marker, by Poizat and by Rothmaler. More basic are the logic textbooks by Shoenfield and by Enderton.

I prepared some notes on:

1. total orders (since the proof I gave in class for quantifier-elimination in the theory of dense total orders without endpoints was not the best);
2. the proof of completeness in the Henkin style (assuming that compactness has been proved in this style);
3. all of the lectures, through those on propositional model-theory.

The course

Math 406 will start with a review of, and a more intensive investigation of, some topics from Math 111. A new set of notes for that course is being edited. The current version is on-line, but Ahmet Önal will be making copies also. In Math 406, we shall look especially at § 2.12 (Compactness [for propositional logic]) and § 4.7 (First-order logic). The main theorem of Math 406 will be the Compactness Theorem for First-order Logic, a powerful tool for showing that models of certain infinite theories exist.

The subject

Please note that model-theory is not at all the same thing as mathematical modelling! See the comments on model-theory near the top of my general math page.

In model-theory, a structure is a non-empty set equipped with some (or no) additional “structure”. For example, the set of rational numbers, together with the operations of addition and multiplication and with the relation < (“less-than”), is a structure, called Q. This structure is a model of certain sentences of first-order logic, such as

∀ x ∃ y (x ≠ 0 → x ⋅ y = 1);

but the structure Z of the integers is not a model of this sentence. Therefore, we say, Z and Q are not elementarily equivalent.

A set of sentences of first-order logic is a theory. So model-theory is about the interaction of theories and their models. The (complete) theory of a structure is the set of sentences of which the structure is a model. Elementarily equivalent structures have the same theory. The thing is, such structures may be quite different, mathematically. One general task of model-theory is to identify the complete theories whose models are not all that different from one another.