Fall 1995
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