lection13.tex

\section{Теория множеств.}

Теория множеств --- это еще одна теория первого порядка, с которой
мы познакомимся в этом курсе.
Мы добавим к исчислению предикатов один новый двуместный предикат --- отношение 
принадлежности $\in$. 

Для изучения теории множеств мы введем несколько сокращений записи.
Первое сокращение --- это новая логическая связка \emph{эквивалентность}. 

\begin{definition}{Эквивалентность.}
Запись $a \leftrightarrow b$ является сокращением записи для 
$ \equiv ( a \rightarrow b) \with (b \rightarrow a)$.
\end{definition}

\begin{definition}Будем говорить, что множество $x$ является подмножеством
множества $y$, если любой элемент $x$ принадлежит $y$. 
Формально: $x \subseteq y$ является сокращением записи для
$\forall z (z \in x \rightarrow z \in y)$.
\end{definition}

\begin{definition}{Принцип объемности.}
Два множества называются равными, если они являются подмножествами друг друга. Формально:
$x = y$ является сокращением записи для $x \subseteq y \with y \subseteq x$.
\end{definition}

\begin{definition}{Принцип Лейбница (неразличимость).}
Два множества называются равными, если для любого предиката $P$ $P(A) \leftrightarrow P(B)$.
\end{definition}

\begin{axiom}{Аксиома равенства.}
Равные множества содержатся в одних и тех же множествах. 
$\forall x \forall y \forall z (x = y \with x \in z \rightarrow y \in z)$.
\end{axiom}

\begin{axiom}{Аксиома пары.}
Каковы бы ни были два различных множества $x$ и $y$, существует множество, состоящее 
в точности из них. Будем записывать его так: $\{x,y\}$.
Формально: 
$\forall x \forall y (\neg x=y \rightarrow \exists p (x \in p \with y \in p \with \forall z (z \in p \rightarrow (z = x \vee z = y))))$.
\end{axiom}

\begin{axiom}{Аксиома объединения.}
Для любого множества $x$, содержащего хотя бы один элемент, найдется такое множество, которое состоит в точности
из тех элементов, из которых состоят элементы $x$. Будем записывать его так: $\cup x$.
Формально: $\forall x (\exists y y \in x \rightarrow \exists p \forall y (y \in p \leftrightarrow \exists s (y \in s \with s \in x)))$
\end{axiom}

\begin{axiom}{Аксиома степени.}
Каково бы ни было множество $x$, существует множество $2^x$, содержащее в точности
все возможные подмножества множества $x$.
Формально: $\forall x \exists p \forall y (y \in p \leftrightarrow y \subseteq x)$.
\end{axiom}

\begin{axiom}{Схема аксиом выделения.}
Для любого множества $x$ и любой формулы от одного аргумента $\phi(y)$, такой, что
$b$ в нее не входит свободно, найдется такое множество $b$, в которое
входят те и только те элементы из множества $x$, что $\phi(y)$ истинно.
Формально: $\forall x \exists b \forall y (y \in b \leftrightarrow (y \in x \with \phi(y)))$
\end{axiom}

\begin{definition}Пересечением множеств $x$ и $y$ называется множество, состоящее
в точности из тех элементов, которые присутствуют и в $x$ и в $y$. Формально:
$x \cap y$ --- это такое множество $z$, что $\forall t (t \in z \leftrightarrow t \in x \with t \in y)$
\end{definition}

\begin{definition}Пустое множество $\emptyset$ --- множество, которому не принадлежит
никакой элемент: $\forall x \neg x \in \emptyset$.
\end{definition}

\begin{theorem}\begin{enumerate}
\item Для любого множества $X$ существует множество $\{X\}$, содержащее в точности $X$.
\item Если существует хотя бы одно множество, то существует пустое множество.
\item Пустое множество единственно.
\item Для двух множеств существует множество, являющееся их пересечением.
\end{enumerate}\end{theorem}

\begin{definition}Дизъюнктным (разделённым) множеством называется множество, элементы которого
не пересекаются. Формально:
$$Dj(x) \equiv \forall y \forall z ((y \in x \with z \in x \with \neg y=z) \rightarrow 
\neg \exists t (t \in y \with t \in z))$$
\end{definition}

