B1.1 Logic - Material for the year 2020-2021

We have updated our Undergraduate exams guidance in preparation for the Trinity Term examinations.

Please see our new webpages dedicated to TT exams.

2020-2021
Lecturer(s): 
Prof. Jonathan Pila
General Prerequisites: 

There are no formal prerequisites, but familiarity with basic mathematical objects and notions
will be helpful at some points in the course, in particular with some examples. In particular, such objects/notions as:
the rational, real and complex number fields; sets; the idea of surjective, injective and bijective functions;
order relations; the definitions of basic abstract mathematical structures such as groups and fields
(all covered in Mathematics I and II in Prelims).

Course Term: 
Michaelmas
Course Lecture Information: 

16 lectures

Course Weight: 
1.00 unit(s)
Course Level: 
H

Assessment type:

Course Overview: 

To give a rigorous mathematical treatment of the fundamental ideas and results of logic that is suitable for the non-specialist mathematicians and will provide a sound basis for more advanced study. Cohesion is achieved by focusing on the Completeness Theorems and the relationship between provability and truth. Consideration of some implications of the Compactness Theorem gives a flavour of the further development of model theory. To give a concrete deductive system for predicate calculus and prove the Completeness Theorem, including easy applications in basic model theory.

Learning Outcomes: 

Students will be able to use the formal language of propositional and predicate calculus and be familiar with their deductive systems and related theorems. For example, they will know and be able to use the soundness, completeness and compactness theorems for deductive systems for predicate calculus.

Course Synopsis: 

The notation, meaning and use of propositional and predicate calculus. The formal language of propositional calculus: truth functions; conjunctive and disjunctive normal form; tautologies and logical consequence. The formal language of predicate calculus: satisfaction, truth, validity, logical consequence.

Deductive system for propositional calculus: proofs and theorems, proofs from hypotheses, the Deduction Theorem; Soundness Theorem. Maximal consistent sets of formulae; completeness; constructive proof of completeness.

Statement of Soundness and Completeness Theorems for a deductive system for predicate calculus; derivation of the Compactness Theorem; simple applications of the Compactness Theorem.

A deductive system for predicate calculus; proofs and theorems; prenex form. Proof of Completeness Theorem. Existence of countable models, the downward Löwenheim-Skolem Theorem.

Reading List: 
  1. R. Cori and D. Lascar, Mathematical Logic: A Course with Exercises (Part I) (Oxford University Press, 2001), sections 1, 3, 4.
  2. A. G. Hamilton, Logic for Mathematicians (2nd edition, Cambridge University Press, 1988), pp.1-69, pp.73-76 (for statement of Completeness (Adequacy) Theorem), pp.99-103 (for the Compactness Theorem).
  3. W. B. Enderton, A Mathematical Introduction to Logic (Academic Press, 1972), pp.101-144.
  4. D. Goldrei, Propositional and Predicate Calculus: A model of argument (Springer, 2005).
  5. A. Prestel and C. N. Delzell, Mathematical Logic and Model Theory (Springer, 2010).
Further Reading: 
  1. R. Cori and D. Lascar, Mathematical Logic: A Course with Exercises (Part II) (Oxford University Press, 2001), section 8.