# Course Description

#### Summary

In a first course on logic the emphasis is on proving theorems within a logical system, whereas in this course we will prove theorems about logical systems. Because of this, this course is quite different in character than an introductory logic course: it is much more mathematical in nature!

We will begin with a brief introduction to types of proofs, basic set theory, and a discussion of the Completeness Theorem of propositional logic. After this we shall concentrate our studies on classical first-order predicate logic. In particular our focus will revolve around two major groups of results: (1) the Completeness Theorem for first-order logic, and (2) Gödel's First Incompleteness Theorem.

In part (1) we shall study Henkin's proof, the Compactness Theorem, and the Löwenheim-Skolem Theorem regarding the non-categoricity of the first-order axioms for arithmetic and the existence of non-standard models, while part (2) includes elements of recursive function theory, Gödel numbering and representability, Church's Theorem on the undecidability of first-order logic, Tarski's Theorem on the undefinability of truth, and Gödel's Second Incompleteness Theorem.

Thus, by studying some of the most important theorems of 20th century logic we will learn about the power and the limitations of first-order logic. These technical results have far-reaching philosophical implications (e.g., computational theory of mind, nature of mathematical and scientific theories, Hilbert's programme).

#### Prerequisites

Introduction to Deductive Logic (PHIL 210), or equivalent. Not open to students who have done MATH 498.

#### Textbook

The lectures will follow closely the development in the second half of the book by Moshé Machover: Set Theory, Logic and Their Limitations (Cambridge University Press). The book is available at The Word Bookstore, 469 Milton Street (5 mins. from the University Street Gates). This text is essential.

Students will be required to attend and participate in class, do the assigned readings, complete weekly homeworks, and take a final exam.

Usually a set of problems will be assigned once a week, and is due the following week. The assignments will be posted on WebCT.

Assignments are due at the beginning of class on the date mentioned in the assignment, and have to be turned in on paper. You may type them up or turn them in in legible handwriting. If you use a word-processor, make sure to use the spell-checker. Grading will be based on correctness and clarity.

Late day policy: Every student can take up to two "late days" during the semester. Otherwise, late homework will not be accepted (except in cases of documented emergencies).

The final grade depends on homeworks (70%), final exam (25%), and participation in class (5%). Failure to hand in the homeworks in time will result in the loss of marks.

"According to Senate regulations, instructors are not permitted to make special arrangements for final exams. Please consult the Calendar, section 4.7.2.1, General University Information and Regulations at www.mcgill.ca."