Fall 1995
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.
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.
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