Course pages 2012–13
Introductory Logic
Principal lecturer: Dr Bjarki Holm
Taken by: MPhil ACS, Part III
Code: R07
Hours: 8
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).
Aims
This module aims to provide the basic mathematical logic which will be assumed in later courses.
Syllabus
- 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.
Objectives
On completion of this module, students should have a good understanding of propositional logic and first-order logic, their proof systems and their models.
Coursework
Exercises will be provided.
Practical work
None.
Assessment
The course will be assessed by means of a written test to be set and marked by the course lecturer.
Recommended reading
Enderton, H.B. (2001). A mathematical introduction to logic. Academic Press (2nd ed.).