Course description:

This course covers logical metatheory and elementary meta-mathematics. Topics include completeness and consistency proofs for first-order logic, formal semantics, elementary number theory (especially Robinson and Peano arithmetics), and Gödel’s incompleteness theorems and related results.

Prerequisites:

Phil 310 (Intermediate Logic) or equivalent and solid grasp of high school algebra, or consent of instructor. You must also be prepared for a lot of challenging work. Fair warning: most students find this course much more difficult than their earlier logic courses.

Contact information:

Prof. Klement’s email is klement@umass.edu, and his office is South College E319. Office hours are Wednesdays 11am–noon, Fridays 2pm–3pm, or click here to schedule an appointment. or schedule an appointment online at https://logic.umasscreate.net/appts/?view=klement

Moodle page:

We have a site on the UMass Moodle LMS (https://moodle.umass.edu/), where you can view your grades and download course materials.

Lecture notes:

I have prepared a lengthy document containing all my lecture notes for the course. It is available both through Moodle and at the link just given. on our public-facing webpage for the course: https://people.umass.edu/klement/513/. You are expected to have them available (print them beforehand or access them on a device) during class. I will not distribute these to you, and lectures will be impossible to follow without them. Page numbers to be covered are on the schedule, but we may get ahead of schedule, so print ahead of time.

Textbook:

We will be using the Open Logic Text, a freely available, “copyleft-ed”, open educational resource, which anyone can modify or contribute to. It is available to download from Moodle or from the Open Logic Project website. the Open Logic Project website: http://builds.openlogicproject.org/

The section numbers in the schedule below come from the “Clean Version”, Revision 1802995, dated 2019-08-24, but new versions are posted often. I hope eventually to create my own “remix” of this book, but it is unlikely I will do so this semester.

Requirements and grading:

Your final grade is determined by (1) four homework bundles (10% each / 40% total); (2) two exams (25% each / 50% total); and (3) class attendance and participation (10%).

The two exams will be take-home exams, and may require quite a bit of thought to complete. Questions will be distributed weeks in advance of their due date, and you may need all that time. Do not wait till the last minute. The first is due October 22nd and the second is due at the end of finals week.

There are one or two homework exercises assigned nearly every class: a total of 32. The actual assignments are found scattered in the lecture notes, alongside the material they involve. Assigned exercises will be collected in four “bundles”:
  • Bundle 1 (HW1–8) is due Th September 26th
  • Bundle 2 (HW9–15) is due Tu October 22nd with Exam 1
  • Bundle 3 (HW16–26) is due Tu November 19th
  • Bundle 4 (HW27–32) is due Th December 19th with Exam 2

Policies:

Homework and exams may be handwritten. You may collaborate with your peers on homework assignments provided you do not copy from them. However, you may not collaborate with your peers on exams.

Schedule

Warning! Everything about this schedule can and will change.

Date Material (lecture notes pages) Book sections Homework
Tu 3 Sept Course introduction
Th 5 Sept Metatheory, set theory (pp. 1–3) §§1.1–4.6 HW1
Tu 10 Sept Mathematical induction, propositional logic (pp. 4–6) §§5.1–5.5; §§54.1–54.5 HW2, HW3
Th 12 Sept Syntax/semantics of first-order logic (pp. 7–11) §§12.1–12.12 HW4, HW5
Tu 17 Sept More on semantics of first-order logic (pp. 12–13) §§12.13–12.14; §§14.1–14.5 HW6, HW7
Th 19 Sept Tableaux for first-order logic (pp. 13–15) §§17.1–17.6 HW8
Tu 24 Sept Axiomatic deductions (pp. 16–20) §§18.1–18.6 HW9, HW10
Th 26 Sept Deduction theorem and corollaries (pp. 20–22)
HW 1–8 due
§§18.7–18.11 HW11
Tu 1 Oct Soundness and consistency (pp. 23–25) §18.12; §§30.1–30.2 HW12
Th 3 Oct Lemmas for completeness (pp. 25–30) §§19.1–19.6 HW13
Tu 8 Oct Completeness, compactness (pp. 30–31) §§19.8–19.11 HW14
Th 10 Oct Identity logic (pp. 31–34) §18.13; §19.7 HW15
Tu 15 Oct No class. Monday class schedule.
Th 17 Oct Unit 1 review and questions.
Tu 22 Oct Theories; Peano and Robinson arithmetics (pp. 35–38)
Exam 1 and HW 9–15 due.
§§13.1–13.3; 29.1–29.4 HW16, HW17
Th 24 Oct Naïve foundations (pp. 39–40) §1.6 HW18
Tu 29 Oct Numerals; Q vs. PA (pp. 40–45) §31.1; §31.5 HW19
Th 31 Oct Recursive functions (pp. 45–49) §§25.1–25.7 HW20, HW21
Tu 5 Nov More on recursive functions (pp. 49–52) §§25.8–25.13 HW22, HW23
Th 7 Nov Representing functions in Q (pp. 52–56) §31.6–31.9 HW24, HW25
Tu 12 Nov Representing recursion (pp. 56–59) §§31.3–31.4 HW26
Th 14 Nov Arithmetization of syntax (pp. 59–64) §§30.3–30.5; §30.8; §31.2 HW27, HW28
Tu 19 Nov Fixed point theorem; Gödel’s first theorem (pp. 64–69)
HW 16–26 due.
§§33.1–33.3 HW29
Th 21 Nov Gödel-Rosser and Gödel’s second theorem (pp. 69–72) §§33.4–33.7 HW30
24–30 Nov No class. Thanksgiving break.
Tu 3 Dec Löb’s theorem; Tarski’s theorem (pp. 72–74) §§33.8–33.9 HW31
Th 5 Dec Recursive undecidability (pp. 74–77) §31.10; §32.4; §32.9 HW32
Tu 10 Dec Unit 2 review and questions.
Th 19 Dec End of finals week.
Exam 2 and HW 27–32 due.

Looking for a version of this syllabus to print? Your browser should convert the page to something more suitable for printing (in terms of colors and formatting) automatically when printed.