Advanced course in classical logic
(Дополнительные главы классической логики)
(полугодовой спецкурс на английском языке)
к.ф.-м.н., с.н.с. Е.Е.Золин

Чтобы сдавать данный курс, напишите лектору по email (см. на главной странице).

Весна 2018

Конспект лекций: [ pdf ] (обновлено 2018.06.05 17:00)

Вопросы к экзамену: [ pdf ]

Примеры задач: [ pdf ]

Весна 2017

Конспект лекций: [ pdf ]

Вопросы к экзамену: [ pdf ]

Примеры задач: [ pdf ]

Весна 2016

Конспект лекций: [ pdf ]

Вопросы к экзамену: [ pdf ]

Примеры задач: [ pdf ]


Весна 2018

Темы прошедших лекций:
  1. 2018.02.16: Classical propositional logic (reminder). // Syntax, semantics. Axiomatic system. Completeness and strong completeness. Compactness. Interesting facts: axiomatization of the implication fragment of CL (classical logic) and Int (intuitionistic logic); axiomatization with only one axiom for CL and Int; axiomatizations for other connectives (equivalence, Sheffer stroke, Pierce's arrow); undecidability of the problem of recognizing axiomatizations of CL, Int and (almost any) other logic.
  2. 2018.03.02: Algebraic semantics for the classical propositional logic. // Boolean algebras: definition, examples. Interpretation in an algebra. Completeness and strong completeness: the construction of the Lindenbaum algebra. (Strong completeness is not in the PDF yet.)
  3. 2018.03.16: Sequent calculus for the classical propositional logic. // Axioms and rules; completeness. Decidability of the provability problem as a consequence.
  4. 2018.03.23: The Cook–Levin theorem. // Turing machines. The classes of problems P, NP: definition, examples. Polynomial reduction of one problem to another problem; its basic properties.
    Proof of Cook–Levin theorem (video lecture)
  5. 2018.03.30: Infinitary propositional logic. // Syntax, semantics. The cardinality of the set of formulas. Axiomatization. Deduction theorem.
  6. 2018.04.06: Classical predicate logic: reminder. // Syntax: terms, formulas. Semantics: valid formulas. Axiomatization: classical predicate calculus. Main results: Completeness (Godel), Compactness (Maltsev), Undecidability (Church, Turing).
  7. 2018.04.13: Ehrenfeucht games. // 1) Two models M and N are elementarily equivalent iff the second player has a winning strategy in the Game(M,N). 2) Two models M and N are indistinguishable by any formula of quantifier rank at most k iff the second player has a winning strategy in the Gamek(M,N). Examples of pairs of models, games for them, tasks of finding the minimal quantifier rank of formula that distinguishes two given models.
  8. 2018.04.20: Filters and ultrafilters.
  9. 2018.04.27: Ultraproduct of first-order models. Los' Theorem. Ultrapower MΦ of a model M. Elementary equivalence of M and MΦ.
  10. 2018.05.04: Applications of ultraproducts. // 1) Compactness. If a class of models K is closed under ultraproducts, then K is compact. 2) Axiomatizable classes of models, finitely axiomatizable classes of models. Criterion of axiomatizability: a class is axiomatizable iff it is closed under elementary equivalence and ultraproducts.
    Ultraproducts as a bridge between discrete and continuous analysis — a lecture by ... at Simons Institute.
  11. 2018.05.11: Criterion of finite axiomatizability: a class of models K is finitely axiomatizable iff K and its complement are axiomatizable. Corollary: the class of infinite groups is axiomatizable, but not finitely axiomatizable; the class of finite groups is not axiomatizable. The same result holds for any class of models K that is finitely axiomatizable and has arbitrarily large finite models.

    Finite Model Theory: the lack of compactness; the lack of completeness; games still work.
    Lemma: Every finite model has a closed formula that characterizes this model up to isomorphism.
    Corollary: Two finite models are elementary equivalent iff they are isomorphic.

  12. 2018.05.18: Theorem: If a class of finite models is closed under isomorphism, then it is axiomatizable (within the class of all finite models).
    Theorem: If a class of finite models K is finitely axiomatizable (= definable), then it is closed under ≡m for some m. (In fact, “iff” holds.)
    Examples of FO definable and undefinable classes of finite models.
    Finite Model Theory — five lectures by Anuj Dawar at Simons Institute.

Литература

  1. Верещагин Н.К., Шень А.Х. Языки и исчисления, 4-е издание, Москва, МЦНМО, 2014. [доступно в сети: pdf ]
  2. Chang C.C., Keisler H.J. Model Theory, North-Holland Pub. Co., 1990. [доступно в сети]
    Кейслер Г., Чэн Ч.Ч. Теория моделей, Москва, Мир, 1977. [доступно в сети]
  3. Sikorski R. Boolean Algebras, 3rd edition, Springer, 1969. [доступно в сети]
    Сикорский Р. Булевы алгебры, Москва, Мир, 1969. [доступно в сети]
  4. Bell J.L., Slomson A.B. Models and Ultraproducts: An Introduction, North-Holland Pub. Co., 1969. [доступно в сети]
  5. Keisler H.J. Model Theory for Infinitary Logic. North-Holland Pub. Co., 1971. [доступно в сети]
  6. Zolin E. Undecidability of the problem of recognizing axiomatizations of superintuitionistic propositional calculi, Studia Logica, 102(5):1021-1039, 2014. [ pdf ]
  7. Bokov - статьи (напишу позже)

  8. Leonid Libkin. Elements of Finite Model Theory. 2004. Главы 1 и 3. [доступно в сети]
  9. Ebbinghaus, Flum. Finite Model Theory. 2006. Глава 2. [доступно в сети]