Undergraduate Course: Logic, Computability and Incompleteness (PHIL10133)
Course Outline
School  School of Philosophy, Psychology and Language Sciences 
College  College of Humanities and Social Science 
Credit level (Normal year taken)  SCQF Level 10 (Year 3 Undergraduate) 
Availability  Available to all students 
SCQF Credits  20 
ECTS Credits  10 
Summary  This course examines some fundamental topics relating to firstorder Logic and the theory of computability, with particular emphasis on key limitative results. 
Course description 
This course will focus on key metatheoretical results linking computability and logic. In particular, Turing machines and their formalization in firstorder logic, linking uncomputability and the halting problem to undecidability of firstorder logic. We will then study recursive functions and their construction, followed by firstorder formalizations of arithmetic, particularly Robinson arithmetic and Peano arithmetic. We will then turn to the topic of the arithmetization of syntax and the diagonal lemma, before proceeding to prove some of the main limitative results concerning formal systems, in particular G?del's two incompleteness theorems, along with allied results employing the diagonal lemma, including Tarski's Theorem and Lob's Theorem.

Entry Requirements (not applicable to Visiting Students)
Prerequisites 
It is RECOMMENDED that students have passed
Logic 1 (PHIL08004)

Corequisites  
Prohibited Combinations  
Other requirements  Students studying Mathematics and/or Informatics may be able to take this course without the prerequisites; this must be discussed with the Course Organiser who can give the necessary permission. 
Information for Visiting Students
Prerequisites  Visiting students should have at least 3 Philosophy courses at grade B or above (or be predicted to obtain this). We will only consider University/College level courses. 
High Demand Course? 
Yes 
Course Delivery Information
Not being delivered 
Learning Outcomes
Upon successful completion of the course, students will be able to demonstrate:
¿ familiarity with the general philosophical/mathematical project of Hilbert's program and how this is impacted by the technical results explored in the course;
¿ thorough understanding of some key limitative results in logic and computability, including the halting problem, the undecidability of firstorder logic, and the incompleteness of firstorder arithmetic;
¿ ability to employ abstract, analytical and problem solving skills;
¿ ability to formulate clear and precise pieces of mathematical reasoning.
Also, students will demonstrate the following transferable skills:
¿ evaluating abstract theoretical claims;
¿ grasping and analysing complex metatheoretical concepts;
¿ deploy rigorous formal methods.

Reading List
The following is a sample bibliography, intended to indicate the type of reading that will be covered in the course.
[1] Boolos, G.S., J.P. Burgess & R.C. Jeffrey (2002) Computability and Logic, 4th edition, Cambridge University Press.
[2] Machover, M (1996) Set Theory, Logic and Their Limitations, Cambridge University Press.
[3] Enderton, H. (2001) A Mathematical Introduction to Logic.
[4] Mendelson, E. (1987) An Introduction to Mathematical Logic.
[5] Smith, P. (2007) An Introduction to G¿del's Theorems, Cambridge University Press.

Additional Information
Graduate Attributes and Skills 
Not entered 
Keywords  Not entered 
Contacts
Course organiser  Dr Paul Schweizer
Tel: (0131 6)50 2704
Email: paul@inf.ed.ac.uk 
Course secretary  Miss Susan Richards
Tel: (0131 6)51 3733
Email: sue.richards@ed.ac.uk 

