* 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

- Brief Introduction
- What is Mathematical Logic
- Mathematical preliminaries.
- Sets, relations and functions.
- Induction and recursion.

- Sentential Logic
- The concept of a formal language and examples.
- The language of sentencial logic.
- The unique readability theorem.
- Elementary theorems of sentential logic.
- The Deduction theorem
- Truth assignments
- Craig’s theorem
- Compactness theorem for sentential logic.
- Completeness theorem for sentential logic
- Effectiveness.

- First order predicate calculus
- First order languages
- Unique readability
- An axiomatization of the first order predicate calculus.
- First order structures.
- Tarski’s definition of truth.
- Model theory
- Soundness and completeness theorems.

- Undecidability (Time permitting)
- Number theory
- The natural numbers.
- Arithmetization of syntax
- Incompleteness and undecidability.

### Texts

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

#### Bibliography

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