hw-theory.tex

\documentclass[10pt,a4paper,oneside]{article}
\usepackage[utf8]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{enumerate}
\usepackage{stmaryrd}
\usepackage{cmll}
\usepackage{mathrsfs}
\usepackage[left=2cm,right=2cm,top=2cm,bottom=2cm,bindingoffset=0cm]{geometry}
\usepackage{proof}
\usepackage{tikz}
\usepackage{multicol}
\usepackage{mathabx}
\usepackage{comment}

\makeatletter
\newcommand{\dotminus}{\mathbin{\text{\@dotminus}}}

\newcommand{\@dotminus}{%
  \ooalign{\hidewidth\raise1ex\hbox{.}\hidewidth\cr$\m@th-$\cr}%
}
\makeatother

\usetikzlibrary{arrows,backgrounds,patterns,matrix,shapes,fit,calc,shadows,plotmarks}

\newtheorem{definition}{Определение}
\begin{document}

\begin{center}{\Large\textsc{\textbf{Теоретические (``малые'') домашние задания}}}\\
             \it Математическая логика, ИТМО, М3232-М3239, весна 2023 года\end{center}

\section*{Задание №1. Знакомство с исчислением высказываний.}


При решении заданий вам может потребоваться теорема о дедукции (будет доказана на второй лекции): 
$\Gamma, \alpha \vdash \beta$ 
тогда и только тогда, когда $\Gamma \vdash \alpha\rightarrow\beta$. Например, если было показано 
существование вывода $A \vdash A$, то тогда теорема гарантирует и существование вывода $\vdash A \rightarrow A$.

\begin{enumerate}
\item Докажите:
\begin{enumerate}
\item $\vdash (A \rightarrow A \rightarrow B) \rightarrow (A \rightarrow B)$
\item $\vdash \neg (A \with \neg A)$
\item $\vdash A \with B \rightarrow B \with A$
\item $\vdash A \vee B \rightarrow B \vee A$
\item $A \with \neg A \vdash B$
\end{enumerate}

\item Докажите:
\begin{enumerate}
\item $\vdash A \rightarrow \neg \neg A$
\item $\neg A, B \vdash \neg(A\& B)$
\item $\neg A,\neg B \vdash \neg( A\vee B)$
\item $ A,\neg B \vdash \neg( A\rightarrow B)$
\item $\neg A, B \vdash  A\rightarrow B$
\end{enumerate}

\item Докажите:
\begin{enumerate}
\item $\vdash (A \rightarrow B) \rightarrow (B \rightarrow C) \rightarrow (C \rightarrow A)$ 
\item $\vdash (A \rightarrow B) \rightarrow (\neg B \rightarrow \neg A)$ \emph{(правило контрапозиции)}
\item $\vdash A \with B \rightarrow \neg (\neg A \vee \neg B)$
\item $\vdash \neg (\neg A \vee \neg B) \rightarrow (A \with B)$
\item $\vdash (A \rightarrow B) \rightarrow (\neg A \vee B)$
\item $\vdash A \with B \rightarrow A \vee B$
\item $\vdash ((A \rightarrow B) \rightarrow A)\rightarrow A$ \emph{(закон Пирса)}
\end{enumerate}

\item Следует ли какая-нибудь расстановка скобок из другой: $(A \rightarrow B) \rightarrow C$ и 
$A \rightarrow (B \rightarrow C)$? Предложите вывод в исчислении высказываний или докажите, что его не
существует (например, воспользовавшись теоремой о корректности, предложив соответствующую оценку).

\item Предложите схемы аксиом, позволяющие добавить следующие новые связки к исчислению.
\begin{enumerate}
\item Связка <<и-не>> (<<штрих Шеффера>>, ``|''): $A\ |\ B$ истинно, когда один из аргументов ложен. Новые схемы аксиом должны 
давать возможность исключить конъюнкцию и отрицание из исчисления. 

Поясним, что мы понимаем под словами <<исключить связку>>.
Как вы знаете, конъюнкция и отрицание выражаются через <<и-не>> ($\neg \alpha := \alpha\ |\ \alpha$ и т.п.). 
При такой замене все схемы аксиом для конъюнкции и отрицания должны стать теоремами.
При этом исчисление должно остаться корректным относительно классической модели исчисления высказываний.

\item Связка <<или-не>> (<<стрелка Пирса>>, ``$\downarrow$''): $A \downarrow B$ истинно, когда оба аргумента ложны.
Новые схемы аксиом должны давать возможность исключить дизъюнкцию и отрицание из исчисления.
\item Нуль-местная связка <<ложь>> (``$\bot$''). Мы ожидаем вот такую замену: $\neg A := A \rightarrow \bot$.
Аналогично, аксиомы для отрицания в новом исчислении должны превратиться в теоремы. 
\end{enumerate}

\item Достаточно ли лжи и <<исключённого или>> ($A \oplus B$ истинно, когда $A \ne B$) для выражения
всех остальных связок? 

\item Даны высказывания $\alpha$ и $\beta$, причём $\vdash \alpha\rightarrow\beta$ и $\not\vdash\beta\rightarrow\alpha$. 
Укажите способ построения высказывания $\gamma$, такого, что
$\vdash\alpha\rightarrow\gamma$ и $\vdash\gamma\rightarrow\beta$, причём $\not\vdash\gamma\rightarrow\alpha$ и
$\not\vdash\beta\rightarrow\gamma$.

\item Покажите, что если $\alpha \vdash \beta$ и $\neg\alpha\vdash\beta$, то $\vdash\beta$.
\end{enumerate}

\section*{Задание №2. Теоремы об исчислении высказываний. Интуиционистская логика.}

\begin{enumerate}
\item Покажите, что в классическом исчислении высказываний $\Gamma \models \alpha$ влечёт $\Gamma \vdash \alpha$.

\item Покажите, что следующие высказывания не доказуемы в интуиционистской логике:
\begin{enumerate}
\item $\neg\neg A \rightarrow A$
\item $((A \rightarrow B) \rightarrow A) \rightarrow A$
\item $(A \rightarrow B) \vee (B \rightarrow A)$
\item $(A \rightarrow B \vee \neg B) \vee (\neg A \rightarrow B \vee \neg B)$
\item $\bigvee_{i=0,n-1} A_i \rightarrow A_{(i+1) \% n}$
\end{enumerate}

\item Выполнены ли формулы де Моргана в интуиционистской логике? Докажите или опровергните:
\begin{enumerate}
\item $\alpha\vee\beta \vdash \neg(\neg\alpha\with\neg\beta)$ и $\neg(\neg\alpha\with\neg\beta) \vdash \alpha\vee\beta$
\item $\neg\alpha\with\neg\beta \vdash \neg(\alpha\vee\beta)$ и $\neg(\alpha\vee\beta) \vdash \neg\alpha\with\neg\beta$
\item $\alpha\rightarrow\beta \vdash \neg\alpha\vee\beta$ и $\neg\alpha\vee\beta \vdash \alpha\rightarrow\beta$
\end{enumerate}

