Postgraduate Course: Logic, Computability and Incompleteness (PHIL11114)
Course Outline
| School | School of Philosophy, Psychology and Language Sciences |
College | College of Humanities and Social Science |
| Course type | Standard |
Availability | Available to all students |
| Credit level (Normal year taken) | SCQF Level 11 (Postgraduate) |
Credits | 20 |
| Home subject area | Philosophy |
Other subject area | None |
| Course website |
None |
Taught in Gaelic? | No |
| Course description | The 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 G¿del's two incompleteness theorems, and allied results employing the diagonal lemma, including Tarski's Theorem and L¿b's Theorem.
Shared with the undergraduate course Logic, Computability and Incompleteness PHIL10133 |
Entry Requirements (not applicable to Visiting Students)
| Pre-requisites |
Students MUST have passed:
Logic 1 (PHIL08004)
|
Co-requisites | |
| Prohibited Combinations | |
Other requirements | Students must have passed Logic 1 or equivalent course in their previous undergraduate studies. |
| Additional Costs | None |
Information for Visiting Students
| Pre-requisites | Students must have passed Logic 1 or equivalent course in their previous undergraduate studies. |
| Displayed in Visiting Students Prospectus? | Yes |
Course Delivery Information
| Not being delivered |
Summary of Intended 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 first-order logic, and the
incompleteness of first-order 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. |
Assessment Information
| There will be an opportunity for formative assessment and guidance based on exercise sets assigned during the semester. The course will be assessed by a final examination; the mark for the course will be based on this examination. |
Special Arrangements
| None |
Additional Information
| Academic description |
Not entered |
| Syllabus |
Not entered |
| Transferable skills |
Not entered |
| 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. |
| Study Abroad |
Not entered |
| Study Pattern |
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 Lynsey Buchanan
Tel: (0131 6)51 5002
Email: Lynsey.Buchanan@ed.ac.uk |
|
|
University Homepage