\begin{definition}Прямым произведением дизъюнктного множества $a$ называется 
множество $\times a$ всех таких множеств $b$, что:
\begin{itemize}
\item $b$ пересекается с каждым из элементов множества $a$ в точности в одном элементе
\item $b$ содержит элементы только из $\cup a$.
\end{itemize}

Формально:
$$\forall b (b \in \times a \leftrightarrow (b \subseteq \cup a \with \forall y (y \in a \rightarrow \exists ! x (x \in y \with x \in b))))$$
\end{definition}

Заметим, что прямое произведение дизъюнктного множества
существует по аксиоме выделения, поскольку $\times a \subseteq \cup a$.

\begin{axiom}{Аксиома выбора.}
Прямое произведение непустого дизъюнктного множества, 
не содержащего пустых элементов, непусто.
Формально: 

$$\forall t (Dj (t) \rightarrow 
\forall x (x \in t \rightarrow \exists p (p \in x)) \rightarrow
\exists p (p \in \times t))$$
\end{axiom}

\begin{axiom}{Аксиома бесконечности.}
Существует множество N, такое, что:
$$\emptyset \in N \with \forall x(x \in N \rightarrow x\cup\{x\} \in N)$$
\end{axiom}

\begin{axiom}{Аксиома фундирования.}
В каждом непустом множестве найдется элемент, не пересекающийся с исходным множеством.
$$\forall x (x = \emptyset \vee \exists y (y \in x \with y \cap x = \emptyset))$$
\end{axiom}

Аксиома фундирования исключает множества, которые могут принадлежать 
сами себе (возможно, через цепочку принадлежностей):
$X \in Y \in Z \in X$

\begin{definition}{Упорядоченная пара.}
Упорядоченной парой двух множеств $a$ и $b$ назовем множество
$\{a,\{a,b\}\}$, еще будем записывать его так: $\langle{}a,b\rangle$
\end{definition}

\begin{lemma}
Упорядоченную пару можно построить для любых множеств, также 
$\langle{}a,b\rangle = \langle{}c,d\rangle$ тогда и только тогда,
когда $a = b$ и $c = d$.
\end{lemma}

\begin{axiom}{Схема аксиом подстановки.}
Если задана некоторая функция f, представимая в исчислении предикатов
(то есть задана некоторая формула $\phi$, такая, что $f(x) = y$
тогда и только тогда, когда $\phi(x,y) \with \exists ! z \phi(x,z)$),
то для любого множества S существует множество f(S) --- образ
множества S при отображении f.

Формально: 
$$\forall s (\forall x \forall y_1 \forall y_2 (x \in s \with \phi (x,y_1) \with \phi
(x,y_2) \rightarrow y_1=y_2) \rightarrow 
\exists t \forall y (y \in t 
\leftrightarrow \exists x (x \in s \with \phi (x,y)))) $$
\end{axiom}

