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)


Outline of topics:
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