Introductory description

This module will develop the metatheory of propositional and first-order logic. Our primary goal will be to show that a proof system similar to that presented in Logic I is sound (i.e. proves only logically true sentences) and complete (proves all logically true sentences). In order to better understand how we prove things about (as opposed to within) a proof system, we will first study the syntax, semantics, and proof theory of propositional logic. We will then consider Tarski's definitions of satisfaction and truth in a model and proceed to develop the Henkin completeness proof for first-order logic. Other topics covered along the way will include countable versus uncountable sets, the compactness theorem, and the expressive limitations of first-order logic. PH210 is recommended as a prerequisite for PH340 (Logic III: Incompleteness and Undecidability), PH341 (Modal Logic), and PH345 (Computability Theory).

Module aims

Outline syllabus

This is an indicative module outline only to give an indication of the sort of topics that may be covered. Actual sessions held may differ.

• Week 1: Introduction, set theory, inductive definitions
• Week 2: Syntax and semantics of propositional logic
• Week 3: Natural deduction
• Week 4: Soundness and completeness of propositional logic
• Week 5: Syntax and semantics of first-order logic
• Week 7: Semantic notions, theories and models
• Week 8: Natural deduction and soundness for first-order logic
• Week 9: Completeness for first-order logic
• Week 10: The compactness theorem and applications

Learning outcomes

By the end of the module, students should be able to:

• Demonstrate knowledge of the Soundness and Completeness Theorems for propositional and first-order logic and related technical results and definitions (subject knowledge and understanding)
• Understand the significance these concepts and results have for logic and mathematics (cognitive skills)
• Use and define concepts with precision, both within formal and discursive contexts (key skills)
• Write precise mathematical proofs (subject specific skills)

Indicative reading list

Our primary text will be a version of the Open Logic text customised for PH210.

The same material is also covered in a number of other sources including:

Logic and Structure, 5th edition by Dirk van Dalen, Springer Verlag, 2008.

Much of the material we will be covering is also presented at a more elementary level in chapters 15–19 of the textbook for PH136 (Logic I):

Language, Proof, and Logic by Jon Barwise and John Etchemendy, CSLI Publications, 2002.

Students desiring additional background on problem solving techniques are also encouraged to
obtain:

How to Prove It by Daniel J. Velleman, Cambridge University Press, 2006.

Subject specific skills

Demonstrate knowledge of the Soundness and Completeness Theorems for propositional and first-order logic and related technical results and definitions
Understand the significance these concepts and results have for logic and mathematics
Use and define concepts with precision, within both formal and discursive contexts

Transferable skills

Understand definitions and proof techniques from metalogic applicable in other domains—e.g. such as mathematical and structural induction, basic set theoretic operations and constructions
The ability to comprehend and construct precise mathematical proofs