Через данную аксиому легко выразить аксиому выделения,
%пусть дан предикат $P$ и множество $X$. Тогда зададим функцию
%$$f(x) = \left\{\begin{array}{rl}
%   \{x\}, & \mbox{если $P(x)$}\\
%   \emptyset, & \mbox{если $\neg P(x).$}
%\end{array}\right.
%$$
%Нетрудно видеть, что объединением образа множества X будет множество,
%получаемое по аксиоме выделения из предиката $P(x)$:
%$\cup f(X) = \{x \mid x \in X \with P(x)\}$.
%
однако аксиома подстановки не может быть сведена к аксиоме выделения.

Данная аксиома позволяет строить множества большой и очень большой мощности:
допустим, если при $D(m)=2^m$ положить $f(x) = D^x(\omega)$ 
(то есть $f(1) = 2^\omega$, $f(2) = 2^{2^\omega}$, $\dots$), 
то мощность $\cup f(\omega)$ будет больше мощности
любого кардинального числа с конечным номером.
Впрочем, эта аксиома нужна даже для доказательства
существования $2 \cdot \omega$: аксиома бесконечности гарантирует
существование только $\omega$.

\begin{definition}{Бинарное отношение.}
Бинарным отношением на множестве $X$ назовем подмножество множества
всех упорядоченных пар элементов из $X$.
\end{definition}

На бинарных отношениях естественным образом вводятся отношения 
рефлексивности, симметричности и транзитивности.

\begin{definition}{Упорядочивание.}
Отношение $R$ на множестве $S$ упорядочивает $X$, если это отношение
транзитивно и оно образует линейный порядок 
(строгое неравенство: справедливо
$\forall x \forall y (x \in X \rightarrow y \in X \rightarrow R(x,y) \vee x =
y \vee R(y,x))$ и
$\forall x \neg R(x,x)$).
Отношение вполне упорядочивает $S$, если к тому же для любого 
непустого подмножества $S$ выполнено 
$\exists x (x \in B \with \forall y (y \in B \rightarrow \neg R(y,x)))$.
\end{definition}

Также можно ввести понятие максимума, минимума, верхней грани, супремума.

\begin{definition}
Множество $x$ - транзитивное, если $z \in y, y \in x \rightarrow z \in x$.
\end{definition}

\begin{definition}
Ординал (порядковое число) --- транзитивное, вполне упорядоченное с 
помощью отношения $(\in)$ множество.
\end{definition}

Ординалы --- это некоторое обобщение понятия натурального числа.
Для натуральных чисел есть прямой аналог:
$0 \coloneqq  \emptyset$; $1 \coloneqq  \{\emptyset\}$; $2 \coloneqq  1 \cup \{1\}$ и т.п.
Существование каждого из этих ординалов легко доказать.

\begin{definition}Ординал $x$ называется \emph{предельным}, если 
$\neg x = \emptyset \with \neg \exists y (y \cup \{y\} = x)$.
\end{definition}

\begin{definition}Ординал $x$ называется \emph{конечным}, если
он меньше любого предельного ординала. То есть он не содержит
ни одного предельного:
$\neg\exists t (t \in x \with \neg \exists y (y \cup \{y\} = t))$
\end{definition}

\begin{definition}Ординал $\omega$ --- это минимальный
предельный ординал.
\end{definition}

Ясно, что любое натуральное число меньше, чем $\omega$. 

\begin{theorem}Ординал $\omega$ существует.
\end{theorem}
\begin{proof}
Рассмотрим множество $N$, существование которого гарантирует аксиома 
бесконечности. Заметим, что в этом множестве содержатся все конечные ординалы: 
$\emptyset, \{\emptyset\}, \dots$ (это можно доказать по индукции на
метаязыке).

Для доказательства теоремы осталось выделить множество всех конечных ординалов 
с помощью аксиомы выделения.
\end{proof}

Для ординалов можно определить арифметические операции.

\begin{definition}
Верхней гранью подмножества $x$ некоторого вполне упорядоченного
множества $S$ мы назовем всякий такой элемент $y$, что он больше
всех элементов из $x$.

Минимальной верхней гранью подмножества $x$ некоторого вполне упорядоченного
множества $S$ мы назовем множество 
$\operatorname{Upb}_S(x) = \min \{y \mid y \in S \with \forall t (t \in x \rightarrow t < y)\}$.
\end{definition}

Вообще, минимальная верхняя грань множества обычно носит название супремума
(обозначаемого как $\sup$), но в данном случае определение немного отличается:
мы указали строгое неравенство вместо нестрогого из-за чего минимальная верхняя
грань подмножества $\{1\}$ множества $\{1,2\}$ не $1$ (как было бы естественно
для супремума), а $2$. Поэтому и обозначение (для избежания путаницы) также было
изменено: $\operatorname{Upb}$ вместо $\sup$.

Заметим, что $\operatorname{Upb}$ определена только для подмножеств некоторого множества, 
(где минимум существует в силу вполне упорядоченности $S$, если для $x$ в $S$
есть хотя бы одна верхняя грань). Однако, для ординалов, при условии использования
стандартного сравнения ординалов в качестве отношения $<$, мы можем отказаться
от такого ограничения.

%\begin{definition}
%Минимальной верхней гранью множества ординалов $x$ называется 
%ординал $\operatorname{Upb}_{Ord}(x)$, 
%\end{definition}

\begin{definition}{Арифметические операции над ординалами.}
За $a + 1$ обозначим $x \cup \{x\}$. Тогда следующими рекурсивными 
определениями мы введем операции сложения, умножения и возведения в степень:

$$a + b \equiv \left\{ \begin{array}{rl} 
   a, & b \equiv 0\\
   (a + c)+1, & b \equiv c+1\\
   \operatorname{Upb}_{\mathrm{ord}} \{ a+c \mid c < b \}, &\mbox{$b$ --- предельный ординал }\end{array}\right.$$

$$a \cdot b \equiv \left\{ \begin{array}{rl} 
   0, & b \equiv 0\\
   (a \cdot c) + a, & b \equiv c+1\\
   \operatorname{Upb}_{\mathrm{ord}} \{ a \cdot c \mid c < b \}, &\mbox{$b$ --- предельный ординал }\end{array}\right.$$

$$a ^ b \equiv \left\{ \begin{array}{rl} 
   1, & b \equiv 0 \with a > 0\\
   (a ^ c) \cdot a, & b \equiv c+1\\
   \operatorname{Upb}_{\mathrm{ord}} \{ a^c \mid c < b \}, &\mbox{$b$ --- предельный ординал }\end{array}\right.$$
\end{definition}

Заметим, что в смысле введенной операции прибавления единицы, предельный
ординал --- это такой ненулевой ординал $x$, для которого нет ни одного ординала 
$y$, что $y + 1 = x$.

Так определенные операции на конечных ординалах ведут себя подобно
обычным арифметическим операциям на натуральных числах, однако в целом их
поведение может быть неочевидным. Например, легко заметить, что 
$1 + \omega = \omega$.

\begin{definition}
Назовем множества $X$ и $Y$ равномощными, если найдется биективное
отображение $X$ на $Y$. Будем записывать это как $|X| = |Y|$.
Будем говорить, что множество $X$ имеет мощность не превышающую $Y$,
если найдется инъективное отображение $X$ в $Y$. Будем записывать
это как $|X| \le |Y|$. Будем записывать $|X| < |Y|$, если известно,
что $|X| \le |Y|$, но неверно, что $|X| = |Y|$.
\end{definition}

\begin{definition}{Кардинальные числа.}
Кардинальное число - такой ординал $x$, что $y < x \leftrightarrow |y| < |x|$.
\end{definition}

Ясно, что все конечные ординальные числа являются кардинальными. 
Также, например, $\omega$ --- кардинальное число 
(еще оно обозначается как $\aleph_0$, если речь идет о мощности множеств).
Кардинальное число $\aleph_1$ (соответствующая мощность называется \emph{континуум}) ---
это следующее по порядку кардинальное число за $\aleph_0$.

Верно ли, что $2^\aleph_0 = \aleph_1$?
Континуум-гипотеза (что это так) была высказана
довольно давно и длительное время была одной из главных проблем в теории множеств.
Однако, оказалось, что данный факт не зависит от аксиоматики Цермело-Френкеля, и можно
как признавать этот факт, так и предполагать существование промежуточных мощностей.

\section{Теорема Лёвенгейма-Сколема}

Как мы знаем из предыдущих разделов, рассмотрение формальной теории неполно, 
если не сопровождается рассмотрением её моделей. Действительно, каковы могут
быть модели теории множеств? Например, обязан ли объект, соответствующий
множеству мощности $\aleph_1$, действительно иметь несчётное количество
элементов? В данном разделе мы прольём некоторый свет на этот вопрос.

\begin{definition}{Мощность модели.}
Пусть $M$ --- модель некоторой теории первого порядка. Напомним, что модель
задаётся предметным множеством $D$ и функциями, соответствующим всем
предикатам теории и всем функциональным символам теории. Тогда назовем
мощность множества $D$ мощностью модели.
\end{definition}

\begin{definition}{Элементарная подмодель.}
Пусть $M$ --- модель некоторой теории первого порядка с предметным
множеством $D$, и пусть определено $D_1$, $D_1 \subset D$. Тогда
структура $M_1$, построенная на предметном множестве $D_1$ с предикатами
и функциями, получающимися из предикатов и функций $M$ путем сужения 
их области определения на $D_1$, называется \emph{элементарной подмоделью} $M$,
если:
\begin{enumerate}
\item любая функция теории $f$ замкнута на $D_1$ 
(т.е. если $x_1 \in D_1, \dots x_n \in D_1$, то
$f(x_1, \dots x_n) \in D_1$)
\item Любая формула $A(x_1, \dots x_n)$ теории при любых значениях
$x_1, \dots x_n$ из $D_1$, истинная в $M$, истинна также и в $M_1$.
\end{enumerate}
\end{definition}

Заметим, что второе условие необходимо: пусть некоторая теория 1-го 
порядка содержит предикат равенства. Тогда формула
$\exists x \exists y \neg (x = y)$ при сужении предметного множества до
одноэлементного перестаёт быть верной.

\begin{lemma}
Элементарная подмодель теории является моделью данной теории.
\end{lemma}

\begin{proof}
Рассмотрим некоторую доказуемую формулу теории $A$. Она является общезначимой 
в $M$, значит, она является общезначимой в $M_1$. 
\end{proof}

\begin{definition}
Назовём теорию счётно-аксиоматизируемой (конечно-аксио\-ма\-ти\-зи\-руемой), если ее 
множество аксиом и правил вывода имеет счётную (конечную) мощность.
\end{definition}

Заметим, что аксиомы и правила вывода явно содержат все <<содержательные>> 
формулы в теории --- формулы, которые могут использоваться в доказательствах
хоть в каком-нибудь качестве. 
В наших определениях ничего не запрещает создать теорию, в которой 
заданы и дополнительные функции и предикаты, ни разу не упоминаемые в 
аксиомах и правилах вывода, но таким предикатам и 
функциям мы можем приписать произвольный смысл (например, все функции 
возвращают некоторую заранее выбранную константу $c_0$, а все предикаты 
ложны), не повредив корректности модели. Поэтому мы без ущерба для
общности можем предположить, что язык теории не содержит 
<<несодержательных>> формул.
При этом заметим, что в силу конечного размера каждой аксиомы и правила
вывода любая конечно(счётно)-аксиоматизируемая теория имеет
конечное (счётное) множество всех возможных <<содержательных>> формул.

\begin{theorem}{Теорема Лёвенгейма-Сколема.}
Пусть $M$ --- модель некоторой теории первого порядка, и пусть $T$ ---
множество всех формул этой теории. Тогда у $M$ есть элементарная
подмодель, такая, что $|M| = \max(|T|, \aleph_0)$.
\end{theorem}

\begin{proof}
Для построения требуемой модели нам необходимо построить предметное множество
требуемой мощности и показать, что сужение теории на него даст нам 
элементарную подмодель. Отсюда доказательство естественным образом
разбивается на две части.

Часть 1. Построение множества. 
Рассмотрим некоторое предметное множество $D'$. На его основе
построим множество $D''$, рассмотрев все формулы из $T$, и 
по каждой формуле (возможно) добавив некоторое количество элементов
к $D'$. 

Фиксируем некоторую $n$-местную 
формулу $A(y, x_1, \dots x_n)$ из $T$. 
Фиксируем некоторый набор аргументов $x_1, \dots x_n$ из $D'$.
В ходе вычисления $A$ в результате применения функций к аргументам мы можем
выйти из $D'$ --- добавим эти новые константы к $D''$. Их будет не
более чем конечное количество. Заметим, что формула $A$ может быть:
\begin{itemize}
\item тождественно истинной или ложной при любом $y$ из $D$ --- 
пропустим эту формулу и пойдем дальше. Поступим так же, если функция
может быть как истинной, так и ложной при разных значениях $y$ из $D'$.
\item Найдутся такие $y$, что $A(y,x_1,\dots x_n)$ истинна, но при этом
для любого $y$ из $D'$ формула $A(y,x_1,\dots x_n)$ ложна --- тогда
добавим какой-нибудь один из этих $y$ к множеству $D''$. Также пополним
множество всеми константами, которые необходимо добавить вследствие
вычисления $A$ на данных аргументах. Этим мы также увеличим $D''$ на
конечное количество элементов.
\end{itemize}

Рассмотрим множество $D_0$, $D_0 \subseteq D$,
такое, что в него входят только те элементы предметного множества, которые
соответствуют константам (т.е. нульместным функциям), упоминающимся в
формулах из $T$. Если это множество получается пустым --- добавим 
к нему какую-нибудь одну константу из $D$. Оно ляжет в начало счётной
последовательности из множеств, $D_0 \subseteq D_1 \subseteq D_2 \subseteq \dots$
(такой, что $D_k' = D_{k+1}$), 
объединив которую, 
мы получим множество $D^*$, которое и будет требуемым предметным 
множеством.

Заметим, что в результате однократного процесса пополнения мы увеличим
множество $D'$ не более чем на $|T|\cdot \aleph_0\cdot|D'|$ элементов
(по каждой формуле по каждой константе из $D'$ добавим не более чем конечное 
количество элементов). Поэтому мы не выйдем из мощности $|T|$, если $T$
несчётно, или из $\aleph_0$, если $T$ --- конечно.
Значит, мощность $D^*$ также будет отвечать условию теоремы.

Часть 2. Покажем, что структура $M^*$, полученная сужением модели $M$ на
предметное множество $D^*$, является элементарной подмоделью.
Докажем это индукцией по структуре формул. Рассмотрим некоторую формулу 
$A(x_1, \dots x_n)$, при этом $x_i \in D^*$.

База. Эта формула --- предикат $P (f_1 (x_1, \dots x_n), \dots f_k (x_1,
\dots x_n) )$. Если $x_1, \dots x_n$ взяты из $D^*$, то все они
добавлены на некотором шаге, значит, найдётся такой $t$, что $x_i \in D_t$.
Значит, все результаты функций $f_j (x_1, \dots x_n)$ лежат в $D_{t+1}$.
Значит, формула будет определена на этих значениях. Очевидно, что истинность
(ложность) формулы сохранится.

Переход. Пусть есть некоторая формула $A$ --- связка одной или двух 
подформул, и $A$ имеет следующий вид:

\begin{enumerate}
\item $X \with Y, X \vee Y, \neg X, X \rightarrow Y$ --- ясно, что
все эти правила работают на сужении исходной модели и истинность
формулы сохраняется.

\item $\exists y B (y, x_1, \dots x_n)$. Фиксируем некоторый набор 
$x_1, \dots x_n$ из $D^*$.
Пусть формула $A$ истинна в $M$, покажем её истинность в $M^*$.
Заметим, что каждый из $x_i$ был добавлен в $D^*$ на конкретном шаге, 
то есть найдется такой номер $t$, что все $x_i$ принадлежат $D_t$. 
Тогда по построению множества $D_{t+1}$, в нём неизбежно найдётся 
такой $y$, что $B (y, x_1, \dots x_n)$ определено и выполнено в $M$.
Значит, $B$ будет выполнено и в $M^*$ (по предположению индукции).
Значит, $A$ истинна и в $M^*$.
Обратное также очевидно: если $y$ найдётся в узкой модели, то он тем более
найдётся в широкой.

\item $\forall y B (y, x_1, \dots x_n)$. Доказательство зеркально
соответствует предыдущему пункту. 
Истинность $\forall y B(y,x_1, \dots x_n)$ в $M$ очевидно влечет
истинность $\forall y B(y,x_1, \dots x_n)$ в $M^*$, так как $D^* \subseteq D$. 
Если же $\forall y B(y,x_1, \dots x_n)$ ложно в $M$, то существует такой $y$ из $D$, 
что $\neg B(y,x_1,\dots x_n)$ истинно в $M$, значит, по построению $D^*$ и в
нём найдется элемент $z$ с таким свойством, то есть $B(z,x_1,\dots x_n)$ ложно
в $M$. И по предположению индукции $B(z,x_1, \dots x_n)$ ложно в $M^*$. То есть 
$\forall y B(y,x_1, \dots x_n)$ ложно в $M^*$.
\end{enumerate}

\end{proof}

Данная теорема в частности показывает, что для теории множеств (очевидно,
счётно-аксиоматизируемой) имеется счётная модель. В частности, это приводит
к следующему утверждению, называемому \emph{парадоксом Сколема}:
для любого множества, определимого в аксиоматике Цермело-Френкеля, мы можем 
предложить способ перенумеровать его элементы натуральными числами.
В том числе это справедливо и для несчётных множеств --- то есть для тех
множеств, для которых доказано отсутствие этого способа.

Парадокс, тем не менее, здесь кажущийся, поскольку тут (некорректно)
сталкивается утверждение, формулируемое на предметном языке 
(об отсутствии способа пересчёта внутри теории), с утверждением на метаязыке
(о существовании этого способа вне теории).