Mathematics 114AB

Winter 2005

Instructor: Herbert B. Enderton

hbe@math.ucla.edu

Office MS 7905. Office hours Mon & Wed 2:00-3:30.

Teaching Assistant: Joe Busch

jbusch@math.ucla.edu

Office MS 2925. Office hours Tues 12:30-2.

Click here for our " virtual office hours" for this class.

"PROOFS, TRUTH, AND COMPUTABILITY"

If a sentence is true, is there necessarily a proof of it? What is the connection between computability and logic? Math 114A is a logic course, in which we plan to explore these concepts. (Math 114B, not offered this year, continues the exploration, with an emphasis on computability.) Some of the major goals of the two-quarter Math 114AB sequence are these:

The completeness theorem for first-order logic, which shows that the concept of provability (from axioms) can be completely nailed down. (This theorem, and its many consequences, will be this quarter's main objective.)
The Gödel incompleteness theorem, which shows that there is an inherent gap between what is true (about the natural numbers, for example) and what you can prove in a formal system. (This theorem is the main objective of 114B; this quarter we will only sketch some of the main ideas.)
The unsolvability of the halting problem, which shows that you can't do everything. (This quarter we will give an informal version; the formal details are in 114B.)

These issues are relevant to theoretical computer science and to philosophy, as well as to mathematics.
See also the Mathematics Department's description of this course.

Prerequisites: There is no specific body of information that is required. But our main order of business is proving theorems (not calculating numbers or writing programs). For this reason, you should have some positive experience with proofs before taking this course.

Textbook: A Mathematical Introduction to Logic (second edition) by H. B. Enderton. I think very highly of this book, but that doesn't mean that I will follow it slavishly. In 114A, we will cover roughly Chapters 1 and 2. Chapter 3 is covered in 114B. The book is available in the ASUCLA bookstore now. I recommend also reading the commentary on the web. Click here for errata.

Homework: Yes! Although the homework problem sets account for only a small part of the course grade, you should definitely do them, in order to master the material. Besides, every little bit helps, especially if the tests do not all go well. Late homework will normally not be graded.

Tests: There will be a first midterm exam on Wednesday, February 2, and a second midterm on Friday, March 4. The final exam is on Friday, March 18, 11:30-2:30 (exam code 2).

Grading: The final exam constitutes a large part of the grade. The two midterms together constitute another large part. The homework accounts for a small part. ("Large" means 40-50%. "Small" means no more than 10%.) To get an Incomplete grade, you must be doing passing work when struck by unforeseen external disaster.

Website: http://www.math.ucla.edu/~hbe/114a.1.05w