MATH33001/43001 - 2008/2009
- Title: Predicate Calculus
- Unit code: MATH33001/43001
- Credits: 10 (MATH33001), 15 (MATH43001)
- Prerequisites: Propositional Calculus
- Corequisites: none
- School responsible: Mathematics
- Members of staff responsible: Dr. Marcus Tressl
Specification
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.
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.
Learning Outcomes
On successful completion of the course unit the 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.
Prerequisites
Some familiarity with the propositional calculus. This may be gained by study of a chapter(s) on propositional calculus up to the completeness theorem from one of the many logic textbooks, such as the ones listed below.Future topics requiring this course unit
This course will be a prerequisite for Gödel's Incompleteness Theorem
Syllabus
The following is the syllabus for MATH43001. Not everything will be covered in the lectures for MATH33001. The lectures will be supplemented by additional reading for MATH43001.- Introduction and Revision of Propositional Calculus[2 lectures]
- The language of predicate calculus: Alphabet, terms, formulas, sentences, complexity of formulas, syntactic manipulation of formulas, subformulas [8 lectures]
- Formal proofs: Inference rules, normal form theorems, consistent sets of formula, Deduction Theorem, deductive closure, theories [8 lectures]
- Structures: First order structures and Tarski's definition of truth, satisfaction, logical consequence, correctness of proofs, term models, basic manipulation of structures [7 lectures]
- 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]
- 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 MATH43001.