You are here: Mathematics > undergraduate > undergraduate studies > course units > level 3 units > MATH43001
School of Mathematics

# MATH43001/MATH33001 - 2009/2010

General Information
• Title: Predicate Logic
• Unit code: MATH43001/MATH33001
• Credits: 15 (MATH43001), 10 (MATH33001)
• Prerequisites: MATH20302 Propositional Logic 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.
• Co-requisite units: None
• School responsible: Mathematics
• Members of staff responsible:
Page Contents
Other Resources

## 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 MATH43001. Not everything will be covered in the lectures for MATH33001. The lectures will be supplemented by additional reading for MATH43001.

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 MATH43001. In addition students should expect to do at least four hours private study each week for this course unit (and seven hours for MATH43001).

### Assessment

Coursework: weighting 20%
End of semester examination: two hours (MATH33001), two and a half hours (MATH43001); weighting 80%