## Schedule

All section references are to Enderton's book, A Mathematical Introduction to Logic.
95.09.06
Overview of entire course. Section 2.0.
95.09.08
Section 2.1: First-order languages.
95.09.11
Start Section 2.2: Truth and models.
95.09.13
Finish Section 2.2: Truth and models. Lightly over Section 2.3: Unique readability.
95.09.15
Start Section 2.4: Hilbert-style axiomatic systems.
95.09.18
Continue Section 2.4.
95.09.20
Conclude Section 2.4. Not every part of 2.4 will be presented in lecture, some studying will be left to you to do alone.
95.09.22
Start Section 2.5: Soundness and Completeness. Equivalent statements of Soundness and Completeness, and their proofs.
95.09.25
Continue Section 2.5: Soundness and Completeness. Compactness theorem, Enumerability theorem, and their corollaries.
95.09.27
Continue Section 2.5: Soundness, start Completeness.
95.09.29
Conclude Section 2.5: Finish Completeness.
95.10.02
Solutions for some of the exercises in Sections 2.4 and 2.5.
95.10.04
Start Section 2.6: Beginning model theory, Lowenheim-Skolem Theorems, sizes of models.
95.10.06
Continue Section 2.6: Theories (axiomatizable, finitely axiomatizable, complete), non-standard models.
95.10.10
Finish Section 2.6: Los-Vaught test, applications.
95.10.11
Start Section 2.7: Interpretations between theories.
95.10.13
Examples worked out: Discrete linear orderings with first element, the theory of (N,0,S) from Section 3.1.
95.10.16
Exercise 6, page 153: Solution based on material on prenex normal forms in Section 2.6 (details in handout), solution based on Corollary 32B in Section 3.2. Continue Section 3.1, start Section 3.2.
95.10.18
Finish section 2.7. Finish Section 3.1.
95.10.20
Continue Section 3.2. Presburger arithmetic, more on elimination of quantifiers.
95.10.23
Continue Section 3.2. More on elimination of quantifiers.
95.10.25
Finish Section 3.2. Start Section 3.3.
95.10.27
Continue Section 3.3. Definability versus representability.
95.10.30
Exercises 4 and 5, page 184.
95.11.01
Alternative solutions for Exercise 5, page 184. Continue Section 3.3. Representabilty of functions, Church's Thesis, equivalent conditions on the computability of functions.
95.11.03
Solution for Exercise 6, page 184. Continue Section 3.3. More on representable functions.
95.11.06
Conclude Section 3.3 on representable functions.
95.11.08
Start Sections 3.4 and 3.5.
95.11.10
Finish Section 3.4, continue Section 3.5.
95.11.13
Finish Section 3.5.
95.11.15
Remarks about the arithmetical hierarchy, Sections 3.6 and 3.7.
95.11.17
Highlights from Section 3.8.
95.11.20
Solution for Ex 4, page 239. General comments on Handouts 1, 2, 3, and 5. Motivation for studying intuitionism.
95.11.27
Material from Handout 4. Equivalence of the rules RAA (reductio ad absurdum), EM (law of excluded middle), and NCD (non-constructive dilemna).
95.11.29
More on Intuitionism. Comparison with classical logic. The "disjunction property" and the "existence property", satisfied by intuitionistic but not classical logic.
95.12.01
More on Intuitionism. Comparison with classical logic.
95.12.04
Discussion of Ex 1 in Hwk 11. Properties of normal derivations, based on the rules of natural deduction.
95.12.06
More on the properties of normal derivations.
95.12.08
Complete proof that every derivation can be normalized. Start definitions for a sketch of the Curry-Howard isomorphism.
95.12.11
Exercises 2 and 3 in Hwk 11. More on the Curry-Howard isomorphism, restricted to a propositional logic based on "arrow" and "conjunction" only.
```
Assaf Kfoury
Created:  95.09.06
Modified: 95.12.11
```