MATH 445 -- ELEMENTARY MATHEMATICAL LOGIC

FALL 2010



Time and Room: MWF at 11:00 in MTH 0304

Instructor: Professor David W. Kueker
Office: MTH 2105
Phone: (301)405-5159
dwk@math.umd.edu
Office Hours: MW 2:00

Text: D.W. Kueker, Elementary Mathematical Logic (online notes).

Notes:
Revised notes will be posted as they become available. For the unrevised notes, see the Math 445 webpage from Fall 2009.
Introduction. **Revised**
Chapter 1. Sentential Logic. **Revised**
Chapter 2. First Order Logic. **Revised**
Chapter 3. The Completeness Theorem, **Revised**
Appendix: Axioms for Arithmetic on the Natural Numbers. **Revised**
Chapter 4. Computability and Decidability. **First Part Revised**
Chapter 5. The Incompleteness Theorem. **Revised**

Homework:
Homework 1 ** due Sept 10 **
Homework 2 ** due Sept 20 **
Homework 3 ** due Sept 27 **
Homework 4 ** due Oct 18 **
Homework 5 ** due Oct 25 **
Homework 6 ** due 1 Nov **
Homework 7 ** due 22 Nov **
Homework 8 ** due 3 Dec **
Homework 9 ** due 10 Dec **

Exam Review Sheets:
Exam 1
Exam 2
Final Exam

Sample Exams:
Exam 1
Exam 2
Final Exam

Description: This course is an introduction to mathematical logic. Mathematical logic studies reasoning as used in mathematics. In mathematics we try to show that various statements are true of some specific mathematical structure or of some collection of structures. We do this by constructing proofs, that is arguments following certain specified rules. The obvious question is: do proofs enable us to derive all statements true of the structure or structures in question? Gödel gave two contrasting answers to this question (for statements which can be written in first order logic). In his Completeness Theorem he showed that a statement is true in all models of a set of axioms iff it has a proof from those axioms. In his Incompleteness Theorem he showed that there is no axiomatic proof system strong enough to derive all true statements about arithemetic on the integers. Our goal in this course is to explain and prove these two theorems.

Outline:
  • Chapter 1. Sentential Logic.
  • Chapter 2. First order Logic.
  • Chapter 3. The Completeness Theorem.
  • Chapter 4. Computability and Decidability.
  • Chapter 5. The Incompleteness Theorem.

Course Work: There will be regular homework assignments, two one-hour exams, and a two-hour final exam. The homeworks are worth a total of 100 points, the one-hour exams are worth 100 points apiece, and the final is worth 200 points, for a total of 500 points.

Exam Schedule:
  • Exam 1: Friday 1 October.
  • Exam 2: Friday 5 November.
  • Final Exam: Wednesday 15 December, 8:00-10:00.

Collaboration on homework: You may freely discuss the homework with others, but the work submitted must be your own, written in your own words.