Дневник лекций 2007 года
7-Feb-2007
Идея Лейбница о формализации математических рассуждений и создание математической логики в первой половине XX века.
Логика высказываний: пропозициональные формулы, тавтологии, эквивалентные формулы. Основные законы рассуждений в форме тавтологий. ДНФ и КНФ.
Исчисление высказываний: аксиомы и правила вывода. Вывод и выводимые формулы.
Теорема о корректности исчисления высказываний.
Лемма о дедукции.
Производные правила.
14-Feb-2007
Лемма о дедукции.
Производные правила.
Теорема о полноте ИВ.
21-Feb-2007
Термы и формулы языка первого порядка данной сигнатуры.
Примеры сигнатур. Интерпретации.
Определение параметров формулы. Определение истинности формулы в данной интерпретации на данной оценке переменных.
Изоморфизмы интерпретаций.
Элементарная эквивалентность интепретаций.
Теорема об элементарной эквивалентности изоморфных интерпретаций.
Выразимые в данной интерпретации предикаты.
Доказательство невыразимости с помощью автоморфизмов.
28-Feb-2007
Общезначимые формулы, равносильные формулы.
Элиминация кванторов: целые числа с добавлением единицы, целые числа с порядком и добавлением единицы.
Невыразимость порядка через сложение на целых числах.
Элементарная эквивалентность упорядоченных множеств Z и Z+Z.
Алгоритм распознавания истинности замкнутых формул в инетрепретациях (Z,S,=) и (Z,S,=,<).
7-Mar-2007
Элиминация кванторов в упорядоченном множестве рациональных чисел.
Элементарная эквивалентность упорядоченных множеств Q и R.
Алгоритм распознавания истинности замкнутых формул в упорядоченном множестве рациональных чисел.
Теория данной сигнатуры (множество замкнутых формул).
Модели теории, нормальные модели теории.
Элементарная теория интерпретации.
Семантическое следствие (для нормальных моделей).
Совместность и семантическая полнота теории.
Критерий полноты (любые две модели элементарно эквивалентны).
14-Mar-2007
Аксиоматизация элементарных теорий: рациональные числа с порядком, целые числа с добавлением единицы, целые числа с порядком и добавлением единицы.
Элиминация кванторов в поле комплексных чисел.
Разрешимость и аксиоматизация элементарной теории поля комплексных чисел.
21-Mar-2007
Элиминация кванторов в упорядоченном поле действительных чисел.
Разрешимость элементарной теории упорядоченного поля действительных чисел.
28-Mar-2007
Исчисление предикатов первого порядка.
Выводы из гипотез.
Теорема корректности исчисления предикатов.
Лемма о дедукции.
4-Apr-2007
Лемма о добавлении новых констант в сигнатуру (множество выводимых формул данной сигнатуры не изменяется, если в сигнатуру добавить новые константы).
Лемма о новых константах (если выводима $\phi(c)$, то выводима и $\phi(x)$).
Непротиворечивые и полные теории.
Лемма о пополнении непротиворечивой теории.
Эксистенциально полные теории.
11-Apr-2007
Теорема о существовании модели непротиворечивой теории.
Ее доказательство.
Теорема Геделя о полноте исчисления предикатов.
18-Apr-2007
Теорема о существовании нормальной модели непротиворечивой теории с равенством.
Теорема Геделя о полноте исчисления предикатов с равенством.
25-Apr-2007
Универсальная вычислимая функция для семейства всех вычислимых частичных функций. Отсутствие универсальной вычислимой функции для семейства всех тотальных вычислимых функций.
Перечислимые множества. Теорема Поста.
Теорема о существовании функции, не имеющей вычислимого тотального продолжения.
Теорема о существовании перечислимого неразрешимого множества.
7-May-2009
Классические неразрешимые алгоритмические проблемы: проблема остановки алгоритма на данном входе, проблема совместности системы диофантовых уравнений, проблема тождества в конечно заданных полгруппах, проблема выводимости формул в исчислении предикатов.
Программы с конечным числом переменных.
Выразимость в интерпретации $(N,+,*)$ (то есть, арифметичность) любого разрешимого предиката.
Замкнутость класса арифметических предикатов относительно пересечений, объединений и проекций.
Арифметичность перечислимых множеств.
Первая теорема Геделя о неполноте: множество всех истинных формул неперечислимо. Следствие: оно не имеет разрешимой аксиоматизации.
25-Apr-2007
Программа Гильберта обоснования математики. Вторая теорема Геделя о неополноте арифметики Пеано. Вторая теорема Геделя о неполноте для аксиоматической теории множеств.