questions.tex

\documentclass[11pt,a4paper,oneside]{scrartcl}
\usepackage[utf8]{inputenc}
\usepackage[english,russian]{babel}
\usepackage[top=1cm,bottom=1cm,left=1cm,right=1cm]{geometry}

\begin{document}
\pagestyle{empty}

\begin{center}
{\large\scshape\bfseries Программа курса <<Математическая логика>>}\\
{\large\scshape Вопросы к зачёту и экзамену.}\\
\itshape ИТМО, группы M3232--M3239, осень 2023 г.
\end{center}

%\vspace{0.3cm}

\begin{enumerate}
\item Исчисление высказываний. Общезначимость, следование, доказуемость, выводимость. Корректность, полнота, непротиворечивость.
Теорема о дедукции для исчисления высказываний. 
\item Теорема о полноте исчисления высказываний.
\item Интуиционистское исчисление высказываний. Вывод в Гильбертовском стиле и натуральный вывод.
BHK-интерпретация. Решётки. Булевы и псевдобулевы алгебры.
\item Алгебра Линденбаума. Полнота интуиционистского исчисления высказываний в псевдобулевых алгебрах.
Модели Крипке. Сведение моделей Крипке к псевдобулевым алгебрам. Нетабличность 
интуиционистского исчисления высказываний.
\item Топологическое пространство. Примеры. Открытые и замкнутые множества. Связность. Компактность. Непрерывные функции. Путь.
Линейная связность. Теорема о том, что лес связен (является деревом) тогда и только тогда, когда связан в топологическом смысле.
\item Гёделева алгебра. Операция $\Gamma(A)$. Дизъюнктивность интуиционистского исчисления высказываний. Разрешимость 
интуиционистского исчисления высказываний.
\item Исчисление предикатов. Общезначимость, следование, выводимость. Теорема о дедукции в исчислении предикатов.
Теорема о корректности исчисления предикатов.
\item Непротиворечивые множества формул. Доказательство существования моделей у непротиворечивых множеств формул 
в бескванторном исчислении предикатов.
Теорема Гёделя о полноте исчисления предикатов. Доказательство полноты исчисления предикатов.
\item Машина Тьюринга. Задача об останове, её неразрешимость. Доказательство неразрешимости исчисления предикатов.
\item Порядок теории (0, 1, 2). Теории первого порядка. Аксиоматика Пеано. Арифметические операции. 
Доказательство коммутативности сложения. Формальная арифметика. 
\item Примитивно-рекурсивные и рекурсивные функции. Примитивная рекурсивность арифметических операций, 
функций вычисления простых чисел, частичного логарифма.
Выразимость отношений и представимость функций в формальной арифметике. Характеристические функции.
Представимость примитивов $N$, $Z$, $S$, $U$ в формальной арифметике.
Функция Аккермана.
\item Бета-функция Гёделя. Представимость примитивов $R$ и $M$ и рекурсивных функций в формальной арифметике.
Гёделева нумерация. Рекурсивность представимых в формальной арифметике функций.
\item Непротиворечивость (эквивалентные определения, доказательство эквивалентности), $\omega$-не\-про\-ти\-во\-ре\-чи\-вость. 
Первая теорема Гёделя о неполноте арифметики.
Формулировка первой теоремы Гёделя о неполноте арифметики в форме Россера. 
Синтаксическая и семантическая неполнота арифметики.
Ослабленные варианты: арифметика Пресбургера, система Робинсона.
\item Вторая теорема Гёделя о неполноте арифметики, $Consis$. 
Лемма об автоссылках. Условия Гильберта-Бернайса-Лёба. Теорема Тарского о невыразимости истины. Неразрешимость формальной
арифметики.
\item Теория множеств. Определения равенства. Парадокс брадобрея. Аксиоматика Цермело-Френкеля. Конструктивные аксиомы
(пустого, пары, объединения, множества подмножеств, выделения).
Частичный, линейный, полный порядок. Ординальные числа, аксиома бесконечности. 
Конечные ординалы, существование ординала $\omega$, операции над ординалами, 
доказательство $1+\omega\ne\omega+1$. Связь ординалов и упорядочений. Аксиомы фундирования и подстановки.
\item Кардинальные числа, мощность множеств. Теорема Кантора-Бернштейна, теорема Кантора. 
\item Мощность модели. Элементарные подмодели. Теорема Лёвенгейма-Сколема, парадокс Сколема.
\item Аксиома выбора, альтернативные формулировки (лемма Цорна, теорема Цермело, существование
частичной обратной), доказательство переходов (кроме доказательства леммы Цорна).
\item Применение аксиомы выбора: эквивалентность определений пределов (по Коши и по Гейне).
Теорема Диаконеску. Ослабленные варианты (счётный выбор и зависимый выбор), универсум фон-Неймана.
Аксиома конструктивности.
\item Индукция и полная индукция. Трансфинитная индукция. Система $S_\infty$. 
Сечение, устранение сечений. Доказательство непротиворечивости формальной арифметики.
\item Лямбда-исчисление. Пред-лямбда-термы и лямбда-термы. Альфа-эквивалентность, бета-редукция
и бета-эквивалентность. Теорема Чёрча-Россера (формулировка). Комбинатор неподвижной точки. Комбинаторный базис $SK$.
Чёрчевские нумералы. Просто-типизированное лямбда исчисление. Изоморфизм Карри-Ховарда. 
\item Теорема Гёделя о компактности. Универсум Эрбрана. Унификация. Метод резолюции.
\end{enumerate}
\end{document}