questions-ml.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 Система $S_\infty$. Доказательство непротиворечивости формальной арифметики.
\end{enumerate}
\end{document}