Math 4021 Mathematical Logic I

Three credits. Three hours of lecture per week. Prerequisite: MATH 4032.

Propositional calculus. First order predicate calculus. Syntactic and semantic approach to the concept of truth. Gödel’s completeness theorem. Model theory. Decision problems. The arithmetization of logic.

Notes

• Some Axioms for Set Theory
• Propositional Calculus – Syntax
• Propositional Calculus – Theorems
• Propositional Calculus – Proofs
• Propositional Calculus – Semantics
• Functions, Relations and Structures
• First Order Logic – Syntax
• First Order Logic – Axioms
• First Order Logic – Semantics
• Logical circuit symbols and connectives
• Turing Machines
• First Order Logic – Substitution

Syllabus

1. Brief Introduction
   1. What is Mathematical Logic
   2. Mathematical preliminaries.
      • Sets, relations and functions.
      • Induction and recursion.
2. Sentential Logic
   1. The concept of a formal language and examples.
   2. The language of sentencial logic.
   3. The unique readability theorem.
   4. Elementary theorems of sentential logic.
   5. The Deduction theorem
   6. Truth assignments
   7. Craig’s theorem
   8. Compactness theorem for sentential logic.
   9. Completeness theorem for sentential logic
   10. Effectiveness.
3. First order predicate calculus
   1. First order languages
   2. Unique readability
   3. An axiomatization of the first order predicate calculus.
   4. First order structures.
   5. Tarski’s definition of truth.
   6. Model theory
   7. Soundness and completeness theorems.
4. Undecidability (Time permitting)
   1. Number theory
   2. The natural numbers.
   3. Arithmetization of syntax
   4. Incompleteness and undecidability.

Texts

1. H. B. Enderton, A Mathematical Introduction to Logic, Academic Press, 1972
2. J. N. Crossley, et al. What is Mathematical Logic, Dover, 1990.
3. Hamilton Mathematical Logic, Cambridge University Press.

Bibliography

1. J. L. Bell, and M. Machover, A Course in Mathematical Logic, Amsterdam: North-Holland, 1977.
2. G. S. Boolos, and R. C. Jeffrey, Computability and Logic, New York, Cambridge University Press, 1989.
3. H. D. Ebbinghaus, J. Flum, and W. Thomas, Mathematical Logic , New York, Springer-Verlag, 1984.
4. Roger C. Lyndon, Notes on Logic, D. Van Nostrand, 1966.
5. J. R. Shoenfield, Mathematical Logic, Addison-Wesley Pub. Co., 1967.
6. Alfred Tarski, Logic, Semantics, Metamathematics, Indianapolis, IN: Hackett, 1983.