1. Программа Гильберта. Математика, как деятельность по формальным правилам. Содержательное представление о полноте и непротиворечивости и возможности их установить.
2. «Наивная теория множеств» Кантора. Отношения, функции, свойства, как множества. Множества: объединение, пересечение, прямое произведение, проекция.
3. Существование множества, заданного своим описанием; Парадокс Рассела.
4. Индуктивные определения и задаваемые ими множества объектов; примеры.
5. Логика высказываний. Синтаксис и семантика. Определение формулы (логики высказываний). Теорема об однозначности анализа.
6. Сокращения. Опускание скобок.
7. Значение формулы при данной интерпретации. Свойство подстановки: значение формулы определяется значениями подформул из которых она образована. Выполнимость и общезначимость (тавтологии). Теорема компактности для логики высказываний.
8. Построение формулы логики высказываний по булевой функции. Теорема о совершенной дизъюнктивной нормальной форме.
9. Представление в логике высказываний распространенных способов рассуждения.
10. Структура данной сигнатуры. Гомоморфизмы, вложения, изоморфизмы, автоморфизмы структур.
11. Логика отношений; синтаксис и семантика логики отношений. Определимость. Выполнимость. Истинность. Совместность.
12. Предваренная нормальная форма.
13. Примеры определимых отношений в упорядоченных множествах.
14. Примеры определимости в арифметике. Китайская теорема об остатках. Бета-функция Гёделя.
15. Пространства определимости.
16. Расширение сигнатуры операциями, расширение логики отношений термами. Использование отношений вместо функций.
17. Определимость отношений в поле действительных чисел. Полуалгебраические множества. Теорема Тарского – Зайденберга.
18. Теория. Модель теории. Теория структуры. Соответствие Галуа для теорий и классов моделей.
19. Критерий элементарности подструктуры.
20. Теория с равенством. Теория равенства.
21. Теория линейного порядка. Дискретный порядок с наименьшим элементом. Плотный неограниченный линейный порядок. Сложение порядков.
22. Нестандартная арифметика. Галактики.
23. Построение модели непротиворечивой теории. Перечислимость истин.
24. Теорема компактности для логики отношений. Полная теория.
25. Категоричность; рассмотрение случая плотного линейного порядка. Признак Лося – Воота.
26. Теорема Лёвенгейма – Сколема об элементарной подмодели.
27. Доказательства неопределимости. Метод автоморфизмов. Теорема Свенониуса.
28. Соответствие Галуа для пространств определимостей и групп автоморфизмов. Подмногообразия и надгруппы. Применения теоремы Свенониуса.
29. Определимость одноместных отношений в порядке на натуральных числах.
30. Модальная логика. Шкала Крипке. Исчисление Крипке.
31. Теорема об истинности для исчисления Крипке.
32. Теорема о полноте для исчисления Крипке.
33. Исчисление логики отношений. Теорема Геделя о полноте, без доказательства.
34. Алфавиты. Ансамбли: слов, цепочек слов, списков. Кодирование элементов ансамблей двоичными словами. Переход к следующему в ансамбле.
35. Действия и проверки.
36. Общее понятие исчисления. Породимые множества. Теоремы замкнутости для исчислений.
37. Вывод объекта.
38. Грамматики. Тезис Поста.
39. Алгоритмы. Вычислимые функции.
40. Универсальный алгоритм. Универсальная вычислимая функция.
41. Диагональ невычислимости.
42. Алгоритмы Маркова. Тезис Черча.
43. Алгоритмические проблемы. 10-ая Проблема Гильберта.
44. Равнообъемность класса областей определения вычислимых функций и класса перечислимых множеств.
45. Равнообъемность классов перечислимых и породимых множеств.
46. Возможность определить класс вычислимых функций через породимость.
47. Разрешимость; соотношение с перечислимостью.
48. Сложность вычислений. Задачи, решаемые перебором. Задача о рюкзаке. Задача выполнимости.
49. Универсальная переборная задача. P=NP?
50. Сложность объекта. Теорема Колмогорова. Случайность.
51. Теорема Тарского о невыразимости истины.
52. Теорема Геделя о неполноте.
53. Арифметика Пеано. Червь Беклемишева
54. Аксиоматическое построение математики. Теория множеств. Равномощность. Гипотеза континуума.
55. Теорема Кантора - Бернштейна.
56. Вполне упорядоченные множества. Трансфинитная индукция. Определение (в ZF) множества ω и свойства этого множества.
57. Теорема Цермело. Аксиома выбора.
58. Независимость Гипотезы Континуума и Аксиомы выбора от Теории множеств (без доказательства). Парадокс Банаха – Тарского (без доказательства).
Идеи и методы (Предполагается, что готовясь к ответу студент вспомнит все упоминаемые в вопросе доказательства и расскажет одно, на свой выбор, выделяя центральную заглавную конструкцию, а также может получить предложение привести пример применения назвываемого преподавателем метода или идеи и приведет какой-то один пример)
59. Применения диагонального метода: в доказательстве несчетности континуума, в теории вычислимых функций.
60. Применение челночного метода: в доказательствах теоремы Свенониуса, теоремы Левенгейма – Сколема, категоричности теории плотного линейного порядка без первого и последнего элемента.
61. Применение идеи самоприменимости в парадоксе Рассела, в доказательствах теорем Тарского и Гёделя.
62. Применение идеи универсального моделирования в теории алгоритмов: построение универсальной функции, теорема Колмогорова, существование универсальной переборной задачи, моделирование вычисления в логике высказываний.