Дневник лекций 2009 года

5-Mar-2009

Определение истинности формулы в данной интерпретации на данной оценке переменных (по Тарскому).
Понятие теории (множество замкнутых формул) данной сигнатуры.
Нормальные интерпретации и модели. Семантическое следование.

Автоморфизмы интерпретаций.
Выразимые в данной интерпретации предикаты.
Доказательство невыразимости с помощью автоморфизмов.

12-Mar-2009

Элиминация кванторов в целых числах с операцией добавления единицы. Разрешимость элементарной теории этой интерпретации.
Аксиоматизация элементарной теории этой интерпретации.

Элиминация кванторов в упорядоченном множестве рациональных чисел. Разрешимость элементарной теории этой интерпретации.
Аксиоматизация элементарной теории этой интерпретации.
Элементарная эквивалентность любых двух линейно упорядоченных плотных множеств без первого и последнего элементов.

Элиминация кванторов в упорядоченном множестве рациональных чисел с операцией сложения и константой 1.
Разрешимость элементарной теории этой интерпретации.

19-Mar-2009

Элиминация кванторов в поле комплексных чисел.
Разрешимость элементарной теории поля комплексных чисел.
Аксиоматизация элементарной теории поля комплексных чисел.
«Почти» логическое доказательство теоремы Гильберта о нулях.

26-Mar-2009

Элиминация кванторов в упорядоченном поле действительных чисел (теорема Зайденберга-Тарского).
Разрешимость элементарной теории упорядоченного поля действительных чисел.
Аксиоматизация элементарной теории теории упорядоченного поля действительных чисел.

2-Apr-2009

Аксиомы и правила вывода Исчисления предикатов. Упражнения в выводимости. Теорема корректности исчисления предикатов: все дедуктивные следствия любого множества формул являются его семантическими следствиями.

9-Apr-2009

Лемма о дедукции для ИП.
Непротиворечивые и полные теории. Теорема Линденбаума о пополнении непротиворечивой теории. Лемма о консервативности исчисления предикатов при расширении сигнатуры добавлением новых констант.

16-Apr-2009

Теорема о совместности непротиворечивой теории.
Теорема о существовании счетной модели непротиворечивой теории в не более чем счетной сигнатуре.
Теорема Геделя о полноте.
Теорема Мальцева о компактности.

Исчисление предикатов с равенством. Теорема о существовании нормальной модели непротиворечивой теории с равенством.
Теорема Геделя о полноте для нормальных моделей.

23-Apr-2009

Теорема о существовании конечной или счетной нормальной модели непротиворечивой теории с равенством в счетной сигнатуре.

Нестандартные модели арифметики.
Нестандартный анализ.

Вычислимые функции. Разрешимые и перечислимые множества.
Существование невычислимых функций и неразрешимых и неперечислимых множеств.

30-Apr-2009

Критерии перечислимости: множество перечислимо тогда и только тогда, когда оно является областью определения вычислимой функции, множеством значений (частичной) вычислимой функции, его полухарактеристическая функция вычислима.
Пересечение и объединение перечислимых множеств.

Теорема Поста.
Критерий перечислимости в терминах проекции разрешимых множеств.

Критерий вычислимости в терминах перечислимости: теорема о графике.
Образ и прообраз перечислимых множеств относительно вычислимых функций.

Универсальная вычислимая функция.
Отсутствие вычислимой функции, универсальной для семейства всех всюду определенных вычислимых функций.
Вычислимая функция, не имеющая всюду определенных вычислимых продолжений.
Перечислимое неразрешимое множество.
Неразрешимость проблемы остановки.
Первая теорема Геделя о неполноте: элементарная теория натуральных чисел неперечислима.

Программы с конечным числом переменных.

7-May-2009

Арифметичность вычислимых функций.
Замкнутость класса арифметических предикатов относительно пересечений, объединений и проекций.
Арифметичность перечислимых множеств.

Доказательство первой теоремы Геделя о неполноте.

14-May-2009

Программа Гильберта обоснования математики. Вторая теорема Геделя о неполноте арифметики Пеано. Вторая теорема Геделя о неполноте для аксиоматической теории множеств.