# Logic II : Metatheory (PH210-15)

## TIMING & CATS

This module runs in the Autumn Term and is worth 15 CATS.

## MODULE DESCRIPTION

This module will develop the metatheory of propositional and first-order logic. The primary goal is to show that a proof system similar to that of 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 elementary set theory and inductive definitions. 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 Russell's Paradox, countable versus uncountable sets, the compactness theorem and the expressive limitations of first-order logic.

## LEARNING OUTCOMES OR AIMS

By the end of the module the student should be able to: 1) demonstrate knowledge of the Soundness and Completeness Theorems for propositional and first-order logic and related technical results and definitions; 2) understand the significance these concepts and results have for logic and mathematics; 3) use and define concepts with precision with precision, both within formal and discursive contexts.

## CONTACT TIME

For this module students must attend 3 hours of lectures and 1 hour of seminars per week

##### Lectures for 2015-16

**Monday 11am to 1pm in P5.21****Wednesday 11am to 12pm in MS.04**

There will be no lectures in reading week (week 6)

##### Seminars for 2015-16

There is only one large seminar group for this module which can be viewed on Tabula.

The seminar for this course starts in week 2. There will be no seminar in reading week (week 6).

## ASSESSMENT METHODS

This module is assessed in the following way:

- One 2-hour exam (worth 100% of the module)

## BACKGROUND READING AND TEXTBOOKS

Our primary text will be* *

*- Logic and Structure*, 4th edition by Dirk van Dalen, Springer Verlag, 2004

in which we will cover most of chapters 1-3. The same material is also covered at a more elementary level in chapters 15-19 of

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

Students lacking a background in elementary discrete maths (e.g. basic set theory and mathematical induction) are encouraged to obtain

*- Prove It: A Structured Approach*, Daniel J. Velleman, Cambridge University Press, 2006.

Maths students considering taking further logic courses might consider getting a copy of

*- The Mathematics of Logic*, Richard Kaye, Cambridge University Press, 2007.

## COURSE MATERIALS

## PREVIOUS YEARS

Please be aware that these materials may not be relevant to the current version of this module; they are intended primarily for students who took the module in other years.