2008/09 Taught Postgraduate Module Catalogue

MATH5102M Advanced Logic

15 creditsClass Size: 20

Module manager: Professor S. B. Cooper
Email: s.b.cooper@leeds.ac.uk

Taught: Semester 2 (Jan to Jun) View Timetable

Year running 2008/09

Pre-requisites

MATH2040

Mathematical Logic 1

This module is mutually exclusive with

MATH3102

Mathematical Logic 2

This module is not 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? (answer: no) Are mathematicians necessary? (answer: yes). The main goal is to prove Godel'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.

Objectives

On completion of this module, students should be able to:
a) carry out elementary proofs in first-order formal logic and Peano Arithmetic;
b) prove representability and recursiveness of basic number-theoretic functions and relations;
c) understand and reproduce proofs of Godel's Completeness Theorem for predicate logic, Godel's Incompleteness Theorems for Peano Arithmetic, Lob's Theorem and related results;
d) describe connections between incompleteness, consistency, computability and undecidability;
e) show a capacity for independent study, including further development of the theory via a range of more challenging homework problems, and through an oral presentation.

Syllabus

Revision of first-order logic including Godel's Completeness Theorem; the axiomatic method and formal Peano Arithmetic; recursive functions and representability; the arithmetization of syntax and Godel's First Incompleteness Theorems; Lob's Theorem and the Second Incompleteness Theorem; consistency, undecidability and computability; non-standard models of arithmetic. Additional topics chosen from: decidable fragments of arithmetic, Rosser's theorem, and reflection principles.

Teaching methods

Delivery type	Number	Length hours	Student hours
Example Class	7	1.00	7.00
Lecture	26	1.00	26.00
Private study hours			117.00
Total Contact hours			33.00
Total hours (100hr per 10 credits)			150.00

Private study

Reading lecture notes: 72 hours;
Solving coursework problems: 25 hours;
Preparing for examination and oral presentation: 20 hours.

Opportunities for Formative Feedback

Regular problems sheets.

Methods of assessment

Coursework

Assessment type	Notes	% of formal assessment
Presentation	10 minute oral presentation	15.00
Total percentage (Assessment Coursework)		15.00

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

Exams

Exam type	Exam duration	% of formal assessment
Standard exam (closed essays, MCQs etc)	3 hr	85.00
Total percentage (Assessment Exams)		85.00

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

Reading list

The reading list is available from the Library website

Last updated: 24/03/2010

Disclaimer

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