Fall 1995

All section references are to Enderton's book,

- 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