\item Покажите, что никакие связки не выражаются друг через друга: то есть, нет такой формулы $\varphi(A,B)$ из языка 
интуиционистской логики, не использующей связку $\star$, что $\vdash A \star B \rightarrow \varphi(A,B)$ и $\vdash\varphi(A,B) \rightarrow A \star B$.
Покажите это для каждой связки в отдельности:
\begin{enumerate}
\item $\star$ --- конъюнкция;
\item $\star$ --- дизъюнкция;
\item $\star$ --- импликация;
\item $\star$ --- отрицание.
\end{enumerate}

\item Существует несколько схожих вариантов аксиомы исключённого третьего. Не пользуясь 10 схемой аксиом, покажите
следующее:
\begin{enumerate}
\item $\alpha\vee\neg\alpha, \alpha\rightarrow\neg\alpha\rightarrow\beta \vdash ((\alpha\rightarrow\beta)\rightarrow\alpha)\rightarrow\alpha$
\item $((\alpha\rightarrow\beta)\rightarrow\alpha)\rightarrow\alpha, \alpha\rightarrow\neg\alpha\rightarrow\beta \vdash \neg\neg\alpha\rightarrow\alpha$
\end{enumerate}

\item Рассмотрим несколько моделей троичной логики. Логики похожи истинностными значениями ($V = \{ -1, 0, 1 \}$, истиной считаем 1)
и определением большинства операций:
$\llbracket A \with B\rrbracket = \min(\llbracket A \rrbracket, \llbracket B \rrbracket)$,
$\llbracket A \vee B\rrbracket = \max(\llbracket A \rrbracket, \llbracket B \rrbracket)$,
$\llbracket \neg A\rrbracket = -\llbracket A \rrbracket$. Отличаются логики определением импликации (ниже), и в одном случае -- определением отрицания.
Про каждую из них ответьте на четыре вопроса:
являются ли они корректными и/или полными моделями классического и/или интуиционистского исчисления высказываний.

