# 2016/17 Taught Postgraduate Module Catalogue

## MATH5104M Advanced Proof and Computation

### 20 creditsClass Size: 30

**Module manager:** Dr Paul Shafer**Email:** TBC

**Taught:** Semester 2 (Jan to Jun) View Timetable

**Year running** 2016/17

### Pre-requisite qualifications

Propositional logic and beginnings of predicate logic### Pre-requisites

MATH2040 | Mathematical Logic 1 |

### This module is mutually exclusive with

MATH3104 | Proof and Computation |

**This module is approved as an Elective**

### Module summary

Metamathematics and proof theory try to answer fundamental questions about axiomatic theories (e.g. number theory) like: - Are they consistent (free from contradiction)?- How do we know?- Could they be developed by computers without human assistance?- Are mathematicians necessary? The main goal is to prove Gödel's Incompleteness Theorems (1931) which show that if a formal theory has strong enough axioms then there are statements which it can neither prove nor refute. This module will also provide background to the impact of Gödel's Theorem on the modern world, and the way it sets an agenda for further research.### Objectives

On completion of this module, students should be able to:a) carry out elementary proofs in systems of arithmetic;

b) prove representability and recursiveness of basic number-theoretic functions and relations;

c) understand and reproduce proofs of Gödel's Incompleteness Theorem and related results;

d) describe connections between incompleteness, consistency, computability and undecidability;

e) show a capacity for independent thinking, including further development of the theory via a range of more challenging homework problems.

**Learning outcomes**

a) An understanding of basic systems of arithmetic;

b) an understanding of the notions of compubtability, recursive enumerability and representability;

c) A knowledge of Gödel's Incompleteness Theorem, its proof and implications.

**Skills outcomes**

Diagonalisation

Understanding how a basic computing device works and can be programmed

How to show unprovability results

### Syllabus

- Revision of first-order logic including Gödel's Completeness Theorem;

- The axiomatic method and basic systems of arithmetic;

- register machines;

- recursive functions and representability;

- the arithmetization of syntax and Gödel's First Incompleteness Theorem;

- consistency, undecidability and computability;

- Further topics from amongst the following: Second Incompleteness Theorem, Löb's Theorem, relative computation and Turing degrees.

### Teaching methods

Delivery type | Number | Length hours | Student hours |

Lecture | 44 | 1.00 | 44.00 |

Private study hours | 156.00 | ||

Total Contact hours | 44.00 | ||

Total hours (100hr per 10 credits) | 200.00 |

### Private study

Homework questions in which the student is asked to display independent thinking in order to further develop the theory described in class.### Opportunities for Formative Feedback

Examples classes and final exam.### Methods of assessment

**Exams**

Exam type | Exam duration | % of formal assessment |

Standard exam (closed essays, MCQs etc) | 3 hr | 100.00 |

Total percentage (Assessment Exams) | 100.00 |

Normally resits will be assessed by the same methodology as the first attempt, unless otherwise stated

### Reading list

There is no reading list for this moduleLast updated: 20/07/2016

## Browse Other Catalogues

- Undergraduate module catalogue
- Taught Postgraduate module catalogue
- Undergraduate programme catalogue
- Taught Postgraduate programme catalogue

Errors, omissions, failed links etc should be notified to the Catalogue Team.PROD