MATH 445 -- ELEMENTARY MATHEMATICAL LOGIC

FALL 2009

Time and Room: MWF at 1: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). Recommended: J.N. Crossley et al, What is Mathematical Logic? Dover, 1990.

Notes:

Introduction.

Chapter 1. Sentential Logic.

Chapter 2. First Order Logic.

Chapter 3. The Completeness Theorem,

Appendix: Axioms for Arithmetic on the Natural Numbers.

Chapter 4. Computability and Decidability.

Chapter 5. The Incompleteness Theorem.

Homework:

Homework 1

Homework 2

Homework 3

Homework 4

Homework 5

Homework 6

Homework 7

Homework 8

Homework 9

Exams:

Exam 1

Exam 2

Review:

Exam 1 Review

Exam 2 Review

Final Exam Review: Topics List

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 2 October.
• Exam 2: Friday 6 November.
• Final Exam: Tuesday 15 December, 1:30-3:30.

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