## Fall 2018

The **Final Exam** is cumulative and covers all material up to and including Nov. 20 (Ax’s Theorem), with the same exception as for Midterm 2.

Here is the final exam I gave 4 years ago. Note that it included a question about first-order arithmetic, because there was more time between the last day of class and the exam than there is this year. I will not post the solutions; if you have questions, please come and talk to me.

Good luck on your other final exams, and Happy Holidays!

### Homework

Note: Only a few selected solutions are posted. Please feel free to ask me directly about marked homework.

Date Due | Assignment | Remarks |

September 18 | Exercises 2.28, 2.31, 2.45, 2.70 | due at beginning of class |

October 2 | Exercises 3.9(b), 3.14(a), 3.27 | due at beginning of class |

October 16 | Exercises 4.7, 4.24, 4.38, 4.54 | due at beginning of class |

October 30 | Exercises 4.69, 4.76, 4.93, 4.111 | due at beginning of class |

November 13 | Exercises 5.26, 5.33, 5.37 | due at beginning of class |

November 30changed due date! | Homework 6 Solutions | due at beginning of class |

Problems on definability | Problems on definability |

### Covered so far

Week | Tuesday | Thursday | Friday | Required reading and recommended exercises |

Sep 4–7 | Construction of propositional formulas | Interpretation of propositional formulas | Logical equivalence | Sections 2.1 to 2.5 and embedded exercises Exercises 2.29, 2.30, 2.35 |

Sep 10–14 | Logical consequence | Formal proof | Formal proof | Sections 2.6 and 3.2 and embedded exercises Exercises 2.69, 2.75, 2.82, 3.7 |

Sep 17-21 | Soundness and consistency | Completeness | Compactness | Section 3.3 and embedded exercises Exercises 3.20, 3.22, 3.23 |

Sep 24-28 | First order formulas | Structures and interpretation of terms | Interpretation of formulas | Sections 4.1 and 4.2 and embedded exercises 4.5, 4.8, 4.9, 4.20, 4.23 |

Oct 1-5 | Midterm 1 Covers propositional logic Sections 2.1 — 3.3 of the bookSolutions | Validity | Free substitution | Section 4.3 and embedded exercises 4.38, 4.40, 4.43, 4.44 |

Oct 15-19 | Theories | Quantifier elimination | Algebraically closed and real closed fields | Section 4.4 and embedded exercises algebraically closed and real closed fields |

Oct 22-26 | Substructures | Substructures | Isomorphisms | Sections 4.5 and embedded exercises Exercises 4.103, and 4.109 |

Oct 29-Nov 2 | Formal predicate logic | Some derivations | Soundness and consistency | Sections 5.2-5.4 and embedded exercises Exercises 5.10, 5.13, 5.15, 5.24 and 5.25 |

Nov 5-9 | Midterm 2Covers predicate calculus, up to Oct. 26 From Section 4.4, only the axiom systems discussed in class are included; axioms will be given on the test if needed. Solutions | Completeness, part I | Completeness, part II | Section 5.5 and embeded exercises Exercises 5.32 and 5.35 |

Nov 12-16 | Downward Löwenheim-Skolem | Compactness | Completeness of algebraically closed fields | Sections 6.1 and 6.4 |

Nov 19-23 | Ax’s Theorem | class cancelled | First-order arithmetic | |

Nov 26-30 | Expressibility | Recursive functions | Examples of recursive functions | Proof of Lemma 1 |

Dec 3-5 | Gödel numbering Gödel’s incompleteness theorem (slides) | Gödel’s incompleteness theorem (notes with proofs) |

### General information

Instructor: | Patrick Speissegger |

Office: | HH 409A |

Telephone: | extension 23430 |

E-mail: | speisseg@math.mcmaster.ca |

Office Hours: | Tuesday and Thursday 10:00–11:00, or by appointment |

Lectures: | Tuesday, Thursday and Friday 11:30–12:20 in HH 312 (the room has been changed as of Aug. 30). |

Text: | Propositional and predicate calculus, a model of argument, byDerek Goldrei, Springer-Verlag London 2005, ISBN-13 978-1-85233-921-0. This book is available for download through the McMaster Library website (access from campus or via login) |

Assessment: | Your grade will be based on six homework assignments, in-class participation, one or two in-class midterms and the final exam (check back for details). The distribution is as follows: homework 20%, in-class participation 20%, midterm(s) 20% and final 40%. The instructor reserves the right to change the weight of any portion of this marking scheme. |

Homework: | Assigned every other week; collected on the due date in class, at the beginning of class. |

In-class participation: | There are a lot of reading assignments in this class. Discussion of the read material is an integral part of class, especially the exercises embedded in the text. |

Midterms: | Tuesday, Oct. 2 and Tuesday, Nov. 6 in class (tentative) |

Final: | to be announced on Mosaic |

Missed academic work: | In the event of an absence for medical or other reasons, students should review and follow the Academic Regulation in the Undergraduate Calendar Requests for Relief for Missed Academic Term Work. |