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

2019-2020
Lecturer(s): 
Prof. Jochen Koenigsmann
General Prerequisites: 

None.

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.