Phil 513: Mathematical Logic I
Fall 2013 — Kevin C. Klement


Course description and goals.

This course covers elementary meta-mathematics and logical meta-theory. Topics include completeness and consistency proofs for first-order logic, model theory, elementary number theory (especially Peano arithmetic), and Gödel’s incompleteness theorems and related results.

Prerequisites.

Phil 310 (Intermediate Logic) or equivalent and solid grasp of high school algebra, or consent of instructor.
Syllabus

Course requirements, contact info and course schedule.
Log in to Moodle Page

Check grades, get readings, use chat and discussion boards, etc.
Lecture Notes, Unit I

Introduction
   A. The Topic — 1
   B. Metalanguage and Object Language — 2
   C. Set Theory — 3
   D. Mathematical Induction — 6
1. Metatheory for Propositional Logic
   A. The Syntax of Propositional Logic — 8
   B. The Semantics of Propositional Logic — 9
   C. Reducing the Number of Connectives — 12
   D. Axiomatic Systems and Natural Deduction — 16
   E. Axiomatic System L — 17
   F. The Deduction Theorem — 19
   G. Soundness and Consistency — 22
   H. Completeness — 23
   I. Independence of the Axioms — 25
Lecture Notes, Unit II

2. Metatheory for Predicate Logic
   A. The Syntax of Predicate Logic — 28
   B. The Semantics of Predicate Logic — 31
   C. Countermodels and Semantic Trees — 35
   D. An Axiom System — 39
   E. The Deduction Theorem in Predicate Logic — 40
   F. Doing without Existential Instantiation — 41
   G. Metatheoretic Results for System PF — 43
   H. Identity Logic — 50
Lecture Notes, Unit III

3. Peano Arithmetic and Recursive Functions
   A. The System S — 55
   B. The Quasi-Fregean System F — 58
   C. Numerals — 62
   D. Ordering, Complete Induction and Divisibility — 63
   E. Expressibility and Representability — 67
   F. Primitive Recursive and Recursive Functions — 70
   G. Number Sequence Encoding — 77
   H. Representing Recursive Functions in System S — 79
Lecture Notes, Unit IV

4. Gödel’s Results and their Corollaries
   A. The System — 84
   B. System S as its Own Metalanguage — 85
   C. Arithmetization of Syntax — 87
   D. Robinson Arithmetic — 93
   E. Diagonalization — 94
   F. ω-Consistency, True Theories and Completeness — 95
   G. Gödel’s First Incompleteness Theorem — 97
   H. Church’s Thesis — 100
   I. Löb’s Theorem / Gödel’s Second Theorem — 101
   J. Recursive Undecidability — 103
   K. Church’s Theorem — 106
All Lecture Notes Together

(Contains notes for all four units, plus hyperlinked table of contents and index of symbols/definitions.)
Links: Email Kevin / Kevin’s Homepage / UMass Philosophy / Five College Logic Certificate
This website was created and is maintained entirely with free license/open-source software. It is best viewed by Firefox 3.5+ or Chromium. Like every website, it is best not viewed with Micro$oft Internet Explorer.