Incompleteness and Computability

This book is an introduction to metamathematics and Gödel’s theorems. It covers recursive function theory, arithmetization of syntax, the first and second incompleteness theorem, models of arithmetic, second-order logic, and the lambda calculus. It is based on the Open Logic Project, and available for free download at ic.openlogicproject.org.

Table of Contents

1 Introduction to Incompleteness

2 Recursive Functions

3 Arithmetization of Syntax

4 Representability in Q

5 Incompleteness and Provability

6 Models of Arithmetic

7 Second-Order Logic

8 The Lambda Calculus

A Derivations in Arithmetic Theories

B First-order Logic

C Natural Deduction

D Biographies

Richard Zach is Professor of Philosophy at the University of Calgary, Canada. He works in logic, the history of analytic philosophy, and the philosophy of mathematics. In logic, his main interests are non-classical logics and proof theory. He has also written on the development of formal logic and historical figures associated with this development such as Hilbert, Gödel, and Carnap. He has held visiting appointments at the University of California, Irvine, McGill University, and the University of Technology, Vienna.