Postgraduate Course: Logic, Computability and Incompleteness (PHIL11114)
|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
|Summary||This course examines some fundamental topics relating to first-order logic and the theory of computability, with particular emphasis on key limitative results.
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)
||Other requirements|| None
Course Delivery Information
|Academic year 2018/19, Available to all students (SV1)
|Learning and Teaching activities (Further Info)
Lecture Hours 20,
Feedback/Feedforward Hours 2,
Programme Level Learning and Teaching Hours 4,
Directed Learning and Independent Learning Hours
|Assessment (Further Info)
|Additional Information (Assessment)
||The course will be assessed 100% by exam; the mark for the course will be based on this examination.
||Guidance based on exercise sets assigned during the semester.
||Hours & Minutes
|Main Exam Diet S2 (April/May)||2:00|
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 first-order logic, and the incompleteness of first-order arithmetic
- grasp and analyze complex metatheoretical concepts
- formulate rigorous and precise pieces of logico-mathematical reasoning.
- deploy rigorous formal methods including diagonalization and proof by mathematical induction.
|Core Syllabus Topics|
Cardinality, Enumerability, Diagonalization
Turing Machines and Computability
First-Order Logic Revisited
Uncomputability and Undecidability
Completeness, Compactness and Lowenheim-Skolem
Diagonal Lemma, Godel and Tarski Theorems
Provability Predicates and Lob's Theorem
 Boolos, G. & R. Jeffrey (1989) Computability and Logic. Cambridge University Press, 3rd edition.
 Machover, M (1996) Set Theory, Logic and Their Limitations. Cambridge University Press.
 Mendelson, E. (2015) An Introduction to Mathematical Logic. Chapman and Hall/CRC 6th edition
 Enderton, H. (2001) A Mathematical Introduction to Logic.
 Smith, P. (2013) An Introduction to Godel's Theorems. Cambridge University
|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
|Keywords||Turing machines,recursive functions,first-order meta-theory,Godel's theorems
|Course organiser||Dr Paul Schweizer
Tel: (0131 6)50 2704
|Course secretary||Ms Becky Verdon
Tel: (0131 6)51 5002