- Lecturer: Jochen Koenigsmann
General Prerequisites:
There are no formal prerequisites, but familiarity with basic mathematical objects and notions will be helpful at some points in the course, in particular with some examples. In particular, such objects/notions as: the rational, real and complex number fields; sets; the idea of surjective, injective and bijective functions; order relations; the definitions of basic abstract mathematical structures such as groups and fields (all covered in Mathematics I and II in Prelims).
Course Term: Michaelmas
Course Lecture Information: 16 lectures
Course Weight: 1
Course Level: H
Assessment Type: Written Examination
Course Overview:
To give a rigorous mathematical treatment of the fundamental ideas and results of logic that is suitable for the non-specialist mathematicians and will provide a sound basis for more advanced study. Cohesion is achieved by focusing on the Completeness Theorems and the relationship between provability and truth. Consideration of some implications of the Compactness Theorem gives a flavour of the further development of model theory. To give a concrete deductive system for predicate calculus and prove the Completeness Theorem, including easy applications in basic model theory.
Learning Outcomes:
Students will be able to use the formal language of propositional and predicate calculus and be familiar with their deductive systems and related theorems. For example, they will know and be able to use the soundness, completeness and compactness theorems for deductive systems for predicate calculus.
Course Synopsis:
The notation, meaning and use of propositional and predicate calculus. The formal language of propositional calculus: truth functions; conjunctive and disjunctive normal form; tautologies and logical consequence. The formal language of predicate calculus: satisfaction, truth, validity, logical consequence.
Deductive system for propositional calculus: proofs and theorems, proofs from hypotheses, the Deduction Theorem; Soundness Theorem. Maximal consistent sets of formulae; completeness; constructive proof of completeness.
Statement of Soundness and Completeness Theorems for a deductive system for predicate calculus; derivation of the Compactness Theorem; simple applications of the Compactness Theorem.
A deductive system for predicate calculus; proofs and theorems; prenex form. Proof of Completeness Theorem. Existence of countable models, the downward Löwenheim-Skolem Theorem.
Deductive system for propositional calculus: proofs and theorems, proofs from hypotheses, the Deduction Theorem; Soundness Theorem. Maximal consistent sets of formulae; completeness; constructive proof of completeness.
Statement of Soundness and Completeness Theorems for a deductive system for predicate calculus; derivation of the Compactness Theorem; simple applications of the Compactness Theorem.
A deductive system for predicate calculus; proofs and theorems; prenex form. Proof of Completeness Theorem. Existence of countable models, the downward Löwenheim-Skolem Theorem.