%\documentstyle[russcorr]{article} \documentclass{article} %\usepackage{russcorr} \usepackage{amsmath} %\usepackage{new} \usepackage{fullpage} %\textwidth 15cm %\textwidth 15cm \oddsidemargin 0cm \newcounter{jjjjj} \newcommand{\jjjjj}{\refstepcounter{jjjjj}% \noindent\thejjjjj. } \newcounter{hhhh} \newcommand{\hhhh}{\refstepcounter{hhhh}% \noindent\thehhhh. } \newcommand\ZF{\mathrm{ZF}} \newcommand\ZFC{\mathrm{ZFC}} \newcommand\pair[1]{\langle #1\rangle} \newcommand\ex[1]{\exists #1\,} \newcommand\all[1]{\forall #1\,} \newcommand\exx[1]{(\exists #1)\,} \newcommand\alll[1]{(\forall #1)\,} \DeclareMathOperator{\un}{\mathrm{Un}} \begin{document} {\Large Программа экзамена по спецкурсу ``Формальные теории''} \section{Языки первого порядка} \jjjjj Понятие языка первого порядка. Термы, формулы, замкнутые формулы. \jjjjj Понятие интерпретации языка первого порядка. \jjjjj Язык формальной арифметики. Выразимость в этом языке любого разрешимого отношения. $\beta$-функция Гёделя. \jjjjj Нумерация арифметических термов и формул. Теорема Тарского о невыразимости в языке формальной арифметики множества номеров истинных арифметических формул. \section{Исчисление высказываний} \jjjjj Аксиомы и правила вывода исчисления высказываний. Теорема корректности исчисления высказываний. \jjjjj Лемма о дедукции для исчисления высказываний. Другие производные правила вывода: правило сведения к противоречию, правило разбора случаев. Выводимость законов де Моргана и законов контрапозиции. \jjjjj Теорема о полноте исчисления высказываний. \section{Исчисление предикатов} \jjjjj Аксиомы и правила вывода исчисления предикатов. Теорема корректности исчисления предикатов. \jjjjj Лемма о дедукции для исчисления предикатов. Лемма о свежих константах. \jjjjj Теорема о полноте исчисления предикатов: формула выводима из множества замкнутых формул тогда и только тогда, когда она истинна во всех моделях этого множества. \jjjjj Аксиомы равенства и теорема о полноте исчисления предикатов с аксиомами равенства. \section{Формальная арифметика} \jjjjj Аксиоматизация различных фрагментов арифметики: (1) множества формул сигнатуры $\{0,S\}$, истинных в стандартной интерпретации, (2) множества формул сигнатуры $\{0,S,<\}$, истинных в стандартной интерпретации, (3) множества формул сигнатуры $\{0,S,<,+\}$, истинных в стандартной интерпретации. \jjjjj Аксиомы формальной арифметики Пеано (PA). Теорема Гёделя о неполноте PA. \jjjjj Выводы в PA основных свойств натуральных чисел. Формульное определение отношения ``быть меньше'' и вывод его свойств. \jjjjj Вывод в PA принципа полной математической индукции и принципа наименьшего числа. \jjjjj Принцип свёртывания и его вывод в PA. \jjjjj Следствия принципа свёртывания: (1) для любых конечных последовательностей существует последовательность, равная конкатенации этих последовательностей, (2) возможность рекурсивных определений. \jjjjj Понятие финитного доказательства и тезис о том, что любое финитное доказательство можно провести в рамках PA. Доказательство в PA основной теоремы арифметики. \jjjjj Формула непротиворечивости PA и её невыводимость в PA (вторая теорема Гёделя о неполноте). \jjjjj Теоремы Бернайса. Принцип отражения. Короткое доказательство второй теоремы Гёделя о неполноте на основе теорем Бернайса и принципа отражения. \section{Аксиоматическая теория множеств} \jjjjj Аксиомы теории множеств Цермело- Френкеля. Доказательство существования объединения, пересечения, разности двух множеств. \jjjjj Определение упорядоченной пары по Куратовскому. Доказательство основного свойства упорядоченной пары. Определение понятия произвольной функции. Доказательство существования декартова произведения двух множеств. \jjjjj Понятие транзитивного множества. Ординалы. Элемент ординала --- ординал. Сравнение ординалов. Если имеется ординал с некоторым свойством, то есть и минимальный ординал с этим свойством. \jjjjj Теорема о сравнимости любых двух ординалов. \jjjjj Теорема о том, что для любого множества ординалов существует ординал, больший всех элементов этого множества. \jjjjj Предельные и непредельные ординалы. Натуральные числа. Существование множества натуральных чисел. Определение арифметических операций. Доказательство аксиом Пеано. \jjjjj Принцип трансфинитной индукции. \jjjjj Определения по трансфинитной рекурсии. Теорема о существовании и единственности функции, задаваемой данным рекурсивным правилом. \jjjjj Теорема об изоморфности любого вполне упорядоченного множества некоторому ординалу. \jjjjj Аксиома выбора. Теория множеств с аксиомой выбора $\ZFC$. Доказательство теоремы Цермело в $\ZFC$. \jjjjj Равномощные множества. Кардиналы (мощности). Определение мощности данного множества как кардинала, равномощного этому множеству (в ZFC). Доказательство того, что все натуральные числа и множество натуральных чисел являются кардиналами. Определение конечных и счетных множеств. \jjjjj Мощность подмножества не превосходит мощности множества (доказательство этого факта в $\ZFC$). Доказательство теоремы Кантора--Бернштейна в $\ZFC$. \jjjjj Формула, устанавливающая взаимно-однозначное соответствие между парами ординалов и ординалами. Теорема о том, что декартов квадрат любого бесконечного кардинала равномощен этому кардиналу. \section{Конструктивные множества} \jjjjj Определение класса конструктивных множеств $L$. Определение порядка конструктивного множества. \jjjjj Лемма о том, что если все элементы множества конструктивны, то множество может быть расширено до конструктивного. \jjjjj Лемма о конструктивности множества кортежей, элементы которых принадлежат данному конструктивному множеству и обладают в $L$ данным свойством. \jjjjj Теорема о том, что в классе конструктивных множеств истинны все аксиомы ZF, кроме аксиомы бесконечности. \jjjjj Конструктивность всех ординалов. Теорема о том, что в классе конструктивных множеств истинна аксиома бесконечности. \jjjjj Абсолютность формулы ``$x$ есть конструктивное множество с номером $\alpha$''. Аксиома конструктивности $V=L$ и её истинность в классе конструктивных множеств. \jjjjj Истинность аксиомы выбора в классе конструктивных множеств. \jjjjj Гипотеза континуума и её истинность классе конструктивных множеств. \section{Задачи} Кроме знания указанных теоретических вопросов, необходимо уметь решать следующие задачи. \hhhh Вывести в исчислении высказываний формулу $((p\to q)\to q)\to (p\lor q)$. \hhhh Вывести в исчислении высказываний формулу $((p\to q)\to p)\to p)$. \hhhh Вывести в исчислении предикатов формулу $\ex x P(f(x)) \to \ex y P(y)$. \hhhh Докажите, что для каждого натурального числа $n$ в PA выводима формула $x\le\bar n\to x=0 \lor x=\bar 1 \lor x=\bar 2 \lor\dots\lor x=\bar n)$, где $\bar n$ обозначает $S(S(\dots S(0)))$ ($n$ раз). \hhhh Докажите, что для любых натуральных чисел $m,n$ в PA выводимы формулы $\bar m+\bar n=\overline{m+n}$ и $\bar m\cdot\bar n=\overline{mn}$. \hhhh Докажите, что аксиома существования неупорядоченной пары и аксиома существования пустого множества следуют из остальных аксиом $\ZF$. \hhhh Докажите (в ZF), что для любой функции $f$ существуют её область определения $\{x\mid\ex y(\pair{x,y}\in f)\}$ и множество значений $\{y\mid\ex x(\pair{x,y}\in f)\}$. \hhhh Докажите (в ZF), что если для всех $x\in z$ существует единственное $y$, для которого $A(x,y)$ (где $A(x,y)$ некоторая формула), то существует функция, всюду определённая на $z$, сопоставляющая каждому $x$ такое $y$. \hhhh Докажите, что формула ``$x$ есть функция'' абсолютна. \hhhh Пусть формула $\phi_A$ получена из формулы $\phi$ языка ZF, релятивизацией всех кванторов к конструктивному множеству $B$ (квантор $\exists x$ заменяется на $\exx{x\in B}$, а квантор $\forall x$ --- на $\alll{x\in B}$). Докажите, что формула $\phi_B$ абсолютна. \hhhh Определим множество $V(\alpha)$, где $\alpha$ произвольный ординал, трансфинитной рекурсией: $V(\alpha)$ есть множество всех подмножеств множества $\cup_{\beta<\alpha}V(\beta)$. Докажите, что для каждого множества $x$ найдётся ординал $\alpha$, для которого $x\in V(\alpha)$. \begin{thebibliography}{9} \bibitem{} Н.К.Верещагин. А.Шень. Лекции по математической логике и теории алгоритмов. Часть 1. Начала теории множеств. Москва: МЦНМО. 1999. \bibitem{ф} Н.К.Верещагин. А.Шень. Лекции по математической логике и теории алгоритмов. Часть 2. Языки и исчисления. Москва: МЦНМО. 2000. \bibitem{ы} И.А. Лавров и Л.Л. Максимова. Задачи по теории множеств, математической логике и теории алгоритмов. М.: Наука, 1984 \bibitem{в} Дж. Шенфилд. Математическая логика. М.: Наука, 1975 \bibitem{g} Конспекты: \texttt{http://lpcs.math.msu.ru/\~{}ver/formal-theories} \end{thebibliography} \end{document}