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

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.