Admission requirements
This course is also open as elective choice/keuzevak to mathematics and computer science students.
Description
At the end of the nineteenth and beginning of the twentieth century, mathematicians and logicians such as Georg Cantor, Kurt Gödel, and Alan Turing proved results about the nature of the infinite, truth, and provability itself that would raise fundamental questions and inaugurate intense philosophical discussion. The most prominent metalogical results—that is, concerning logic itself—were Gödel’s first and second Incompleteness Theorems. Gödel’s first Incompleteness Theorem has as its key consequence that there is no way to prove all and only the truths of arithmetic.
This course will introduce these results and will culminate in a proof of Gödel’s First Incompleteness Theorem, along with an informal presentation of Gödel’s Second Theorem. Along the way, we will consider philosophical issues concerning the nature of infinite, computation, truth and provability. We will begin with Cantor’s diagonalization proof that there are different sizes of infinity and Alan Turing’s fundamental results concerning the limits of computability (the halting problem), which have the consequence that no algorithm for first-order logical validity can exist. We will then provide a mathematically rigorous review of first-order logic and will learn proof techniques, which will help us in examining the central results of metalogic: undecidability, compactness, the Löwenheim-Skolem theorem, completeness and, finally, the incompleteness of arithmetic.
Our textbook will be George Boolos, John Burgess, and Richard Jeffrey, Computability and Logic (5th Edition). Weekly problem sets will be required, and there will be a midterm and final exam, with a mix of exercises and short-answer questions.
Course objectives
Students who successfully complete the course will have a good understanding of:
The mathematical account of enumerability and Cantor’s technique of diagonalization.
The theory of Turing computability and familiarity with examples of uncomputable functions.
The syntax and semantics of first-order predicate logic and central metalogical notions.
Basic results in metalogic including the undecidability of first-order logic, the soundness and completeness of first-order logic, compactness, and the Löwnheim-Skolem theorem.
The technique of Gödel numbering and the use of this technique in the proof of the First-Incompleteness Theorem.
Students who successfully complete the course will be able to:
Using mathematical induction to prove basic formal results;
Analyze and think critically about the central results concerning logic and computability considered in the course;
Informally but rigorously consider extensions of these results;
Apply the formal results considered to philosophical questions concerning the nature of infinity, proof, truth, and the mathematical universe.
Timetable
The timetables are available through My Timetable.
Mode of instruction
Seminar
Assessment method
Assessment
Midterm written examination with problems and short answers: 30%
Final written examination with problems and short answers: 50%
Weekly problem sets: 20%
Weighing
The final mark for the course is established by determining the weighted average. To pass the course, the weighted average of the partial grades must be 5.5 or higher.
Resit
The resit consists of one examination for both the midterm and final examination, consisting of a written exam covering the entire course content. The mark for the resit will replace all previously earned marks for the midterm and final exam (80%). No separate resits will be offered for mid- term tests.
Inspection and feedback
How and when an exam review will take place will be disclosed together with the publication of the exam results at the latest. If a student requests a review within 30 days after publication of the exam results, an exam review will have to be organized.
Reading list
G. Boolos, J. Burgess, R. Jeffrey (2007), Computability and Logic, 5th Edition
This text may be purchased online and by ordering at local bookshops. Students are required to purchase a copy in advance. There is no reading for the first class.
Registration
Enrolment through MyStudymap is not possible for this course. Students are requested to submit their preferences for the third-year electives by means of an online registration form. They will receive the instruction and online registration form by email (uMail account); in June for courses scheduled in semester 1, and in December for courses scheduled in semester 2. Registration in uSis will be taken care of by the Education Administration Office.
Contact
For substantive questions, contact the lecturer listed in the right information bar.
For questions about enrolment, admission, etc, contact the Education Administration Office: Huizinga
Remarks
This course is suitable for students in mathematics and computer science, in addition to students enrolled in the Philosophy BA.