Course pages 2012–13
Principal lecturer: Dr Bjarki Holm
Taken by: MPhil ACS, Part III
Prerequisites: Basic familiarity with discrete mathematics and set theory (for example, to the level of Discrete Mathematics I and II from Part 1A of the Cambridge Computer Science Tripos).
This module aims to provide the basic mathematical logic which will be assumed in later courses.
- Propositional calculus: truth-functional models, a deductive calculus and proofs of soundness and completeness.
- First-order predicate logic: Tarskian truth and models, a deductive calculus, completeness and a proof of soundness.
- Compactness and Loewenheim-Skolem theorems.
- First-order theories and their models. Some examples with indications (and in some cases proofs) of which theories are complete/incomplete: dense linear orders, natural numbers with successor, Peano arithmetic, real-closed fields.
On completion of this module, students should have a good understanding of propositional logic and first-order logic, their proof systems and their models.
Exercises will be provided.
The course will be assessed by means of a written test to be set and marked by the course lecturer.
Enderton, H.B. (2001). A mathematical introduction to logic. Academic Press (2nd ed.).