THE UNIVERSITY of EDINBURGH

DEGREE REGULATIONS & PROGRAMMES OF STUDY 2017/2018

University Homepage
DRPS Homepage
DRPS Search
DRPS Contact
DRPS : Course Catalogue : School of Philosophy, Psychology and Language Sciences : Philosophy

Postgraduate Course: Logic, Computability and Incompleteness (PHIL11114)

Course Outline
SchoolSchool of Philosophy, Psychology and Language Sciences CollegeCollege of Humanities and Social Science
Credit level (Normal year taken)SCQF Level 11 (Postgraduate) AvailabilityNot available to visiting students
SCQF Credits20 ECTS Credits10
SummaryThis course examines some fundamental topics relating to first-order 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 co-taught 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 first-order logic, linking uncomputability and the halting problem to undecidability of first-order logic. We will then study recursive functions and their construction, followed by first-order 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)
Pre-requisites Co-requisites
Prohibited Combinations Other requirements None
Course Delivery Information
Not being delivered
Learning Outcomes
On completion of this course, the student will be able to:
  1. demonstrate analytical and abstract problem solving skills
  2. understand and engage with key limitative results in logic and computability theory, including the halting problem, the undecidability of first-order logic, and the incompleteness of first-order arithmetic
  3. grasp and analyze complex metatheoretical concepts
  4. formulate rigorous and precise pieces of logico-mathematical reasoning.
  5. 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
First-Order Logic Revisited
Uncomputability and Undecidability
Completeness, Compactness and Lowenheim-Skolem
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
KeywordsTuring machines,recursive functions,first-order meta-theory,Godel's theorems
Contacts
Course organiserDr Paul Schweizer
Tel: (0131 6)50 2704
Email: Joshua.Stapp@ed.ac.uk
Course secretaryMiss Lynsey Buchanan
Tel: (0131 6)51 5002
Email:
Navigation
Help & Information
Home
Introduction
Glossary
Search DPTs and Courses
Regulations
Regulations
Degree Programmes
Introduction
Browse DPTs
Courses
Introduction
Humanities and Social Science
Science and Engineering
Medicine and Veterinary Medicine
Other Information
Combined Course Timetable
Prospectuses
Important Information
 
© Copyright 2017 The University of Edinburgh - 6 February 2017 9:15 pm