MATH33001/43001 - 2008/2009

 

Specification

Aims

To introduce students to the formal notions of language, proof, semantics, and completeness with quantificational logic, in order to:

• improve their understanding and appreciation of the foundations of mathematics and
• provide the necessary background knowledge for later logic course units.

Brief Description of the unit

What do we mean by saying that a mathematical statement is true? Can we show that mathematics is consistent? Can mathematics be reduced to computer programming? In order to answer such questions it is necessary to develop a framework which allows to speak in a mathematically correct way about formulas, proofs, truth, etc. This motivates the study of mathematical logic. Predicate logic provides remarkable insight into these questions by providing a precise formalism capable of expressing all ordinary mathematics. The course will lead up to a proof of the completeness theorem, a striking result of Kurt Gödel (1930), which demonstrates the equivalence of a natural notion of logical consequence with provability in a certain axiomatic system.

Learning Outcomes

On successful completion of this course unit students will

• appreciate how arguments involving predicates can be formalised semantically and syntactically and how these are connected (via the Completeness Theorem);
• in simple cases be able to construct formal proofs and counterexamples using semantics.
• in simple cases be able to analyse mathematical structures with first-order logic.

Future topics requiring this course unit

MATH43042 Gödel's Theorems,

Syllabus

The following is the syllabus for '4th year Course Code'. Not everything will be
covered in the lectures for '3rd year Course Code'. The lectures will be
supplemented by additional reading for '4th year Course Code'.

1. Introduction and Revision of Propositional Calculus[2 lectures]
2. The language of predicate calculus: Alphabet, terms, formulas, sentences, complexity of formulas, syntactic manipulation of formulas, subformulas [8 lectures]
3. Formal proofs: Inference rules, normal form theorems, consistent sets of formula, Deduction Theorem, deductive closure, theories [8 lectures]
4. Structures: First order structures and Tarski's definition of truth, satisfaction, logical consequence, correctness of proofs, term models, basic manipulation of structures [7 lectures]
5. Completeness theorem: We show that every valid logical expression is provable, i.e. we give a semantic reformulation of proofs which is fundamental to many parts of logic [5 lectures]
6. Applications and consequences of the completeness theorem: The compactness theorem, axiomatizability of classes of first order structures [3 lectures]

Textbooks

• Enderton, Herbert B; A mathematical introduction to logic. Second edition. Harcourt/Academic Press, Burlington, MA, 2001. xii+317 pp. ISBN: 0-12- 238452-0
• Cori, René, Lascar, Daniel; Mathematical logic. A course with exercises. Part I. Propositional calculus, Boolean algebras, predicate calculus. Translated from the 1993 French original by Donald H. Pelletier. With a foreword to the original French edition by Jean-Louis Krivine and a foreword to the English edition by Wilfrid Hodges. Oxford University Press, Oxford, 2000. xx+338 pp. ISBN: 0-19-850049-1; 0-19-850048-3
• Hamilton, A. G. Logic for mathematicians. Second edition. Cambridge University Press, Cambridge, 1988. viii+228 pp. ISBN: 0-521-36865-0 03-01
• Goldrei, Derek; Propositional and Predicate Calculus: A Model of Argument. Springer 2005, VIII, 315 p., ISBN: 978-1-85233-921-0

Teaching and learning methods

Three lectures each week which will include opportunities to discuss problems from the Example Sheets. The lectures will be supplemented by additional reading for '4th year Course Code'.

Assessment

Coursework: weighting 20%

End of semester examination: two hours ('3rd year Course Code'), three hours ('4th year Course Code'); weighting 80%

to the top

Arrangements

Reading Assignments

Some of the details concerning languages for predicate logic with function symbols and equality and the proof of the completeness theorem will not be covered in lectures but left as reading assignments.