MAT 309: Introduction to Mathematical Logic – Winter 2018

Instructor: Benjamin Rossman
Teaching assistants: Jamal Kawach and Ming Xiao

Lectures: Tuesday 2-4 and Thursday 3-4 (room MP 203)
Tutorials: Wednesday 4-5 (room BA 1240), Wednesday 5-6 (room BA 1240), Friday 3-4 (room HA 316), Friday 4-5 (room HA 316)
Office hours: Thursday 4-6 (BA 6214) or by appointment

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

Course Information Sheet


Announcements


Assignments (equally weighted)

Schedule

 Thu Jan 4 Course overview, review of propositional logic
 Tue Jan 9 Syntax and semantics of first-order logic (Preface and Sections 1.1-1.4 of textbook)
Handout
 Thu Jan 11 Syntax and semantics of first-order logic, continued (Sections 1.5-1.7)
 Tue Jan 16 Substitutions, logical implication (Sections 1.8-1.10)
 Thu Jan 18 Deductions (Sections 2.1-2.4)
 Tue Jan 23 Deductions, continued
 Thu Jan 25 Soundness Theorem (Sections 2.5-2.6)
 Tue Jan 30 Deduction Theorem and Nonlogical Axioms (Sections 2.7-2.9)
 Thu Feb 1 Fun stuff lecture: Ehrenfeucht-Fraisse Games
Slides (recommended reading: this website gives a nice overview)
 Tue Feb 6 Completeness Theorem (Sections 3.1-3.2)
 Thu Feb 8 Completeness Theorem, continued
 Tue Feb 13 Midterm #1
 Thu Feb 15 Wrapping up the Completeness Theorem (Proposition 3.2.6)
Slides
 Tue Feb 20 Reading week - no class
 Thu Feb 22 Reading week - no class
 Tue Feb 27 Compactness Theorem and applications (Sections 3.3-3.4)
 Thu Mar 1 Σ-, Π- and Δ-formulas of LNT (Sections 4.1-4.4)
 Tue Mar 6 Coding sequences of numbers and the axioms of N (Sections 4.5-5.2)
 Thu Mar 8 Review: Applications of compactness
 Tue Mar 13 Midterm #2
 Thu Mar 15 Representable and definable sets and functions; Rosser's Lemma (Sections 5.3-5.4)
 Tue Mar 20 Godel numbering (Sections 5.5-5.9)
Slides
 Thu Mar 22 Definitions by recursion are representable and coding deductions (Sections 5.10-5.13)
Slides
 Tue Mar 27 The 1st Incompleteness Theorem (Sections 6.3)
 Thu Mar 29 The Self-Reference Lemma and review of 1st Incompleteness Theorem and Tarski's Theorem (Sections 6.2-6.4)
Slides
 Tue Apr 3 Overview of 2nf Incompleteness Theorem (Sections 6.6-6.7), review of EF Games and the 0-1 Law
Slides: part 1 and part 2