Undergraduate Course: Logic, Computability and Incompleteness (PHIL10133)
Course Outline
| School | School of Philosophy, Psychology and Language Sciences |
College | College of Arts, Humanities and Social Sciences |
| Credit level (Normal year taken) | SCQF Level 10 (Year 4 Undergraduate) |
Availability | Available to all students |
| SCQF Credits | 20 |
ECTS Credits | 10 |
| Summary | This course examines some fundamental topics relating to first-order 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 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, 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 |
It is RECOMMENDED that students have passed
Logic 1 (PHIL08004)
|
Co-requisites | |
| Prohibited Combinations | |
Other requirements | ***Mathematics and/or Informatics Secretaries - please contact Course Secretary prior to enrolling students onto this course***
Students studying Mathematics and/or Informatics may be able to take this course without the pre-requisites; this must be discussed with the Course Organiser who can give the necessary permission.
This is an advanced logic course and interested philosophy students are strongly recommended to take a look at Richard Jeffreys Formal Logic: Its Scope and Limits, particularly chapter 4 on Multiple Generality and chapter 5 on Identity, in advance of the course. If you have any doubts about the suitability of this course given your background, please consult the course organiser prior to enrolling. |
Information for Visiting Students
| Pre-requisites | Visiting students should have completed at least 3 Philosophy courses at grade B or above. We will only consider University/College level courses. Applicants should note that, as with other popular courses, meeting the minimum does NOT guarantee admission. **Please note that 3rd year Philosophy courses are high-demand, meaning that they have a very high number of students wishing to enrol in a very limited number of spaces.** These enrolments are managed strictly by the Visiting Student Office, in line with the quotas allocated by the department, and all enquiries to enrol in these courses must be made through the CAHSS Visiting Student Office. It is not appropriate for students to contact the department directly to request additional spaces. |
| High Demand Course? |
Yes |
Course Delivery Information
|
| Academic year 2021/22, Available to all students (SV1)
|
Quota: 0 |
| Course Start |
Semester 1 |
Timetable |
Timetable |
| Learning and Teaching activities (Further Info) |
Total Hours:
200
(
Programme Level Learning and Teaching Hours 4,
Directed Learning and Independent Learning Hours
196 )
|
| Assessment (Further Info) |
Written Exam
0 %,
Coursework
100 %,
Practical Exam
0 %
|
| Additional Information (Assessment) |
Midterm Assignment (30%); Final Take Home Test (70%) |
| Feedback |
Not entered |
| No Exam Information |
|
| Academic year 2021/22, Part-year visiting students only (VV1)
|
Quota: 1 |
| Course Start |
Semester 1 |
Timetable |
Timetable |
| Learning and Teaching activities (Further Info) |
Total Hours:
200
(
Seminar/Tutorial Hours 22,
Programme Level Learning and Teaching Hours 4,
Directed Learning and Independent Learning Hours
174 )
|
| Assessment (Further Info) |
Written Exam
0 %,
Coursework
100 %,
Practical Exam
0 %
|
| Additional Information (Assessment) |
Midterm Assignment (30%); Final Take Home Test (70%) |
| Feedback |
Not entered |
| No Exam Information |
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.
|
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 Ann-Marie Cowe
Tel: (0131 6)50 3961
Email: Annmarie.Cowe@ed.ac.uk |
|
|
University Homepage