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

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 3032.03, or MATH 3502.03, or MATH 3031.03 and MATH 3501.03, or CSCI 3110.03 and CSCI 3136.03, or permission of the instructor.

This course is suitable for advanced undergraduates as well as graduate students, from both mathematics and computer science. 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: Dirk van Dalen. Logic and Structure. 4th edition, Springer Universitext 2008. The 5th edition is also fine, and contains one additional chapter. The 4th edition may be cheaper.

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 Dalhousie Common Grade Scheme.

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