Дополнительные главы математической логики
Полугодовой спецкурс на английском языке для 5-го курса (весна 2022)
Лекторы: Н.К. Верещагин и Е.Е. Золин
Студенты, желающие изучить курс, слушают самостоятельно лекции Е.Е.Золина на Youtube https://www.youtube.com/playlist?list=PL6ZCZFyULOwc-5vrmomPf8EyYNQcFf9w5 и каждую неделю решают две задачи.
Каждый четверг 15–16:35 он-лайн на платформе Zoom, начиная с 10 февраля, происходят консультации Н.К. Верещагина.
Контакты: nikolay.vereshchagin@math.msu.ru | Группа в Телеграм
Краткое описание курса:
This course covers themes on classical logic that are not included in the standard courses on mathematical logic. The course consists of two parts.
Part 1: Classical Propositional Logic. Includes the following topics: completeness of the classical propositional calculus (CPC) proved via maximal consistent sets; completeness of the CPC with respect to set semantics and algebraic semantics; representation of finite Boolean algebras (Stone’s Theorem); completeness of the sequent calculus; Cook-Levin Theorem on NP-completeness of the satisfiability problem for propositional formulas; Linial-Post Theorem on undecidability of the axiomatization recognizing problem; a complete axiomatization of the infinitary propositional logic (logic with countable conjunction and disjunction).
Part 2: Classical Predicate Logic. Includes the following topics: conservative extensions of theories; criterion of elementary equivalence of models (Ehrenfeucht games); filters and ultrafilters; ultraproducts; Los’ Theorem on preservation of first-order formulas under ultraproducts; application of ultraproducts — «effective» proof of the compactness theorem, Keisler’s Theorem on criterion of axiomatizability of a class of first-order structures, species of elementary classes (axiomatizable, co-axiomatizable, quasi-axiomatizable classes), representation of arbitrary Boolean algebras; finite model theory.
Лекции
Каждую неделю, начиная с 7 февраля, нужно прослушать одну лекцию с канала Ютуб https://www.youtube.com/playlist?list=PL6ZCZFyULOwc-5vrmomPf8EyYNQcFf9w5. После прослушивания лекции можно в четверг прийти на консультацию он-лайн https://us02web.zoom.us/j/88045913915?pwd=Tk9LcHkyWDkwNmJ4MnlpaUxkSGlqZz09 и задать любые вопросы по содержанию прослушанной лекции или предыдущих лекций. Это можно сделать как по-английски, так и по-русски. После этого надо решить две задачи (см. следующий абзац) и послать их решение ф формате PDF на английском языке в письменном виде лектору.
Домашние задания
После каждой лекции дается домашнее задание, состоящее из двух задач. Это домашнее задание надо сдать (послав PDF Н.К. Верещагину) на английском языке не позже дедлайна, указанного перед самим заданием. Решения, присланные после дедлайна, не проверяются. Повторно решать задачи нельзя. При проверке за каждое задание выставляется оценка, не превосходящая 1. Общая оценка за домашние задания равна среднему арифметическому оценок, полученных за все домашние задания (по существу, это – доля правильно решенных задач).
Экзамен
В конце семестра будет устный экзамен на английском языке. В билете будет два теоретических вопроса, каждый из которых оценивается в 0.5 балла.
Итоговая оценка
Сначала вычисляется среднее арифметическое оценки за задачи и оценки за экзамен. Итоговая оценка выставляется по следующему правилу:
отлично — среднее арифметическое не меньше 80%,
хорошо — 65%,
удовлетворительно — 50%.
Зачет — 60%.