## Godel's Theorems

 Unit code: MATH43042 Credit Rating: 15 Unit level: Level 4 Teaching period(s): Semester 2 Offered by School of Mathematics Available as a free choice unit?: N

#### Requisites

Prerequisite

Students need to have seen

• an introduction to Predicate Logic (as for example taught in the last chapter of MATH20302 Introduction to Logic)
• be familiar with an introduction to recursive functions (as for example taught in chapter 3 of MATH33011 Mathematical Logic).

Students are not permitted to take, for credit, MATH43042 in an underdraduate programme and then MATH63042 in a postgraduate programme at the University of Manchester, as the courses are identical.

#### Aims

The main goal is to present a rigorous understanding of Godel's Incompleteness theorems and their most important consequences.

#### Overview

Can a computer be programmed to generate all true statements of mathematics and no false ones? An extraordinary result, proved by Kurt Godel in 1931, shows that even if we restrict ourselves to the most fundamental part of mathematics, namely statements about the natural numbers, the answer to the above question is no. Moreover Godel's method is such that given any "mechanical procedure" for generating true statements about the natural numbers we are actually able to construct a true statement about the natural numbers which will not be generated by that procedure. Later results have shown that such statements can always be chosen to have the simple logical form of an assertion that a particular polynomial equation has no solution over the integers.

Godel's work stands as one of the great landmarks of 20th century thought and has a significance which reaches well beyond mathematics. The course unit will be centred on proofs of Godel's two incompleteness theorems and will examine some of their principal applications.

#### Learning outcomes

On successful completion of this course unit students will be able to:

• write down a Hilbert style proof system for first order Predicate Logic and explain the completeness theorem of this formalism,
• name and apply various tools to manufacture recursive and recursively enumerable sets,
• sketch a proof of Church’s Theorem on Undecidability of Robinson Arithmetic,
• construct a Gödel sentence for every strengthening of Peano Arithmetic,
• apply Tarski’s method of interpretation to detect undecidable structures,
• explain Hilbert’s 10th problem and a strategy towards a negative answer for integers.

#### Assessment methods

• Other - 20%
• Written exam - 80%

#### Assessment Further Information

• Two take home tests weighting 10% each
• End of semester examination: three hour exam weighting 80%

#### Syllabus

(The numbers in square brackets indicate the hours spent on the respective topic by lecturers and feedback time.)

1. A proof system for predicate logic.First order theories, structures and the completeness theorem. [8]

2. Recursive functions and relations, a revision. Basic properties. Primitive recursion. Closure under bounded quantification. Gödel's β-function. Coding of finite sequences. Recursively enumerable sets.  Church-Turing Thesis. [4]

3. Rrepresentation of recursive functions in arithmetic; Robinson Arithmetic. [3]

4. Gödel numbering and the arithmetization of logic. The recursiveness of the proof predicate. Gödel first incompleteness theorem. Tarskis undefinability theorem. [6]

5. Applications of the incompleteness theorem. Undecidability of the predicate calculus and other axiom systems. Peano Arithmetic. [5]

6. Kleenes Enumeration Theorem. Hilberts 10th problem. The MRDP theorem and its corollaries. [5]

7. Gödel's second incompleteness theorem. The limitations of the axiomatic method. [2]

Self contained course notes will be provided, although the first two books listed below cover much of it, albeit using different notation.

• H.B. Enderton, A Mathematical Introduction to Logic, (especially chapter 3), Academic Press,
• J.R. Shoenfield, Mathematical Logic, (chapters 4 and 6). Addison-Wesley 1967,
• Peter Smith, An Introduction to Godels Theorems, Cambridge University Press, 2007,
• Hao Wang, A Logical Journey,  MIT Press, 1997,
• Hao Wang, From Mathematics to Philosophy. RKP 1974,
• G.T. Kneebone, Mathematical Logic and the Foundations of Mathematics. Van Nostrand 1963.

#### Feedback methods

A third of the 33 hours will be used for an opportunity for students' to discuss the work and to provide feedback on their understanding.  Two take home tests provide an opportunity for students to receive feedback.  Students can also get feedback on their understanding during the lecturer's office hour.

#### Study hours

• Lectures - 22 hours
• Tutorials - 11 hours
• Independent study hours - 117 hours

#### Teaching staff

Marcus Tressl - Unit coordinator