## Fall Semester 2008

### Primary Text

Introduction to Mathematical Logic, Fourth Edition, by Elliott Mendelson.

### Secondary Text

Introduction to Mathematical Logic, by Richard Hodel. This will be made available as a course-pack.

### Instructor

William K. Allard, Professor of Mathematics
• Office: 029A Physics Building
• Phone: (919) 660-2861
• Fax: (919) 660-2821
• E-mail: wka@math.duke.edu
• Office Hours: Tuesday and Thursday 10am-Noon and by appointment.
• ### Time and Place for Mathematics 187, Spring Semester 2005

• Tuesday and Thursday, 1:15-2:30pm, Physics 235
• ### Syllabus For Mathematics 187

Propositional logic and first-order logic, with an emphasis on the relationship between the semantic and syntactic approaches; these ideas are summarized in Godel's Completeness Theorems. Hilbert's Program and the work of Godel [Incompleteness Theorems], Church, Turing, and Tarski on undecidability and indefinability.

We will cover in considerable detail 1.1-1.6, 2.1-2.2 and 3.1-3.4 from Hodel's book. We will cover in considerable detail nearly all of Chapters 2 and 3 from Mendelson's book. All of this material will be supplemented with my own notes

We will introduce some concepts from computer science to clarify some of the material in the beginning as well as to allow some calculations to be done by the computer.

There will be weekly assignments which will be graded; this will count for 50% of your grade. There will be two in class tests on the terminology; these will each count 10% of your grade. There will be a final assignment which will count the remaining 20% of your grade.

Here are the definitions from which the first test will be taken: PDF

This supplants what was in the course synopsis (although it really isn't that different, is it?) I may change this slightly later on.

It may be possible to do some sort of project on a topic related to logic which interests you. We'll see.

Students with excused absences will be given a make-up exam. No quizzes or homework will be made up for credit, but it's important to make it up for your own benefit. Late homework will not be accepted.

Forthcoming. Maybe.

### Math 187 Notes

• Sets, relations and functions PDF Revised September 1, 2008.
• Languages and formal theories. PDF Revised September 1, 2008.
• Trees and context free grammars. PDF Revised September 3, 2008.
• A class of good context free grammars. PDF Revised October 2, 2008. The proof at the end needs more work.
• Propositional logic, Part One. PDF Revised September 3, 2008.
• Disjunctive normal form. PDF Revised September 11, 2008.
• Axioms for propositional logic. PDF Revised October 15, 2008.
• Free and bound variables. PDF Revised September 29, 2008.
• Interpretations and Tarski's definition of truth. PDF Revised October 2, 2008.
• The tautology theorem and other useful stuff. PDF Revised October 15, 2008.
• The model existence theorem. PDF Revised October 29, 2008.
• A couple of useful examples. PDF Revised October 29, 2008.
• Equivalence is preserved under substitution. PDF Revised November 4, 2008.
• Expressibility and representablility. PDF Revised November 17, 2008.
• Gödel's Theorem. PDF Revised November 17, 2008.
• Recursive functions. PDF Revised November 26, 2008.
• Being the code of term is recursive. PDF Revised November 26, 2008.
• The class of representable functions is closed under recursion. PDF Revised November 25, 2008.
• ### Homework for Math 187, Spring Semester 2005

• Homework One. PDF Due September 4, 2008.
• Homework Two. Handed out in class. Due September 11, 2008.
• Homework Three. PDF Due September 18, 2008. More or less.
• Final problem set. PDF Due December 11 at 5pm.
• ### Some References

Coming later!

### The Duke Community Standard

"Duke University is a community of scholars and learners, committed to the principles of honesty, trustworthiness, fairness, and respect for others. Students share with faculty and staff the responsibility for promoting a climate of integrity. As citizens of this community, students are expected to adhere to these fundamental values at all times, in both their academic and nonacademic endeavors."

Specifically,

• All quizzes and exams will be done without books or notes and without collaborating with any other student.
• Homework assignments can discussed with other students in the course and I encourage you to do so. However, solutions must be written up individually without consulting anyone else's written solution and any assistance received must be acknowledged.
• Calculators may be used on homework but not on quizzes or exams unless specified in class in advance.