# MATH 4L03/6L03 — Introduction to Mathematical Logic

## 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 6Solutions 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 exercisesExercises 2.29, 2.30, 2.35 Sep 10–14 Logical consequence Formal proof Formal proof Sections 2.6 and 3.2 and embedded exercisesExercises 2.69, 2.75, 2.82, 3.7 Sep 17-21 Soundness and consistency Completeness Compactness Section 3.3 and embedded exercisesExercises 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 exercises4.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 exercises4.38, 4.40, 4.43, 4.44 Oct 15-19 Theories Quantifier elimination Algebraically closed and real closed fields Section 4.4 and embedded exercisesalgebraically closed and real closed fields Oct 22-26 Substructures Substructures Isomorphisms Sections 4.5 and embedded exercisesExercises 4.103, and 4.109 Oct 29-Nov 2 Formal predicate logic Some derivations Soundness and consistency Sections 5.2-5.4 and embedded exercisesExercises 5.10, 5.13, 5.15, 5.24 and 5.25 Nov 5-9 Midterm 2Covers predicate calculus, up to Oct. 26From 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 exercisesExercises 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 numberingGödel’s incompleteness theorem (slides) Gödel’s incompleteness theorem (notes with proofs)

### General information

Course information