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

**Instructor:** Peter Selinger. Office:

**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/

selinger@mathstat.dal.ca