# 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 2014-15

**Mondays 11am-1pm P5.21****Wednesdays 10am-11am F1.10 (seminar room)****Wednesdays 11am-12pm MS.04**

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

##### Seminars for 2014-15

There is only one large seminar group for this module.

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.