This web page provides the module description, and organisational information for students taking the second half of MSM3P17 or MSM4P17 on Computability and Logic in the academic year 2014-15 at Birmingham University.
Lecturer: Dr Richard Kaye, Room 308 Watson building. Email: R.W.Kaye@bham.ac.uk.
Office hours: TBA.
Logic is concerned with the consistency of sets of axioms, and setting up precise rules for deriving theorems from these axioms. Two significant theorems (the Soundness Theorem and the Completeness Theorem) will be proved. The Soundness and Completeness Theorems have important applications for mathematics. In one direction, they are applied to give rigorous proofs that certain statements cannot be proved from given axioms. In the other direction, they are applied to provide new interesting mathematical structures such as nonstandard versions of the integers which behave like the usual finite integers in many ways but which nevertheless contain infinite numbers.
By the end of the module the student should be able to:
The Soundness and Completeness Theorems are complex theorems with
many aspects that will be new to students. The approach I will take is
to first look at simpler cases of these theorems, applied to easy
systems of proof, and in looking a number of these systems build up
the techniques to look at the predicate calculus (also called
first-order logic) and Completeness and Soundness for that.
I will be following The Mathematics of Logic
(Cambridge
University Press, 2007) in this course. There are a number of copies
available in the library, some of which are on short loan. You may
well wish to buy a copy. Additional notes (many of which are much more
advanced than you will need) can be found at
Lectures will be at 9am on Thursdays in Nuffield G13 and 4pm on Fridays in Arts 4 (101) weeks 1-11. Examples classes will be on Fridays at 5pm in in Arts 4 (101) weeks 2,4,6,8,10. Assessed work will be issued well in advance of the classes. You should read and at least start to attempt all questions prior to the class. Further announcements, hints and other help will be available in the class. Work is to be handed in to the smaller white pigeonhole with the lecturer's name on the second floor of Watson building by 4pm on the Friday following the examples class. Marked work and feedback will be provided as soon as possible, normally the following exercise class.
The five assessments have equal weight and in total count as 5% of the total mark for the 20-credit module MSM3P17/MSM4P17, the other 5% continuous assessment being from the computability section.
The logic half of this module is aimed at proving and using two main theorems, the Completeness and Soundness Theorems for first order logic. Since the full discussion of these will take all term, and since these are the main goal of the half-module you cannot succeed this module and achieve the course objectives by just doing the first 80% of the course and omitting the last 20%. For this reason, the final assessment is compulsary. The full continuous assessment element of the module is made from assessment 5 plus the best three marks from assessments 1-4.
The exam in the summer will count 90%. There are 3 questions on computability and 3 on logic and you will be required to answer 4 questions.