colloq2.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, осень 2025 г.
\end{center}

%\vspace{0.3cm}

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