1. Propositional logic: provability, truth tables, consistency, compactness, completeness.
2. First-order predicate logic: syntax and semantics.
   • Deduction systems and formal proofs.
   • Consistency, completeness and decidability of theories the methods of elimination of quantifiers, the Ehrenfeucht-Fraisse Test, and Vaught's Test.
   • Godel's Completeness Theorem. The Henkin proof of a proof using consistency properties. The Compactness Theorem and its application.
   • Elementary model theory. Elementary substructures and the Lowenheim-Skolem-Tarski Theorem.
   • Godel's Incompleteness Theorem. Applications to undecidable theories.

1. Set Theory.
   • Axiomatic set theory. The systems ZF and GB. Relations between sets and classes.
   • Principles of transfinite induction and recursion, and applications.
   • The definitions of cardinal and ordinal numbers. Cardinal and ordinal arithmetic with and without the Generalized Continuum Hypothesis.
   • The Axiom of Choice and its equivalents.
   • Natural models of set theory. Reflection principles.

Recursive function theory.
• Definition of recursive and partial recursive functions. Recursive and recursively enumerable sets. Definability in arithmetic of recursive and r.e. sets. Church's Thesis.
• Unsolvability of the halting problem, and sample applications.
• Elementary recursive function theory. The recursion theorems and the enumeration of parameterization (s-m-n) theorems.
• Turing reducibility and degrees of Unsolvability.

Below is a list of sources for the material in the syllabus. The letters to the left refer to the parts of the syllabus covered in the source. Each source is followed by a "telegraphic" review.

• Chang & Keisler, Model Theory, North-Holland, 1973. The standard graduate text. The first two chapters are particularly relevant. Excellent exercises.

• D. van Dalen, H. C. Doets, H. de Swart, Sets: Naive, Axiomatic and Applied, Pergamon, 1978. A good "mathematical" presentation of set theory. Little explicit use of first-order logic. Good choice of topics.