Math 4680/5680, Topics in Logic and Computation
Winter 2012
Peter Selinger

"Introduction to Mathematical Logic"

Time and Location: MWF 10:30-11:30, Chase 227.

Please note that there will be no class on January 18, because I will be away at a conference. This class will be made up later in the term.

Instructor: Peter Selinger. Office: Chase 303. Email: selinger@mathstat.dal.ca (please mention "4680" or "5680" in the subject line).

Office Hours: TBA.

Course Description: Logic is the study of the formal principles of reasoning. In this course, we will study symbolic logic. We will introduce the formal languages of propositional and first-order logic, and we will learn how to formalize the notions of truth and proof. Logic is unlike other branches of mathematics, in that we do not just prove things, but we reason about the proofs themselves. For this reason, logic has sometimes been called meta-mathematics. On the other hand, the study of modern formal logic uses some of the same methods and techniques that are used in other branches of mathematics, and thus logic can also be regarded as just another mathematical discipline.

Topics: In the first part of the course, we will introduce the notion of a formal language. We will study the propositional connectives, tautologies, and tautological consequences. The heart of the course is the study of first order predicate logic and its models. We will study formal proofs, establish soundness and completeness theorems, and explore some of their applications. We will see how to formalize elementary number theory. By the end of the course we should be able to state and understand Gödel's First Incompleteness Theorem.

Prerequisites: MATH 3030 or MATH 3500, or CSCI 3110 and CSCI 3136, or permission of the instructor.

This course is suitable for advanced undergraduates as well as graduate students, from mathematics, computer science, or related fields. Suggested prerequisites for math students are algebra and analysis at honours undergraduate level. Students from computer science should be familiar with formal language theory and concepts of programming languages. All students should be comfortable with writing mathematical proofs. When in doubt about prerequisites, please consult the instructor.

Textbook: Herbert B. Enderton. A Mathematical Introduction to Logic. Academic Press.

Course Work: There will be an in-class midterm and a final exam. There will be weekly or biweekly homework assigned in class. Graduate students will be given additional homework and/or additional exam questions. Graduate students will also be expected to give an in-class presentation towards the end of the term. For undergraduate students, this additional work is optional and voluntary.

Grading: Grades will be based on the exams, homework, and presentations (if applicable). Active participation in class may be taken into account. You must pass the final exam to pass the course. Grades will be calculated as follows: homework 10-20%, midterm 20-40%, final exam 40-70%, presentations 10-20% (for graduate students) or 0-20% (for undergraduate students). Within these constraints, and provided they add up to 100%, you may pick your own percentages.

Numerical grades are converted to letter grades via the standard Faculty of Science scheme: 90-100 = A+, 85-89.9 = A, 80-84.9 = A-, 75-79.9 = B+, 70-74.9 = B, 65-69.9 = B-, 62-64.9 = C+, 58-61.9 = C, 55-57.9 = C-, 50-54.9 = D, 0-49.9 = F.

Course Homepage: Updated information, homework sets, lecture notes, handouts, etc., will be available from http://www.mathstat.dal.ca/~selinger/5680/

To Peter Selinger's Homepage: [home]

Peter Selinger / Department of Mathematics and Statistics / Dalhousie University
selinger@mathstat.dal.ca / PGP key
Updated Jan 3, 2012