MAT 309: Introduction to Mathematical Logic – Fall 2019

Instructor: Benjamin Rossman
Teaching assistants: Ming Xiao and Daniel Zackon

Lectures: Tuesday 11-12 and Thursday 11-1 (room MP 202 -- NOTE: Changed from MP 203.)
Tutorials (starting September 13): Friday 11-12 (room BA 1200), Friday 12-1 (room UC 244), Friday 3-4 (room HA 403), Friday 4-5 (room HA 401)
Instructor office hours: Tuesday 12-1 after lecture (BA 6214)

Textbook: "A Friendly Introduction to Mathematical Logic" (2nd Edition) by Christopher C. Leary and Lars Kristiansen

Course Information Sheet (updated Oct 24)

Announcements:

• The final exam will be held Tuesday Dec 10, 9-12am.
• The final tutorial is Friday Nov 29. The final lecture is Tuesday Dec 3. I will be holding extra office hours on Thursday Dec 5 (11-12:30) in the usual classroom MP 202.
• Problem Set 4, covering material in Chapter 4-5, has been posted to CrowdMark. It is due by 11:59pm Thursday, November 28.
• Problem Set 3 is being graded on 25-point scale with Questions 1-5 worth 6,4,6,3,6 points respectively.
• Tuesday October 29: Supplementary lecture on Ehrenfeucht-Fraisse games. See schedule below for link to slides and recommended reading.
• The Nov 14 term test has been cancelled. Weight for this test has been transferred to the remaining problem sets and final exam: Problem Set 3 will count for 8%, Problem Set 4 for 12%, and the Final Exam will count for 50% (up from 45%). (The Oct 10 test will still count for 20%.) The course information sheet has been updated to reflect these changes.
• Problem Set 3 has been posted to Crowdmark. The due date is Nov 7.
• Midterm grades have been posted on Quercus and exams will be returned in tutorial on Friday (or afterwards during Tuesday office hours).
Exam statistics: Average 72, Median 77. Breakdown of marks: 90-100 (14), 80-89 (27), 70-79 (13), 60-69 (12), 50-59 (6), 40-49 (11), <40 (6).
Note on grading: I failed to notice that the exam included two question #3's, each originally worth 20 points. To maintain a 100-point scale for the exam, these questions were graded as follows:
• Parts (a) and (b) of the first question #3, concerning structures Q and R, were worth 6 points each.
• Part (a) of the second question #3, on deductions, was worth 8 points. Part (b), which in retrospect was trickier than expected, was worth 3 extra credit points.
With this change, it was possible to score up to 103 on the 100-point scale, with any points over 100 contributing to the final grade for the course.
• Problem Set 2 due at the start of lecture on Thursday October 3
• The lecture room has been changed from MP 203 to MP 202 (next-door)
• Problem Set 1 due at the start of lecture on Thursday September 19
• Tutorials begin on Friday September 13. The 10-11am tutorial has been rescheduled to 12-1pm in UC 244.
• Please enroll in the course forum: https://piazza.com/utoronto.ca/fall2019/mat309h1
• The textbook is available at the UofT bookstore for \$45. A pdf version is freely available online.
• A volunteer note-taker is requested for this course (information here). Contact me if interested.
Outline of topics:
• Weeks 1-2: The Syntax and Semantics of First-Order Logic (Chapter 1)
• Weeks 3-4: Deductions and the Soundness Theorem (Chapter 2)
• Week 5: Deductions from Robinson arithmetic axioms, groundwork for the Completeness Theorem
• Week 6: Review of Chapters 1-2 and first term test
• Weeks 7-8: Completeness and compactness theorems (Chapter 3)
• Weeks 9-12: Gödel's Incompleteness Theorems (Chapters 4-6)
Daily Schedule:

 Th Sep 5 Course overview, syntax of first-order logic (reading: Preface and Sections 1.1-1.4) T Sep 10 Free and bound variables, structures (Sections 1.5-1.6) Th Sep 12 Truth in structures, substitution, logical implication (Sections 1.8-1.10) T Sep 17 Deductions (Sections 2.1-2.4) Th Sep 19 Deductions, continued T Sep 24 Soundness Theorem (Sections 2.5-2.6) Th Sep 26 Deduction Theorem and Nonlogical Axioms (Sections 2.7-2.9) T Oct 1 Robinson Arithmetic (Section 2.8) Th Oct 3 Groundwork for the Completeness Theorem (Sections 3.1-3.2) T Oct 8 Review of Chapters 1-2 Th Oct 10 Term Test T Oct 15 Proof of the Model Existence Theorem Th Oct 17 Completed proof of Model Existence Theorem, started discussing Compactness Theorem T Oct 22 Compactness Theorem and applications (Sections 3.3-3.4) Th Oct 24 Additional applications of compactness T Oct 29 Supplementary lecture on Ehrenfeucht-Fraisse games (slides and recommended reading) Th Oct 31 Σ-, Π- and Δ-formulas of LNT (Chapter 4.1-4.2) Review of Completeness/Model Existence/Compactness Theorems (slides) F Nov 1 Tutorial: More on Ehrenfeucht-Fraisse games Nov 4-8 Reading week - no lecture or tutorial T Nov 12 Coding sequences of natural numbers (Section 4.3-4.5) Th Nov 14 Rosser's Lemma; Representable sets; Church's thesis (Sections 5.1-5.4) (slides) F Nov 15 Tutorial: Solutions to Problem Set 3 T Nov 19 Godel numbers of formulas and Δ-definability (Sections 5.5-5.9) (slides) Th Nov 21 Definitions by recursion are representable; coding deductions (Sections 5.10-5.13) (slides) F Nov 22 Tutorial: Construction sequences and review of Chapter 5 T Nov 26 The Self-Reference Lemma (Sections 6.1-6.2) (slides) Th Nov 28 1st Incompleteness Theorem and Tarski's Theorem (Sections 6.3-6.5) (slides) F Nov 29 Tutorial: Solutions to Problem Set 4 T Dec 3 Peano Arithmetic and 2nd Incompleteness Theorem (Sections 6.6-6.7) (slides) Th Dec 5 Extra office hours (11-12:30) in the usual classroom MP 202