Course pages 2012–13

# Introductory Logic

**Principal lecturer:** Dr Bjarki Holm**Taken by:** MPhil ACS, Part III**Code:** R07**Hours:** 8**Prerequisites:** Basic familiarity with discrete mathematics and set theory (for example, to the level of Discrete Mathematics I and II from Part 1A of the Cambridge Computer Science Tripos).

## Aims

This module aims to provide the basic mathematical logic which will be assumed in later courses.

## Syllabus

- Propositional calculus: truth-functional models, a deductive calculus and proofs of soundness and completeness.
- First-order predicate logic: Tarskian truth and models, a deductive calculus, completeness and a proof of soundness.
- Compactness and Loewenheim-Skolem theorems.
- First-order theories and their models. Some examples with indications (and in some cases proofs) of which theories are complete/incomplete: dense linear orders, natural numbers with successor, Peano arithmetic, real-closed fields.

## Objectives

On completion of this module, students should have a good understanding of propositional logic and first-order logic, their proof systems and their models.

## Coursework

Exercises will be provided.

## Practical work

None.

## Assessment

The course will be assessed by means of a written test to be set and marked by the course lecturer.

## Recommended reading

Enderton, H.B. (2001). *A mathematical introduction to logic.*
Academic Press (2nd ed.).