Math 4000 Fall 24

MATH 4000/5000: Foundations of Mathematics (Fall 2024)

Syllabus

Final Exam:

Schedule

Numbers are for orientation and refer to sections with related material in the book by Enderton.
  1. 08/26: set theory, logic, computability, model theory
  2. 08/28: syntax: sentential logic, formulas (1.1)
  3. 08/30: semantics: truth assignments, tautological implication (1.2)
  4. 09/04: tautology and SAT, Boolean functions (1.5)
  5. 09/06: DNF
  6. 09/09: complete set of functions (1.5)
  7. 09/11: Compactness Theorem (1.7)
  8. 09/13: deductions (1.7)
  9. 09/16: algorithms, decidability (1.7)
  10. 09/18 enumerability (1.7)
  11. 09/20: first order language (2.1)
  12. 09/23: fo formulas, free variables, sentences (2.1)
  13. 09/25: L-structures (2.2)
  14. 09/27: models for formulas (2.2)
  15. 09/30: logical implications (2.2)
  16. 10/02: tautologies (2.4)
  17. 10/04: substitutions, Substitution Lemma (2.4)
  18. 10/07: logical axioms, deduction (2.4)
  19. 10/09: deduction and tautological implication (2.4)
  20. 10/11: Generalization Theorem, Rule T, Contraposition (2.4)
  21. 10/14: review
  22. 10/16: MIDTERM
  23. 10/18: generalization of constants, alphabetic variants (2.4)
  24. 10/21: discussion of midterm
  25. 10/23: Soundness Theorem, logical axioms are valid (2.5)
  26. 10/25: Completeness Theorem (2.5)
  27. 10/28: Henkin construction, expanding signature, maximal consistent set
  28. 10/30: term structure, replacing =
  29. 11/01: quotient structure
  30. 11/04: Compactness Theorem, Enumerability (2.5)
  31. 11/06: models and theories (2.6)
  32. 11/08: Loewenheim-Skolem Theorem
  33. 11/11: non-standard models for set theory, elementary arithmetic (2.6)
  34. 11/13: complete theories, definable sets (2.6)
  35. 11/15: proof sketch of Goedel's Incompleteness Theorem (3.0)
  36. 11/18: finitely axiomatizable subtheory A_E of number theory (3.3)
  37. 11/20: representable relations (3.3)
  38. 11/22: bounded quantifiers, primes are representable (3.3)
  39. 12/02: Church's thesis, recursive relations, representable functions (3.3)
  40. 12/04: prime power encoding of tuples is representable (3.4)
  41. 12/06: Goedel numbers of formulas, deductions are representable (3.4)
  42. 12/09: Fixed Point Lemma, Tarski's Undefinability Theorem, Goedel's Incompleteness Theorem (3.5)
  43. 12/11: Goedel's Second Incompleteness Theorem (3.7), review [pdf]

Assignments

  1. due 09/04 [pdf] [tex] [solutions]
  2. due 09/11 [pdf]
  3. due 09/18 [pdf]
  4. due 09/25 [pdf] [solutions]
  5. due 10/02 [pdf]
  6. due 10/09 [pdf]
  7. due 10/14 [pdf] [solutions]
  8. due 10/23 [pdf]
  9. due 10/30 [pdf]
  10. due 11/06 [pdf]
  11. due 11/13 [pdf]
  12. due 11/20 [pdf]
  13. due 12/04 [pdf]

Handouts

  1. quantifying over variables in some set using unary predicates [pdf]

Reading