1. Introduction: The course in concerned with foundational issues of modern pure mathematics. It is a rigorous introduction to first-order logic. Proofs will be given for most of the results discussed. Some degree of mathematical sophistication is called for and familiarity with (and a taste for) mathematical proofs, such as would be seen in a rigorous first-year analysis or algebra course, will be assumed. The prerequisite is Algebra I and there are connections with Discrete Mathematics II.

2. Timetable Hours, Credits, Assessments: 33 one hour lectures; 20 UCU. Assessment: Coursework 20% via assessed homework; 3 hour examination 80%. There will be 5 problem sheets which will make up the coursework component of the unit. Sketch solutions will be distributed and consulting hours arranged.

3. Overview: Mathematical logic analyses symbolically the way in which we reason formally, particularly about mathematical structures. The subject was developed the 20th century with Alfred Tarski and Kurt Gödel as its major figures. Although it is highly abstract, its ideas are fundamental in theoretical computer science and artificial intelligence and its results have applications in other parts of Mathematics (via an area known as Model Theory).

The first level of the subject is the propositional calculus. We look at the way simple statements (propositions) can be built into more complicated ones using connectives (`or,’ `and,’ `not,’ `implies’) and make precise how the truth or falsity of the component statements influences the truth or falsity of the compound statement. This is done using truth tables and can be useful for testing the validity of various forms of reasoning. It provides a way of analysing deductions of the form `if the following statements are true: ..... ; then so is .... .’ We then move on to a completely symbolic process of deduction and describe the formal deduction system for propositional calculus. The statements we consider (propositional formulas) are regarded as strings of symbols and we give rules for deducing a new formula from a given collection of formulas. We want these deduction rules to have the property that anything that could be deduced using truth tables (so by considering truth or falsity of the various statements), can be deduced in this formal way, and vice versa. This is the soundness and completeness of our formal system.

The next level of the subject is the predicate calculus. This is what is needed to analyse `real’ mathematics and the extra ingredient is the use of quantifiers (`for all’ and `there exists’). We introduce the notion of a first-order structure, which is general enough to include many of the algebraic objects you come across in mathematics (groups, rings, vector spaces). We then have to be precise about the expressions (formulas) which make statements about these structures, and give a precise definition of what it means for a particular formula to be true in a structure. This is quite intricate, and the clever part is in getting the definitions right (- this is due to Tarski), but it corresponds to ordinary mathematical usage. Once this is done, we set up a formal deduction system for predicate calculus. This parallels what we did for propositional calculus, but is much harder. Nevertheless, the end result is the same: the formulas which are produced by our formal deduction system (the `theorems’) are precisely the formulas which are true in all first-order structures. This is Gödel’s Completeness Theorem.

The final section of the unit is concerned with model theory: the study and classification of mathematical structures in terms of what can be said about them in 1st order languages.

4.  Recommended Reading:  The following can be found in the UEA library. An asterisk (*) indicates that a copy of the book has been placed in the Restricted Loan collection and can only be taken out for short periods of time. There may be another copy available and other suitable books. Check the Library Catalogue.

Propositional calculus: Truth tables; propositional formulas; adequacy of sets of connectives; disjunctive normal form. (4 lectures)

The formal system L for propositional calculus. Proofs and deduction in L. Soundness; the Deduction Theorem. Proof of the Completeness Theorem (Adequacy) for propositional calculus. (5 lectures)

Predicate calculus: First-order structures. Construction of first-order languages and formulas. Interpretations. Satisfaction and truth of formulas. (6 lectures)

The formal system for predicate calculus. Soundness; the Deduction Theorem. Gödel’s completeness theorem for countable first-order languages (Henkin’s proof). The compactness theorem. Normal models and applications of the compactness theorem. (9 lectures)

Set theory: Countability and a brief discussion of cardinality and the Axiom of Choice. The General version of the completeness theorem. (4 lectures)

Model theory: Substructures and embeddings. elementary equivalence. The Löwenheim-Skolem theorems, categoricity and the Los-Vaught test. Applications: dense linear orders, the random graph, and the zero-one law for graphs. (5 lectures)

Advanced Topic: The Zermelo-Fraenkel axioms for set theory. Construction of the natural numbers. Cardinality. the Axiom of Choice and its equivalents. (5 hrs directed reading)

A formal treatment of set theory including cardinality and the Axiom of Choice.