Postgraduate Course: Logic, Computability and Incompleteness (PHIL11114)
Course Outline
School  School of Philosophy, Psychology and Language Sciences 
College  College of Humanities and Social Science 
Credit level (Normal year taken)  SCQF Level 11 (Postgraduate) 
Availability  Not available to visiting 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.
Shared with the undergraduate course Logic, Computability and Incompleteness PHIL10133
For courses cotaught with undergraduate students and with no remaining undergraduate spaces left, a maximum of 8 MSc students can join the course. Priority will be given to MSc students who wish to take the course for credit on a first come first served basis after matriculation. 
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 Godel'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 

Corequisites  
Prohibited Combinations  
Other requirements  None 
Course Delivery Information
Not being delivered 
Learning Outcomes
On completion of this course, the student will be able to:
 demonstrate analytical and abstract problem solving skills
 understand and engage with key limitative results in logic and computability theory, including the halting problem, the undecidability of firstorder logic, and the incompleteness of firstorder arithmetic
 grasp and analyze complex metatheoretical concepts
 formulate rigorous and precise pieces of logicomathematical reasoning.
 deploy rigorous formal methods including diagonalization and proof by mathematical induction.

Reading List
Core Syllabus Topics
Cardinality, Enumerability, Diagonalization
Turing Machines and Computability
Recursive Functions
FirstOrder Logic Revisited
Uncomputability and Undecidability
Completeness, Compactness and LowenheimSkolem
Formal Arithmetic
Diagonal Lemma, Godel and Tarski Theorems
Provability Predicates and Lob's Theorem
Recommended references:
[1] Boolos, G. & R. Jeffrey (1989) Computability and Logic. Cambridge University Press, 3rd edition.
[2] Machover, M (1996) Set Theory, Logic and Their Limitations. Cambridge University Press.
[3] Mendelson, E. (2015) An Introduction to Mathematical Logic. Chapman and Hall/CRC 6th edition
[4] Enderton, H. (2001) A Mathematical Introduction to Logic.
[5] Smith, P. (2013) An Introduction to Godel's Theorems. Cambridge University
Reading List and all assigned reading material available on Learn.

Additional Information
Course URL 
Please see Learn page 
Graduate Attributes and Skills 
Ability to grasp and analyze complex theoretical concepts
Ability to utilize rigorous formal methods
Ability to analyse philosophical arguments
Ability to articulate and defend positions in a philosophical debate

Additional Class Delivery Information 
The course is taught by Dr Paul Schweizer 
Keywords  Turing machines,recursive functions,firstorder metatheory,Godel's theorems 
Contacts
Course organiser  Dr Paul Schweizer
Tel: (0131 6)50 2704
Email: paul@inf.ed.ac.uk 
Course secretary  Miss Lynsey Buchanan
Tel: (0131 6)51 5002
Email: Lynsey.Buchanan@ed.ac.uk 