\begin{enumerate}
\item Сильная логика неопределённости Клини: $\llbracket A \rightarrow B \rrbracket = \llbracket \neg A \vee B \rrbracket$.
\item Троичная логика Лукасевича: $\llbracket A \rightarrow B \rrbracket = \min(1,1 -\llbracket A \rrbracket + \llbracket B \rrbracket)$
\item Логика Гёделя $G_3$: $$\llbracket \neg A \rrbracket = \left\{\begin{array}{ll}1,& \llbracket A \rrbracket = -1\\-1,&\text{иначе} \end{array}\right.
  \quad\quad \llbracket A \rightarrow B \rrbracket = \left\{\begin{array}{ll}1,& \llbracket A \rrbracket \le \llbracket B \rrbracket \\\llbracket B \rrbracket,&\text{иначе}\end{array}\right.$$
\end{enumerate}

\item Изоморфизм Карри-Ховарда --- соответствие между интуиционистским исчислением высказываний, с одной стороны, и 
языками программирования, с другой. А именно, можно заметить, что программа соответствует доказательству, тип программы --- 
логическому высказыванию. Связки (как составные части логического высказывания) соответствуют определённым типовым конструкциям:
функция --- импликации, конъюнкция --- упорядоченной паре, дизъюнкция --- алгебраическому типу (\verb!std::variant! и т.п.).

Например, функция \verb!A id(A x) { return x; }! доказывает $A \rightarrow A$, а функция 
\begin{verbatim}
std::pair<A,B> swap(std::pair<B,A> x) { return std::pair(x.second, x.first); }
\end{verbatim}
доказывает $B\with A \rightarrow A \with B$.

Ложь выражается менее очевидно. Давайте за ложь мы возьмём выражение, имеющее тип несвязанного типового параметра
(идея в том, чтобы данное выражение легко приводилось бы к любому типу: из лжи следует всё что угодно). 
Данный код доказывает $\neg Z$, то есть $Z \rightarrow \bot$: 
\begin{verbatim}
template <class A>   
A negate(Z x) { throw ("Value of type Z is impossible"); }
\end{verbatim}

Конечно, в смысле изоморфизма Карри-Ховарда большинство языков программирования противоречивы.

В завершение теоретической части заметим, что в свете BHK-интерпретации в изоморфизме Карри-Ховарда нет
ничего странного: если под конструкцией мы понимаем тип, то любое значение типа --- это метод построения конструкции
(типы, значения которых можно построить, мы будем называть \emph{обитаемыми}), 
а функция --- это способ перестроения одного значения в другое.

Докажите следующие утверждения, написав соответствующую программу:
\begin{enumerate}
\item $A \rightarrow B \rightarrow A$
\item $A \with B \rightarrow A \vee B$
\item $(A \with (B \vee C)) \rightarrow ((A \with B) \vee (A \with C))$
\item $(A \rightarrow C) \with (B \rightarrow C) \with A \vee B \rightarrow C$
\item $(B \vee C \rightarrow A) \rightarrow (B \rightarrow A) \with (C \rightarrow A)$
\item $(A \rightarrow B) \rightarrow (\neg B \rightarrow \neg A)$
\item $((A \rightarrow B) \rightarrow C) \rightarrow (A \rightarrow (B \rightarrow C))$
\item $(A \rightarrow B) \with (A \rightarrow \neg B) \rightarrow \neg A$
\item Выразимые в интуиционистском исчислении высказываний аналоги правил де Моргана для импликации.
\item $\bot$
\end{enumerate}
\end{enumerate}

\section*{Задание №3. Топология, решётки.}

\begin{enumerate}
\item Напомним определения: \emph{замкнутое} множество --- такое, дополнение которого открыто.
\emph{Внутренностью} множества $A^\circ$ назовём наибольшее открытое множество, содержащееся в $A$.
\emph{Замыканием} множества $\overline{A}$ назовём наименьшее замкнутое множество, содержащее $A$.
Назовём \emph{окрестностью} точки $x$ такое открытое множество $V$, что $x \in V$.
Будем говорить, что точка $x \in A$ \emph{внутренняя}, если существует окрестность $V$, что $V \subseteq A$.
Точка $x$ --- \emph{граничная}, если любая её окрестность $V$ пересекается как с $A$, так и с его дополнением.
\begin{enumerate}
\item Покажите, что $A$ открыто тогда и только тогда, когда все точки $A$ --- внутренние.
Также покажите, что $A^\circ = \{ x|x \in A \with x\text{ --- внутренняя точка}\}$.
\item Покажите, что $A$ замкнуто тогда и только когда, когда содержит все свои граничные точки.
Также покажите, что $\overline{A} = \{ x\ |\ x\text{ --- внутренняя или граничная точка}\}$.
Верно ли, что $\overline{A} = X \setminus ((X\setminus A)^\circ)$?
\item Введём топологию на деревьях способом, рассмотренным на лекции. Рассмотрим некоторое множество
вершин $V$. Опишите множества $V^\circ$ и $\overline{V}$. Какие вершины будут являться граничными для $V$?
\item Пусть $A \subseteq B$. Как связаны $A^\circ$ и $B^\circ$, а также $\overline{A}$ и $\overline{B}$?
\item Верно ли $(A \cap B)^\circ = A^\circ \cap B^\circ$ и $(A \cup B)^\circ = A^\circ \cup B^\circ$?
\item Покажите, что $\overline{\left(\overline{A^\circ}\right)^\circ} = \overline{A^\circ}$.
\item \emph{Задача Куратовского.} Будем применять операции взятия внутренности и замыкания к некоторому множеству
всевозможными способами. Сколько различных множеств может всего получиться?
\end{enumerate}


\item Напомним, что евклидовой топологией называется топология на $\mathbb{R}$ с базой $\mathcal{B} = \{ (a,b)\ |\ a,b \in \mathbb{R} \}$.
\begin{enumerate}
\item Связны ли $\mathbb{Q}$ и $\mathbb{R}\setminus\mathbb{Q}$ как топологические подпространства $\mathbb{R}$?
\item Связен ли интервал $(0,1)$?
%\item Если для некоторой функции каждый прообраз открытого множества открыт, то такая функция называется \emph{непрерывной}.
%Покажите, что в эвклидовой топологии функция $f : \mathbb{R} \rightarrow \mathbb{R}$ непрерывна тогда и только тогда,
%когда $\forall x_0 \in \mathbb{R}.\forall \varepsilon > 0. \exists \delta > 0. \forall x \in \mathbb{R}.|x - x_0| < \delta \rightarrow |f(x) - f(x_0)| < \varepsilon$.
\end{enumerate}

\item Примеры топологий.
Для каждого из примеров ниже проверьте, задано ли в нём топологическое пространство, и ответьте на следующие вопросы, если это так:
каковы окрестности точек в данной топологии;
каковы замкнутые множества в данной топологии;
связно ли данное пространство.

\begin{enumerate}
\item Топология Зарисского на $\mathbb{R}$: 
$\Omega = \{\varnothing\} \cup \{ X \subseteq \mathbb{R}\ |\ \mathbb{R} \setminus X\ \text{конечно} \}$,
то есть пустое множество и все множества с конечным дополнением.
\item Топология стрелки на $\mathbb{R}$:
$\Omega = \{\varnothing, \mathbb{R}\} \cup \{ (x,+\infty) | x \in \mathbb{R} \}$, то есть пустое, 
всё пространство и все открытые лучи.
\item Множество всех бесконечных подмножеств $\mathbb{R}$:
$\Omega = \{\varnothing\} \cup \{ X \subseteq \mathbb{R}\ |\ X\ \text{бесконечно} \}$
\item Множество всевозможных объединений арифметических прогрессий:
$A(a) = \{ a\cdot x\ |\ x \in \mathbb{Z}\}$;
$X \in \Omega$, если $X=\varnothing$ или $X = \bigcup_i A(a_i)$ (все $a_i > 0$).
\end{enumerate}

\item Непрерывной функцией называется такая, для которой прообраз открытого множества всегда открыт.
Путём на топологическом пространстве $X$ назовём непрерывное отображение вещественного отрезка $[0,1]$ в $X$.
Опишите пути (то есть, опишите, какие функции могли бы являться путями):
\begin{enumerate}
\item на $\mathbb{N}$ (с дискретной топологией);
\item в топологии Зарисского;
\item на дереве (с топологией с лекции);
\end{enumerate}

\item Связным множеством в топологическом пространстве назовём такое, которое связно как подпространство.
Линейно связным множеством назовём такое, в котором две произвольные точки могут быть соединены путём,
образ которого целиком лежит в множестве. 
\begin{enumerate}
\item Покажите, что линейно связное множество всегда связно;
\item Покажите, что связное не обязательно линейно связное.
\end{enumerate}

\item Всегда ли непрерывным образом связного пространства является другое связное (под)пространство? Докажите или опровергните.

\item Рассмотрим подмножество частично упорядоченного множества, и рассмотрим следующие свойства:
(а) наличие наибольшего элемента; (б) наличие супремума;
(в) наличие единственного максимального элемента. Всего можно рассмотреть шесть утверждений ((а) влечёт (б), 
(а) влечёт (в), и т.п.) --- про каждое определите, выполнено ли оно в общем случае,
и приведите либо доказательство, либо контрпример. Задача состоит из одного пункта, для получения баллов 
все шесть утверждений должны быть разобраны.


\item Покажите следующие утверждения для импликативных решёток:
\begin{enumerate}
\item монотонность: пусть $a \preceq b$ и $c \preceq d$, тогда $a + c \preceq b + d$ и $a \cdot c \preceq b \cdot d$;
\item \emph{законы поглощения:} $a \cdot (a + b) = a$; $a + (a \cdot b) = a$;
\item $a \preceq b$ выполнено тогда и только тогда, когда $a \rightarrow b = 1$;
\item из $a \preceq b$ следует $b\rightarrow c \preceq a\rightarrow c$ и $c\rightarrow a \preceq c \rightarrow b$;
\item из $a \preceq b \rightarrow c$ следует $a \cdot b \preceq c$;
\item $b \preceq a \rightarrow b$ и $a \rightarrow (b \rightarrow a) = 1$;
\item $a \rightarrow b \preceq ((a \rightarrow (b \rightarrow c)) \rightarrow (a \rightarrow c))$;
\item $a \preceq b \rightarrow a \cdot b$ и $a \rightarrow (b \rightarrow (a \cdot b)) = 1$
\item $a \rightarrow c \preceq (b \rightarrow c) \rightarrow (a + b \rightarrow c)$
\item импликативная решётка дистрибутивна: $(a + b) \cdot c = (a \cdot c) + (b \cdot c)$
\end{enumerate}

\item Докажите, основываясь на формулах предыдущих заданий, что интуиционистское исчисление высказываний
корректно, если в качестве модели выбрать алгебру Гейтинга.

\item Покажите, что на конечном множестве дистрибутивная решётка всегда импликативна.
\item Постройте пример дистрибутивной, но не импликативной решётки.
\item Покажите, что в дистрибутивной решётке всегда $a + (b \cdot c) = (a + b) \cdot (a + c)$.

\item Покажите, что $(\preceq)$ --- отношение предпорядка, а $(\approx)$ --- отношение эквивалентности.
\item Покажите, что $[\alpha]_\mathcal{L} + [\beta]_\mathcal{L} = [\alpha\vee\beta]_\mathcal{L}$.
Зависит ли результат от выбора представителей классов эквивалентности $[\alpha]$ и $[\beta]$? Ответ также докажите.
\item Покажите, что $[\alpha\rightarrow\beta]_\mathcal{L}$ --- псевдодополнение $[\alpha]_\mathcal{L}$ до $[\beta]_\mathcal{L}$.
\end{enumerate}

\section*{Задание №4. Модели Крипке. Естественный вывод.}

\begin{enumerate}
\item Опровергните формулы, построив соответствующие модели Крипке:

\begin{enumerate}
\item $\neg\neg A \rightarrow A$
\item $((A \rightarrow B) \rightarrow A) \rightarrow A$
\item $(A \rightarrow B \vee \neg B) \vee (\neg A \rightarrow B \vee \neg B)$
\item $\bigvee_{i=0,n-1} A_i \rightarrow A_{(i+1) \% n}$
\end{enumerate}

\item Покажите, что любая модель Крипке обладает свойством: для любых $W_i, W_j, \alpha$, 
если $W_i \preceq W_j$ и $W_i \Vdash \alpha$, то $W_j \Vdash \alpha$.

\item Несколько задач на упрощение структуры миров моделей Крипке.
\begin{enumerate}
\item Покажите, что формула опровергается моделью Крипке тогда и только тогда, когда она
опровергается древовидной моделью Крипке.

\item Верно ли, что если формула опровергается некоторой древовидной моделью Крипке (причём
у каждой вершины не больше двух сыновей), то эту 
древовидную модель можно достроить до полного бинарного дерева, с сохранением свойства опровержимости?

\item Верно ли, что если некоторая модель Крипке опровергает некоторую формулу,
то добавление любого мира к модели в качестве потомка к любому из узлов оставит опровержение в силе?
\end{enumerate}

\item Постройте опровержимую в ИИВ формулу, которая не может быть опровергнута моделью Крипке (ответ требуется доказать):
\begin{enumerate}
\item глубины 2 и меньше;
\item глубины $n \in \mathbb{N}$ и меньше.
\end{enumerate}

\item Покажите аналог теоремы о дедукции для естественного вывода: $\Gamma,\alpha\vdash\beta$ тогда и только тогда, когда
$\Gamma\vdash\alpha\rightarrow\beta$.


\item Определим отображение между языками вывода (гильбертов и естественный вывод): 

\begin{tabular}{ll}
$|\varphi|_\text{е}=\left\{\begin{array}{ll} |\alpha|_\text{е}\star|\beta|_\text{е}, & \varphi = \alpha\star\beta\\
                                              |\alpha|_\text{е}\rightarrow\bot, & \varphi = \neg\alpha\\
                                              X, & \varphi = X\end{array}\right.$
&
$|\varphi|_\text{г}=\left\{\begin{array}{ll} |\alpha|_\text{г}\star|\beta|_\text{г}, & \varphi = \alpha\star\beta\\
                                              A\with\neg A, & \varphi = \bot\\
                                              X, & \varphi = X\end{array}\right.$
\end{tabular}

\begin{enumerate}
\item Покажите, что $\vdash_\text{е}\alpha$ влечёт $\vdash_\text{г}|\alpha|_\text{г}$;
\item Покажите, что $\vdash_\text{г}\alpha$ влечёт $\vdash_\text{е}|\alpha|_\text{е}$.
\end{enumerate} 

\item Классическое исчисление высказываний также можно сформулировать в стиле естественного вывода, заменив правило исключения лжи на такое:
$$\infer[(\text{удал}\neg\neg)]{\Gamma\vdash\varphi}{\Gamma,\varphi\rightarrow\bot\vdash\bot}$$

В этом задании будем обозначать через $\Gamma\vdash_\text{к}\varphi$ тот факт, что формула $\varphi$ выводится из контекста
$\Gamma$ в классическом И.В. в варианте естественного вывода.

\begin{enumerate}
\item Покажите, что если $\vdash_\text{к}\varphi$ и $A_1, \dots, A_n$ --- все
пропозициональные переменные из $\varphi$, то\\$\vdash_\text{е} A_1 \vee \neg A_1 \rightarrow A_2 \vee \neg A_2 \rightarrow \dots \rightarrow A_n \vee \neg A_n \rightarrow \varphi$.

\item Покажите теорему Гливенко: если $\vdash_\text{к} \varphi$, то $\vdash_\text{е} \neg\neg\varphi$.
\end{enumerate}

\end{enumerate}

\section*{Задание №5. Исчисление предикатов}

\begin{enumerate}
\item Докажите (или опровергните) следующие формулы в исчислении предикатов:
\begin{enumerate}
\item $(\forall x.\phi)\rightarrow (\forall y.\phi[x := y])$, если есть свобода для подстановки $y$ вместо $x$ в $\phi$ и $y$ не входит свободно в $\phi$.
\item $(\exists x.\phi)\rightarrow (\exists y.\phi[x := y])$, если есть свобода для подстановки $y$ вместо $x$ в $\phi$ и $y$ не входит свободно в $\phi$.
\item $(\forall x.\phi)\rightarrow (\exists x.\phi)$
\item $(\forall x.\forall x.\phi) \rightarrow (\forall x.\phi)$
\item $(\forall x.\phi) \rightarrow (\neg \exists x.\neg \phi)$ 
\item $(\exists x.\neg\phi) \rightarrow (\neg \forall x.\phi)$
\item $(\forall x.\alpha\vee\beta) \rightarrow (\neg \exists x.\neg \alpha) \with (\neg \exists x.\neg\beta)$
\item $((\forall x.\alpha) \vee (\forall y.\beta)) \rightarrow \forall x.\forall y.\alpha\vee\beta$. Какие условия
надо наложить на переменные и формулы? Приведите контрпримеры, поясняющие необходимость условий.
\item $(\alpha\rightarrow\beta) \rightarrow \forall x.(\alpha\rightarrow\beta)$. Возможно, нужно наложить
какие-то условия на переменные и формулы? Приведите контрпримеры, поясняющие необходимость условий (если 
условия требуются).
\end{enumerate}

\item Опровергните формулы $\phi\rightarrow\forall x.\phi$ и $(\exists x.\phi)\rightarrow (\forall x.\phi)$

\item Докажите или опровергните (каждую формулу в отдельности): $(\forall x.\exists y.\phi) \rightarrow (\exists y.\forall x.\phi)$ и
$(\exists x.\forall y.\phi) \rightarrow (\forall y.\exists x.\phi)$;
\item Докажите или опровергните (каждую формулу в отдельности): $(\forall x.\exists y.\phi) \rightarrow (\exists x.\forall y.\phi)$ и
$(\exists x.\forall y.\phi) \rightarrow (\forall x.\exists y.\phi)$

\item Рассмотрим интуиционистское исчисление предикатов (добавим схемы аксиом и правила вывода с кванторами
поверх интуиционистского исчисления высказываний).
\begin{enumerate}
\item Определим модель для исчисления предикатов. Пусть $\langle X, \Omega\rangle$ --- некоторое топологическое
пространство. Возможно ли рассмотреть $V = \Omega$ (как и в исчислении высказываний),
пропозициональные связки определить аналогично топологической интерпретации И.И.В., 
оценки же кванторов сделать такими:
$$\llbracket \forall x.\varphi \rrbracket = \left(\bigcap_{v \in D} \llbracket \varphi \rrbracket^{x := v}\right)^\circ,\quad
  \llbracket \exists x.\varphi \rrbracket = \bigcup_{v \in D} \llbracket \varphi \rrbracket^{x := v}$$

\item Покажите, что в интуиционистском исчислении предикатов теорема Гливенко не имеет места
(а именно, существует формула $\alpha$, что $\vdash_\text{к}\alpha$, но $\not\vdash_\text{и}\neg\neg\alpha$).
\item Определим операцию $(\cdot)_\text{Ku}$:
$$(\varphi\star\psi)_\text{Ku} = \varphi_\text{Ku} \star \psi_\text{Ku}, \quad 
(\forall x.\varphi)_\text{Ku} = \forall x.\neg\neg\varphi_\text{Ku}, \quad
(\exists x.\varphi)_\text{Ku} = \exists x.\varphi_\text{Ku}$$

Тогда \emph{преобразованием Куроды} формулы $\varphi$ назовём $\neg\neg(\varphi_\text{Ku})$. 
Покажите, что $\vdash_\text{к}\alpha$ тогда и только тогда, когда $\vdash_\text{и}\neg\neg(\alpha_\text{Ku})$.
\end{enumerate}

\item Покажите, что исчисление предикатов не полно в моделях ограниченной конечной мощности. 
А именно, пусть дана модель $\mathcal{M} = \langle D, F, T, E \rangle$. 
Назовём мощностью модели мощность её предметного множества: $|\mathcal{M}| = |D|$.
Покажите, что для любой конечной мощности модели $n\in\mathbb{N}$ найдётся такая формула $\alpha$, что 
при $|\mathcal{M}|\le n$ выполнено $\llbracket\alpha\rrbracket_\mathcal{M} = \text{И}$, но $\not\vdash\alpha$.
\end{enumerate}

\section*{Задание №6. Теорема о полноте исчисления предикатов}

\begin{enumerate}
\item Покажите, что следующие определения противоречивой теории эквивалентны (ваше рассуждение
должно подходить для всех исчислений, которые мы проходили до этого момента --- КИВ, ИИВ, КИП;
задача состоит из одного пункта, для получения баллов все четыре утверждения должны быть разобраны):
(а) существует формула $\alpha$, что $\vdash\alpha\with\neg\alpha$;
(б) существует формула $\alpha$, что $\vdash\alpha$ и $\vdash\neg\alpha$;
(в) $\vdash A \with \neg A$;
(г) любая формула доказуема.

\item Покажите, что если классическое исчисление высказываний противоречиво, то также противоречиво и интуиционистское исчисление высказываний.

\item Покажите, что если $\neg\varphi\vdash\varphi$, то $\vdash\varphi$. Аналогично, покажите, что из $\neg\varphi\vdash\alpha\with\neg\alpha$
следует $\vdash\varphi$. Покажите требуемые утверждения конструктивно, перестроив данные в условии доказательства в доказательство $\varphi$. 

%\item Покажите, что если $\vdash \gamma \rightarrow A \with \neg A$ и $\vdash $, то 

\item Пусть $M$ --- непротиворечивое множество формул и $\mathcal{M}$ --- построенная в соответствии с теоремой о 
полноте исчисления предикатов оценка для $M$. Мы ожидаем, что $\mathcal{M}$ будет моделью для $M$, для чего было необходимо доказать
несколько утверждений. Восполните некоторые пробелы в том доказательстве. А именно, если $\varphi$ --- 
некоторая формула и для любой формулы $\zeta$, более короткой, чем $\varphi$, выполнено
$\mathcal{M}\models\zeta$ тогда и только тогда, когда $\zeta\in M$, тогда покажите:
\begin{enumerate}
\item если $\varphi = \alpha\with\beta$, $\mathcal{M}\models\alpha\with\beta$, то $\alpha\with\beta\in M$; и если $\mathcal{M}\not\models\alpha\with\beta$, то $\alpha\with\beta\notin M$;
\item если $\varphi = \neg\alpha$, $\mathcal{M}\models\neg\alpha$, то $\neg\alpha\in M$; и если $\mathcal{M}\not\models\neg\alpha$, то $\neg\alpha\notin M$.
\end{enumerate}

\item 
Напомним, что \emph{машиной Тьюринга} называется упорядоченная шестёрка $$\langle A_\text{внешн}, A_\text{внутр}, T, \varepsilon, s_\text{нач}, s_\text{доп}\rangle$$
где внешний и внутренний алфавиты конечны и не пересекаются ($A_\text{внешн} \cap A_\text{внутр} = \varnothing$), $\varepsilon \in A_\text{внешн}$, $s_\text{нач}, s_\text{доп} \in A_\text{внутр}$, 
и $T$ --- это функция переходов: $T : A_\text{внутр} \times A_\text{внешн} \rightarrow A_\text{внутр} \times A_\text{внешн} \times \{ \leftarrow, \rightarrow, \cdot \}$.

Все неиспользованные клетки ленты заполнены $\varepsilon$, головка перед запуском стоит на самой левой заполненной клетке.
При работе машина последовательно выполняет переходы и двигает ленту (в соответствии с $T$), пока не окажется в 
допускающем состоянии $s_\text{доп}$ (успешное завершение). Также можно выделить отвергающее состояние $s_\text{отв}$, 
оказавшись в котором, машина оканчивает работу с ошибкой (неуспешное завершение).

Например, пусть $A_\text{внешн} = \{ 0, 1, \varepsilon \}$, $A_\text{внутр} = \{s_s, s_f\}$, $s_\text{нач} = s_s$, $s_\text{доп} = s_f$,
отвергающего состояния не задано, и функция переходов указана в таблице ниже:

\begin{center}\begin{tabular}{c|ccc}
    & $\varepsilon$ & 0 & 1\\\hline
$s_s$ & $\langle s_f,\varepsilon,\cdot\rangle$ & $\langle s_s,1,\rightarrow\rangle$ & $\langle s_s,0,\rightarrow\rangle$\\
$s_f$ & $\langle s_f,\varepsilon,\cdot\rangle$ & $\langle s_f,0,\cdot\rangle$ & $\langle s_f,1,\cdot\rangle$
\end{tabular}\end{center}

Такая машина Тьюринга меняет на ленте все 0 на 1, а все 1 --- на 0. Например, для строки $011$:

$$\underline{0}11 \Rightarrow 1\underline{1}1 \Rightarrow 10\underline{1} \Rightarrow 100\underline{\varepsilon}$$

Заметьте, что на последнем шаге головка сдвинулась вправо, за заполненные клетки --- оказавшись на неиспользованной, заполненной символами $\varepsilon$
части ленты --- и остановилась благодаря 
тому, что $T(s_s, \varepsilon) = \langle s_f, \dots \rangle$.

Напишите следующие программы для машины Тьюринга и продемонстрируйте их работу на каком-нибудь эмуляторе:
\begin{enumerate}
\item разворачивающую строку в алфавите $\{0,1\}$ в обратном порядке (например, из $01110111$ программа должна сделать $11101110$);
в этом и в последующих заданиях в алфавит внешних символов при необходимости можно добавить дополнительные символы;
\item в строке в алфавите $\{0,1,2\}$ сокращающую все <<постоянные>> подстроки до одного символа:
машина должна превратить $1022220101111$ в $1020101$;
\item допускающую правильные скобочные записи (например, $(())$ должно допускаться, а $)()($ --- отвергаться);
\item допускающую строки вида $a^nb^nc^n$ в алфавите $\{a,b,c\}$ (например, строка $aabbcc$ должна допускаться, а $abbbc$ --- отвергаться);
\item допускающую только строки, состоящие из констант и импликаций (алфавит $\{ 0, 1, \rightarrow, (, ) \}$), 
содержащие истинные логические выражения;
например, выражение $(((0 \rightarrow 1) \rightarrow 0) \rightarrow 0)$ машина должна допустить, а
выражение $((1 \rightarrow 1) \rightarrow 0)$ --- отвергнуть. Можно считать, что выражение написано в корректном синтаксисе (все скобки корректно
расставлены, никаких скобок не пропущено).
\end{enumerate}

\item Пусть дано число $k \in \mathbb{N}$. Известно, что если $0 \le k < 2^n$, то возможно закодировать $k$ с помощью $n$ цифр 0 и 1.
А как закодировать число, если мы не знаем верхней границы $n$? Какую лучшую асимптотику длины кодировки относительно $\log_2 k$ вы можете
предложить? Кодировка должна использовать только символы 0 и 1, также код должен быть префиксным (ни один код не является префиксом другого).

\item Как известно, машина Тьюринга может быть проинтерпретирована другой машиной Тьюринга.
Предложите способ закодировать машину Тьюринга в виде текста в алфавите $\{0,1\}$.
Естественно, символы алфавитов при кодировке меняются на их номера, и эти номера надо будет как-то записывать в виде последовательностей цифр 0 и 1.
\end{enumerate}

\section*{Задание №7. Аксиоматика Пеано, формальная арифметика.}
\begin{enumerate}
\item Рассмотрим аксиоматику Пеано. 
Пусть $$a^b = \left\{\begin{array}{ll}1,& b= 0 \\a^c\cdot a,&b = c'\end{array}\right.$$
Докажите, что:
\begin{enumerate}
\item $a \cdot b = b \cdot a$
\item $(a + b) \cdot c = a \cdot c + b \cdot c$
\item $a^{b+c} = a^b \cdot a^c$
\item $(a^b)^c = a^{b \cdot c}$
\end{enumerate}

\item Определим отношение <<меньше или равно>> так: $0 \le a$ и $a' \le b'$, если $a \le b$. Докажите, что:
\begin{enumerate}
\item $x \le x+y$;
\item $x \le x \cdot y$ (укажите, когда это так --- в остальных случаях приведите контрпримеры);
\item Если $a \le b$ и $m \le n$, то $a \cdot m \le b \cdot n$;
\item $x \le y$ тогда и только тогда, когда существует $n$, что $x + n = y$;
\item Будем говорить, что $a$ делится на $b$ с остатком, если существуют такие $p$ и $q$, что 
$a = b \cdot p + q$ и $0 \le q < b$. Покажите, что $p$ и $q$ всегда существуют и единственны,
если $b > 0$.
\end{enumerate}

\item Определим <<ограниченное вычитание>>: $$a \dotminus b = \left\{\begin{array}{ll}0, & a = 0\\a, & b = 0\\p \dotminus q, & a = p', b = q'\end{array}\right.$$
Докажите, что:
\begin{enumerate}
\item $a + b \dotminus b = a$;
\item $(a \dotminus b) \cdot c = a \cdot c \dotminus b \cdot c$;
\item $a \dotminus b \le a + b$;
\item $a \dotminus b = 0$ тогда и только тогда, когда $a \le b$.
\end{enumerate}

\item Обозначим за $\overline{n}$ представление числа $n$ в формальной арифметике: %, по сути это ноль с $n$ штрихами:

$$\overline{n} = \left\{\begin{array}{ll}0, &n = 0\\
           \left(\overline{k}\right)', & n=k+1\end{array}\right.$$

Например, $\overline{5} = 0'''''$. Докажите в формальной арифметике:
\begin{enumerate}
\item $\vdash \overline{2} \cdot \overline{3} = \overline{6}$;
\item $\vdash \forall p.(\exists q.q' = p) \vee p = 0$ (единственность нуля);
\item $\vdash p \cdot q = 0 \rightarrow p = 0 \vee q = 0$ (отсутствие делителей нуля);
\end{enumerate}

\item Будем говорить, что $k$-местное отношение $R$ выразимо в формальной арифметике,
если существует формула формальной арифметики $\rho$ со свободными переменными $x_1, \dots, x_k$, что:
\begin{itemize}
\item для всех $\langle a_1, \dots, a_k \rangle \in R$ выполнено $\vdash\rho[x_1 := \overline{a_1}]\dots[x_k := \overline{a_k}]$
(доказуема формула $\rho$ с подставленными значениями $a_1, \dots, a_k$ вместо свободных переменных $x_1, \dots, x_k$);
\item для всех $\langle a_1, \dots, a_k \rangle \notin R$ выполнено $\vdash\neg\rho[x_1 := \overline{a_1}]\dots[x_k := \overline{a_k}]$.
\end{itemize}

Выразите в формальной арифметике (укажите формулу $\rho$ и докажите требуемые свойства про неё):
\begin{enumerate}
\item <<полное>> отношение $R = \mathbb{N}^2$ (любые два числа состоят в отношении);
\item отношение $(=)$;
\item двуместное отношение <<хотя бы один из аргументов равен 0>>.
\end{enumerate}

\end{enumerate}

\section*{Задание №8. Рекурсивные функции. Выразимость и представимость.}
\begin{enumerate}
\item С использованием эмулятора рекурсивных функций (применённый на лекции синтаксис
подсказывает использование библиотеки на С++, но вы можете выбрать любой другой способ эмуляции),
покажите, что следующие функции примитивно-рекурсивны. Ваше решение должно быть продемонстрировано
в работе на простых примерах. Возможно, при реализации сложных функций вам потребуется 
для ускорения работы заменить базовые функции на <<нативные>> (например, умножение, реализованное
через примитивы, заменить на встроенную операцию) --- это можно делать при условии, что для них у вас есть 
эквивалентная примитивно-рекурсивная реализация.
\begin{enumerate}
\item умножение и ограниченное вычитание;
\item сравнение: $$\textsc{le}(x,y)=\left\{\begin{array}{ll}1,&x \le y\\0,&x > y\end{array}\right.$$
\item факториал;
\item целочисленное деление и остаток от деления;
\item извлечение квадратного корня (на лекции речь шла только о рекурсивности квадратного корня);
\item функции построения упорядоченной пары и взятия её проекций; в решении используйте представление пары натуральных
чисел $\langle a,b\rangle$ через диагональную нумерацию:

\begin{center}\begin{tabular}{r|ccccc}
a\textbackslash{}b & 0 & 1 & 2 & 3 & \dots\\\hline
  0                & 0 & 2 & 5 & 9 \\
  1                & 1 & 4 & 8 & 13  \\
  2                & 3 & 7 & 12 & 18   \\
  3                & 6 & 11 & 17 & 24\\
  \dots
\end{tabular}\end{center}
\item сложение и вычитание целых чисел (в стиле определения целых чисел через упорядоченную пару), также добавьте
функцию нормализации (назовём целое число $\langle p,q\rangle$ записанным в нормальном виде, если $p \cdot q = 0$);
\item вычисление $n$-го простого числа (напомним теорему Бертрана-Чебышёва: для любого натурального $n \ge 2$ найдётся
простое число между $n$ и $2n$);
\item частичный логарифм $\textsc{plog}_n(k) = \max\{p\ |\ k\ \raisebox{-0.5ex}{\vdots}\ n^p\}$ (например, $\textsc{plog}_2(96)=5$);
\item вычисление длины списка в гёделевой нумерации (например, $\textsc{len}(3796875000) = \textsc{len}(2^3\cdot 3^5\cdot 5^9) = 3$);
\item выделение подсписка из списка (например, $\textsc{sublist}(2^2 \cdot 3^3 \cdot 5^4 \cdot 7^5, 2, 2) = 2^4 \cdot 3^5$);
\item склейка двух списков в гёделевой нумерации (например, $\textsc{append}(2^3 \cdot 3^5,2^7 \cdot 3^6) = 2^3 \cdot 3^5 \cdot 5^7 \cdot 7^6$).
\item проверка парности скобок: дана строка из скобок в гёделевой нумерацией, верните 1, если скобки парные и 0 иначе (например, 
$\textsc{ispaired}(2^{\ulcorner ( \urcorner} \cdot 3^{\ulcorner ( \urcorner} \cdot 5^{\ulcorner ) \urcorner}) = 0$,
но $\textsc{ispaired}(1944) = 1$)
\end{enumerate}

\item С использованием эмулятора рекурсивных функций покажите, что функция Аккермана --- рекурсивная.

\item Пусть $n$-местное отношение $R$ выразимо в формальной арифметике. Покажите, что
тогда его характеристическая функция $C_R$ представима в формальной арифметике:
$$C_R(\overrightarrow{x}) = \left\{\begin{array}{ll}1,& \overrightarrow{x}\in R\\0, &\text{иначе}\end{array}\right.$$

\item Покажите, что в определении представимости пункт
$\vdash\neg\varphi(\overline{x_1},\dots,\overline{x_n},\overline{y})$ при $f(x_1,\dots,x_n) \ne y$ не является
обязательным и может быть доказан из остальных пунктов определения представимой функции.

\item Покажите, что функция $f(x) = x+2$ представима в формальной арифметике (в ответе также требуется привести все пропущенные
на лекции выводы в формальной арифметике).
\end{enumerate}

\section*{Задание №9. Теоремы о неполноте арифметики.}
\begin{enumerate}
\item Покажите, что омега-непротиворечивая теория непротиворечива.
\item Предложите пример омега-противоречивой теории, являющейся расширением формальной арифметики.
\item Пусть $\zeta_\varphi(x) := \forall z.\sigma (x,x,z) \rightarrow \varphi(z)$,
где формула $\sigma(p,q,r)$ представляет функцию $\textsc{SUBST}(p,q)$, заменяющую в формуле с гёделевым номером $p$
все свободные переменные $x_1$ на формулу $q$. Тогда покажите, что формулу $\alpha_\varphi := \zeta_\varphi(\overline{\ulcorner\zeta_\varphi\urcorner})$
можно взять в качестве формулы $\alpha$ в лемме об автоссылках: $\vdash \varphi(\overline{\ulcorner\alpha_\varphi\urcorner}) \leftrightarrow \alpha_\varphi$.

\item Какое из условий Гильберта-Бернайса-Лёфа нарушает формула $\pi'$?
\item Покажите, что вопрос о принадлежности формулы $\alpha(x) = \forall p.\delta(x,p) \rightarrow \neg \sigma(p)$ в доказательстве 
теоремы о невыразимости доказуемости к множеству $Th_\mathcal{S}$ ведёт к противоречию.
\item Покажите, что формула $D(x)$ из доказательства теоремы о невыразимости доказуемости является представимой в формальной арифметике.
\end{enumerate}

\section*{Задание №10. Теория множеств.}
\begin{enumerate}
\item Пусть заданы списки (в любом языке программирования) $L(\alpha)$, хранящие значения типа $\alpha$.
Реализуйте следующие функции, являющиеся аналогами конструктивных аксиом теории множеств:
\begin{itemize}
\item $\texttt{empty}: L(\alpha)$, строит пустой список.
\item $\texttt{pair}: (\alpha, \alpha) \rightarrow L(\alpha)$, формирует список из двух своих аргументов.
\item $\texttt{flatten}: L(L(\alpha)) \rightarrow L(\alpha)$, соединяет все списки внутри списка в один.
\item $\texttt{powerset}: L(\alpha) \rightarrow L(L(\alpha))$, делает из списка список всех возможных подсписков.
\item $\texttt{filter}: (\alpha \rightarrow \texttt{bool}) \rightarrow L(\alpha) \rightarrow L(\alpha)$,
выделяет из списка все элементы, соответствующие условию.
\end{itemize}
Данное задание не разбивается на пункты.
\item Определим упорядоченную пару $\langle a,b\rangle := \{\{a\},\{a,b\}\}$. Покажите, что
$\langle a,b \rangle = \langle c,d\rangle$ тогда и только тогда, когда $a = c$ и $b = d$.
\item Докажите, что следующие конструкции являются множествами, также предложите их реализацию в смысле п.1: 
\begin{enumerate}
\item пересечение всех элементов множества ($\bigcap a$);
\item $a\ \setminus\ b$ (разность множеств);
\item $a \uplus b$ (дизъюнктное объединение множеств: $\{\langle x,0\rangle\mid x\in a\}\cup\{\langle x,1\rangle\mid x\in b\}$);
\item $a \times b$ (декартово произведение множеств: $\{\langle p,q\rangle\ |\ p\in a, q\in b\}$).
\end{enumerate}
\item Определите формулу $\varphi(x)$ для свойства <<$x$ --- конечный ординал>>. Укажите замкнутый
вид для формулы, задающей ординал $\omega$.
\item Покажите, что если $x$ --- ординал, то $x'$ --- тоже ординал.
\item Верно ли, что если $x'$ --- ординал, то $x$ --- тоже ординал?
\item Покажите, что на множестве $\omega$ выполняется аксиоматика Пеано (полная формализация рассуждений не требуется,
но из изложения должно быть понятно, как эту формализацию в рамках теории первого порядка получить):
\begin{enumerate}
\item $\forall x.x \in \omega \rightarrow \neg x' = \varnothing$
\item $\forall x.\forall y.x \in \omega \with y \in \omega \rightarrow x' = y' \rightarrow x = y$
\item (\emph{указание к следующему пункту}) покажите, что если $\vdash\forall x.\neg\phi(x)\rightarrow A\with\neg A$, то $\vdash\forall x.\phi(x)$.
\item Если $\phi(\varnothing)$ и $\forall x.x \in \omega \rightarrow \phi(x) \rightarrow \phi(x')$, 
то $\forall x.x \in \omega \rightarrow \phi(x)$.
\end{enumerate}
\item Проверьте следующие равенства (докажите или опровергните):
\begin{enumerate}
\item $\omega\cdot\overline{2} = \overline{2}\cdot\omega$
\item $\omega\cdot\overline{2} = \omega + \omega$
\item $(\omega+\overline{1})^{\overline{2}} = \omega^{\overline{2}} + \overline{2}\cdot \omega + \overline{1}$
\item $\omega ^ \omega = (\omega ^ {\overline{2}}) ^ \omega$
\item $\omega ^ {\omega + \overline{1}} = \omega ^ \omega + \overline{1}$
\item Имеет ли место ассоциативность сложения и/или умножения?
\end{enumerate}
\item Верно ли, что $1^\omega = \omega$ и/или $\omega^1 = \omega$?
\item Зачёт за пункт ставится, если одновременно решены два подпункта:
(i) Покажите, что множество $\omega^\omega$ имеет счётную мощность. 
(ii) Определим $\uparrow k$ (башню из омег) так:

$$\uparrow k = \left\{\begin{array}{ll}\omega,&k = 1\\\omega^{\uparrow n},&k = n'\end{array}\right.$$

Скажем, $\uparrow 3 = \omega^{\left(\omega^\omega\right)}$. Будет ли счётным ординал $\sup\{\uparrow k\ |\ k \in \omega\}$?
\item Существует ли ординал, которому соответствует множество неотрицательных рациональных чисел и упорядоченность на нём?
То есть, существует ли ординал $\sigma$, что существует биекция $f: \mathbb{Q^+} \rightarrow \sigma$, причём
для всех $a,b \in \mathbb{Q^+}$ из $a \le b$ следует $f(a) \le f(b)$ (и обратно).
\end{enumerate}

\section*{Задание №11. Порядок и мощность.}

\begin{enumerate}
\item Покажем, что оба условия в определении ординала существенны: предъявите примеры вполне упорядоченного отношением $(\in)$ и не транзитивного множества, а также транзитивного и не
вполне упорядоченного отношением $(\in)$ множества.
\item Покажите, что аксиома фундированности запрещает существование множества $x$, что $x \in x$. 
Указание: рассмотрите множество $\{x\}$.
\item Покажите  $\vdash \{a\} = \{b\}\rightarrow a=b$.
Доказательство может использовать метаязык, но должно показывать существование
вывода в предметном языке.
\item Верно ли, что для любого отношения полного порядка на счётном множестве существует соответствующий ему ординал,
имеющий тот же порядок?
\item Покажите следующее (обозначим за $\mathcal{F}(p,q)$ множество функций из $p$ в $q$):
\begin{enumerate}
\item $|a|=0$ тогда и только тогда, когда $a = \varnothing$;
\item если $|a|\le|b|$, то $|\mathcal{F}(g,a)| \le |\mathcal{F}(g,b)|$;
\item если $|a|\le|b|$ и $\overline{0}<|g|$, то $|\mathcal{F}(a,g)| \le |\mathcal{F}(b,g)|$;
\item $|\mathcal{F}(\overline{0},a)| = \overline{1}$, $|\mathcal{F}(\overline{1},a)| = \overline{1}$; если $|a| > 0$, то $|\mathcal{F}(a,\overline{0})| = \overline{0}$;
\item если $|a|\ge\aleph_0$ и $0 < |n| < \aleph_0$, то $|\mathcal{F}(a,n)| = a$.
\end{enumerate}
\item Покажите эквивалентность следующих определений конечного множества (задание $(k)$ предполагает доказательство
импликации $(k)\rightarrow(k')$; возможно, некоторые из переходов потребуют аксиому выбора):
\begin{enumerate}
\item $a$ конечно, если каждое непустое семейство подмножеств $a$ имеет максимальный по включению элемент.
Например, при $a = \{0,1,2\}$ в семействе подмножеств $\{\varnothing,\{0,1\},\{1,2\}\}$ элементы $\{0,1\}$ и $\{1,2\}$ --- максимальны.
\item $a$ конечно, если $\mathcal{P}(a)$ не равномощно своему собственному подмножеству (собственное подмножество --- подмножество, не совпадающее с множеством).
\item $a$ конечно, если оно не равномощно своему собственному подмножеству.
\item $a$ конечно, если $|a|=\varnothing$ или $|a|\cdot\overline{2} > |a|$.
\item $a$ конечно, если $|a|=\varnothing$ или $|a|=\overline{1}$ или $|a|^2 > |a|$.
\item $a$ конечно, если $|a|<\aleph_0$.
\end{enumerate}
\item Покажите, что представимая функция $f: a \rightarrow b$ биективна (т.е. инъективна и сюръективна) тогда и только тогда,
когда $\forall y.\exists!x.\phi(x,y)$. Здесь за $\phi(x,y)$ мы обозначаем формулу, представляющую функцию $f$
в теории множеств, по аналогии с формальной арифметикой.
\item Покажите, что если $a$ и $b$ --- непустые множества, то существует функция из $a$ в $b$ 
(однако функция не обязана быть инъективной или сюръективной).
\item Пусть множество $a$ вполне упорядоченное. Назовём множество $\{ x\in a \mid x < y\}$, где $y\in a$, начальным отрезком $a$. 
Рассмотрим произвольную пару вполне упорядоченных множеств $a$ и $b$.
Покажите, что либо между $a$ и $b$ есть биекция, сохраняющая порядок (такая, что $x < y$ влечёт $f(x) < f(y)$), 
либо есть инъективное отображение из одного множества в начальный отрезок другого, также сохраняющее порядок.
\item Покажите, что $|\{ f \ |\ f: \mathbb{R}\rightarrow\mathbb{R}, f\text{ --- непрерывна } \}| = \beth_1$ 
и $|\{ f \ |\ f: \mathbb{R}\rightarrow\mathbb{R} \}| = \beth_2$.
\item Покажите, что $|\mathbb{R}| =\beth_1$,
также найдите $|\{ f \ |\ f: \mathbb{Q}\rightarrow\mathbb{R}, f\text{ --- непрерывна } \}|$ и 
$|\{ f \ |\ f: \mathbb{R}\rightarrow\mathbb{Q}, f\text{ --- непрерывна } \}|$. 
\end{enumerate}

\end{document}