MAT 309: Introduction to Mathematical Logic – Fall 2019

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:

• Please complete your course evaluations by Dec 6. I appreciate your feedback!
• 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.

• 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)

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