1. Home ›
  2. Graduate ›
  3. Basic Courses ›
  4. Logic I and II

Logic I and II

Logic I, II – 60510, 60520

1. Model Theory

First order predicate logic. Structures and theories. Compactness theorem. Ultraproducts. Löwenheim-Skolem theorems. Saturation and homogeneity. Quantifier elimination: methods, examples, and applications. Types and type spaces. Prime and Saturated models. Countable models and countable categoricity. Henkin constructions should be seen, for example in the omitting types theorem.

If time permits, more advanced topics may be included.

References

  • C. C. Chang and H. J. Keisler, Model Theory.
  • D. Marker, Model theory, an introduction.
  • K. Tent and M. Ziegler, A course in model theory.

2. Computability Theory

Turing machines. Primitive recursive functions, partial recursive functions, equivalence of Turing and Kleene definitions. Recursive sets, computably enumerable sets. The Recursion Theorem. Index sets and Rice's Theorem. Strong reducibilities (m-reducibility, 1-reducibility). Relative computability, Turing degrees, jumps, the Kleene-Post Theorem. The arithmetical hierarchy. Computably enumerable degrees, the Friedberg-Muchnik Theorem, the Low Basis Theorem.

If time permits, further topics may be included.

References

  • R. I. Soare, Recursively Enumerable Sets and Degrees.
  • H. Rogers, Theory of Recursive Functions and Effective Computability.
  • B. Cooper, Computability Theory

3. Set Theory

Axioms of ZFC, Schröder-Bernstein Theorem, ordinals, ordinal arithmetic, proof and definition by recursion. The Von Neumann hierarchy. Cardinals, cardinal arithmetic. Special kinds of cardinals—regular and singular, successor and limit, inaccessible, equivalent versions of the Axiom of Choice, the constructible hierarchy.

If time permits, further topics may be included.

References

  • T. Jech, Set Theory.
  • K. Kunen, Set Theory.
  • Cohen, Set Theory and the Continuum Hypothesis.

Logic I covers the material on model theory and part of the material on set theory, including ordinal and cardinal arithmetic, and definitions by recursion. Logic II covers the material on computability, plus more set theory.