BU CLA MA 531: Computability and Logic

Fall 1995


Overview (by A. Kanamori):

The course begins with a treatment of first-order logic as the basis for mathematical logic and an underlying language for mathematics. The syntax and semantics of quantifiers are analyzed, leading to Godel's Completeness Theorem. A sketch is then given of Godel's Incompleteness Theorem.

This leads to Turing's Halting Problem and the beginnings of the theory of computability. After describing the class of computable functions and Church's Thesis, the theory is developed through the Enumeration and Parametrization Theorems to Kleene's Recursion Theorem. Recursive and recursively enumerable sets are then discussed. Throughout, questions of undecidability ultimately related to Godel's Incompleteness Theorem provide a driving theme.

Required textbooks:

A Mathematical Introduction to Logic, by Herbert B. Enderton, Academic Press, 1972,

and if available, A Programming Approach to Computability, by Assaf J. Kfoury, Robert N. Moll and Michael A. Arbib, Springer Verlag, 1982.

Notes on Enderton's Book (by A.J. Kfoury):

Chapter 0. Not covered in class.
This short chapter (10 pages) presents basic notations and concepts from set theory that are used in the rest of the book. It is probably best to refer to this chapter as the need arises, rather than try to study it right at the beginning.

Chapter 1. Not covered in class.
If your knowledge of Sentential Logic (also called Propositional or Boolean Logic) is a bit rusty, you will have to review some of the material in this chapter on your own. All the topics in this chapter are fundamental, except Switching Circuits (Section 1.6) which are just a digression. If you need to read through Chapter 1, it is perhaps best to do it in parallel with the material of Chapter 2. For example, the material in the last section of Chapter 1 (Compactness and Effectiveness) is encountered again in Sections 2.4 and 2.5, but in the more general setting of first-order logic.

Chapter 2. Covered in class.
The material in Sections 2.0 to 2.6 is fundamental and will be covered in detail. Depending on time and class interest, the last two sections (2.7 and 2.8) may be covered in class.

Chapter 3. Partly covered in class.
We will cover as much of this chapter as we need (mostly from Sections 3.0 to 3.4) to reach Godel's Incompleteness Theorem (in Section 3.5). Depending on time, I may give a survey of the material in the last sections (Sections 3.6 to 3.8) with most of the details omitted.

Chapter 4. Probably not covered in class.

Additional Topic (by A.J. Kfoury):

The last 2 (minimum) to 4 (maximum) weeks of the semester will cover material on Intuitionistic Logic, which is of special interest to computer scientists and a prelude to a seminar I will teach in the Spring 96 semester. Several handouts will be distributed on this material, some of which drawn from the book Logic and Structure by D. van Dalen.

Assaf Kfoury
Created: 95.09.07
Modified: 95.12.06