MATH43042 - 2007/2008

 

Specification

Aims

To introduce the student to Gödel's two incompleteness theorems and to their most important corollaries.

Brief Description of the unit

Can a computer be programmed to generate all true statements of mathematics and no false ones? An extraordinary result, proved by Kurt Gödel 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 Gödel'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 numbers which will not be generated by that procedure.

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

Learning Outcomes

On successful completion of this course unit students will

• be familiar with the notion of recursive function;
• have developed a facility in the manipulation and application of these functions, with particular emphasis on applications to logic and decision problems.

Future topics requiring this course unit

None.

Syllabus

1. The completeness theorem for the predicate calculus: a review. First order theories. [2 lectures]
2. Recursive functions and relations. Basic properties. Primitive recursion. Closure under bounded quantification. [4]
3. Gödel's β-function. Coding of finite sequences. Recursively enumerable sets and the arithmetic hierarchy. Church's Thesis. [5]
4. Gödel numbering and the arithmetization of logic. The recursiveness of the proof predicate. Gödel's first incompleteness theorem. Tarski's undefinability theorem. [6]
5. Applications of the incompleteness theorem to show the undecidability of the predicate calculus and other axiom systems. Examples of decidable theories: Presburger arithmetic. [8]
6. Gödel's second incompleteness theorem. The philosophical impact of Gödel's work. The limitations of the axiomatic method. [2]

Textbooks

• 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.
• G.T. Kneebone, Mathematical Logic and the Foundations of Mathematics. Van Nostrand 1963.
• Hao Wang, From Mathematics to Philosophy. RKP 1974.

Teaching and learning methods

24 lectures, 7 examples classes and assigned reading

Assessment

Mid-semester coursework: two take home tests weighting 20%

End of semester examination: two and a half hours weighting 80%

to the top

Arrangements

Timing of the course

The classes will take place in the eight weeks prior to the Easeter vacation. The examination will take place soon after the Easter vacation and before the normal examination period.