Mathematics Honors Courses in Armenia

Initiative of Armenian Society of Fellows (ASOF)

Mathematical Logic: Model Theory & Computability

2024 Spring


Lecture info

Problem session info

Details

Lectures

Homework

Recordings

Prerequisits

 Comfort with definitions and proofs, as well as familiarity with mathematical structures such as graphs, partial orders, groups, rings, fields, and vector spaces.

Coursework and grades

Course description

 The course will introduce the main ideas and basic results of mathematical logic from a fairly modern prospective, providing a number of applications to other fields of mathematics such as combinatorics, Ramsey theory, algebra, and algebraic geometry. It will consist of two parts: model theory and computability theory.
 Model theory is a study of mathematical structures, examples of which include groups, rings, fields, graphs, and partial orders. We will first abstractly study structures and definability, theories, models and categoricity, as well as formal proofs, and this will culminate in proofs of the Gödel Completeness and Compactness Theorems – two of the most useful tools of logic. Then we will apply the developed techniques to concrete examples such as the structure of natural numbers and algebraically closed fields; the latter will yield a rigorous proof of the Lefschetz Principle (a first-order sentence is true in the field of complex numbers if and only if it is true in all algebraically closed fields of sufficiently large characteristic) and an amusingly slick proof of Ax's theorem (if a polynomial function ℂn → ℂn is injective, then it is surjective). We will also discuss applications of the Compactness theorem in deriving finitary analogues of the infinitary combinatorial statements such as the infinite Ramsey theorem, van der Waerden's or Szemerédi's theorems, graph colorings, etc.
 The computability theory part will begin with a robust definition of computation (algorithm), followed by a rather short investigation of computable functions and sets. The investigation will be short because we will quickly discover that many interesting functions and sets are not computable, as illustrated by the Gödel Incompleteness Theorem and Church's theorem on undecidability of first-order logic, both of which we will prove.

Literature

  • A. TSERUNYAN, Mathematical Logic, lecture notes [pdf]
  • C. C. LEARY, L. KRISTIANSEN, A Friendly Introduction to Mathematical Logic, 2nd Edition [free download]
  • A. TSERUNYAN, A quick introduction to basic set theory, 20-page lecture notes and problems for undergraduates [pdf]