# Part III - Logic

## Lectured by T. E. Forster, Lent 2017

These notes are not endorsed by the lecturers, and I have modified them (often significantly) after lectures. They are nowhere near accurate representations of what was actually lectured, and in particular, all errors are almost surely mine.

This is an HTML version of the notes, generated using some horribly-written scripts and pdf2htmlEX. These are not guaranteed to display well, but do let me know if something is broken. Note however that I cannot help you if your browser does not support standard HTML features (eg. this part is known not to work well with w3m). You can either view all sections in a single page (Full version), or access individual sections below. If you want to download a pdf, head to the Notes page.

# Contents

- V Full version
- 1 Proof theory and constructive logic
- 1.1 Natural deduction
- 1.2 Curry–Howard correspondence
- 1.3 Possible world semantics
- 1.4 Negative interpretation
- 1.5 Constructive mathematics
- 2 Model theory
- 3 Computability theory
- 3.1 Computability
- 3.2 Decidable and semi-decidable sets
- 3.3 Computability elsewhere
- 3.4 Logic
- 3.5 Computability by λ-calculus
- 3.6 Reducibility
- 4 Well-quasi-orderings