Math 160A (Fall 2024)
Summary
Math 160A is first course in mathematical logic. The main object of study are formal proof systems and their models. We will also cover some set theory, computability theory and maybe some other topics. One of the chief goals of the course is the formal statement, and an outline of the proof, of Godel's incompleteness theorem.
Math 160B will be taught in Spring 2025 (by me) and will follow on from this course. It will cover some of the same topics in further detail, as well as ordinals and recursion theory and formal set theory, which we probably won't get to cover this quarter.
Two important comments about the course:—
- Do not be confused by the word "Elementary" in the course title. Mathematical Logic uses, and interacts with, other fields of mathematics (algebra, analysis etc.). While we will not assume detailed knowledge of any one of these other fields, fluency with abstract mathematical language and proofs is an essential prerequisite for this course.
- This is a course in Mathematics, not a course in Philosophy.
Contacts
The instructor is Freddie Manners (email fmanners); my office is AP&M 7343. The TA is Su Zhou (email suzhou).
Class and section
Lectures are held on Mondays, Wednesdays and Fridays, 1100–1150. They will be held in-person in HSS-2150. The course will not be generally available as a podcast, so lecture attendance is required (but not enforced).
Section will take place in-person at the advertized times and places.
The Google calendar below has times and locations for all class events.
Note there is NO class on Monday November 11 (Veterans Day), or on Wednesday November 27 and Friday November 29 (Thanksgiving).
Exams
There will be two evening midterm exams, on Wednesday October 23 (Week 4) and Wednesday November 13 (Week 7), 1900–2030 (i.e., 7pm to 8:30pm), in APM-2301.
The final exam is on Tuesday December 10, at 1130–1430. It is also in-person (location TBD).
You should ensure at the start of the quarter that you can attend these exams. In general, alternative modalities, dates or times (in particular, remote exams) will not be offered.
(Note: it is standard practice in the Mathematics Department to use multiple versions of exams where necessary.)
Homework
Homework is due every Saturday at 2359, starting in Week 1 (October 5).
Midterm weeks will have reduced homework loads, but still some homework.
Please note: while discussing homework problems in groups is permitted (and encouraged), your final written-up solutions must be written by you, by yourself, in your own words. If your homework appears to have been copied directly from another student (or another source, including the internet or AI systems) that will almost certainly constitute an academic integrity violation. You also may not post homework questions or solicit answers on the internet.
It is guaranteed that every exam will contain at least one problem which is a close variant of a homework problem.
Grading
Your combined grade for the course is calculated as follows. First, your lowest homework score is dropped. Then, take 10% homework + 25% midterm 1 + 25% midterm 2 + 40% final.
The letter grade cut-offs will be at least as generous as the following table (but may be more generous). Separately, exam scores may be curved to adjust for difficulty.
| A+ | A | A- | B+ | B | B- | C+ | C | C- | F |
|---|---|---|---|---|---|---|---|---|---|
| 97 | 93 | 90 | 87 | 83 | 80 | 77 | 73 | 70 | < 70 |
Resources
In addition to this website, the course has a Canvas page, a Gradescope page and a Piazza site. The sign-up codes for Gradescope and Piazza are listed on the Canvas home page.
Provisional schedule
A very rough provisional course schedule is given below. It can and probably will change.
| Week | Mon | Wed | Fri | Topic |
|---|---|---|---|---|
| 0 | L1 | Introduction. Recap on Set Theory. | ||
| 1 | L2 | L3 | L4 | Propositional logic. Syntax and semantics. Proofs. |
| 2 | L5 | L6 | L7 | The deduction theorem. The completeness theorem and its applications. |
| 3 | L8 | L9 | L10 | Computability. Turing machines (briefly). Recursively enumerable sets. |
| 4 | L11 | Review | L12 | Universal Turing machines. The Halting Problem. Introduction to first-order logic. |
| 5 | L13 | L14 | L15 | First-order logic. Languages, syntax and semantics. |
| 6 | L16 | L17 | L18 | First-order axioms and proofs. The completeness theorem. |
| 7 | X | Review | L19 | Soundness, adequacy, the model existence lemma. |
| 8 | L20 | L21 | L22 | Sketch proof of the model existence lemma. Consequences of completeness. |
| 9 | L23 | X | X | The incompleteness theorem. |
| 10 | L24 | L25 | Review | Sketch proof of incompleteness. Further topics. |
Office hours
Regular office hours and locations are listed in the table below. However, please check the calendar below for any one-off changes or cancellations.
| Instructor / TA | Location | Regular hours |
|---|---|---|
| Freddie Manners | AP&M 7343 | 1:30–2:30pm Wednesdays, 2:30–3:30pm Fridays |
| Su Zhou | AP&M 5748 | 4:00pm–5:00pm Tuesdays, 5:00pm–6:00pm Fridays |
Course calendar
A link to add this calendar is available on the course's Canvas page.